[LLVMdev] Register class intersection

[Evan Cheng]

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.

Evan

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