[LLVMdev] Assert in live update from MI scheduler.

Sergei Larin slarin at codeaurora.org
Wed Jun 13 10:49:45 PDT 2012


Andy, 

  I traced my problem to this point:
In ScheduleDAGInstrs.cpp we have the following function: 

/// addVRegDefDeps - Add register output and data dependencies from this
SUnit
/// to instructions that occur later in the same scheduling region if they
read
/// from or write to the virtual register defined at OperIdx.
///
/// TODO: Hoist loop induction variable increments. This has to be
/// reevaluated. Generally, IV scheduling should be done before coalescing.
void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) {
  const MachineInstr *MI = SU->getInstr();
  unsigned Reg = MI->getOperand(OperIdx).getReg();

  // SSA defs do not have output/anti dependencies.
  // The current operand is a def, so we have at least one.
  if (llvm::next(MRI.def_begin(Reg)) == MRI.def_end())   <<<<<<<<<<<<<<<<<<
This is what I am missing. See below.
    return;

  // Add output dependence to the next nearest def of this vreg.
  //
  // Unless this definition is dead, the output dependence should be
  // transitively redundant with antidependencies from this definition's
  // uses. We're conservative for now until we have a way to guarantee the
uses
  // are not eliminated sometime during scheduling. The output dependence
edge
  // is also useful if output latency exceeds def-use latency.
  VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg);
  if (DefI == VRegDefs.end())
    VRegDefs.insert(VReg2SUnit(Reg, SU));
  else {
    SUnit *DefSU = DefI->SU;
    if (DefSU != SU && DefSU != &ExitSU) {
      unsigned OutLatency = TII->getOutputLatency(InstrItins, MI, OperIdx,
                                                  DefSU->getInstr());
      DefSU->addPred(SDep(SU, SDep::Output, OutLatency, Reg));
    }
    DefI->SU = SU;
  }
}

So if this early exit is taken:

  // SSA defs do not have output/anti dependencies.
  // The current operand is a def, so we have at least one.
  if (llvm::next(MRI.def_begin(Reg)) == MRI.def_end())
    return;

we do not ever get to this point:

   VRegDefs.insert(VReg2SUnit(Reg, SU));

But later, when checking for anti dependency for another MI here:

void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) {
...
  // Add antidependence to the following def of the vreg it uses.
  VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg);
  if (DefI != VRegDefs.end() && DefI->SU != SU)
    DefI->SU->addPred(SDep(SU, SDep::Anti, 0, Reg));

We will never find that def in VRegDefs.find(Reg) even though it exists.

I know this has been working for a while, but I am still missing something
here.
What is this statement 

if (llvm::next(MRI.def_begin(Reg)) == MRI.def_end())

should guarantee? From it there must be more than one definition in MRI.def
for that reg for it to work... 




To connect it to the original example... When parsing (BU order) this
instruction:

SU(1):   %vreg10<def> = LDriw %vreg9<kill>, 0; mem:LD4[%stack.0.in]

The %vreg10<def> never inserted to VRegDefs, so with next instruction:

SU(0):   %vreg1<def> = COPY %vreg10<kill>; IntRegs:%vreg1,%vreg10

