[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