llvm dev - Jun 2017 - Ok with mismatch between dead-markings in BUNDLE and bundled instructions?

Hi Quentin and llvm-dev,

I've got a regalloc-related question that you might have an opinion or 
answer about.

In our out-of-tree target we've been doing some bundling before register 
allocation for quite some time now, and last night a new problem popped 
up. What the fix should be depends on if this bundle is legal or not:

     BUNDLE %vreg39<imp-def,dead>
       * %vreg39:hiAcc<def> = mv_ar16_ar16_lo16In32 %vreg37
       [...]

%vreg39 isn't used after the bundle so the dead-marking in the BUNDLE is 
correct. However, the def in the actual bundled instruction defining 
%vreg39 is not marked with dead.

Is the above bundle ok or not?


When the register allocator later tries to spill/reload %vreg39 it 
thinks that %vreg39 is live, so it inserts a reload after the bundle, 
but then the verifier pukes on it and says that there is a use of the 
register after it's dead.

The dead-marking on the BUNDLE is introduced by 
LiveIntervals::computeDeadValues which does

       // This is a dead def. Make sure the instruction knows.
       MachineInstr *MI = getInstructionFromIndex(Def);
       assert(MI && "No instruction defining live value");
       MI->addRegisterDead(LI.reg, TRI);