Anti dep on %vreg10 is never created.

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: Wednesday, June 13, 2012 9:15 AM
> To: 'Andrew Trick'
> Cc: llvmdev at cs.uiuc.edu
> Subject: Re: [LLVMdev] Assert in live update from MI scheduler.
> 
> Andy,
> 
>   Thanks for reply. I was able to trace the problem to the MI DAG dep
> constructor. See this:
> 
> SU(0):   %vreg1<def> = COPY %vreg10<kill>; IntRegs:%vreg1,%vreg10
>   # preds left       : 0
>   # succs left       : 0
>   # rdefs left       : 1
>   Latency            : 1
>   Depth              : 0
>   Height             : 0
> 
> SU(1):   %vreg10<def> = LDriw %vreg9<kill>, 0; mem:LD4[%stack.0.in]
> IntRegs:%vreg10,%vreg9
>   # preds left       : 0
>   # succs left       : 3
>   # rdefs left       : 1
>   Latency            : 1
>   Depth              : 0
>   Height             : 0
>   Successors:
>    val SU(3): Latency=1
>    val SU(2): Latency=1
>    antiSU(2): Latency=0
> 
> SU(2):   %vreg9<def> = ADD_ri %vreg10, 8; IntRegs:%vreg9,%vreg10
>   # preds left       : 2
>   # succs left       : 0
>   # rdefs left       : 1
>   Latency            : 1
>   Depth              : 0
>   Height             : 0
>   Predecessors:
>    val SU(1): Latency=1 Reg=%vreg10
>    antiSU(1): Latency=0
> 
> The anti dep between SU(0) and SU(1) is missing, so when scheduler
> decides to reorder them, LI rightfully complains.
> Again, this is branch code, but if I can see something wrong in
> platform independent portion, I'll track it on the trunk.
> 
> Thanks.
> 
> Sergei
> 
> --
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum.
> 
> 
> > -----Original Message-----
> > From: Andrew Trick [mailto:atrick at apple.com]
> > Sent: Tuesday, June 12, 2012 10:21 PM
> > To: Sergei Larin
> > Cc: llvmdev at cs.uiuc.edu List; Lang Hames
> > Subject: Re: [LLVMdev] Assert in live update from MI scheduler.
> >
> >
> > On Jun 12, 2012, at 10:22 AM, Sergei Larin <slarin at codeaurora.org>
> > wrote:
> >
> > >
> > > Hello everyone,
> > >
> > >  I am working on a release based on the branch 3.1 version of code.
> > > Unfortunately it has enough differences that exact rev does not
> > apply.
> > > I am hitting an assert in liveness update with seemingly trivial
> > > code (attached).
> > >
> > > /local/mnt/workspace/slarin/tools/llvm-mainline-
> > merged/lib/CodeGen/Liv
> > > eInter
> > > valAnalysis.cpp:1078: void
> > >
> llvm::LiveIntervals::HMEditor::moveAllRangesFrom(llvm::MachineInstr*
> > > ,
> > > llvm::SlotIndex): Assertion `validator.rangesOk() &&
> > > "moveAllOperandsFrom broke liveness."' failed.
> > >
> > > The code being scheduled (function "push") is trivial:
> > >
> > > # Machine code for function push: Post SSA Function Live Outs: %R0
> > >
> > > 0B  BB#0: derived from LLVM BB %entry
> > > 16B     %vreg9<def> = TFRI_V4 <ga:@xx_stack>; IntRegs:%vreg9
> > >        Successors according to CFG: BB#1
> > >
> > > 48B BB#1: derived from LLVM BB %for.cond
> > >        Predecessors according to CFG: BB#0 BB#1
> > > 80B     %vreg1<def> = COPY %vreg10<kill>; IntRegs:%vreg1,%vreg10
> > > 96B     %vreg10<def> = LDriw %vreg9<kill>, 0; mem:LD4[%stack.0.in]
> > > IntRegs:%vreg10,%vreg9
> > > 112B    %vreg9<def> = ADD_ri %vreg10, 8; IntRegs:%vreg9,%vreg10
> > > 128B    %vreg6<def> = CMPEQri %vreg10, 0; PredRegs:%vreg6
> > IntRegs:%vreg10
> > > 176B    JMP_cNot %vreg6<kill>, <BB#1>, %PC<imp-def>;
> PredRegs:%vreg6
> > > 192B    JMP <BB#2>
> > >        Successors according to CFG: BB#2 BB#1
> > >
> > > 208B    BB#2: derived from LLVM BB %for.end
> > >        Predecessors according to CFG: BB#1
> > > 224B    %vreg7<def> = LDriw %vreg1<kill>, 0;
> > mem:LD4[%first1](tbaa=!"any
> > > pointer") IntRegs:%vreg7,%vreg1
> > > 240B    STriw_GP <ga:@yy_instr>, 0, %vreg7<kill>;
> > > mem:ST4[@yy_instr](tbaa=!"any pointer") IntRegs:%vreg7
> > > 256B    JMPR %PC<imp-def>, %R31<imp-use>, %R0<imp-use,undef>
> > >
> > > Hexagon MI scheduler is working with BB1 and picks this load:
> > >
> > >  %vreg10<def> = LDriw %vreg9<kill>, 0; mem:LD4[%stack.0.in]
> > > IntRegs:%vreg10,%vreg9
> > >
> > > To be scheduled first (!). Right there after
> > >
> > > 7  clang           0x000000000226aece
> > > llvm::LiveIntervals::handleMove(llvm::MachineInstr*) + 378
> > > 8  clang           0x0000000001c2574f
> > > llvm::VLIWMachineScheduler::listScheduleTopDown() + 595
> > > 9  clang           0x0000000001c24cd5
> > llvm::VLIWMachineScheduler::schedule()
> > > + 505
> > >
> > > It does not seem to happen on the trunk.
> > >
> > > My question is - Does anyone recognizes the issue, and what
> > > patch(es) do I need to address it. Since my release is based on
> 3.1,
> > > I have to cherry pick them...
> > > Any lead is highly appreciated.
> > >
> > > Thanks.
> > >
> > > Sergei
> > >
> >
> > Quickly scanning the commit log, I only see this one since 3.1:
> >
> > commit f905f69668e5dd184c0a2b5fae38d9f3721c0d3b
> > Author: Lang Hames <lhames at gmail.com>
> > Date:   Tue May 29 18:19:54 2012 +0000
> >
> >     Clear the entering, exiting and internal ranges of a bundle
> before
> > collecting
> >     ranges for the instruction about to be bundled. This fixes a bug
> > in an external
> >     project where an assertion was triggered due to spurious
> 'multiple
> > defs' within
> >     the bundle.
> >
> >     Patch by Ivan Llopard. Thanks Ivan!
> >
> > git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157632
> >
> > Maybe Lang can remember something relevant though.
> >
> > I still see a number of these asserts on trunk. I just haven't gotten
> > around to making a push to fix them yet, because I've been focussing
> > on other areas. However, if you reproduce your problem on trunk, file
> > a bug right away. If you aren't able to work around this, I'll take
> > some time to file bugs for asserts that I can reproduce in case
> > they're related to your problem.
> >
> > -Andy
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev




More information about the llvm-dev mailing list