llvm dev - Jan 2016 - DCE in the presence of control flow.

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

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

----- Original Message -----
> From: "David Callahan via llvm-dev" <llvm-dev at
lists.llvm.org>
> To: "LLVM Dev Mailing list" <llvm-dev at lists.llvm.org>
> Sent: Wednesday, January 27, 2016 3:56:33 PM
> Subject: [llvm-dev] DCE in the presence of control flow.
> 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.
Can you provide a small example where this matters? 

-Hal 
> 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
-- 

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

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

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160129/d1446639/attachment.html>

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
lists.llvm.org<mailto: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

On Wed, Jan 27, 2016, 1:56 PM David Callahan via llvm-dev <llvm-dev at
lists.llvm.org<mailto: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<mailto: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=>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160129/96c16fda/attachment.html>