similar to: RFC: New aggressive dead code elimination pass

[+Danny] ----- Original Message ----- > From: "Justin Bogner via llvm-dev" <llvm-dev at lists.llvm.org> > To: "David Callahan via llvm-dev" <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

On Mon, Apr 4, 2016 at 11:49 AM, David Callahan <dcallahan at fb.com> wrote: > > I may have not correctly used the IDFCalculator. I passed in the > PostDominator tree and then changed the loop over successor blocks to also > be able to iterate over predecessors. I did not see anything in the > interface that would let that happen but perhaps I don’t understand the API > so

Some question: 1. IDFCalculator already allows reverse graphs, and gets used for that, so what did you have to change? (this change was made in the past year, so i wonder if you were working on a branch or something). 2. What are the actual numbers here in terms of calculation of IDF vs your method. IDF calculator is linear time (Well, depends on priority queue impl, but we could fix that

David Callahan via llvm-dev <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. > >

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> wrote: > [+Danny] > > ----- Original Message ----- > > From:

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> 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 Fri, Mar 25, 2016 at 3:52 PM, Hal Finkel <hfinkel at anl.gov> wrote: > > ------------------------------ > > *From: *"Mehdi Amini via llvm-dev" <llvm-dev at lists.llvm.org> > *To: *"Daniel Berlin" <dberlin at dberlin.org> > *Cc: *"David Callahan via llvm-dev" <llvm-dev at lists.llvm.org> > *Sent: *Friday, March 25, 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

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

----- Original Message ----- > From: "Mehdi Amini via llvm-dev" <llvm-dev at lists.llvm.org> > To: "Daniel Berlin" <dberlin at dberlin.org> > Cc: "David Callahan via llvm-dev" <llvm-dev at lists.llvm.org> > Sent: Friday, March 25, 2016 5:43:12 PM > Subject: Re: [llvm-dev] RFC: New aggressive dead code elimination > pass > >

I think you can also avoid the RDF computation using a more directed form of control dependence testing such as described in Keshav Pingali and Gianfranco Bilardi. 1997. Optimal control dependence computation and the Roman chariots problem. ACM Trans. Program. Lang. Syst. 19, 3 (May 1997), 462-491. DOI=http://dx.doi.org/10.1145/256167.256217 However one challenge seems to be fixing the SSA graph

I had assumed you would treat phi nodes differently from other operations in that they don’t need to keep the block alive just to retain the data flow facts but it would be simplest to do that. Thanks Daniel From: Daniel Berlin <dberlin at dberlin.org<mailto:dberlin at dberlin.org>> Date: Friday, January 29, 2016 at 10:26 PM To: David Callahan <dcallahan at

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

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

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<mailto:dberlin at dberlin.org>> Date: Thursday, January 28, 2016 at 8:45 PM To: David Callahan <dcallahan at fb.com<mailto:dcallahan at fb.com>>, LLVM Dev Mailing list <llvm-dev at

In practice, APT is not faster to build than rdf. The df calculator we use is linear time and quite fast. Updating is also pretty trivial since it's only deletes of dead and unreachable code. So anything it reached can be replaced with undef in most cases. Cd-dce is not slower in GCC than dce On Fri, Jan 29, 2016, 8:31 PM David Callahan <dcallahan at fb.com> wrote: > I think you

You should not expect pretty much any perf uplifts from any DCE, ever. If it does, it's mostly luck (better cache behavior, etc). You should expect size improvements ;) On Mon, Aug 1, 2016 at 10:51 PM, Das, Dibyendu via llvm-dev < llvm-dev at lists.llvm.org> wrote: > What kind of perf. uplifts are expected and in what benchmarks/apps ? > > > > *From:* llvm-dev

Maybe I was too quick here. Does gcc record the incoming edge to a phi? If so, won’t those change when you delete blocks in a non-trivial manner? How are those updated? From: David Callahan <dcallahan at fb.com<mailto:dcallahan at fb.com>> Date: Saturday, January 30, 2016 at 7:02 AM To: Daniel Berlin <dberlin at dberlin.org<mailto:dberlin at dberlin.org>>, Hal Finkel

Can you give an example of a case that is missed today but catched by your pass? > On Mar 23, 2016, at 6:43 AM, David Callahan via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > 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

I have a rewrite of the aggressive dead code elimination pass which handles control flow and allows may-be-infinite loops to be removed under optional flag. Chandler suggested rather than a large change a series of small changes and, while that may not get us to small changes easily, there has been no further commentary on the diff: https://reviews.llvm.org/D18762. Given that, I will plan on