Re: Register Allocation for Register Pairs

To summarize the replies (which consisted mainly of a private discussion
with Preston Briggs):


----------
I had asked how it helped to copy the components of a pair into separate
registers. In particular, after coalescing, aren't you back to the
program you started with?


Preston agrees that after this transformation, it may still help to
separately track the lifetimes of each half of a pair:


> Coalescing would indeed get us back to where we started [in the example]
> and we will have to track both lifetimes separately (at least, we will
> for best results). No getting around that.


However, as he points out, there are several other good reasons to split
out these uses:


> A single value may be loaded once and copied many times.
> The allocator will attempt to coalesce away all the copies, but some may
> still remain. The fact that we can load a pair with a single instruction
> is a vote for them to remain in an adjacent pair of registers,
> but it's just 1 vote. We might need the values in other registers
> later (e.g., dictated by parameter passing conventions or some such).
> By inserting the copy, we give the allocator freedom to choose what
> seems best. Remember that the copy is not necessarily coalesced away.


----------
I also didn't understand the model for when a single register interferes
with one half of a pair, but not the other half. My example was:


> X[0,1] = .... // start of lifetime of pair X[0,1]
> ... = X[1] // X[1] dies
> A = .... // start of lifetime of singleton A
> ... = A op X[0]
>
> Clearly, A interferes with X[0] but not X[1], so the register
> allocator should be able to allocate A to the same register as X[1].


My issue was that if you model the interference as a single edge between
A and X[0], as proposed in the paper, you run into a problem:


> Suppose this is the only edge in the graph (A interferes with X[0]),
> and that we have only two colors. The degree of A is 1, the degree of
> X is ... 1, so we can simplify either. We arbitrarily choose to
> simplify X first, followed by A; then we assign A to register 0, and
> now we are in trouble because we needed A to be in register 1 in order
> to be able to color X. But when we simplified X, its degree was only 1,
> indicating that it was supposed to be colorable, regardless of the
> color assigned to A.


This violates Preston's principle for determining degrees (from LOPLAS):


> Thus, for the allocator to work correctly, a node's degree should
> accurately reflect its colorability. For register pairs, we must add
> enough edges to ensure proper behavior. Too few edges lead to a
> situation where simplify fails to reserve enough registers; too many
> edges leads to excess spilling.


If you use only a single edge for this situation, you find that
"simplify fails to reserve enough registers" for X, implying that we
have too few edges. X's degree is wrong in this case--it should be two,
because, as the example shows, we might not be able to color it,
depending on how its neighbor is colored.


Preston seems to agree:


> And A's [degree] should be less than 2 because we _are_ certain of
> coloring it, regardless of what happens to X.


> > It seems to me that when A interferes with X[0], it constrains the
> > coloring of X just as much as when A interferes with all of X.
>
> Yep. Seems like A should be getting 1 "count" of interference from X,
> but X should be getting 2 from A.


This is more complicated than the model described in the paper, and I
haven't worked out exactly how to represent it yet.


Thanks very much to Preston for his help with this, and for an
incredibly helpful thesis.


-Vince Del Vecchio
vince.delvecchio@analog.com

Return to the comp.compilers page.
Search the comp.compilers archives again.