[LLVMdev] Assert in LiveInterval update

Sergei Larin slarin at codeaurora.org
Fri Aug 31 11:57:21 PDT 2012


Lang, 

 

  I think I am getting closer to understanding this. The findLastUseBefore()
should probably look something like this:

 

// Return the last use of reg between NewIdx and OldIdx.

  SlotIndex findLastUseBefore(unsigned Reg, SlotIndex OldIdx) {

    SlotIndex LastUse = NewIdx;

 

    if (TargetRegisterInfo::isPhysicalRegister(Reg)) {

      for (MCRegUnitRootIterator Roots(Reg, &TRI); Roots.isValid(); ++Roots)
{

        unsigned Root = *Roots;

        for (MachineRegisterInfo::use_nodbg_iterator

             UI = MRI.use_nodbg_begin(Root),

             UE = MRI.use_nodbg_end();

             UI != UE; UI.skipInstruction()) {

          const MachineInstr* MI = &*UI;

          SlotIndex InstSlot =
LIS.getSlotIndexes()->getInstructionIndex(MI);

          if (InstSlot > LastUse && InstSlot < OldIdx) 

            LastUse = InstSlot;

      }

        //for (MCSuperRegIterator Supers(Root, &TRI); Supers.isValid();
++Supers) 

        //  I do not think we should be doing this here.

      }

    } else {

      for (MachineRegisterInfo::use_nodbg_iterator

             UI = MRI.use_nodbg_begin(Reg),

             UE = MRI.use_nodbg_end();

           UI != UE; UI.skipInstruction()) {

        const MachineInstr* MI = &*UI;

        SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);

        if (InstSlot > LastUse && InstSlot < OldIdx) 

          LastUse = InstSlot;

      }

    }

    return LastUse;

  }

 

This is not a patch, more like thinking aloud. If this does not make sense,
please let me know.

 

Sergei

 

---

Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by
The Linux Foundation

 

From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On
Behalf Of Sergei Larin
Sent: Friday, August 31, 2012 11:53 AM
To: 'Lang Hames'
Cc: 'LLVM Developers Mailing List'
Subject: Re: [LLVMdev] Assert in LiveInterval update

 

Hi Lang,

 

  Just one more quick question. in LiveIntervalAnalysis.cpp In 

 

SlotIndex findLastUseBefore(unsigned Reg, SlotIndex OldIdx)

 

Did you really mean to use

 

for (MachineRegisterInfo::use_nodbg_iterator

           UI = MRI.use_nodbg_begin(Reg),

           UE = MRI.use_nodbg_end();

         UI != UE; UI.skipInstruction()) {}

 

 

Aren't we currently dealing with units, not registers ?

 

SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx);

 

.and isn't MRI.use_nodbg_begin(Reg) expects a register, not a unit? .or did
I got it wrong again. Sorry to bug you on this.

 

Sergei

 

---

Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by
The Linux Foundation

 

From: Lang Hames [mailto:lhames at gmail.com] 
Sent: Thursday, August 30, 2012 3:17 PM
To: Sergei Larin
Cc: Andrew Trick; LLVM Developers Mailing List
Subject: Re: [LLVMdev] Assert in LiveInterval update

 

Hi Sergei, Andy,

 

Sorry - I got distracted with some other work. I'm looking into this and
PR13719 now. I'll let you know what I find out.

 

Sergei - thanks very much for the investigation. That should help me pin
this down.

 

Cheers,

Lang.

 

On Tue, Aug 28, 2012 at 2:33 PM, Sergei Larin <slarin at codeaurora.org> wrote:

Andy, Lang,

  Thanks for the suggestion.


  I have spent more time with it today, and I do see some strange things in
liveness update. I am not at the actual cause yet, but here is what I got so
far:

I have the following live ranges when I start scheduling a region:

R2 = [0B,48r:0)[352r,416r:5)...
R3 = [0B,48r:0)[368r,416r:5)...
R4 = [0B,32r:0)[384r,416r:4)...
R5 = [0B,32r:0)[400r,416r:4)...

I schedule the following instruction (48B):

0B      BB#0: derived from LLVM BB %entry
            Live Ins: %R0 %R1 %D1 %D2
8B              %vreg27<def> = COPY %R1<kill>; IntRegs:%vreg27
12B             %vreg30<def> = LDriw <fi#-1>, 0;
mem:LD4[FixedStack-1](align=8) IntRegs:%vreg30
20B             %vreg31<def> = LDriw <fi#-2>, 0; mem:LD4[FixedStack-2]
IntRegs:%vreg31
24B             %vreg26<def> = COPY %R0<kill>; IntRegs:%vreg26
28B             %vreg106<def> = TFRI 16777216;
IntRegs:%vreg106<<<<<<<<<<<<<<<<<<<<<<<<<<< CurrentTop
32B             %vreg29<def> = COPY %D2<kill>; DoubleRegs:%vreg29
48B             %vreg28<def> = COPY %D1<kill>; DoubleRegs:%vreg28
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< Needs to move above 28B
96B             %vreg37<def> = LDriw <fi#-8>, 0; mem:LD4[FixedStack-8]
IntRegs:%vreg37

In Hexagon %D1==%R0:R1 (double reg), %D2==%R2:R3 etc.
The MI move triggers liveness update, which first triggers SlotIndex
renumbering:

