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

Mon Apr 18 14:20:53 PDT 2016

Quentin approved it but I still have to commit (and add two typedefs). I'll
do it today

On Mon, Apr 18, 2016, 1:18 PM David Callahan <dcallahan at fb.com> wrote:

> I update the diff to use IDFCalculator, it is indistinguishable in
> compile-time from the ad hoc approach (once I used it correctly).
> You mentioned changing to handle the reverse graph correctly, if that is
> in truck I will update shortly
>
>
> From: Daniel Berlin <dberlin at dberlin.org>
> Date: Monday, April 4, 2016 at 12:32 PM
>
> To: David Callahan <dcallahan at fb.com>
> Cc: Hal Finkel <hfinkel at anl.gov>, Mehdi AMINI <mehdi.amini at apple.com>,
> LLVM Dev Mailing list <llvm-dev at lists.llvm.org>
> Subject: Re: [llvm-dev] RFC: New aggressive dead code elimination pass
>
>
>
> 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 I modified it to explicitly iterate over predecessors under a flag.
>>
>
> Sigh.
> Yes, we fixed it to take domtreebase, so it can take the postdomtree, but
> nobody modified it to change the calculation.
> I'll fix this in a second.
>
>
>
>>  I don’t have comparisons but the problem I had was it would iterative
>> over two much of the graph when we discovered a block was live.
>>
>
> So, the calculation should only happen once, and IDFCalculator should only
> touch each block in the CFG a maximum of once, ever.
>
> If it's doing more than that, it's broken for post-dom.
> In the forwards, problem, i've never seen the *IDF* calculation to be
> noticeable, only the post-dom calculation.
> This would not be completely surprising if it's broken, but it would
> definitely be broken :)
>
>
> We would need to limit the processing. Perhaps the LiveInBblocks vector
>> could be used to filter.  I will take a look and see if that allows an
>> appropriate subgraph to be analyzed. The cost of building the
>> post-dominator tree however was also noticible, but as you observe, it
>> would remove a chunk of code.
>>
>
> Yeah, the post-dom cost problem is a problem we have elsewhere, and we
> should just fix that in one of a myriad of ways.
>
>
>>
>> —david
>>
>> From: Daniel Berlin <dberlin at dberlin.org>
>> Date: Monday, April 4, 2016 at 10:23 AM
>> To: David Callahan <dcallahan at fb.com>
>> Cc: Hal Finkel <hfinkel at anl.gov>, Mehdi AMINI <mehdi.amini at apple.com>,
>> LLVM Dev Mailing list <llvm-dev at lists.llvm.org>
>>
>> Subject: Re: [llvm-dev] RFC: New aggressive dead code elimination pass
>>
>> 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 too), so it should not be *that* bad.
>> We can make it calculate subgraphs like you do as well.
>>
>> 3.
>> While i think the way you compute CD for the subset is cool, it is a
>> bunch of code, and probably hard for the vast majority of people to
>> understand and debug :)
>>
>> So if we can make IDF (assuming postdom) within a few percent of what you
>> are doing, we should just do it, IMHO.
>>
>> If not, well, it's the old "compile time cost vs actual runtime
>> performance improvement vs any reduced maintenance burden/stuff we can make
>> architecturally more sound" game.
>>
>>
>> On Mon, Apr 4, 2016 at 9:46 AM, David Callahan <dcallahan at fb.com> wrote:
>>
>>> Sorry to have disappeared.
>>>
>>> No I do not use Post-dominators. I tried building post-dominatirs and
>>> changing iterated dominance frontier to allow a reverse graph but I found
>>> it was significant more expensive than solving a custom data flow problem
>>> over the “may be dead” subset of the CFG. I did separately rewrite the
>>> post-dominator code to fit the new pass manager but now there are no
>>> clients for it http://reviews.llvm.org/D17114
>>> <https://urldefense.proofpoint.com/v2/url?u=http-3A__reviews.llvm.org_D17114&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=TjhLe787EuDZv6Mmmq-6oKIeTmBGSqKpOi0Bd4C18Uk&s=DLqmvY_Iw3UrR0wZKmvHFSycRNNCEIOCFcq8QF6W104&e=>
>>>
>>> —david
>>>
>>> From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of LLVM Dev
>>> Mailing list <llvm-dev at lists.llvm.org>
>>> Reply-To: Daniel Berlin <dberlin at dberlin.org>
>>> Date: Friday, March 25, 2016 at 4:05 PM
>>> To: Hal Finkel <hfinkel at anl.gov>
>>> Cc: LLVM Dev Mailing list <llvm-dev at lists.llvm.org>
>>> Subject: Re: [llvm-dev] RFC: New aggressive dead code elimination pass
>>>
>>>
>>>
>>> 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 5:43:12 PM
>>>> *Subject: *Re: [llvm-dev] RFC: New aggressive dead code elimination
>>>> pass
>>>>
>>>>
>>>> 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/
>>>> <https://urldefense.proofpoint.com/v2/url?u=http-3A__www.cs.princeton.edu_-257Erwerneck_dominators_&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=09bq6lIe4oGqpw_lE_NAxpN_v13km9w1s-BagEV_Qb8&s=OUaq2P8-4iXMAqcItqLccu1gA856S_ElzN0I0tNjiFk&e=>,
>>>> 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?
>>>>
>>>>
>>>> I'm also curious about this, especially because I'd naively think that:
>>>>
>>>>   representation change == a little thinking and (potentially) a lot of
>>>> typing
>>>>
>>>
>>> It also may change space characteristics for programs with lots of edges.
>>>
>>>
>>>
>>>>   preserving post dom == a lot of thinking and a little typing
>>>>
>>>> and, thus, while updating the analysis might be the *right* thing to
>>>> do, it is probably not easier (especially once you factor in the time taken
>>>> to fix bugs where we subtly get it wrong). Maybe in the long run, we should
>>>> do both?
>>>>
>>>
>>> If we try to keep constant time edge redirection, both are fairly
>>> complicated in terms of thinking :)
>>>
>>>
>>>>
>>>>  -Hal
>>>>
>>>> --
>>>> Mehdi
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> On Thu, Mar 24, 2016 at 11:56 PM, Eric Christopher <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> 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> wrote:
>>>>>>
>>>>>>> [+Danny]
>>>>>>>
>>>>>>> ------------------------------
>>>>>>>
>>>>>>> > 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 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
>>>>>>> > > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>>>> <https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=09bq6lIe4oGqpw_lE_NAxpN_v13km9w1s-BagEV_Qb8&s=cHLE-CvXoQpfSfgjfaPlgAD2ZL_0oH1rLGQWZ3AYeT4&e=>
>>>>>>> > _______________________________________________
>>>>>>> > LLVM Developers mailing list
>>>>>>> > llvm-dev at lists.llvm.org
>>>>>>> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>>>> <https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=09bq6lIe4oGqpw_lE_NAxpN_v13km9w1s-BagEV_Qb8&s=cHLE-CvXoQpfSfgjfaPlgAD2ZL_0oH1rLGQWZ3AYeT4&e=>
>>>>>>> >
>>>>>>>
>>>>>>> --
>>>>>>> Hal Finkel
>>>>>>> Assistant Computational Scientist
>>>>>>> Leadership Computing Facility
>>>>>>> Argonne National Laboratory
>>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> LLVM Developers mailing list
>>>>>> llvm-dev at lists.llvm.org
>>>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>>> <https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=09bq6lIe4oGqpw_lE_NAxpN_v13km9w1s-BagEV_Qb8&s=cHLE-CvXoQpfSfgjfaPlgAD2ZL_0oH1rLGQWZ3AYeT4&e=>
>>>>>>
>>>>>
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org
>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>> <https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=09bq6lIe4oGqpw_lE_NAxpN_v13km9w1s-BagEV_Qb8&s=cHLE-CvXoQpfSfgjfaPlgAD2ZL_0oH1rLGQWZ3AYeT4&e=>
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org
>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>> <https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=09bq6lIe4oGqpw_lE_NAxpN_v13km9w1s-BagEV_Qb8&s=cHLE-CvXoQpfSfgjfaPlgAD2ZL_0oH1rLGQWZ3AYeT4&e=>
>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> 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/20160418/4ae956d1/attachment-0001.html>