llvm dev - Dec 2012 - [LLVMdev] problem trying to write an LLVM register-allocation pass

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/20121202/e986ce4b/attachment.html>

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 
> <mailto: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 <tel:50%2064%20117%20118> }).  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 <mailto: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/3cafd5e4/attachment.html>

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>