[LLVMdev] Assert in LiveInterval update

Tue Aug 28 14:33:30 PDT 2012

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