and the reload after the BUNDLE is introduced by 
InlineSpiller::spillAroundUses which has determined that the register is 
live:

     // Rewrite instruction operands.
     bool hasLiveDef = false;
     for (const auto &OpPair : Ops) {
       MachineOperand &MO = OpPair.first->getOperand(OpPair.second);
       MO.setReg(NewVReg);
       if (MO.isUse()) {
         if (!OpPair.first->isRegTiedToDefOperand(OpPair.second))
           MO.setIsKill();
       } else {
         if (!MO.isDead())
           hasLiveDef = true;
       }


So I suppose we could either make LiveIntervals::computeDeadValues mark 
the individual defs dead as well, or we could change 
InlineSpiller::spillAroundUses so that if we only look at the BUNDLE 
instruction (if it exists) in case of bundled instructions when looking 
for defs.

Any opinions on what way to go?

Thanks,
Mikael

Hi Mikael,

Thanks for bringing that up.
> Le 27 juin 2017 à 04:55, Mikael Holmén <mikael.holmen at
ericsson.com> a écrit :
> 
> Hi Quentin and llvm-dev,
> 
> I've got a regalloc-related question that you might have an opinion or
answer about.
> 
> In our out-of-tree target we've been doing some bundling before
register allocation for quite some time now, and last night a new problem popped
up. What the fix should be depends on if this bundle is legal or not:
> 
>    BUNDLE %vreg39<imp-def,dead>
>      * %vreg39:hiAcc<def> = mv_ar16_ar16_lo16In32 %vreg37
>      [...]
> 
> %vreg39 isn't used after the bundle so the dead-marking in the BUNDLE
is correct. However, the def in the actual bundled instruction defining %vreg39
is not marked with dead.
> 
> Is the above bundle ok or not?
Ultimately, I would like this to be the way we represent these situations,
unfortunately the code base is not ready for that yet.
> 
> 
> When the register allocator later tries to spill/reload %vreg39 it thinks
that %vreg39 is live, so it inserts a reload after the bundle, but then the
verifier pukes on it and says that there is a use of the register after it's
dead.
> 
> The dead-marking on the BUNDLE is introduced by
LiveIntervals::computeDeadValues which does
> 
>      // This is a dead def. Make sure the instruction knows.
>      MachineInstr *MI = getInstructionFromIndex(Def);
>      assert(MI && "No instruction defining live value");
>      MI->addRegisterDead(LI.reg, TRI);
> 
> and the reload after the BUNDLE is introduced by
InlineSpiller::spillAroundUses which has determined that the register is live:
> 
>    // Rewrite instruction operands.
>    bool hasLiveDef = false;
>    for (const auto &OpPair : Ops) {
>      MachineOperand &MO = OpPair.first->getOperand(OpPair.second);
>      MO.setReg(NewVReg);
>      if (MO.isUse()) {
>        if (!OpPair.first->isRegTiedToDefOperand(OpPair.second))
>          MO.setIsKill();
>      } else {
>        if (!MO.isDead())
>          hasLiveDef = true;
>      }
> 
> 
> So I suppose we could either make LiveIntervals::computeDeadValues mark the
individual defs dead as well,
I didn't get that.
> or we could change InlineSpiller::spillAroundUses so that if we only look
at the BUNDLE instruction (if it exists) in case of bundled instructions when
looking for defs.
> 
> Any opinions on what way to go?
> 
I believe we should teach the spiller about the subregs so that it understands a
particular subregs is dead.


Cheers,
Q

> Thanks,
> Mikael

> On Jun 27, 2017, at 4:55 AM, Mikael Holmén via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi Quentin and llvm-dev,
> 
> I've got a regalloc-related question that you might have an opinion or
answer about.
> 
> In our out-of-tree target we've been doing some bundling before
register allocation for quite some time now, and last night a new problem popped
up. What the fix should be depends on if this bundle is legal or not:
> 
>    BUNDLE %vreg39<imp-def,dead>
>      * %vreg39:hiAcc<def> = mv_ar16_ar16_lo16In32 %vreg37
>      [...]
> 
> %vreg39 isn't used after the bundle so the dead-marking in the BUNDLE
is correct. However, the def in the actual bundled instruction defining %vreg39
is not marked with dead.
> 
> Is the above bundle ok or not?
As to whether the bundle is ok: The register allocator should view the whole
bundle as a single instruction with all operands combined. That would
conceptually give us:

    %vreg39<imp-def, dead>, %vreg39:hiAcc<def> = INST...

Of course having two defs for the same register is an uncommon situation.
There's some interesting arguments to be had whether this example means the
whole vreg39 is dead or just the parts of vreg39 that are not covered by the
hiAcc subregister. I think in todays code it means that the whole vreg39
register is dead (though I cannot say off hand whether we do this consistently
or whether it is actually documented somewhere).
> 
> 
> When the register allocator later tries to spill/reload %vreg39 it thinks
that %vreg39 is live, so it inserts a reload after the bundle, but then the
verifier pukes on it and says that there is a use of the register after it's
dead.
> 
> The dead-marking on the BUNDLE is introduced by
LiveIntervals::computeDeadValues which does
> 
>      // This is a dead def. Make sure the instruction knows.
>      MachineInstr *MI = getInstructionFromIndex(Def);
>      assert(MI && "No instruction defining live value");
>      MI->addRegisterDead(LI.reg, TRI);
I think the actual problem here is that MachineInstr::addRegisterDead only works
on a single instruction and not on the whole bundle.

- Matthias

> On Jun 27, 2017, at 2:10 PM, Matthias Braun <mbraun at apple.com>
wrote:
> 
>> 
>> On Jun 27, 2017, at 4:55 AM, Mikael Holmén via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>> 
>> Hi Quentin and llvm-dev,
>> 
>> I've got a regalloc-related question that you might have an opinion
or answer about.
>> 
>> In our out-of-tree target we've been doing some bundling before
register allocation for quite some time now, and last night a new problem popped
up. What the fix should be depends on if this bundle is legal or not:
>> 
>>   BUNDLE %vreg39<imp-def,dead>
>>     * %vreg39:hiAcc<def> = mv_ar16_ar16_lo16In32 %vreg37
>>     [...]
>> 
>> %vreg39 isn't used after the bundle so the dead-marking in the
BUNDLE is correct. However, the def in the actual bundled instruction defining
%vreg39 is not marked with dead.
>> 
>> Is the above bundle ok or not?
> 
> As to whether the bundle is ok: The register allocator should view the
whole bundle as a single instruction with all operands combined. That would
conceptually give us:
> 
>    %vreg39<imp-def, dead>, %vreg39:hiAcc<def> = INST...
> 
> Of course having two defs for the same register is an uncommon situation.
There's some interesting arguments to be had whether this example means the
whole vreg39 is dead or just the parts of vreg39 that are not covered by the
hiAcc subregister. I think in todays code it means that the whole vreg39
register is dead (though I cannot say off hand whether we do this consistently
or whether it is actually documented somewhere).
Yeah I was reading this as “only the non-touched part are dead”, and that’s what
I’d like to see in the representation longer. Obviously, the register is not
dead as a whole here :)
> 
>> 
>> 
>> When the register allocator later tries to spill/reload %vreg39 it
thinks that %vreg39 is live, so it inserts a reload after the bundle, but then
the verifier pukes on it and says that there is a use of the register after
it's dead.
>> 
>> The dead-marking on the BUNDLE is introduced by
LiveIntervals::computeDeadValues which does
>> 
>>     // This is a dead def. Make sure the instruction knows.
>>     MachineInstr *MI = getInstructionFromIndex(Def);
>>     assert(MI && "No instruction defining live
value");
>>     MI->addRegisterDead(LI.reg, TRI);
> 
> I think the actual problem here is that MachineInstr::addRegisterDead only
works on a single instruction and not on the whole bundle.
> 
> - Matthias
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170627/bf8ccedb/attachment-0001.html>

Hi,

Thanks everyone for the answers!

On 06/27/2017 07:21 PM, Quentin Colombet wrote:
> Hi Mikael,
> 
> Thanks for bringing that up.
> 
>> Le 27 juin 2017 à 04:55, Mikael Holmén <mikael.holmen at
ericsson.com> a écrit :
>>
>> Hi Quentin and llvm-dev,
>>
>> I've got a regalloc-related question that you might have an opinion
or answer about.
>>
>> In our out-of-tree target we've been doing some bundling before
register allocation for quite some time now, and last night a new problem popped
up. What the fix should be depends on if this bundle is legal or not:
>>
>>     BUNDLE %vreg39<imp-def,dead>
>>       * %vreg39:hiAcc<def> = mv_ar16_ar16_lo16In32 %vreg37
>>       [...]
>>
>> %vreg39 isn't used after the bundle so the dead-marking in the
BUNDLE is correct. However, the def in the actual bundled instruction defining
%vreg39 is not marked with dead.
>>
>> Is the above bundle ok or not?
> 
> Ultimately, I would like this to be the way we represent these situations,
unfortunately the code base is not ready for that yet.
> 
>>
>>
>> When the register allocator later tries to spill/reload %vreg39 it
thinks that %vreg39 is live, so it inserts a reload after the bundle, but then
the verifier pukes on it and says that there is a use of the register after
it's dead.
>>
>> The dead-marking on the BUNDLE is introduced by
LiveIntervals::computeDeadValues which does
>>
>>       // This is a dead def. Make sure the instruction knows.
>>       MachineInstr *MI = getInstructionFromIndex(Def);
>>       assert(MI && "No instruction defining live
value");
>>       MI->addRegisterDead(LI.reg, TRI);
>>
>> and the reload after the BUNDLE is introduced by
InlineSpiller::spillAroundUses which has determined that the register is live:
>>
>>     // Rewrite instruction operands.
>>     bool hasLiveDef = false;
>>     for (const auto &OpPair : Ops) {
>>       MachineOperand &MO =
OpPair.first->getOperand(OpPair.second);
>>       MO.setReg(NewVReg);
>>       if (MO.isUse()) {
>>         if (!OpPair.first->isRegTiedToDefOperand(OpPair.second))
>>           MO.setIsKill();
>>       } else {
>>         if (!MO.isDead())
>>           hasLiveDef = true;
>>       }
>>
>>
>> So I suppose we could either make LiveIntervals::computeDeadValues mark
the individual defs dead as well,
> 
> I didn't get that.
> 
E.g. extending addRegisterDead so it not only marks the def in the 
BUNDLE instruction as dead, but also each individual def inside the bundle.
>> or we could change InlineSpiller::spillAroundUses so that if we only
look at the BUNDLE instruction (if it exists) in case of bundled instructions
when looking for defs.
>>
>> Any opinions on what way to go?
>>
> 
> I believe we should teach the spiller about the subregs so that it
understands a particular subregs is dead.
> 
I think this issue exists also without involving subregs, but I haven't 
verified it.

In the bundle we have:

      BUNDLE %vreg39<imp-def,dead>
        * %vreg39:hiAcc<def> = mv_ar16_ar16_lo16In32 %vreg37
        [...]

The shown def of %vreg39:hiAcc is the only def of any %vreg39 part in 
the bundle, and that particular def is also dead in the sense that no 
one reads the value, but it's not marked as such since the call to

        MI->addRegisterDead(LI.reg, TRI);

above in LiveIntervals::computeDeadValues only changed the def in the 
BUNDLE instruction.

Right now I've been running tests with

+        // For bundled instructions: Only examine defs in the BUNDLE
+        // instruction itself if it exists.
+        MachineInstr *DefMI = OpPair.first;
+        if (DefMI->isBundled() &&
+            getBundleStart(DefMI->getIterator())->isBundle() &&
+            !DefMI->isBundle())
+            continue;
+
          if (!MO.isDead())
            hasLiveDef = true;

Added to InlineSpiller::spillAroundUses. The assumption is then that if 
there is a BUNDLE we trust that the info in it is correct, that info (at 
least for dead markings) override anything in the individual instructions.

But from Matthias' answer:

On 06/27/2017 11:10 PM, Matthias Braun wrote:
 >
 > [...]
 > I think the actual problem here is that MachineInstr::addRegisterDead 
 > only works on a single instruction and not on the whole bundle.

Maybe we should rather make MachineInstr::addRegisterDead mark the 
individual instruction defs as dead then?

Thanks,
Mikael
> 
> Cheers,
> Q
> 
> 
>> Thanks,
>> Mikael