[LLVMdev] [LLVMDev] Coalescing Registers

[Jeff Kunkel]

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