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@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@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

      /// 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@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@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@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

Matthias Braun <mbraun@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