[llvm-dev] RFC: New aggressive dead code elimination pass

Fri Mar 25 15:43:12 PDT 2016

> On Mar 25, 2016, at 3:30 PM, Daniel Berlin via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> Make most things update post-dominance info and preserve it.
> 
> Our other alternative to not take up too much time seems to be invasive surgery on how BB successors/predecessors work so they are a constant time array.  I say this because GCC recomputes post-dominators roughly 15-19 times per compilation, and can do it about 3-5x faster than we can. All profiling i've done basically says all our time is spent trying to get at successors and predecessors in dominance/post-dominance respectively, which takes basically no time in gcc, because the edge lists are an array.
> 
> (Note that if you look at generic dominance code, like http://www.cs.princeton.edu/~rwerneck/dominators/ <http://www.cs.princeton.edu/~rwerneck/dominators/>, it's much faster than what we do on the same graphs. This is true even though we use the same algorithms .....)
> 
> Given it seems unlikely we are going to change the internal representation anytime soon (or at least i've not seen a proposal), updating post-dom seems the easier answer.

Are we talking about the basic-blocks edges only? I'm not sure changing the IR for the BBs would be a lot more work than preserving dominance analysis everywhere, or I am totally underestimating one / overestimating the other?

-- 
Mehdi

> 
> 
> On Thu, Mar 24, 2016 at 11:56 PM, Eric Christopher <echristo at gmail.com <mailto:echristo at gmail.com>> wrote:
> What do you have in mind here?
> 
> 
> On Thu, Mar 24, 2016, 7:28 PM Daniel Berlin via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
> Yeah, that was gonna be my question.
> If so, my view is we should just bite the bullet and start threading post dominance through the compiler.
> (assuming anyone wants to help. I'm tackling the memoryssa updating stuff with george ATM).
> 
> 
> 
> On Thu, Mar 24, 2016 at 7:04 PM, Hal Finkel <hfinkel at anl.gov <mailto:hfinkel at anl.gov>> wrote:
> [+Danny]
> 
> ----- Original Message -----
> > From: "Justin Bogner via llvm-dev" <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>
> > To: "David Callahan via llvm-dev" <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>
> > Sent: Wednesday, March 23, 2016 12:36:50 PM
> > Subject: Re: [llvm-dev] RFC: New aggressive dead code elimination pass
> >
> > David Callahan via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> writes:
> > > Hi,
> > >
> > > I have a new variant of Aggressive Dead Code Elimination that also
> > > removes dead branching. It is designed to minimize the cost of
> > > control-dependence analysis in the common case where almost the
> > > entire
> > > program is live. It also can optionally remove dead but
> > > may-be-infinite loops.
> > >
> > > When enabled for –O3 (replacing current ADCE pass) and removing
> > > loops,
> > > impact on SPEC2006 is in the noise but it impacts internal
> > > benchmarks
> > > suites 1-2% with a comparable increase in compile time.  My
> > > expectation would be to enable –O3 only until we have some
> > > experience
> > > with cost but I suspect it should be fine –O2.
> >
> > Just to clarify, you're saying that both runtime and compile time
> > impact
> > were in the noise on SPEC, right?
> >
> > > What information would the community like to see about such a
> > > change
> > > before I put up a diff and (including tweaks to unit tests).
> >
> > I'm not sure that there's much to discuss in the abstract - it's much
> > easier to evaluate this kind of thing when there's a patch to refer
> > to.
> > Presumably people will want to try the patch out on their own
> > internal
> > benchmarks as well.
> 
> +1
> 
> Does it use post-dominance information?
> 
>  -Hal
> 
> >
> > > Thanks
> > > david
> > > _______________________________________________
> > > LLVM Developers mailing list
> > > llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> > > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> >
> 
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160325/b346b40d/attachment.html>