Andy,
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.
Sergei
--
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum.
> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu]
> On Behalf Of Sergei Larin
> Sent: Friday, August 17, 2012 3:32 PM
> To: 'Andrew Trick'; 'Jakob Olesen'
> Cc: 'LLVM Developers Mailing List'
> Subject: [LLVMdev] Assert in LiveInterval update
>
>
> Andy, Jacob,
>
> I have ported Hexagon MI scheduler to use the new scheduler
> infrastructure, but one of my tests triggers an assert in LiveInterval
> update. On the surface it does not make much sense to me, so I wonder
> if this is something you readily recognize, before I try to prop it
> open...
>
> The assert is:
>
> lib/CodeGen/LiveInterval.cpp:266: llvm::LiveRange*
> llvm::LiveInterval::addRangeFrom(llvm::LiveRange, llvm::LiveRange*):
> Assertion `B->end <= Start && "Cannot overlap two
LiveRanges with
> differing ValID's" " (did you def the same reg twice in a
> MachineInstr?)"' failed.
>
> has this following call stack:
>
> #3 in llvm::LiveInterval::addRangeFrom (this=0x46e99a0, LR=...,
> From=0x46ee4b0) at lib/CodeGen/LiveInterval.cpp:266
> #4 in llvm::LiveInterval::addRange (this=0x46e99a0, LR=...) at
> include/llvm/CodeGen/LiveInterval.h:384
> #5 in llvm::LiveIntervals::HMEditor::moveInternalFrom
> (this=0x7fffffff8010, OldIdx=..., P=...) at
> lib/CodeGen/LiveIntervalAnalysis.cpp:1220
> #6 in llvm::LiveIntervals::HMEditor::moveAllInternalFrom
> (this=0x7fffffff8010, OldIdx=..., Internal=...) at
> lib/CodeGen/LiveIntervalAnalysis.cpp:1226
> #7 in llvm::LiveIntervals::HMEditor::moveAllRangesFrom
> (this=0x7fffffff8010, MI=0x462ab80, OldIdx=...) at
> lib/CodeGen/LiveIntervalAnalysis.cpp:938
> #8 in llvm::LiveIntervals::handleMove (this=0x448b6f0, MI=0x462ab80)
> at
> lib/CodeGen/LiveIntervalAnalysis.cpp:1388
> #9 in llvm::VLIWMachineScheduler::moveInstruction (this=0x46b0f50,
> MI=0x462ab80, InsertPos=...) at
> lib/Target/Hexagon/HexagonMachineScheduler.cpp:120
> #10 in llvm::VLIWMachineScheduler::schedule (this=0x46b0f50) at
> lib/Target/Hexagon/HexagonMachineScheduler.cpp:378
> #11 in (anonymous namespace)::MachineScheduler::runOnMachineFunction
> (this=0x448c730, mf=...) at lib/CodeGen/MachineScheduler.cpp:263
> #12 in llvm::MachineFunctionPass::runOnFunction (this=0x448c770, F=...)
> at
> lib/CodeGen/MachineFunctionPass.cpp:33
>
>
> For the purpose of this question, you can assume
> HexagonMachineScheduler.cpp == MachineScheduler.cpp and
> VLIWMachineScheduler == ScheduleDAGMI
>
>
> The instruction being moved is a simple call:
>
> let isCall = 1, neverHasSideEffects = 1,
> Defs = [D0, D1, D2, D3, D4, D5, D6, D7, R28, R31,
> P0, P1, P2, P3, LC0, LC1, SA0, SA1, USR] in {
> def CALLv3 : JInst<(outs), (ins calltarget:$dst),
> "call $dst", []>, Requires<[HasV3T]>; }
>
> CALLv3 <ga:@printf>, %D0<imp-def,dead>,
%D1<imp-def,dead>, %D2<imp-
> def,dead>, %R31<imp-def>, %R0<imp-use,kill>, ...
>
> Another clue - slot renumbering just took place:
>
> *** Renumbered SlotIndexes 1056-2120 *** ...
>
> *** Renumbered SlotIndexes 1068-2140 ***
>
> ...and the first move after that produces the assert.
>
> (gdb) p Start.dump()
> 1080r
> (gdb) p B->end.dump()
> 1092r
> (gdb) p *LR.valno
> $7 = {id = 61, def = {lie = {Value = 74160402}}}
> (gdb) p *B->valno
> $9 = {id = 0, def = {lie = {Value = 73472560}}}
>
> I have not yet succeeded to reproduce it on anything other than my
> branch of Hexagon, but I can try...
> This is definitely some corner case, since it is a singular failure in
> a very large test suite. Really hope it rings a bell for you.
>
> Thanks.
>
> Sergei
>
> --
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum.
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
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
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