Overlapping register classes

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.

Regards,
/stoklund

I don't know if there is a 'real' solution to your issue, but you
might consider implementing some pseudo instructions for conversions
between register classes. This should help alleviate the issue you are
currently getting, as (with the right patterns) the generator should
automatically insert the conversion instructions when needed.

Alternatively, you could kill your 'joint' register class, and simply
use multiple patterns on those instructions which can use all
registers. This is probably the right way to go.

Lastly, you could use a single 'joint' register class, and some
predicates in your .td to make sure that only specific registers in
the class are used for a given pattern.

In any case, I recommend you come hang out on the IRC channel. I've
just struggled through a lot of the backend target stuff, and may be
able to help you avoid the pitfalls I hit. (I also know a little
blackfin ;)).

Have you taken a look at MOV16to16_ in X86InstrInfo.td? I think the
situation there is similar to your issue.

-Eli

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

Dan Gohman <gohman@apple.com> writes:

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.

I missed this before (thanks, Eli). I tried adding the explicit move
patterns, and at least it compiles correctly now:

i1_ls:
  R0.H = HI(i1_l); R0.L = LO(i1_l);
  P0 = R0;
  R0.H = HI(i1_s); R0.L = LO(i1_s);
  R1 = B[P0] (Z);
  R2 = 1 (X);
  P0 = R0;
  R0 = R1 & R2;
  B[P0] = R0;
  RTS;

The moves (P0 = R0) did not get optimized away by the register
allocator. RALinScan::attemptTrivialCoalescing almost succeeded; it got
as far as testing if the source register R0 is contained in the
destination regclass (P). It isn't, so the move stayed in.

The problem is that the source register is allocated before coalescing
is attempted. The destination regclass does not backpropagate and
so doesn't influence the allocation class.

PBQP doesn't even attempt to remove a move unless source and destination
regclasses are identical.

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.

Yes, inserting explicit patterns everywhere would make a complete mess
of my InstrInfo.td. All arithmetic requires D-regs, and all load/stores
require P-regs.

It would be fairly simple to insert move instructions in the selection
DAG after instruction selection is complete. I could do this in my
InstructionSelect() as a first fix, but I think I would have to do
something more clever eventually.

I think a few tricks when creating vregs would go a long way:

1. If the def regclass is a subset of the operand regclass, there is no
   problem. ScheduleDAGSDNodes::AddOperand should simply allow this
   case.

2. If there is a regclass contained in the def regclass and all the
   operand regclasses, change the vreg regclass to the intersection.
   This could be a bad idea if there are many uses with different
   regclasses.

3. If def and operand regclasses are disjoint, a move is necessary. It
   should be possible to produce an abstract vreg-vreg copy instruction
   that changes the regclass. The copy instruction would eventually
   become a copyRegToReg() call after registers are allocated.

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.

I have the exact same problem on blackfin. I can add D=D+D or P=P+P,
but no combinations. The same goes for post-modify store: I can have
base+offset as P+P or I+M, where I and M are further register classes I
didn't tell you about.

One way of handling this would be to mark an instruction with a list of
alternative instructions. The alternatives are functionally identical,
but with different operand and result regclasses. Ideally the register
allocator would choose the best alternative. However, this is a rather
big change in the problem definition for the register allocator. I am
going to ignore this issue for now and live with a few redundant
register copies.

Dan Gohman <gohman@apple.com> writes:

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.

I missed this before (thanks, Eli). I tried adding the explicit move
patterns, and at least it compiles correctly now:

i1_ls:
  R0.H = HI(i1_l); R0.L = LO(i1_l);
  P0 = R0;
  R0.H = HI(i1_s); R0.L = LO(i1_s);
  R1 = B[P0] (Z);
  R2 = 1 (X);
  P0 = R0;
  R0 = R1 & R2;
  B[P0] = R0;
  RTS;

The moves (P0 = R0) did not get optimized away by the register
allocator. RALinScan::attemptTrivialCoalescing almost succeeded; it got
as far as testing if the source register R0 is contained in the
destination regclass (P). It isn't, so the move stayed in.

The problem is that the source register is allocated before coalescing
is attempted. The destination regclass does not backpropagate and
so doesn't influence the allocation class.

The coalescer has the capability to coalesce cross register class copies. It's not quite done. Try -join-cross-class-copies.

PBQP doesn't even attempt to remove a move unless source and destination
regclasses are identical.

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.

Yes, inserting explicit patterns everywhere would make a complete mess
of my InstrInfo.td. All arithmetic requires D-regs, and all load/stores
require P-regs.

