llvm dev - Dec 2016 - Understanding SlotIndexes

Hi all,

I'm tracking down a register allocation problem and I'm trying to
understand this piece of code in InlineSpiller::spillAroundUses:

    // Find the slot index where this instruction reads and writes OldLI.
    // This is usually the def slot, except for tied early clobbers.
    SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
    if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getRegSlot(true)))
      if (SlotIndex::isSameInstr(Idx, VNI->def))
        Idx = VNI->def;

Comments in SlotIndexes.h have this to say:

      /// Early-clobber register use/def slot.  A live range defined at
      /// Slot_EarlyCLobber interferes with normal live ranges killed at
      /// Slot_Register.  Also used as the kill slot for live ranges tied to an
      /// early-clobber def.
      Slot_EarlyClobber,

What does this mean, exactly?  My impression was that an instruction
uses a virtual register at Slot_EarlyClobber if it uses a register tied
to a register def in that instruction.  Is that right?

Why would we ever expect the def slot for early-clobber VNInfo to point
to the same instruction as the early-clobber slot originally queried?
In other words, why would we ever expect this:

Idx      = 10r
EC       = 10e
VNI->def = 10B (or 10r or whatever)

I would expect VNI->def to point to a completely different instruction
or a PHI-def.  Otherwise we have a use-before-def, right?

My problem boils down to trying to find the defining instruction for a
virtual register use.  Given an instruction using register A, I want to
be able to look at the VNInfo at the instruction's register use slot and
see what VNInfo::def points to.  Some scenarios I want to understand:

4B  A = ...
10B D = use A

This seems straightforward.  The instruction at slot 10 uses A at 10r
and the VNInfo for 10r should have a def at 4r.

But that's not right!  I am staring at the following:

LiveInterval: %vreg163 [5404r,6432B:0)[6480B,6688r:0)  0 at 5404r
Instruction:  6688B %RDX<def> = COPY %vreg163

There is NO VNInfo at 6688r (the live range excludes it) but there is a
VNInfo at 6688e (Slot_EarlyClobber).  How am I supposed to know which
slot to look at for a register use?  Are ALL uses always at
Slot_EarlyClobber?  The comment for Slot_EarlyClobber sure doesn't seem
to say that.

10B  A = ...

This instruction defines A at 10r and doesn't use A.  The corresponding
VNInfo has 10r as its def.  I don't think I've seen any puzzlers with
this.

4B   <block>
10B  D = use A

