llvm dev - Apr 2016 - RFC: New aggressive dead code elimination pass

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.

What information would the community like to see about such a change before I
put up a diff and (including tweaks to unit tests).

Thanks
david
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160323/fef5ff3f/attachment.html>

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.
> Thanks
> david
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

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 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.
>  
> What information would the community like to see about such a change before
I put up a diff and (including tweaks to unit tests).
>  
> 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
<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/20160323/1d1a2e7d/attachment.html>

[+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 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
> _______________________________________________
> 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

I posted the patch http://reviews.llvm.org/D18762

In the case where loops are retained, current dead code elimination plus some
transformations in SimplifyCFG cover most common cases. This version however
does provide a unified approach which allows extend to removal of
may-be-infinite)loops.
—david

From: Matthias Braun <matze at braunis.de<mailto:matze at
braunis.de>>
Date: Wednesday, March 23, 2016 at 1:07 PM
To: David Callahan <dcallahan at fb.com<mailto:dcallahan at fb.com>>
Cc: LLVM Dev Mailing list <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>
Subject: Re: [llvm-dev] RFC: New aggressive dead code elimination pass

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<mailto: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 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.

What information would the community like to see about such a change before I
put up a diff and (including tweaks to unit tests).

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=CwMF-g&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=rDIdSESZ6OK16HI0D372C_E2G_QraYL_srb2WSdK8T0&s=JPBf_qCTsM0z-74yh9ElddtOerYBr8OwNiuwzNtsRpo&e=>

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