[LLVMdev] request for help writing a register allocator

[Lang Hames]

Hi Susan,

> However, if the same virtual register is used in two different instructions, I get an abort with an error message saying that I'm trying to assign a physical register to a virtual register that's already been mapped.  If I don't call assignVirt2Phys then I get an abort with an error message saying that some virtual register was not assigned a physical register.

Each vreg should be mapped to a singe physreg. The rewriter will
rewrite any operand that refers to the virtreg to use the physreg it
is mapped to (including the operands of the loads/stores inserted for
that virtreg). If no mapping is made, or you attempt to redefine the
mapping (without calling VirtRegMap::clearAllVirt()), you'll get
assertion failures as you saw.

You really want to iterate over the function assigning a physreg to
each virtreg the first time you encounter it, being careful not to
assign the same physreg to two virtual registers if they're ever used
in the same instruction.

Unfortunately this simple approach will not work in all cases. If, for
instance, a virtreg were used in a set of instructions which also
used, between them, every possible physreg, then there'd be no physreg
left to allocate to the virtreg.

You can correct this (at some cost to performance) by inserting new
virtregs (see MachineRegisterInfo::createVirtualRegister), and copies
(see TargetInstrInfo::copyRegToReg) before allocation. You could do
the following:

For each instruction i:
  For each operand o:
    if o is a register operand:
      create a new virtreg v with the same register class as o
      if i uses o:
        insert a copy from o to v before i
      if i defines o:
        insert a copy from v to o after i
      rename o to use v


I believe this should be sufficient to guarantee that you can find a
physreg for every virtreg which does not conflict with the choices for
any other virtreg in that instruction. You would only need to spill
the original vregs, not the ones you inserted in the pre-pass.

One gotcha - Two address instructions. If an operand is used as both
def and use in a two address instruction (see
MachineInstr::isRegTiedToUseOperand &
MachineInstr::isRegTiedToDefOperand) you only want to insert one new
vreg for the two operands and re-use it.

> I've tried calling addSpillPoint and addRestorePoint for every instruction that involves a virtual register, and also not calling those functions, and I still get the same aborts.

You definitely need these calls. They're not the source of your trouble.

Cheers,
Lang.