[LLVMdev] Register class intersection
Jakob Stoklund Olesen
stoklund at 2pi.dk
Tue Apr 28 14:37:51 PDT 2009
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
More information about the llvm-dev
mailing list