Here there's no def of A in the block so the VNInfo for 10r has a def at
4B (a PHI-def).  Again, the instruction mentioned above is puzzling to
me.  It's early-clobber VNI has its def at 5404r, which is wonderful
because it points back to the actual defining instruction but I would
have expected 6480B.  I guess there's no PHI-def because there aren't
actually multiple values floating around (they're all value 0)?  So no
phi instructions existed before phi elimination so value numbering could
track it properly.

4B  A = ...
10B A = use A

What is this supposed to look like?  From my observations, the VNInfo
for 10r has a def at 10r, which makes sense.  The VNInfo for 10e has a
def at 4r, so to get the value def used by the instruction at 10B I need
to look at its Slot_EarlyClobber VNInfo.  This makes sense to me.

So I guess the main question I have concerns register uses for
instructions that don't also define the register.  Am I always supposed
to look at the early-clobber slot to find its def?  Is the general rule
to always look at Slot_EarlyClobber for a register use to get the VNInfo
containing the index of the defining instruction (or PHI-def)?

Thanks for your help!

                            -David

via llvm-dev <llvm-dev at lists.llvm.org> writes:
> My problem boils down to trying to find the defining instruction for a
> virtual register use.  Given an instruction using register A, I want to
> be able to look at the VNInfo at the instruction's register use slot
and
> see what VNInfo::def points to.
Ok, so I think LiveQuery::valueIn is what I want.  That at least seems
to be pointing to the correct defining value.

I still don't understand SlotIndexes but at least I got by my current
issue.  I gather the Register and EarlyClobber slots are *not* actually
register use points (LiveQuery seems to use the Base/Block slot), which
pretty much directly contradicts the comments...

                              -David

On 12/22/2016 4:02 PM, via llvm-dev wrote:
>
>       /// Early-clobber register use/def slot.  A live range defined at
>       /// Slot_EarlyCLobber interferes with normal live ranges killed at
>       /// Slot_Register.  Also used as the kill slot for live ranges tied
to an
>       /// early-clobber def.
>       Slot_EarlyClobber,
>
> What does this mean, exactly?  My impression was that an instruction
> uses a virtual register at Slot_EarlyClobber if it uses a register tied
> to a register def in that instruction.  Is that right?
Early clobber applies to a defined register and it prevents the register 
allocator from using it as an input register.

> My problem boils down to trying to find the defining instruction for a
> virtual register use.  Given an instruction using register A, I want to
> be able to look at the VNInfo at the instruction's register use slot
and
> see what VNInfo::def points to.  Some scenarios I want to understand:
>
> 4B  A = ...
> 10B D = use A
>
> This seems straightforward.  The instruction at slot 10 uses A at 10r
> and the VNInfo for 10r should have a def at 4r.
>
> But that's not right!  I am staring at the following:
>
> LiveInterval: %vreg163 [5404r,6432B:0)[6480B,6688r:0)  0 at 5404r
> Instruction:  6688B %RDX<def> = COPY %vreg163
An instruction by itself doesn't have any meaningful slot.  It shows as 
B, but only because B is the default slot. For a given register you get 
the actual slot from the live interval.

-Krzysztof

Krzysztof Parzyszek via llvm-dev <llvm-dev at lists.llvm.org> writes:
>> 4B  A = ...
>> 10B D = use A
>>
>> This seems straightforward.  The instruction at slot 10 uses A at 10r
>> and the VNInfo for 10r should have a def at 4r.
>>
>> But that's not right!  I am staring at the following:
>>
>> LiveInterval: %vreg163 [5404r,6432B:0)[6480B,6688r:0)  0 at 5404r
>> Instruction:  6688B %RDX<def> = COPY %vreg163
>
> An instruction by itself doesn't have any meaningful slot.  It shows
> as B, but only because B is the default slot. For a given register you
> get the actual slot from the live interval.
Which slot?  In this case I'm staring at a use of vreg163 and want to
find the def of the value reaching that use.  6688r is *not* in the
interval.  Thus I can't look up 6688r in the interval and get the def
from the VNInfo.  If I look up 6688B I get the expected answer.  Thus
the question.

Again, LVQuery seems to do what I want.  But the comments in
LiveInterval.h seem to be misleading at best.

                        -David

Conceptually and in the default case register uses and defs happen at the
"r" slot. We do not include the "r" slot in the interval of
the used value in order to avoid an overlap with intervals from defined register
which start there as well. That means for the default case you have to query
earlier in the "e" or "b" slot.

Now early clobbers are a special case: A definition can be marked as early
clobber to indicate it happens before any "normal" uses appear to
force the register allocator to allocate different regs for the early clobber
defs and uses. The special case mentioned here is that when your use is
additional tied to an early clobber definition then that use conceptually moves
forward to the "e" slot as well.

In any way you seem to just wanting to query for a use:
- If in doubt use LiveRange::Query()
- If you still want to do it manually query the "b" slot as that will
work regardless of tied-to-earlyclobber uses.

- Matthias
> On Dec 22, 2016, at 2:02 PM, via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi all,
> 
> I'm tracking down a register allocation problem and I'm trying to
> understand this piece of code in InlineSpiller::spillAroundUses:
> 
>    // Find the slot index where this instruction reads and writes OldLI.
>    // This is usually the def slot, except for tied early clobbers.
>    SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
>    if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getRegSlot(true)))
>      if (SlotIndex::isSameInstr(Idx, VNI->def))
>        Idx = VNI->def;
> 
> Comments in SlotIndexes.h have this to say:
> 
>      /// Early-clobber register use/def slot.  A live range defined at
>      /// Slot_EarlyCLobber interferes with normal live ranges killed at
>      /// Slot_Register.  Also used as the kill slot for live ranges tied to
an
>      /// early-clobber def.
>      Slot_EarlyClobber,
> 
> What does this mean, exactly?  My impression was that an instruction
> uses a virtual register at Slot_EarlyClobber if it uses a register tied
> to a register def in that instruction.  Is that right?
> 
> Why would we ever expect the def slot for early-clobber VNInfo to point
> to the same instruction as the early-clobber slot originally queried?
> In other words, why would we ever expect this:
> 
> Idx      = 10r
> EC       = 10e
> VNI->def = 10B (or 10r or whatever)
> 
> I would expect VNI->def to point to a completely different instruction
> or a PHI-def.  Otherwise we have a use-before-def, right?
> 
> My problem boils down to trying to find the defining instruction for a
> virtual register use.  Given an instruction using register A, I want to
> be able to look at the VNInfo at the instruction's register use slot
and
> see what VNInfo::def points to.  Some scenarios I want to understand:
> 
> 4B  A = ...
> 10B D = use A
> 
> This seems straightforward.  The instruction at slot 10 uses A at 10r
> and the VNInfo for 10r should have a def at 4r.
> 
> But that's not right!  I am staring at the following:
> 
> LiveInterval: %vreg163 [5404r,6432B:0)[6480B,6688r:0)  0 at 5404r
> Instruction:  6688B %RDX<def> = COPY %vreg163
> 
> There is NO VNInfo at 6688r (the live range excludes it) but there is a
> VNInfo at 6688e (Slot_EarlyClobber).  How am I supposed to know which
> slot to look at for a register use?  Are ALL uses always at
> Slot_EarlyClobber?  The comment for Slot_EarlyClobber sure doesn't seem
> to say that.
> 
> 10B  A = ...
> 
> This instruction defines A at 10r and doesn't use A.  The corresponding
> VNInfo has 10r as its def.  I don't think I've seen any puzzlers
with
> this.
> 
> 4B   <block>
> 10B  D = use A
> 
> Here there's no def of A in the block so the VNInfo for 10r has a def
at
> 4B (a PHI-def).  Again, the instruction mentioned above is puzzling to
> me.  It's early-clobber VNI has its def at 5404r, which is wonderful
> because it points back to the actual defining instruction but I would
> have expected 6480B.  I guess there's no PHI-def because there
aren't
> actually multiple values floating around (they're all value 0)?  So no
> phi instructions existed before phi elimination so value numbering could
> track it properly.
> 
> 4B  A = ...
> 10B A = use A
> 
> What is this supposed to look like?  From my observations, the VNInfo
> for 10r has a def at 10r, which makes sense.  The VNInfo for 10e has a
> def at 4r, so to get the value def used by the instruction at 10B I need
> to look at its Slot_EarlyClobber VNInfo.  This makes sense to me.
> 
> So I guess the main question I have concerns register uses for
> instructions that don't also define the register.  Am I always supposed
> to look at the early-clobber slot to find its def?  Is the general rule
> to always look at Slot_EarlyClobber for a register use to get the VNInfo
> containing the index of the defining instruction (or PHI-def)?
> 
> Thanks for your help!
> 
>                            -David
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Matthias Braun <mbraun at apple.com> writes:
> Conceptually and in the default case register uses and defs happen at
> the "r" slot. We do not include the "r" slot in the
interval of the
> used value in order to avoid an overlap with intervals from defined
> register which start there as well. That means for the default case
> you have to query earlier in the "e" or "b" slot.
>
> Now early clobbers are a special case: A definition can be marked as
> early clobber to indicate it happens before any "normal" uses
appear
> to force the register allocator to allocate different regs for the
> early clobber defs and uses. The special case mentioned here is that
> when your use is additional tied to an early clobber definition then
> that use conceptually moves forward to the "e" slot as well.
>
> In any way you seem to just wanting to query for a use:
> - If in doubt use LiveRange::Query()
> - If you still want to do it manually query the "b" slot as that
will
> work regardless of tied-to-earlyclobber uses.
Thanks, this is very helpful.  It would be nice to see something like
this put in the LiveInterval.h header.

                                  -David