[llvm-dev] Understanding SlotIndexes

[via llvm-dev]

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