[LLVMdev] Overlapping register classes

[Dan Gohman]

On Mar 15, 2009, at 2:02 PM, Jakob Stoklund Olesen wrote:

> Hi,
>
> I am writing a backend for the Blackfin processor from Analog  
> Devices. I
> just started so I still have a lot to learn about the code  
> generator. So
> far, I can compile test/CodeGen/Generic/BasicInstrs.ll correctly, but
> that is about it.
>
> The Blackfin 32-bit registers divide naturally into several classes. I
> have modelled these register classes without knowing anything about  
> what
> the code generator expects.
>
> There are data and pointer registers:
>
> def D : RegisterClass<"Bfin", [i32], 32, [R0, R1, R2, R3, R4, R5,  
> R6, R7]>;
> def P : RegisterClass<"Bfin", [i32], 32, [P0, P1, P2, P3, P4, P5,  
> SP, FP]>;
>
> For instance, a zero-extending byte load needs the address in a P-reg
> and can only load a D-reg:
>
> def LOAD32p_8z: F1<(outs D:$dst), (ins P:$ptr),
>                   "$dst = B[$ptr] (Z);",
>                   [(set D:$dst, (zextloadi8 P:$ptr))]>;
>
> Some instructions work on all registers:
>
> def GR : RegisterClass<"Bfin", [i32], 32,
>    [R0, R1, R2, R3, R4, R5, R6, R7,
>     P0, P1, P2, P3, P4, P5, SP, FP,
>     I0, I1, I2, I3, M0, M1, M2, M3,
>     B0, B1, B2, B3, L0, L1, L2, L3]>;
>
> For instance, I can load an arbitrary 32-bit constant or
> globaladdr/externalsym into any register:
>
> def LOAD32imm: Pseudo<(outs GR:$dst), (ins i32imm:$src),
>                      "$dst.H = HI($src); $dst.L = LO($src);",
>                      [(set GR:$dst, imm:$src)]>;
>
> I think I am stretching the code generator beyond its capability by
> doing this. As far as I can tell, instruction selection is done purely
> based on value types. Register classes are not considered.
>
> I get in trouble when I try to compile this function:
>
> @i1_l = external global i1
> @i1_s = external global i1
>
> define void @i1_ls() nounwind  {
> 	%tmp = load i1* @i1_l
> 	store i1 %tmp, i1* @i1_s
> 	ret void
> }
>
> Instruction selection works correctly, but the scheduling step fails
> with "Register class of operand and regclass of use don't agree!" in
> ScheduleDAGSDNodes::AddOperand. The selected DAG contains:
>
>    (LOAD32p_8z (LOAD32imm (tglobaladdr "i1_l")))
>
> LOAD32imm produces a GR-class vreg, and LOAD32p_8z expects a P-class
> vreg, hence the error. But P is a subclass of GR, so if the vreg class
> were changed to P everything would work.
>
> The solution is not always that simple. There could be multiple uses
> with different regclasses, or the def and use regclasses could be
> disjoint so a reg-to-reg copy would be necessary.
>
> Am I misusing register classes, or is this simply functionality that  
> has
> not been written yet? The existing backends seem to have only one
> register class per machine value type.


The x86 backend has an example of a partial solution.  The GR32
register class has a subset, GR32_, which is the registers in GR32
that support 8-bit subregs.  Instructions that reference 8-bit subregs
are emitted with a copy (MOV32to32_) to put the value in a virtual
register of the needed class.  This copy may then optimized away
by subsequent passes.

Right now the x86 target code has to explicitly spell out where
such copies are needed.  It isn't a lot of trouble because there are
a small number of situations where copies are needed.  From your
description, it sounds like this would be much more significant on
blackfin.  Handling this automatically seems possible, though this
is functionality that has not been written yet.

Also, the register allocator and associated passes don't yet know
how to handle register classes like this.  For example, many
architectures like this have an add instruction that can add two
address registers, and one that can add two data registers, but
not one that can directly add an address register and a data
register.  In this case, if one operand of an add is in a known class,
it may be desireable to allocate the other operand in the same
class (in simple cases).  In LLVM, this is functionality that is not
yet written.

Dan