problem trying to write an LLVM register-allocation pass

Hi Susan,

The problem is that the allocator is re-using the ‘preg’, which is calculated for an operand that may have a subreg index, for loads and stores to a stack-slot. The stack slot always has the same width as vreg (which is the right behavior), but for operands with subreg indexes, ‘preg’'s class will be different from ‘vreg’, in which case you get the mismatched loads/stores you were seeing.

I’ve attached an updated copy of Gcra.cpp that doesn’t exhibit this bug. In the new version the loads and stores always reference ‘preg’, which is always a physical register of the same class as ‘vreg’. The update adds a new variable, preg_op, to hold the subregister of preg that will be used for the operand currently being rewritten, and preg_op will be set to a subreg of preg where appropriate.

  • Lang.

Gcra.cpp (8.01 KB)

Lang -

Your fix does prevent the assembler errors, but it doesn't seem to produce correct assembly.

I created a slightly modified version that, for each instruction that includes a vreg, adds a check that the preg selected is not already in that instruction. I've attached that version.

I think that this version of Gcra.cpp should produce correct assembler, since it's allocating one stackframe for each vreg and always loading/storing from/to that stackframe.

I've attached a simpler version of the test input (now called bug.c) plus the .bc file and the .s file produced by the new code. When I assemble and run I get this output:

x: 1001
x: 200
x: 40
x: 8

while the correct output is

x: 1001
x: 100
x: 10

Susan

Gcra.cpp (9.08 KB)

bug.bc (760 Bytes)

bug.c (170 Bytes)

bug.s (1.85 KB)

Hi Susan,

The problem now is the usedPregSet. Take the instruction:

%vreg13:sub_32bit = ADD32rr %vreg13:sub_32bit, %EAX, %EFLAGS<imp-def,dead>

%EAX will be added to usedPregSet when the instruction is encountered, but %vreg13 is a different class (64bit registers), so none of its candidates will conflict. In addition to checking membership of usedPregSet, you need to check all aliases of the elements of usedPregSet.

The attached Gcra includes code for this. It also moves the erasure of the subreg index out of the inner loop so that if a vreg appears multiple times in an instruction all subreg indexes will be cleared.

  • Lang.

Gcra.cpp (9.68 KB)

Lang -

Attached is a new example for which I still get assembler errors.

Susan

bug1.bc (720 Bytes)

bug1.c (141 Bytes)

Hi Susan,

You should never be getting assembler errors if 'llc -verify-machineinstrs' approves of your machine code. It might give you better error messages than the assembler.

/jakob

Thanks Jakob. I should have mentioned that earlier. :slight_smile:

When you see mismatched sizes on operands it’s a fair bet that the subreg rewriting has gone wrong. I should have pulled that entirely out of the preg search loop in the previous example.

Fixed version attached.

  • Lang.

Gcra.cpp (9.34 KB)

Hi Susan,

Jakob just pointed me to ‘MachineOperand::substPhysReg(unsigned preg, const TargetRegisterInfo& TRI)’. That substitutes the given physreg for a virtreg operand, taking the subregister index into account. That is what my examples have been doing manually. Using substPhysReg would allow you to tidy the Gcra code up slightly.

  • Lang.

Thanks Lang, I'll try substPhysReg.

I did try your latest code, and although it made the assembler errors go away, now some of my tests produce bad output when executed. I need to look into that some more... (I did change my "usedPregSet" to be ALL pregs used in the whole function, not just those in the current instruction, so the problem should not be the erroneous over-writing of a live preg.)

