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 at 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
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 at 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
On Jun 13, 2012, at 10:49 AM, Sergei Larin <slarin at codeaurora.org> wrote:> 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 for the detailed explanation! My understanding is that COPY %vreg10<kill> is illegal because is has no reaching def on all paths (LDriw is the only def). Now, the (llvm::next(MRI.def_begin(Reg)) == MRI.def_end()) check is not really sufficient to test SSA in the presence of undefined operands. However, I thought we would have an IMPLICIT_DEF of the vreg in that case, even after the phi is removed. That right Jakob? Otherwise we I think we should somehow mark the vreg as being undefined. Anyway, I added an assert to catch this problem (see below), and it never triggered on X86. So my guess is that you have incorrect IR coming in. Can you check where %vreg10 is defined. Before coalescing, was it a phi with an <undef> operand? It is safe to workaround the problem by removing the early exit following the SSA check. -Andy --- a/lib/CodeGen/ScheduleDAGInstrs.cpp +++ b/lib/CodeGen/ScheduleDAGInstrs.cpp @@ -413,9 +413,11 @@ void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) { // 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()) + if (llvm::next(MRI.def_begin(Reg)) == MRI.def_end()) { + //!!! + VRegDefs.insert(VReg2SUnit(Reg, SU)); return; - + } // Add output dependence to the next nearest def of this vreg. // // Unless this definition is dead, the output dependence should be @@ -479,8 +481,10 @@ 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) + if (DefI != VRegDefs.end() && DefI->SU != SU) { + assert(llvm::next(MRI.def_begin(Reg)) != MRI.def_end() && "SINGLEDEF"); DefI->SU->addPred(SDep(SU, SDep::Anti, 0, Reg)); + } -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120613/fa07b431/attachment.html>
On Jun 13, 2012, at 7:15 AM, Sergei Larin <slarin at codeaurora.org> wrote:> Again, this is branch code, but if I can see something wrong in platform > independent portion, I'll track it on the trunk.I hate to be the one to start this thread, but I have to say it at least once... General advice. Working off trunk will be less painful than cherry-picking. When it comes to merging, one revision at a time is the only sane approach. If you run sanity tests after merging a set of new trunk revisions, before checking them into your development branch, you can avoid dealing with the rare, temporary breakage, or "instability" as people like to say. If the breakage lasts more than a day, then it's specific to your branch and you want to find out about it ASAP. It will be much harder to fix close to the next release. For example, I just checked in changes to AA scheduling. If you run into a problem with it, I want to know about it now, as in this week. It will be a much bigger burden for me change it again next week, or any time after that. I know for some reason people like their own releases to be "based on llvm release X". That could work if your release cycle is longer than llvm's (after branching your own development you could continue pulling llvm changes until next llvm release). For frequent releases, it's nonsense. Either way, your development branch should still follow trunk. -Andy -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120613/41ba84c4/attachment.html>
On Wed, Jun 13, 2012 at 11:43 AM, Andrew Trick <atrick at apple.com> wrote:> > On Jun 13, 2012, at 7:15 AM, Sergei Larin <slarin at codeaurora.org> wrote: > > Again, this is branch code, but if I can see something wrong in platform > independent portion, I'll track it on the trunk. > > > I hate to be the one to start this thread, but I have to say it at least > once... > > General advice. Working off trunk will be less painful than cherry-picking. >TL;DR: Here here. Yes, more, please! <soap box> I'll go further: don't use development branches. It's just not worth it. I say this as someone who created a development branch of Clang. It was and is a pile of pain. We want to kill it with fire. A lot of people think that a development branch is a useful way to solve problems they run into while developing on trunk: - Commit velocity - Code review latency - API instability - Rough or WIP code being seen by others I assert that these are either not actual problems when working on trunk, or are problems that will actually be worse with a development branch. They are very bad reasons to form one. - Commit velocity may go up, but testing, correctness, and quality of those commits will go down. You also have the added burden of having to commit merges. - Code review latency doesn't go away, it gets deferred until the time at which you want to re-integrate your changes. Deferring code review is like deferring payments on a loan. The more you do it, and the longer you do it, the more interest you build up. It's especially like a loan in that it is a *compounding* phenomenon. However, it's worse than most loans, because the interest rate is somewhere between 20% and 2000%. In such scenarios, micro-payments start to make sense, in the same way that tiny incremental patches make sense on trunk. - API instability is the exact same problem as code review latency -- the API is no more stable, you're just deferring work. The interest rate here is much lower at least, but there is a secondary gotcha -- if your code is on trunk, then the API *changer* will do much of the work for you. - Rough / WIP code *should* be seen by others, in order to get early feedback, avoid bad paths of implementation etc. We should indoctrinate ourselves as developers with a delightful glee in showing code before it's 100% ready for prime time. There are actual cases where you must use a development branch, such as due to controversial changes that need to be demonstrated as viable before accepted, or drastic internal changes that require a lot of work to get into a working state (the type-system rewrite of LLVM is a good example here). If you find yourself in such a scenario, it is essential to make the development branch look as much like trunk as possible. Integrate daily at least, and multiple times a day if you can. Otherwise, all of the problems above will eat away at your productivity. </soap box> -Chandler -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120613/4c6ada4b/attachment.html>