[LLVMdev] problem trying to write an LLVM register-allocation pass

[Lang Hames]

Hi Susan,

There is some high level documentation about the target independent code
generator here <http://llvm.org/docs/CodeGenerator.html#register-allocator>,
but it doesn't contain the specifics needed to build an allocator from
scratch (e.g, it doesn't describe the issue you just encountered). In my
experience the best option has been to just read the existing allocators
and see how they work.

If your allocator project yields any documentation on building an LLVM
register allocator, patches to our documentation are always welcome.
Otherwise, I'll try to find time to distill the lessons from this thread
and add them to the target independent code generator document.

Cheers,
Lang.


On Mon, Dec 3, 2012 at 7:11 AM, Susan Horwitz <horwitz at cs.wisc.edu> wrote:

>  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
>
>
> On 12/2/2012 10:55 PM, Lang Hames wrote:
>
> 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.
>
>
> On Sat, Dec 1, 2012 at 9:31 AM, Susan Horwitz <horwitz at cs.wisc.edu> wrote:
>
>>  On 11/30/2012 6:36 PM, Lang Hames wrote:
>>
>>
>>
>>  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.
>>
>>
>>  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
>>
>>
>>
>>  ArrayRef<MCPhysReg> 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.
>>
>>
>> On Thu, Nov 29, 2012 at 3:49 PM, Susan Horwitz <horwitz at cs.wisc.edu>wrote:
>>
>>> 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
>>>
>>
>>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121203/77dff1a2/attachment.html>