llvm dev - Jun 2017 - VirtRegMap invariant: no reserved physical registers?

Hey all,

I've found a bug in either the PBQP register allocator or in
VirtRegRewriter.

I'm observing this assertion in VirtRegRewriter::rewrite() fail:
        unsigned VirtReg = MO.getReg();
        unsigned PhysReg = VRM->getPhys(VirtReg);
        ...
        assert(!MRI->isReserved(PhysReg) && "Reserved register
assignment");


Indeed there is a case where PhysReg may be a reserved physical register. 
Specificially, RegAllocPBQP::finalizeAlloc() may select a physical register
thusly:
      const TargetRegisterClass &RC = *MRI.getRegClass(LI.reg);
      PReg = RC.getRawAllocationOrder(MF).front();  
    ...
    VRM.assignVirt2Phys(LI.reg, PReg);


The documentation for TargetRegisterClass::getRawAllocationOrder() notes that
the collection may include reserved registers.  So it seems that the PBQP
allocator may insert a reserve physical register into the VirtRegMap.

I'm not sure which component should be fixed.   Is it fair to say that
no-reserved-registers is an invariant of VirtRegMap?  If so, shouldn't that
invariant be enforced in VirtRegRewriter::assignVirt2Phys() ?  Should PBQP
iterate over the allocation order collection to find an un-reserved physical
register?

Thank you,
Nick Johnson
D. E. Shaw Research

> On Jun 5, 2017, at 9:26 AM, Johnson, Nicholas Paul via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> 
> Hey all,
> 
> I've found a bug in either the PBQP register allocator or in
VirtRegRewriter.
> 
> I'm observing this assertion in VirtRegRewriter::rewrite() fail:
>        unsigned VirtReg = MO.getReg();
>        unsigned PhysReg = VRM->getPhys(VirtReg);
>        ...
>        assert(!MRI->isReserved(PhysReg) && "Reserved
register assignment");
> 
> 
> Indeed there is a case where PhysReg may be a reserved physical register. 
Specificially, RegAllocPBQP::finalizeAlloc() may select a physical register
thusly:
>      const TargetRegisterClass &RC = *MRI.getRegClass(LI.reg);
>      PReg = RC.getRawAllocationOrder(MF).front();  
>    ...
>    VRM.assignVirt2Phys(LI.reg, PReg);
> 
> 
> The documentation for TargetRegisterClass::getRawAllocationOrder() notes
that the collection may include reserved registers.  So it seems that the PBQP
allocator may insert a reserve physical register into the VirtRegMap.
> 
> I'm not sure which component should be fixed.   Is it fair to say that
no-reserved-registers is an invariant of VirtRegMap?  If so, shouldn't that
invariant be enforced in VirtRegRewriter::assignVirt2Phys() ?  Should PBQP
iterate over the allocation order collection to find an un-reserved physical
register?
The generic register allocators have not enough knowledge to safely assign vregs
to reserved registers; or put another way the register allocator should only
assign allocatable register and reserved registers are by definition not
allocatable. So this sounds like a bug in the PBQP allocator to me.

- Matthias

> On Jun 5, 2017, at 9:26 AM, Johnson, Nicholas Paul via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> 
> Hey all,
> 
> I've found a bug in either the PBQP register allocator or in
VirtRegRewriter.
> 
> I'm observing this assertion in VirtRegRewriter::rewrite() fail:
>        unsigned VirtReg = MO.getReg();
>        unsigned PhysReg = VRM->getPhys(VirtReg);
>        ...
>        assert(!MRI->isReserved(PhysReg) && "Reserved
register assignment");
> 
> 
> Indeed there is a case where PhysReg may be a reserved physical register. 
Specificially, RegAllocPBQP::finalizeAlloc() may select a physical register
thusly:
>      const TargetRegisterClass &RC = *MRI.getRegClass(LI.reg);
>      PReg = RC.getRawAllocationOrder(MF).front();  
>    ...
>    VRM.assignVirt2Phys(LI.reg, PReg);
> 
> 
> The documentation for TargetRegisterClass::getRawAllocationOrder() notes
that the collection may include reserved registers.  So it seems that the PBQP
allocator may insert a reserve physical register into the VirtRegMap.
> 
> I'm not sure which component should be fixed.   Is it fair to say that
no-reserved-registers is an invariant of VirtRegMap?  If so, shouldn't that
invariant be enforced in VirtRegRewriter::assignVirt2Phys() ?  Should PBQP
iterate over the allocation order collection to find an un-reserved physical
register?
Feel free to send a patch that adds an assert to assignVirt2Phys().

- Matthias

Thanks Matthias.  Will do.
>-----Original Message-----
>From: mbraun at apple.com [mailto:mbraun at apple.com]
>Sent: Monday, June 05, 2017 5:17 PM
>To: Johnson, Nicholas Paul
>Cc: llvm-dev at lists.llvm.org
>Subject: Re: [llvm-dev] VirtRegMap invariant: no reserved physical
registers?
>
>
>> On Jun 5, 2017, at 9:26 AM, Johnson, Nicholas Paul via llvm-dev
<llvm-
>dev at lists.llvm.org> wrote:
>>
>> Hey all,
>>
>> I've found a bug in either the PBQP register allocator or in
VirtRegRewriter.
>>
>> I'm observing this assertion in VirtRegRewriter::rewrite() fail:
>>        unsigned VirtReg = MO.getReg();
>>        unsigned PhysReg = VRM->getPhys(VirtReg);
>>        ...
>>        assert(!MRI->isReserved(PhysReg) && "Reserved
register assignment");
>>
>>
>> Indeed there is a case where PhysReg may be a reserved physical
register.
>Specificially, RegAllocPBQP::finalizeAlloc() may select a physical register
>thusly:
>>      const TargetRegisterClass &RC = *MRI.getRegClass(LI.reg);
>>      PReg = RC.getRawAllocationOrder(MF).front();
>>    ...
>>    VRM.assignVirt2Phys(LI.reg, PReg);
>>
>>
>> The documentation for TargetRegisterClass::getRawAllocationOrder()
>notes that the collection may include reserved registers.  So it seems that
the
>PBQP allocator may insert a reserve physical register into the VirtRegMap.
>>
>> I'm not sure which component should be fixed.   Is it fair to say
that no-
>reserved-registers is an invariant of VirtRegMap?  If so, shouldn't that
>invariant be enforced in VirtRegRewriter::assignVirt2Phys() ?  Should PBQP
>iterate over the allocation order collection to find an un-reserved physical
>register?
>Feel free to send a patch that adds an assert to assignVirt2Phys().
>
>- Matthias