[LLVMdev] Register class intersection

[Jakob Stoklund Olesen]

When the coalescer is run with -join-cross-class-copies it needs to  
determine the register class of the joined virtual registers. The new  
register class must be compatible with both old register classes.

The current implementation chooses the register class with the larger  
spill size, or the less populous class. This works with the current  
targets, but it can produce illegal machine code on blackfin because  
some register classes are disjoint.

The general solution would be to use the intersection of the old  
register classes. If they are disjoint, the copy should not be  
coalesced.

The set-theoretic intersection of two register classes is not  
necessarily a proper register class defined in RegisterInfo.td. This  
is not a big problem, we can use the largest common subclass instead.  
If there is no common subclass, the register classes are considered  
disjoint.

There is a complication, though. A register class is not just a set of  
registers - it also holds information about spill size and alignment.  
Value types are no longer interesting once the selection DAG has been  
destroyed. X86 has the weird examples as usual:

Classes RFP32, RFP64, and RFP80 are identical (FP0-6) except for the  
spill size.
The same goes for FR64 and VR128 (XMM0-15).

The coalescer will join these classes as follows:

RFP32 + RFP64 -> RFP64
FR64 + VR128 -> VR128

This seems perfectly reasonable - choose the larger spill size and  
avoid losing data.

TableGen thinks these classes are unrelated - it currently defines  
register subclasses as follows:

A is a subclass of B iff A != B
and A.Regs is a subset of B.Regs (subset means improper subset)
and A.SpillSize == B.SpillSize

Since the spill sizes differ, FR64 and VR128 have no sub/super class  
relation.

I propose that we change the definition to:

A is a subclass of B iff A != B
and A.Regs is a subset of B.Regs
and A.SpillSize >= B.SpillSize
and A.SpillAlignment is divided by B.SpillAlignment

This would introduce two new subclass chains:

RFP80 subclass of RFP64 subclass of RFP32
VR128 subclass of FR64

Define intersection as described above:

intersection(A, B) = max { X | X subclass-eq A, X subclass-eq B }

The coalescer can then use NewRC = intersection(SrcRC, DstRC). This  
gives the same result for the existing targets, and it works correctly  
for blackfin and other future targets.

The subclass relation can be seen as adding constraints on a virtual  
register. If A is a subclass of B, it is always legal to change a  
virtual register class from B to A. The extra constraints can be fewer  
allocable registers, larger spill size, or stricter spill alignment.


Sorry about the math.

/jakob