Next: , Up: VOP Definition   [Contents]


29.1 Lifetime model

#| Note in doc that the same TN may not be used as both a more operand and as any other operand to the same VOP, to simplify more operand LTN number coalescing. |#

It seems we need a fairly elaborate model for intra-VOP conflicts in order to allocate temporaries without introducing spurious conflicts. Consider the important case of a VOP such as a miscop that must have operands in certain registers. We allocate a wired temporary, create a local preference for the corresponding operand, and move to (or from) the temporary. If all temporaries conflict with all arguments, the result will be correct, but arguments could never be packed in the actual passing register. If temporaries didn’t conflict with any arguments, then the temporary for an earlier argument might get packed in the same location as the operand for a later argument; loading would then destroy an argument before it was read.

A temporary’s intra-VOP lifetime is represented by the times at which its life starts and ends. There are various instants during the evaluation that start and end VOP lifetimes. Two TNs conflict if the live intervals overlap. Lifetimes are open intervals: if one TN’s lifetime begins at a point where another’s ends, then the TNs don’t conflict.

The times within a VOP are the following:

:Load This is the beginning of the argument’s lives, as far as intra-vop conflicts are concerned. If load-TNs are allocated, then this is the beginning of their lives.

(:Argument <n>) The point at which the N’th argument is read for the last time (by this VOP). If the argument is dead after this VOP, then the argument becomes dead at this time, and may be reused as a temporary or result load-TN.

(:Eval <n>) The N’th evaluation step. There may be any number of evaluation steps, but it is unlikely that more than two are needed.

(:Result <n>) The point at which the N’th result is first written into. This is the point at which that result becomes live.

:Save Similar to :Load, but marks the end of time. This is the point at which result load-TNs are stored back to the actual location.

In any of the list-style time specifications, the keyword by itself stands for the first such time, i.e.

    :argument  <==>  (:argument 0)

Note that argument/result read/write times don’t actually have to be in the order specified, but they must *appear* to happen in that order as far as conflict analysis is concerned. For example, the arguments can be read in any order as long as no TN is written that has a life beginning at or after (:Argument <n>), where N is the number of an argument whose reading was postponed.

[### (???)

We probably also want some syntactic sugar in Define-VOP for automatically moving operands to/from explicitly allocated temporaries so that this kind of thing is somewhat easy. There isn’t really any reason to consider the temporary to be a load-TN, but we want to compute costs as though it was and want to use the same operand loading routines.

We also might consider allowing the lifetime of an argument/result to be extended forward/backward. This would in many cases eliminate the need for temporaries when operands are read/written out of order. ]


Next: , Up: VOP Definition   [Contents]