Custom allocation orders

The target description .td files are allowed to change the default allocation order on a register class by overriding the allocation_order_begin() and allocation_order_end() methods on TargetRegisterClass.

Previously, this was used all the time to filter out stack and frame pointers and other reserved registers. I was able to remove most of these custom allocation orders in the tree because the register allocators are now filtering out the reserved registers.

A few instances remain. For example, x86 needs to remove AH-DH from GR8 in 64-bit mode because of the REX prefix encoding constraints. We don't want to reserve those four registers because they are still useful with some *_NOREX instructions.

It looks like this:

def GR8 : RegisterClass<"X86", [i8], 8,
                        [AL, CL, DL, AH, CH, DH, BL, BH, SIL, DIL, BPL, SPL,
                         R8B, R9B, R10B, R11B, R14B, R15B, R12B, R13B]> {
  let MethodProtos = [{
    iterator allocation_order_begin(const MachineFunction &MF) const;
    iterator allocation_order_end(const MachineFunction &MF) const;
  }];
  let MethodBodies = [{
    static const unsigned X86_GR8_AO_64[] = {
      X86::AL, X86::CL, X86::DL, X86::SIL, X86::DIL,
      X86::R8B, X86::R9B, X86::R10B, X86::R11B,
      X86::BL, X86::R14B, X86::R15B, X86::R12B, X86::R13B, X86::BPL
    };

    GR8Class::iterator
    GR8Class::allocation_order_begin(const MachineFunction &MF) const {
      const TargetMachine &TM = MF.getTarget();
      const X86Subtarget &Subtarget = TM.getSubtarget<X86Subtarget>();
      if (Subtarget.is64Bit())
        return X86_GR8_AO_64;
      else
        return begin();
    }

    GR8Class::iterator
    GR8Class::allocation_order_end(const MachineFunction &MF) const {
      const TargetMachine &TM = MF.getTarget();
      const TargetFrameLowering *TFI = TM.getFrameLowering();
      const X86Subtarget &Subtarget = TM.getSubtarget<X86Subtarget>();
      const X86MachineFunctionInfo *MFI = MF.getInfo<X86MachineFunctionInfo>();
      // Does the function dedicate RBP / EBP to being a frame ptr?
      if (!Subtarget.is64Bit())
        // In 32-mode, none of the 8-bit registers aliases EBP or ESP.
        return begin() + 8;
      else if (TFI->hasFP(MF) || MFI->getReserveFP())
        // If so, don't allocate SPL or BPL.
        return array_endof(X86_GR8_AO_64) - 1;
      else
        // If not, just don't allocate SPL.
        return array_endof(X86_GR8_AO_64);
    }
  }];
}

It is inconvenient to compute the front and back of the same list in two different functions, but the biggest problem with this is that TableGen doesn't understand what is happening. It can't verify that the alternative allocation order makes sense, and it can't infer derived register classes.

Here is an alternative syntax for the same thing:

def GR8 : RegisterClass<"X86", [i8], 8,
                        [AL, CL, DL, AH, CH, DH, BL, BH, SIL, DIL, BPL, SPL,
                         R8B, R9B, R10B, R11B, R14B, R15B, R12B, R13B]> {
  let AltOrders = [(sub GR8, AH, BH, CH, DH)];
  let AltOrderSelect = [{
    const TargetMachine &TM = MF.getTarget();
    const X86Subtarget &Subtarget = TM.getSubtarget<X86Subtarget>();
    return Subtarget.is64Bit();
  }];
}

The AltOrders field is a list of dags, each describing an alternative allocation order. The AltOrderSelect field is a snippet of code that returns a number selecting the active allocation order. 0 is the default, 1 is the first AltOrder member etc.

TableGen can help by computing the set difference (sub GR8, AH, BH, CH, DH), there is no need the repeat the entire register list. TableGen can also verify that the alternative allocation orders don't include foreign registers. That would be illegal.

Finally, suppose TableGen wanted to create a register class with the GR8 sub-registers of GR32_NOSP. It would be able to automatically create an allocation order for such a class by basing it on the GR8 order.

I will make this change soon. Out-of-tree targets will need to change their .td files, but most likely they can simply delete the custom allocation orders entirely. That was the case for most of the in-tree targets.

/jakob