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

[Daniel Berlin via llvm-dev]

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 :)

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

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



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
>> <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=pCcZikgFQttaHaETuHc6G00dgArj_Spf58imKkXlTqk&s=NTh5Q1gE2ANS1rQYN9XFok_t8wvWCu1dzzzvHfv3hlI&e=>
>>
>
> _______________________________________________
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160128/9dd13143/attachment-0001.html>