*** Renumbered SlotIndexes 24-56 ***

So my 48B becomes 56B, so after the update new live ranges look like this:

R2 = [0B,56r:0)[352r,416r:5)...
R3 = [0B,56r:0)[368r,416r:5)...
R4 = [0B,48r:0)[384r,416r:4)...
R5 = [0B,48r:0)[400r,416r:4)...

Then in LiveIntervals::handleMove OldIndex 56B and NewIndex is 32B (also new
after renumbering. But happens to match another old one).
collectRanges for MI figures that it is moving a paired register, and
correctly(?) selects these two ranges to update for %R2:R3

[0B,56r:0)[368r,416r:5)...
[0B,56r:0)[352r,416r:5)...

___BUT____ after the update, my new ranges look like this:

R2 = [0B,32r:0)[352r,416r:5)...
R3 = [0B,48r:0)[368r,416r:5)...<<<<< Bogus range, 56r should have become 48r
R4 = [0B,48r:0)[384r,416r:4)...
R5 = [0B,48r:0)[400r,416r:4)...
....
0B      BB#0: derived from LLVM BB %entry
            Live Ins: %R0 %R1 %D1 %D2
8B              %vreg27<def> = COPY %R1<kill>; IntRegs:%vreg27
12B             %vreg30<def> = LDriw <fi#-1>, 0;
mem:LD4[FixedStack-1](align=8) IntRegs:%vreg30
20B             %vreg31<def> = LDriw <fi#-2>, 0; mem:LD4[FixedStack-2]
IntRegs:%vreg31
24B             %vreg26<def> = COPY %R0<kill>; IntRegs:%vreg26
32B             %vreg28<def> = COPY %D1<kill>; DoubleRegs:%vreg28
<<<<<<<<<<<<<<<< Moved instruction
40B             %vreg106<def> = TFRI 16777216; IntRegs:%vreg106
48B             %vreg29<def> = COPY %D2<kill>; DoubleRegs:%vreg29
96B             %vreg37<def> = LDriw <fi#-8>, 0; mem:LD4[FixedStack-8]
IntRegs:%vreg37

This is not caught at this time, and only much later, when another
instruction is scheduled to __the same slot___ the old one "occupied" (48B),
the discrepancy is caught by one of unrelated asserts... I think at that
time there are simply some stale aliases in liveness table.

I'm going to continue with this tomorrow, but if this helps to identify a
lurking bug today, my day was worth it :) :) :)


Sergei

--
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum.


> -----Original Message-----

> From: Andrew Trick [mailto:atrick at apple.com]
> Sent: Tuesday, August 28, 2012 3:47 PM
> To: Sergei Larin
> Cc: LLVM Developers Mailing List; Lang Hames
> Subject: Re: [LLVMdev] Assert in LiveInterval update
>
> On Aug 28, 2012, at 8:18 AM, Sergei Larin <slarin at codeaurora.org>
> wrote:
> >
> >  I've described that issue (see below) when you were out of town... I
> > think I am getting more context on it. Please take a look...
> >
> > So, in short, when the new MI scheduler performs move of an
> > instruction, it does something like this:
> >
> >    // Move the instruction to its new location in the instruction
> stream.
> >    MachineInstr *MI = SU->getInstr();
> >
> >    if (IsTopNode) {
> >      assert(SU->isTopReady() && "node still has unscheduled
> dependencies");
> >      if (&*CurrentTop == MI)              <<<<<<<<<<<<<<<<<<  Here we
> make
> > sure that CurrentTop != MI.
> >        CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom);
> >      else {
> >        moveInstruction(MI, CurrentTop);
> >        TopRPTracker.setPos(MI);
> >      }
> > ...
> >
> > But in moveInstruction we use
> >
> >  // Update the instruction stream.
> >  BB->splice(InsertPos, BB, MI);
> >
> > And splice as far as I understand moves MI to the location right
> > __before__ InsertPos. Our previous check made sure that InsertPos !=
> > MI, But I do hit a case, when MI == InsertPos--, and effectively
> tries
> > to swap instruction with itself... which make live update mechanism
> very unhappy.
> >
> > If I am missing something in intended logic, please explain,
> otherwise
> > it looks like we need to adjust that check to make sure we never even
> > considering this situation (swapping with self).
> >
> > I also wonder if we want explicit check in live update with more
> > meaningful assert :)
>
> Thanks for debugging this! The code above assumes that you're moving an
> unscheduled instruction, which should never be above InsertPos for top-
> down scheduling. If the instruction was in multiple ready Q's, then you
> may attempt to schedule it multiple times. You can avoid this by
> checking Su->isScheduled in your Strategy's pickNode. See
> InstructionShuffler::pickNode for an example. I don't see an equivalent
> check in ConvergingScheduler, but there probably should be.
>
> Another possibility to consider is something strange with DebugValues,
> which I haven't tested much.
>
> I reproduced the same assert on arm and filed PR13719. I'm not sure yet
> if it's exactly the same issue, but we can move the discussion there.
>
> We need a better assert in live update and probably the scheduler too.
> Lang mentioned he may look at the issue today. Meanwhile, I hope my
> suggestion above helps.
>
> -Andy

_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120831/225fe6a0/attachment.html>


More information about the llvm-dev mailing list