[LLVMdev] Register class intersection

Evan Cheng evan.cheng at apple.com
Wed Apr 29 22:14:15 PDT 2009

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  


On Apr 28, 2009, at 2:37 PM, Jakob Stoklund Olesen wrote:

> 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
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

More information about the llvm-dev mailing list