[LLVMdev] Assert in LiveInterval update
Lang Hames
lhames at gmail.com
Sun Sep 2 23:52:37 PDT 2012
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>
More information about the llvm-dev
mailing list