thr3ads.net - llvm dev - [LLVMdev] Assert in LiveInterval update [Aug 2012]

If this information is useful, please help other people find it:
Share via:

Sergei Larin

2012-Aug-31 16:53 UTC

[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/5cb8c4d6/attachment.html>

Sergei Larin

2012-Aug-31 18:57 UTC

head link

[LLVMdev] Assert in LiveInterval update

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>

Lang Hames

2012-Sep-03 06:52 UTC

head link

[LLVMdev] Assert in LiveInterval update

Hi Sergei,

I just fixed the broken test case for PR13719 with r163107, but from the
debugging output you've posted it suspect it won't fix your test case.

Your analysis looks good - findLastUseBefore(..) doesn't appear to be
handling physregs. I'm surprised that isn't causing more failures.
I'll see
if I can find a failing case in the LLVM test-suite (it's been a while
since I ran live-interval-update over all of it) and try out your
modifications to findLastUseBefore.

Thanks very much for all of your work on this.

Cheers,
Lang.

On Sat, Sep 1, 2012 at 4:57 AM, Sergei Larin <slarin at codeaurora.org>
wrote:
> 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 <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/20120903/0151aa35/attachment.html>

Maybe Matching Threads

Search for more apparently analagous threads

llvm dev - Aug 2012 - [LLVMdev] Assert in LiveInterval update

[LLVMdev] Assert in LiveInterval update

[LLVMdev] Assert in LiveInterval update

[LLVMdev] Assert in LiveInterval update

Maybe Matching Threads