It would be fairly simple to insert move instructions in the selection
DAG after instruction selection is complete. I could do this in my
InstructionSelect() as a first fix, but I think I would have to do
something more clever eventually.

I think a few tricks when creating vregs would go a long way:

1. If the def regclass is a subset of the operand regclass, there is no
  problem. ScheduleDAGSDNodes::AddOperand should simply allow this
  case.

2. If there is a regclass contained in the def regclass and all the
  operand regclasses, change the vreg regclass to the intersection.
  This could be a bad idea if there are many uses with different
  regclasses.

3. If def and operand regclasses are disjoint, a move is necessary. It
  should be possible to produce an abstract vreg-vreg copy instruction
  that changes the regclass. The copy instruction would eventually
  become a copyRegToReg() call after registers are allocated.

Sure. These tricks can be added by demand. Patches welcome.

Evan

Evan Cheng <echeng@apple.com> writes:

The problem is that the source register is allocated before coalescing
is attempted. The destination regclass does not backpropagate and
so doesn't influence the allocation class.

The coalescer has the capability to coalesce cross register class
copies. It's not quite done. Try -join-cross-class-copies.

That did the trick! Now my trivial example becomes:

i1_ls:
  P0.H = HI(i1_l); P0.L = LO(i1_l);
  P1.H = HI(i1_s); P1.L = LO(i1_s);
  R0 = B[P0] (Z);
  R1 = 1 (X);
  R0 = R0 & R1;
  B[P1] = R0;
  RTS;

The inserted copies are gone.

1. If the def regclass is a subset of the operand regclass, there is
no problem. ScheduleDAGSDNodes::AddOperand should simply allow this
case.

2. If there is a regclass contained in the def regclass and all the
operand regclasses, change the vreg regclass to the intersection.
This could be a bad idea if there are many uses with different
regclasses.

3. If def and operand regclasses are disjoint, a move is necessary.
It should be possible to produce an abstract vreg-vreg copy
instruction that changes the regclass. The copy instruction would
eventually become a copyRegToReg() call after registers are
allocated.

Sure. These tricks can be added by demand. Patches welcome.

I will look into it. It doesn't feel right to insert moves everywhere
and hope the coalescer will remove then again.

I am not completely sure 2. would be a good idea. Changing the vreg to
a smaller regclass would increase the register pressure. For instance,
in the X86 backend you could change the pattern:

def : Pat<(and GR32:$src1, 0xff),
          (MOVZX32rr8 (i8 (EXTRACT_SUBREG (MOV32to32_ GR32:$src1),
                                          x86_subreg_8bit)))>

into:

def : Pat<(and GR32_:$src1, 0xff),
          (MOVZX32rr8 (i8 (EXTRACT_SUBREG GR32_:$src1,
                                          x86_subreg_8bit)))>

If 2. above were implemented, the vreg representing $src1 would be
forced into GR32_. If it is live for a long time, that might not be a
good thing.

Is the register allocator able to insert moves in this case? A kind of
cross class spilling.

Jakob Stoklund Olesen <stoklund@2pi.dk> writes:

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.

Here is what I have done for now: I have added a narrowing move
instruction for each register subclass, much like the X86 MOV32to32_
instruction:

def MOVE_d: F1<(outs D:$dst), (ins ALL:$src),"$dst = $src;", >;
def MOVE_p: F1<(outs P:$dst), (ins ALL:$src),"$dst = $src;", >;

I do not use these move instructions in patterns; that would be too
messy. Instead, I insert narrowing moves in the selection DAG after
instruction selection is complete, before scheduling. Since the
narrowing moves take operands from the ALL regclass, ScheduleDAGSDNodes
gets upset unless you apply the following patch:

--- a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp
@@ -262,7 +262,7 @@ void ScheduleDAGSDNodes::AddOperand(MachineInstr *MI, SDValue Op,
       const TargetRegisterClass *RC= getInstrOperandRegClass(TRI, *II, IIOpNum);
       assert((RC || II->isVariadic()) && "Expected reg class info!");
       const TargetRegisterClass *VRC = MRI.getRegClass(VReg);
- if (RC && VRC != RC) {
+ if (RC && VRC != RC && !VRC->hasSuperClass(RC)) {
         cerr << "Register class of operand and regclass of use don't agree!\n";
         cerr << "Operand = " << IIOpNum << "\n";
         cerr << "Op->Val = "; Op.getNode()->dump(DAG); cerr << "\n";

When running llc with -join-cross-class-copies as Evan suggested, it
produces good results.

I am going to move on to implementing advanced features like jumps and
condition codes now :slight_smile:

Thanks,
/jakob