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