[LLVMdev] request for help writing a register allocator

[Susan Horwitz]

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