[llvm-dev] DCE in the presence of control flow.

[Hal Finkel via llvm-dev]

----- Original Message -----

> From: "Daniel Berlin" <dberlin at dberlin.org>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "LLVM Dev Mailing list" <llvm-dev at lists.llvm.org>, "David
> Callahan" <dcallahan at fb.com>
> Sent: Friday, January 29, 2016 12:48:37 AM
> Subject: Re: [llvm-dev] DCE in the presence of control flow.

> On Thu, Jan 28, 2016 at 10:09 PM, Hal Finkel < hfinkel at anl.gov >
> wrote:

> > > From: "David Callahan via llvm-dev" < llvm-dev at lists.llvm.org >
> > 
> 
> > > To: "Daniel Berlin" < dberlin at dberlin.org >, "LLVM Dev Mailing
> > > list"
> > > < llvm-dev at lists.llvm.org >
> > 
> 
> > > Sent: Thursday, January 28, 2016 11:35:49 PM
> > 
> 
> > > Subject: Re: [llvm-dev] DCE in the presence of control flow.
> > 
> 

> > > Thanks
> > 
> 
> > > Also I found that some cases are also caught by a specialized
> > > routine
> > > to remove dead loops which is missing the case I noticed.
> > 
> 
> > > odavd
> > 
> 

> > > From: Daniel Berlin < dberlin at dberlin.org >
> > 
> 
> > > Date: Thursday, January 28, 2016 at 8:45 PM
> > 
> 
> > > To: David Callahan < dcallahan at fb.com >, LLVM Dev Mailing list <
> > > llvm-dev at lists.llvm.org >
> > 
> 
> > > Subject: Re: [llvm-dev] DCE in the presence of control flow.
> > 
> 

> > > The post dominators computation costs more on llvm than GCC
> > > because
> > > of how the respective cfgs work under the covers. Even for GCC,
> > > when
> > > we implemented cd-dce, it only catches 1-2% more cases. It's not
> > > really worth the cost in llvm unless postdom comes free
> > 
> 
> > A 1-2% reduction in code size seems like it might well be worth a
> > post-dom calculation.
> 
> 1-2% more cases != 1-2% reduction in code size. In particular, it
> assumes nothing else will catch those cases :)
Fair enough. 

> The cases are mostly caught by SimplifyCFG/etc anyway

> In any case, here are the numbers from when it was turned on by
> default:

> https://gcc.gnu.org/ml/gcc-patches/2004-01/msg00675.html

> Note: GCC is at least 3x faster at computing post-dom than LLVM
Why? 

> > Also, what exactly is the algorithm using post-dom info?
> 

> So, to review for a second, right now, the algorithm answers the
> question when is a branch necessary with "always" :)

> The real answer is "when an already-necessary operation depends on
> its existence". This is of course, requires control-dependence to
> answer.
> So if you take our current DCE algorithm, and instead of marking
> terminators always-live, it simply marks control dependent edges of
> those operands as necessary, and branches that generate those edges.

> (IE

> for each block in RDF(useful block):
> mark terminator of block as useful

FWIW, Keith Cooper's slide deck on this has a nice explanation: https://www.cs.rice.edu/~keith/512/2011/Lectures/L04Dead-1up.pdf 

We might be able to do this without precomputing an RDF, however. For example, you could solve a data-flow problem on the reverse CFG, where for each block you solve for the "next" live instruction. Then a branch is alive only if the next live instruction for each successor is different. You'd need to have "next-live-instruction phi nodes" for cases where there's not a unique answer, etc. 

Thanks again, 
Hal 

> > I suppose that we're looking for cases where we have a CFG diamond
> > with one having only dead instructions, and loops with all dead
> > instructions, etc.
> 
> Yes. Loops with all dead instructions includes "loops with no
> side-effects outside of the loop"

> > Thanks again,
> 
> > Hal
> 

> > > On Wed, Jan 27, 2016, 1:56 PM David Callahan via llvm-dev <
> > > llvm-dev at lists.llvm.org > wrote:
> > 
> 

> > > > I have been looking at some internal codes looking for
> > > > differences
> > > > between Clang (specifically 3.7.1) and gcc (typically 4.8.1 but
> > > > sometimes later).
> > > 
> > 
> 

> > > > One area where I bumped into was dead code elimination in the
> > > > presence of complex control flow. I note that the “aggressive
> > > > dead
> > > > code elimination” (ADCE.cpp) treats all branch operations as
> > > > live
> > > > (
> > > > isa<TerminatorInst>(I)). Doing more requires some approximation
> > > > to
> > > > control dependence.
> > > 
> > 
> 

> > > > I note SimplifyCFG indirectly handles some simple cases. It
> > > > will
> > > > speculate the contents of a basic block into a predecessor but
> > > > this
> > > > is insufficient for more complex structures. This probably
> > > > cherry-picks the most common cases by frequency.
> > > 
> > 
> 

> > > > Have their been prior attempts strengthen dead code elimination
> > > > w.r.t. control flow? If so, any guidance on what went wrong?
> > > 
> > 
> 

> > > > Thanks
> > > 
> > 
> 
> > > > David
> > > 
> > 
> 
> > > > _______________________________________________
> > > 
> > 
> 
> > > > LLVM Developers mailing list
> > > 
> > 
> 
> > > > llvm-dev at lists.llvm.org
> > > 
> > 
> 
> > > > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> > > 
> > 
> 

> > > _______________________________________________
> > 
> 
> > > LLVM Developers mailing list
> > 
> 
> > > llvm-dev at lists.llvm.org
> > 
> 
> > > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> > 
> 

> > --
> 

> > Hal Finkel
> 
> > Assistant Computational Scientist
> 
> > Leadership Computing Facility
> 
> > Argonne National Laboratory
> 

-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160129/6f9026ad/attachment.html>