I want to full understand register coalescing and how to coalesce

copies. From what I have seen from "SimpleRegisterCoalescing,"

"RegAllocLinearSpan," and "RegAllocPBQP" there are three indicators

for the copy instruction x = copy y. Assume that the value number of x

does not equal the value number of y.

For "x = copy y", let the boolean values a,b, and c, equal the following:

a = x is virtual or physical,

b = y is virtual or physical, and

c = class(x) == class(y) or class(x) != class(y).

The resulting coalescing and actions depend on the truth values of

these boolean values. Thus there are 2^3 cases. I expect enumerating

and covering the cases provides an exhaustive solution to coalescing.

1. When x and y are virtual and the classes are the same, x = y in

everything except name.

2. When x and y are virtual and the classes are not the same, the

register class for y has been increased or decreased into the class of

x.

3. When x is physical and y is virtual and the classes are the same,

the copy instruction indicates the virtual value of y must be in the

physical register x.

4. When x is virtual and y is physical and the classes are the same,

the copy instruction indicates the virtual value of x was born out of

the physical register x.

5. When x is virtual and y is physical and the classes are not equal,

then an error has occurred previous to coalescing because the classes

of a virtual values should be equal to the physical value when born.

6. When x is physical and y is virtual and the classes are not equal,

then the same error of 5 has occurred.

7. When x is physical and y is physical and the classes are not equal,

then some physical move is happening, and this cannot be coalesced.

8. When x is physical and y is physical and the classes are equal,

then a physical move has occurred, and this cannot be coalesced.

Have I missed any cases? Have I handled all the cases optimally. Are

my indicators exhaustive?

I am concerned that case 8 may be coalescable, but I have not worked

out the logic and data structures to make it happen.

Thanks,

Jeff Kunkel