llvm dev - Oct 2009 - [LLVMdev] request for help writing a register allocator

Hi Susan,
> 1. I tried running the PBQP allocator (as a dynamic pass), but that
didn't
>   work....


 Can you tell from this what I'm doing wrong?
>
The PBQP allocator is built into the LLVM CodeGen library, so the
"-regalloc=pbqp" option is already available in llc. If you've
built a copy
of the PBQP allocator in a separate library it will try to re-register that
same option, triggering the assertion you're seeing. You can probably get
around this by just changing the option in your copy to "pbqp2".

2. I tried writing a very simple register allocator.  It works as follows...


<snip>

> This allocator works on very simple C code, but fails (with an
> uninformative segmentation fault) as soon as I include a call to scanf, or
a
> loop, or an if-else.
>
There are any number of things that can go wrong in register allocation, so
it's hard for me to guess without seeing your code.

Possible issues:

1) Some machine instructions have implicit register operands. If you are not
including these in your calculations you will probably have some errors. My
apologies for not mentioning this earlier.

You can find the set of implicit uses and defs by querying the
TargetInstDesc object for each MachineInstr (call MachineInstr::getDesc() to
get it, and then the TargetInstrDesc::getImplicitUses() and
TargetInstrDesc::getImplicitDefs() methods to find the regs used/definied by
this instr).

2) How are you making sure that interfering virtregs never receive the same
physreg? If you're using the LiveIntervals analysis (and the
LiveInterval::overlaps(LiveInterval &) test) you should be ok, since it gets
a lot of testing (though bugs are not unheard of). If you've written your
own liveness analysis that would be one of the first places I'd check for
correctness.

> Do you see any obvious errors in the approach outlined above?
>
No obvious errors. My concern would be the liveness issue mentioned above.
In addition, what do you do if/when you encounter an instruction with two or
more operands (in the same class) that have been spilled?

> If not, can you suggest a way to find out what is going wrong?
>
The LLVM bugpoint tool is very handy if your allocator itself is crashing.
It sounds like your allocator is running fine though, but miscompiling
programs. Unfortunately in this case there aren't many tools to help you
(that I know of). I usually just work by inspection. Add some debugging
output to your allocator, or fire llc up under gdb and dump information
(many objects in LLVM have a handy "dump()" method to print out their
state). Try to find a minimal failing test case (if it breaks on if tests
then that's a great start), and just look to see where the allocation goes
wrong.

> Thanks for any help you can give me!!

No problem at all. Writing allocators is non-trivial (took me quite a while
to get my first one going). If you get really stuck try posting your
allocator and a failing test case.

Good luck!

- Lang.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20091021/28be3dc1/attachment.html>

> 1) Some machine instructions have implicit register operands. If you are
> not including these in your calculations you will probably have some
errors.
> My apologies for not mentioning this earlier.
>
> You can find the set of implicit uses and defs by querying the
> TargetInstDesc object for each MachineInstr (call MachineInstr::getDesc()
to
> get it, and then the TargetInstrDesc::getImplicitUses() and
> TargetInstrDesc::getImplicitDefs() methods to find the regs used/definied
by
> this instr).
>
Oops. Seems we copy implicit operands like this into MachineOperands on the
instruction before register allocation. Disregard the above advice - you do
not need to check the TargetInstrDesc implicit operands. You only need to
check the operands returned by MachineInstr::getOperand.


- Lang.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20091021/2d9f49c5/attachment.html>

On Wed, 21 Oct 2009, Lang Hames wrote:
> There are any number of things that can go wrong in register allocation, so
> it's hard for me to guess without seeing your code.
>
> Possible issues:
>
> 2) How are you making sure that interfering virtregs never receive the same
> physreg? If you're using the LiveIntervals analysis (and the
> LiveInterval::overlaps(LiveInterval &) test) you should be ok, since it
gets
> a lot of testing (though bugs are not unheard of). If you've written
your
> own liveness analysis that would be one of the first places I'd check
for
> correctness.
I'm doing VERY simple reg allocation, just to see if I can get something 
to work.  I only allocate a physical register to ONE virtual register (the 
first such virtual I find that hasn't already had a physical register 
allocated to it).  So I don't think my problem has to do with 
interference.