Also, I'm confused about the code that gets a preg for a given vreg. Previously,you gave me code that takes into account the "allocation order" and the "reserved regs", including the following:
   BitVector reservedRegs = TRI->getReservedRegs(Fn);
          ArrayRef<uint16_t> rawOrder = trc->getRawAllocationOrder(Fn);
          ArrayRef<uint16_t>::iterator rItr = rawOrder.begin();
          while (rItr != rawOrder.end()) {
           while (rItr != rawOrder.end() && reservedRegs.test(*rItr)) {
             ++rItr;
           }

As I recall, this prevented some failed assertion. Why has that code gone away?

Susan

Hi Susan,

It looks like the allocation-order aware code didn’t make it into your email on November 7th, and I didn’t think to add it back in. This code is important, and its omission could be the cause of the errors your seeing.

  • Lang.

I tried using this flag and it gave me errors on code that otherwise assembles and runs just fine (using the version of Gcra.cpp that Lang wrote). So I'm wondering if I should really be using the flag? I'm using it like this:

llc -verify-machineinstrs -load Debug/lib/P4.so -regalloc=gc xxx.bc

Susan

Hi Susan,

To my knowledge the verifier doesn’t produce false positives with any of the in-tree allocators. If it is raising an error that is worth investigating. Is it raising an error on any simple test cases? Can you share the failing case?

  • Lang.

Hi Susan,

Jakob pointed out to me that the Gcra.cpp allocator doesn’t record basic-block live-ins, which are used by the verifier to check correctness.

You can record which variables are live into a basic block with MachineBasicBlock::addLiveIn(unsigned physReg). I don’t know the verifier well, but if it’s using other built in infrastructure for register allocation then it may not be a good fit for your allocator.

I’ll try to find time to look at the example files you sent in the next couple of days.

Cheers,
Lang.

To clarify, the live-in lists are not there for the verifier's benefit. They are used by various post-RA passes that care about register liveness, so they are required to be correct.

/jakob

Lang -

I used addLiveIn and that fixed almost all of the problems with the verify
flag, including the example I sent previously, so no need to look into
that. I still have a few cases where I'm getting "verify" errors, though
they don't seem to affect the correctness of the final code. I will send
an example ASAP.

Thanks for all your help!

Susan

I have a new problem: Register RBP is used in a function foo. (I am not allocating RBP to any virtual register, the instances of RBP in function foo are in the machine code when my register allocator starts.)

Function foo calls function bar. Register RBP is not saved across the call, though it is live after the call. Function bar includes a virtual register. The code that I'm using to find the registers available to be allocated to that virtual register includes EBP in that available-preg set. This is a disaster, since writing into EBP clobbers RBP.

I tried to add code to save all live physical registers across calls, but I don't know how to get the appropriate TargetRegisterClass (needed to call CreateSpillStackObject).

Is there a different way to save/restore RBP across calls? Or a way to get its TargetRegisterClass?

Susan

Hi Susan,

RBP is used as the frame pointer on x86 (hence its automatic appearance in your code), and shouldn’t be allocated to any vreg in function bar. Loading/saving RBP should be managed by the stack frame setup/teardown code.

If it doesn’t already, your allocator should filter out reserved registers (See MachineRegisterInfo::isReserved(unsigned preg)) when assigning physregs.

ArrayRef pregs = TRC->getRawAllocationOrder(&MF);
for (int i = 0; i < pregs.size(); ++i) {
if (MRI->isReserved(pregs[i]))
continue;
// use preg…
}

You could also use the AllocationOrder class to simplify the task of finding valid pregs, though it does require you to use VirtRegMap.

If you are already checking the reserved regs then I’ve misdiagnosed the problem. I’d be happy to dig further if you can point me to a copy of your allocator and a test case.

Cheers,
Lang.

I AM filtering out reserved registers. I am not allocating RBP in function bar, I am allocating EBP, because it is NOT in the list of reserved registers for function bar. Neither register RBP nor register EBP is saved/restored across the call from foo to bar, either by the code for the call or the code for entry to bar. The input C file that is causing this problem is flex.c (attached). The calling function is “yyparse” and the called function is “scinstal”. Here are the reserved registers for yyparse: { 7 44 54 106 111 114 118 } Here are the reserved registers for scinstal: { 54 111 114 } Register EBP is preg 44, which is NOT in the reserved list for scinstal (nor is it an alias of any of those reserved registers; the aliases are { 50 64 117 118 }). I don;t know which preg corresponds to RBP. You say that RBP should be saved/restored across the call. I tried to generate that code, but, as I said in my previous mail, I don’t know how to get the appropriate TargetRegisterClass (needed to call CreateSpillStackObject). Should I instead be generating code to save register EBP at the start of scinstal, restoring it at the end of that function? Susan

flex.c.txt (296 KB)

rbp is callee-saved. If you want to use it or part of it in bar, you are
responsible for saving and restoring it.

Joerg

Hi Susan,

Thanks for the clarification, and the test case. I think I know what the problem is now. Saving and restoring RBP is the job of the PEI (PrologEpilogInsertion) pass, which runs after register allocation. To determine which callee-saved physregs actually need to be saved it checks MachineRegisterInfo::isPhysRegOrOverlapUsed(unsigned reg). Your register allocator needs to notify MachineRegisterInfo about the physical registers that have been assigned by calling MachineRegisterInfo::setPhysRegUsed(unsigned reg).

You only need to call setPhysRegUsed for the physregs that you actually use. You do not need to specify the aliasing registers.

Hope this helps!

Regards,
Lang.

Aha, yes, this is definitely helpful!

Is there documentation on all this somewhere? I still have errors for some large test inputs, and it would be nice if I didn't have to keep bugging you for information.

Thanks!

Susan