[LLVMdev] [PATCH] [MachineSinking] Conservatively clear kill flags after coalescing.

Juergen Ributzka juergen at apple.com
Fri Sep 5 12:01:25 PDT 2014


You are right. It isn't worth the risk and effort.

Cheers,
Juergen
  
On 09/05/14, Quentin Colombet  <qcolombet at apple.com> wrote:
> 
> 
> 
> 
> 
> 
> On Sep 5, 2014, at 11:27 AM, Juergen Ributzka <juergen at apple.com> wrote:
> 
> 
> > When the SrcReg has the kill flag set, we don't want to propagate that and just keeping the original DstReg kill flag at its last use. Basically there is no work to be done when SrcReg has the kill flag set.
> > When the kill flag is not set we have to first clear the kill flag from all DstReg uses and then perform the replacement with the SrcReg. If we would do the clearing of the kill flag afterwards we would clear more kill flags than necessary and perform more work too.
> > 
> > 
> > if (!MI->getOperand(1).isKill())
> >   MRI->clearKillFlags(DstReg);
> > MRI->replaceRegWith(DstReg, SrcReg);
> > 
> > 
> > DstReg<def> = COPY SrcReg<kill>     DstReg<def> = COPY SrcReg
> > 
> > 
> > ... = ... DstReg                    ... = ... DstReg
> > ... = ... DstReg<kill>              ... = ... DstReg<kill>
> >                                     ... = ... SrcReg<kill>
> > 
> > 
> > ----->
> > 
> > 
> > ... = ... SrcReg                    ... = ... SrcReg
> > ... = ... SrcReg<kill>              ... = ... SrcReg
> >                                     ... = ... SrcReg<kill> <-- this would get cleared too if we clear the kill flags for SrcReg.
> > 
> > 
> > 
> > 
> 
> Yes, but if you consider a different example where SrcReg is killed before DstReg, then it is wrong:
> 
> 
> DstReg = COPY SrcReg
> 
> 
> … = … SrcReg<kill>
> 
> 
> … = … DstReg<kill or not>
> 
> 
> ——>
> 
> 
> … = … SrcReg<kill> <— this isn’t cleared whereas it should.
> 
> 
> … = … SrcReg<kill or not>
> 
> 
> We could indeed do some tricks to preserve the kill flags, but in my opinion, this is error prone and is not worth the risk.
> 
> 
> Cheers,
> -Quentin
> 
> 
> 
> 
> > -Juergen
> > 
> > 
> > On 09/05/14, Quentin Colombet  <qcolombet at apple.com> wrote:
> > > 
> > > 
> > > 
> > > 
> > > 
> > > 
> > > On Sep 5, 2014, at 10:35 AM, Quentin Colombet <qcolombet at apple.com> wrote:
> > > 
> > > 
> > > > 
> > > > On Sep 5, 2014, at 10:21 AM, Juergen Ributzka <juergen at apple.com> wrote:
> > > > 
> > > > 
> > > > > clearKillFlags seems a little "overkill" to me. In this case you could just simply transfer the value of the kill flag from the SrcReg to the DstReg.
> > > > 
> > > > 
> > > > We are extending the live-range of SrcReg. I do not see how you could relate that to the kill flag of DstReg.
> > > > 
> > > > 
> > > 
> > > 
> > > I mean, we *may* extend, but we do not really know.
> > > 
> > > 
> > > > 
> > > > 
> > > > Therefore, I still think, this is the right fix.
> > > > 
> > > > 
> > > > -Quentin
> > > > 
> > > > 
> > > > > 
> > > > > 
> > > > > -Juergen
> > > > > 
> > > > > On 09/05/14,Quentin Colombet<qcolombet at apple.com> wrote:
> > > > > > 
> > > > > > 
> > > > > > 
> > > > > > 
> > > > > > Hi Patrik,
> > > > > > 
> > > > > > 
> > > > > > LGTM.
> > > > > > 
> > > > > > 
> > > > > > Thanks,
> > > > > > -Quentin
> > > > > > On Sep 5, 2014, at 1:03 AM, Patrik Hägglund H <patrik.h.hagglund at ericsson.com> wrote:
> > > > > > 
> > > > > > 
> > > > > > > Hi Quentin,
> > > > > > > 
> > > > > > > 
> > > > > > > Jonas looked further into the problem below, and asked me to submit his patch. Note the we have our own out-of-tree target, and we have not been able to reproduce this problem on an in-tree target. /PatrikHägglund
> > > > > > > 
> > > > > > > 
> > > > > > > [MachineSinking] Conservatively clear kill flags after coalescing.
> > > > > > > 
> > > > > > > 
> > > > > > > This solves the problem of having a kill flag inside a loop
> > > > > > > with a definition of the register prior to the loop:
> > > > > > > 
> > > > > > > 
> > > > > > > %vreg368<def> ...
> > > > > > > 
> > > > > > > 
> > > > > > > Inside loop:
> > > > > > > 
> > > > > > > 
> > > > > > >        %vreg520<def> = COPY %vreg368
> > > > > > >        %vreg568<def,tied1> = add %vreg341<tied0>, %vreg520<kill>
> > > > > > > 
> > > > > > > 
> > > > > > > => was coalesced into =>
> > > > > > > 
> > > > > > > 
> > > > > > >        %vreg568<def,tied1> =add%vreg341<tied0>, %vreg368<kill>
> > > > > > > 
> > > > > > > 
> > > > > > > MachineVerifierthen complained:
> > > > > > > *** Bad machine code: Virtual register killed in block, but needed live out. ***
> > > > > > > 
> > > > > > > 
> > > > > > > The kill flag for %vreg368 is incorrect, and is cleared by this patch.
> > > > > > > 
> > > > > > > 
> > > > > > > This is similar to the clearing done at the end of
> > > > > > > MachineSinking::SinkInstruction().
> > > > > > > ---
> > > > > > > lib/CodeGen/MachineSink.cpp | 5 +++++
> > > > > > > 1 file changed, 5 insertions(+)
> > > > > > > 
> > > > > > > 
> > > > > > > diff --gita/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp
> > > > > > > index 7782001..261af54 100644
> > > > > > > --- a/lib/CodeGen/MachineSink.cpp
> > > > > > > +++ b/lib/CodeGen/MachineSink.cpp
> > > > > > > @@ -157,6 +157,11 @@boolMachineSinking::PerformTrivialForwardCoalescing(MachineInstr*MI,
> > > > > > >   DEBUG(dbgs() << "*** to: " << *MI);
> > > > > > >   MRI->replaceRegWith(DstReg,SrcReg);
> > > > > > >   MI->eraseFromParent();
> > > > > > > +
> > > > > > > +// Conservatively, clear any kill flags, since it's possible that they are no
> > > > > > > +// longer correct.
> > > > > > > +MRI->clearKillFlags(SrcReg);
> > > > > > > +
> > > > > > >   ++NumCoalesces;
> > > > > > >   return true;
> > > > > > > }
> > > > > > > --
> > > > > > > 2.1.0
> > > > > > > 
> > > > > > > 
> > > > > > > From:llvmdev-bounces at cs.uiuc.edu[mailto:llvmdev-bounces at cs.uiuc.edu <llvmdev-bounces at cs.uiuc.edu>]On Behalf OfQuentin Colombet
> > > > > > > Sent:den 2 september 2014 18:37
> > > > > > > To:Jonas Paulsson
> > > > > > > Cc:llvmdev at cs.uiuc.edu
> > > > > > > Subject:Re: [LLVMdev] Machine code sinking pass
> > > > > > > 
> > > > > > > 
> > > > > > >  
> > > > > > > Hi Jonas,
> > > > > > > 
> > > > > > > 
> > > > > > > This looks like a bug in Machine code sinking pass.
> > > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > Please file a PR onllvm.org/bugs(http://llvm.org/bugs)with a reduced test case to keep track of the issue.
> > > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > Thanks,
> > > > > > > 
> > > > > > > -Quentin
> > > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > On Sep 2, 2014, at 5:57 AM, Jonas Paulsson <jonas.paulsson at ericsson.com> wrote:
> > > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > Hi,
> > > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > I ran into MachineVerifier ”Virtual register killed in block, but needed live out.”
> > > > > > > 
> > > > > > >  
> > > > > > > 
> > > > > > > It was MachineSinking:PerformTrivialForwardCoalescing() that coalesced a COPY inside a single-block loop, but left the
> > > > > > > 
> > > > > > > kill-flag and then MachineVerifier complains that a register in vregsRequired is killed in MBB.
> > > > > > > 
> > > > > > >  
> > > > > > > 
> > > > > > > In the example, %vreg520 is replaced by %vreg368 by PerformTrivialForwardCoalescing(), without clearing the kill flag:
> > > > > > > 
> > > > > > >  
> > > > > > > 
> > > > > > > BB#13: derived from LLVM BB %CF250
> > > > > > > 
> > > > > > >     Predecessors according to CFG: BB#12 BB#13 BB#14
> > > > > > > 
> > > > > > >        …
> > > > > > > 
> > > > > > >         %vreg520<def> = COPY %vreg368
> > > > > > > 
> > > > > > >         %vreg568<def,tied1> = cmp %vreg341<tied0>, %vreg520<kill>
> > > > > > > 
> > > > > > >        brr_cond <BB#13>
> > > > > > > 
> > > > > > >         brr_uncond <BB#14>
> > > > > > > 
> > > > > > >     Successors according to CFG: BB#13, BB#14
> > > > > > > 
> > > > > > >  
> > > > > > > 
> > > > > > > Into
> > > > > > > 
> > > > > > >  
> > > > > > > 
> > > > > > > BB#13: derived from LLVM BB %CF250
> > > > > > > 
> > > > > > >     Predecessors according to CFG: BB#12 BB#13 BB#14
> > > > > > > 
> > > > > > >         …
> > > > > > > 
> > > > > > >         %vreg568<def,tied1> = cmp %vreg341<tied0>, %vreg368<kill>
> > > > > > > 
> > > > > > >        brr_cond <BB#13>
> > > > > > > 
> > > > > > >         brr_uncond <BB#14>
> > > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > =>
> > > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > *** Bad machine code: Virtual register killed in block, but needed live out. ***
> > > > > > > 
> > > > > > > - function:    autogen_SD15028
> > > > > > > 
> > > > > > > - basic block: BB#13 CF250 (0x1c75890)
> > > > > > > 
> > > > > > > Virtual register %vreg368 is used after the block.
> > > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > There is only one use of %vreg368 in the function.
> > > > > > > 
> > > > > > >  
> > > > > > > 
> > > > > > > One thing that strikes me is that one might want to clear the kill flag for a use inside a loop of a register defined prior to
> > > > > > > 
> > > > > > > the loop?
> > > > > > > 
> > > > > > >  
> > > > > > > 
> > > > > > > Best regards,
> > > > > > > 
> > > > > > >  
> > > > > > > 
> > > > > > > Jonas Paulsson
> > > > > > > 
> > > > > > >  
> > > > > > > 
> > > > > > > _______________________________________________
> > > > > > > LLVM Developers mailing list
> > > > > > > llvm-commits at cs.uiuc.edu <LLVMdev at cs.uiuc.edu" style="color: purple; text-decoration: underline;">LLVMdev at cs.uiuc.edu        http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits(http://llvm.cs.uiuc.edu/" style="color: purple; text-decoration: underline;" target="1">http://llvm.cs.uiuc.edu
> > > > > > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> > > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > <0001-MachineSinking-Conservatively-clear-kill-flags-after.patch>
> > > > > > > 
> > > > > > 
> > > > > > 
> > > > > > 
> > > > > > 
> > > > > > 
> > > > > > 
> > > > > > 
> > > > > 
> > > > > 
> > > > 
> > > > 
> > > > _______________________________________________
> > > > llvm-commits mailing list
> > > > 
> > > > 
> > > > 
> > > > 
> > > 
> > > 
> > > 
> > > 
> > > 
> > 
> > 
> > 
> > 
> > 
> > 
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140905/803801a5/attachment.html>


More information about the llvm-dev mailing list