> In addition, what do you do if/when you encounter an instruction with two
or
> more operands (in the same class) that have been spilled?
For each instruction, I iterate over the operands.  For each operand that 
is a virtual register "r", if "r" hasn't been given a
physical register
and there is one available (in "r"'s class), then I allocate that
physical
register to "r".  If not, I call assignVirt2StackSlot(r) and 
assignVirt2Phys(r, sp), where sp is s physical register in "r"'s
class
that has been saved to be used as a spill register.

I don't do anything special for the case you mention, so that may be my 
problem.  I thought that what I am doing, plus calling the spiller at the 
end, would magically take care of everything.  If not, can you point me at 
the relevant documentation or an example from existing code?

I realized that I was unclear about where the actual problem is: My 
allocator runs fine, it is (as you suspected) the generated code that 
crashes.  I can look at the generated (X86) code and I see the problem for 
one simple example: there's an instruction
 	movl    %edi, 4(%edi)
that should have been
 	movl    %edi, 4(%esp)
but I don't understand how the code gets generated, so this isn't very 
helpful.  Is there a way for me to look at the machine instructions before 
register allocation?

Thanks again!

Susan

On 2009-10-22 06:02, Susan Horwitz wrote:
> but I don't understand how the code gets generated, so this isn't
very
> helpful.  Is there a way for me to look at the machine instructions before 
> register allocation?
>
>   
You can run llc with -debug which shows debug information from all
codegen phases.
You can also use -debug-only=<name> to debug only a specific codegen pass.

I see output like this, where I think that instead of LINEAR SCAN your
allocator will be run:

********** MACHINEINSTRS **********
entry:
20      MOV32mr <fi#1>, 1, %reg0, 0, %reg0, %EDI<kill>
28      %reg1026<def> = MOV32rm <fi#1>, 1, %reg0, 0, %reg0
36      MOV32mr <fi#0>, 1, %reg0, 0, %reg0, %reg1026<kill>
44      %EAX<def> = MOV32rm <fi#0>, 1, %reg0, 0, %reg0
64      RET %EAX<imp-usekill>
********** LINEAR SCAN **********
********** Function: foo
fixed intervals:
        %reg14,inf = [0,6:0)[6,14:1)[14,22:2)  0@?-(6) 1@? 2@? -> DI
        %reg2,inf = [46,54:1)[54,66:0)  0 at 54-(66) 1@? -> AL
        %reg23,inf = [0,22:0)  0@?-(22) -> EDI
        %reg1,inf = [46,54:1)[54,66:0)  0 at 54-(66) 1@? -> AH
        %reg15,inf = [0,6:0)[6,14:1)[14,22:2)  0@?-(6) 1@? 2@? -> DIL
        %reg3,inf = [46,54:1)[54,66:0)  0 at 54-(66) 1@? -> AX
        %reg19,inf = [46,66:0)  0 at 46-(66) -> EAX

*** CURRENT ***: %reg1026,inf = [30,38:0)  0 at 30-(38)
        processing active intervals:
        processing inactive intervals:
        allocating current interval: EAX
active intervals:
        %reg1026,inf = [30,38:0)  0 at 30-(38) -> EAX
inactive intervals:
        interval %reg1026,inf = [30,38:0)  0 at 30-(38) expired
********** REGISTER MAP **********
[reg1026 -> EAX]


**** Local spiller rewriting function 'foo':
**** Machine Instrs (NOTE! Does not include spills and reloads!) ****
# Machine code for foo():
  <fi#0>: size is 4 bytes, alignment is 4 bytes, at location [SP+8]
  <fi#1>: size is 4 bytes, alignment is 4 bytes, at location [SP+8]
Live Ins: EDI in VR#1025
Live Outs: EAX
....
Best regards
--Edwin

I found the problem!  My generated code is spilling correctly but is not 
reloading at all.  For example, if the original code has the equivalent of 
this (where %1024 is a virtual reg):

 	%1024 = xxx
 	...
 	yyy = %1024

and I find no physical register for %1024, then I assign it to physical 
register %edi and to a stackslot.  That creates code like this:

 	%edi = xxx
 	store from %edi to the stack
 	...
 	yyy = %edi

The last instruction is wrong.  There needs to be a load from the 
stackslot into %edi before copying from there into yyy.

The documentation says:
 	If the indirect strategy is used, after all the virtual registers
 	have been mapped to physical registers or stack slots, it is
 	necessary to use a spiller object to place load and store
 	instructions in the code.  Every virtual that has been mapped to a
 	stack slot will be stored to memory after been defined and will be
 	loaded before being used.
But this doesn't seem to be happening; the stores to memory are there but 
the loads are not.

Any ideas what's going wrong?

If not, any advice on how to generate the loads myself??

Susan