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

Mon Apr 4 12:32:27 PDT 2016

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/20160404/f01a0029/attachment.html>