llvm dev - Oct 2010 - [LLVMdev] [LLVMDev] Coalescing Registers

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

On Oct 3, 2010, at 11:27 AM, Jeff Kunkel wrote:
> 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.
Make sure your truth table is symmetric when swapping x and y.

Note that physical registers don't really have a register class. A physreg
can belong to many classes.

Also, virtual registers of different classes can be coalesced if there is a
register class representing the intersection.

Then there is subregister copies...

You should look at the CoalescerPair class. It calculates whether a copy can be
coalesced and what the resulting register should look like.

/jakob