Register class intersection

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 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.


Hi Jakob,

What you proposes sounds great. Thanks.

However, at some point of time FR32 and FR64 register classes will no longer be sub-register classes of VR128. I intend to change the registers in these classes to be sub-registers of xmm registers in VR128. This will allow us to eliminate the cross rc copies to and from FR32/64 to XMM and implement them as extract_subreg / insert_subreg instead.