llvm dev - Aug 2016 - [LLVM] New Dead Code Elimination

I have a rewrite of the aggressive dead code elimination pass which handles
control flow and allows may-be-infinite loops to be removed under optional flag.
Chandler suggested rather than a large change a series of small changes and,
while that may not get us to small changes easily, there has been no further
commentary on the diff: https://reviews.llvm.org/D18762.  Given that, I will
plan on proposing a series of diffs and would like to recruit some people who
are interested in the change to help review those changes.

I expect to stage as follows:


1.     Rewrite base algorithm to introduce data structures needed to hold extra
information (no functional change)

2.     Rewrite base algorithm to allow removing of control flow (under option,
off by default). This variant will not be correct in the general case.

3.     Code to rewrite the control flow graph and remove dead basic blocks

4.     Identify Phi nodes with non-instruction reaching definitions and keep the
associated source block live. Identify Phi nodes with multiple-live values from
dead blocks

5.     Remove unreachable code discovered by post-order traversal to avoid.
 (code is functionally correct at this point)

6.     Use post-order traversal to identify loop bottoms. By default this will
be kept live but include switch to allow loops to be removed.

7.     Improve handling of live values out of dead regions

Please respond if you are willing to help or have suggestions on staging or
approach.

Thanks
David
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160801/15e3bab4/attachment-0001.html>

Hi David,

Thanks for working on this.  I’d like to help reviewing your work!

How much code from the original patch are you leaving around? If you are reusing
a lot of code from the original pass then you can refactor, clean and add new
functionality. But if you are not keeping much then maybe it would be useful to
develop a new pass (with small incremental reviewable changes), and when the
work is done flip the switch and start using the new pass. What do you prefer?

I think that introducing the new flag that allows the removal of infinite loops
is a great idea. LLVM is used for compilation of non-C languages, like Swift,
Java, Python, etc, and these languages may benefit from the new functionality.

-Nadav

From: David Callahan <dcallahan at fb.com>
Date: Monday, August 1, 2016 at 10:45 AM
To: LLVM Dev Mailing list <llvm-dev at lists.llvm.org>
Cc: Kevin Frei <freik at fb.com>, Nadav Rotem <nrotem at fb.com>,
Chandler Carruth <chandlerc at gmail.com>
Subject: [LLVM] New Dead Code Elimination

I have a rewrite of the aggressive dead code elimination pass which handles
control flow and allows may-be-infinite loops to be removed under optional flag.
Chandler suggested rather than a large change a series of small changes and,
while that may not get us to small changes easily, there has been no further
commentary on the diff: https://reviews.llvm.org/D18762.  Given that, I will
plan on proposing a series of diffs and would like to recruit some people who
are interested in the change to help review those changes.

I expect to stage as follows:


1.      Rewrite base algorithm to introduce data structures needed to hold extra
information (no functional change)

2.      Rewrite base algorithm to allow removing of control flow (under option,
off by default). This variant will not be correct in the general case.

3.      Code to rewrite the control flow graph and remove dead basic blocks

4.      Identify Phi nodes with non-instruction reaching definitions and keep
the associated source block live. Identify Phi nodes with multiple-live values
from dead blocks

5.      Remove unreachable code discovered by post-order traversal to avoid.
 (code is functionally correct at this point)

6.      Use post-order traversal to identify loop bottoms. By default this will
be kept live but include switch to allow loops to be removed.

7.      Improve handling of live values out of dead regions

Please respond if you are willing to help or have suggestions on staging or
approach.

Thanks
David
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160801/b0662b63/attachment.html>

Hi David,

Feel free to add me as a reviewer (mehdi_amini on Phabricator). I’ll do my best
to help with it.

—
Mehdi
> On Aug 1, 2016, at 10:45 AM, David Callahan via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> I have a rewrite of the aggressive dead code elimination pass which handles
control flow and allows may-be-infinite loops to be removed under optional flag.
Chandler suggested rather than a large change a series of small changes and,
while that may not get us to small changes easily, there has been no further
commentary on the diff: https://reviews.llvm.org/D18762
<https://reviews.llvm.org/D18762>.  Given that, I will plan on proposing a
series of diffs and would like to recruit some people who are interested in the
change to help review those changes.
>  
> I expect to stage as follows:
>  
> 1.     Rewrite base algorithm to introduce data structures needed to hold
extra information (no functional change)
> 2.     Rewrite base algorithm to allow removing of control flow (under
option, off by default). This variant will not be correct in the general case.
> 3.     Code to rewrite the control flow graph and remove dead basic blocks
> 4.     Identify Phi nodes with non-instruction reaching definitions and
keep the associated source block live. Identify Phi nodes with multiple-live
values from dead blocks
> 5.     Remove unreachable code discovered by post-order traversal to avoid.
>  (code is functionally correct at this point)
> 6.     Use post-order traversal to identify loop bottoms. By default this
will be kept live but include switch to allow loops to be removed.
> 7.     Improve handling of live values out of dead regions
>  
> Please respond if you are willing to help or have suggestions on staging or
approach.
>  
> 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/20160801/f77d3b28/attachment.html>

On Mon, Aug 1, 2016 at 11:08 AM, Nadav Rotem via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi David,
>
>
>
> Thanks for working on this.  I’d like to help reviewing your work!
>
>
>
> How much code from the original patch are you leaving around? If you are
> reusing a lot of code from the original pass then you can refactor, clean
> and add new functionality. But if you are not keeping much then maybe it
> would be useful to develop a new pass (with small incremental reviewable
> changes), and when the work is done flip the switch and start using the new
> pass. What do you prefer?
>
>
>
> I think that introducing the new flag that allows the removal of infinite
> loops is a great idea. LLVM is used for compilation of non-C languages,
> like Swift, Java, Python, etc, and these languages may benefit from the new
> functionality.
>
LLVM doesn't handle "infinite loops are a side effect" in a
principled way:
- The LLVM IR corresponding to an infinite loop doesn't contain side
effects which means that the loop itself doesn't have side effects.  Calls
to functions which merely infinite loop can (and will) be removed by LLVM
(because they are readnone, nounwind, etc.).

A proper design for "infinite loops are a side effect" would likely be
a
function attribute which indicates what behavior the optimizer may assume
when it sees a loop with unknown bound in a function.

While this doesn't mean that the pass shouldn't contain logic for
leaving
infinite loops alone, it likely means that parameterizing the pass on a
flag is wrong.

In any case, I'd be willing to pitch in on these reviews.

>
> -Nadav
>
>
>
> *From: *David Callahan <dcallahan at fb.com>
> *Date: *Monday, August 1, 2016 at 10:45 AM
> *To: *LLVM Dev Mailing list <llvm-dev at lists.llvm.org>
> *Cc: *Kevin Frei <freik at fb.com>, Nadav Rotem <nrotem at
fb.com>, Chandler
> Carruth <chandlerc at gmail.com>
> *Subject: *[LLVM] New Dead Code Elimination
>
>
>
> I have a rewrite of the aggressive dead code elimination pass which
> handles control flow and allows may-be-infinite loops to be removed under
> optional flag. Chandler suggested rather than a large change a series of
> small changes and, while that may not get us to small changes easily, there
> has been no further commentary on the diff:
> https://reviews.llvm.org/D18762.  Given that, I will plan on proposing a
> series of diffs and would like to recruit some people who are interested in
> the change to help review those changes.
>
>
>
> I expect to stage as follows:
>
>
>
> 1.      Rewrite base algorithm to introduce data structures needed to
> hold extra information (no functional change)
>
> 2.      Rewrite base algorithm to allow removing of control flow (under
> option, off by default). This variant will not be correct in the general
> case.
>
> 3.      Code to rewrite the control flow graph and remove dead basic
> blocks
>
> 4.      Identify Phi nodes with non-instruction reaching definitions and
> keep the associated source block live. Identify Phi nodes with
> multiple-live values from dead blocks
>
> 5.      Remove unreachable code discovered by post-order traversal to
> avoid.
>
>  (code is functionally correct at this point)
>
> 6.      Use post-order traversal to identify loop bottoms. By default
> this will be kept live but include switch to allow loops to be removed.
>
> 7.      Improve handling of live values out of dead regions
>
>
>
> Please respond if you are willing to help or have suggestions on staging
> or approach.
>
>
>
> 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/20160801/d202ab59/attachment.html>

What kind of perf. uplifts are expected and in what benchmarks/apps ?

From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of David
Callahan via llvm-dev
Sent: Monday, August 01, 2016 11:15 PM
To: LLVM Dev Mailing list <llvm-dev at lists.llvm.org>
Cc: Nadav Rotem <nrotem at fb.com>
Subject: [llvm-dev] [LLVM] New Dead Code Elimination

I have a rewrite of the aggressive dead code elimination pass which handles
control flow and allows may-be-infinite loops to be removed under optional flag.
Chandler suggested rather than a large change a series of small changes and,
while that may not get us to small changes easily, there has been no further
commentary on the diff: https://reviews.llvm.org/D18762.  Given that, I will
plan on proposing a series of diffs and would like to recruit some people who
are interested in the change to help review those changes.

I expect to stage as follows:


1.     Rewrite base algorithm to introduce data structures needed to hold extra
information (no functional change)

2.     Rewrite base algorithm to allow removing of control flow (under option,
off by default). This variant will not be correct in the general case.

3.     Code to rewrite the control flow graph and remove dead basic blocks

4.     Identify Phi nodes with non-instruction reaching definitions and keep the
associated source block live. Identify Phi nodes with multiple-live values from
dead blocks

5.     Remove unreachable code discovered by post-order traversal to avoid.
 (code is functionally correct at this point)

6.     Use post-order traversal to identify loop bottoms. By default this will
be kept live but include switch to allow loops to be removed.

7.     Improve handling of live values out of dead regions

Please respond if you are willing to help or have suggestions on staging or
approach.

Thanks
David
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160802/4feee33f/attachment.html>

You should not expect pretty much any perf uplifts from any DCE, ever.
If it does, it's mostly luck (better cache behavior, etc).

You should expect size improvements ;)


On Mon, Aug 1, 2016 at 10:51 PM, Das, Dibyendu via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> What kind of perf. uplifts are expected and in what benchmarks/apps ?
>
>
>
> *From:* llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] *On Behalf Of
*David
> Callahan via llvm-dev
> *Sent:* Monday, August 01, 2016 11:15 PM
> *To:* LLVM Dev Mailing list <llvm-dev at lists.llvm.org>
> *Cc:* Nadav Rotem <nrotem at fb.com>
> *Subject:* [llvm-dev] [LLVM] New Dead Code Elimination
>
>
>
> I have a rewrite of the aggressive dead code elimination pass which
> handles control flow and allows may-be-infinite loops to be removed under
> optional flag. Chandler suggested rather than a large change a series of
> small changes and, while that may not get us to small changes easily, there
> has been no further commentary on the diff:
> https://reviews.llvm.org/D18762.  Given that, I will plan on proposing a
> series of diffs and would like to recruit some people who are interested in
> the change to help review those changes.
>
>
>
> I expect to stage as follows:
>
>
>
> 1.     Rewrite base algorithm to introduce data structures needed to hold
> extra information (no functional change)
>
> 2.     Rewrite base algorithm to allow removing of control flow (under
> option, off by default). This variant will not be correct in the general
> case.
>
> 3.     Code to rewrite the control flow graph and remove dead basic blocks
>
> 4.     Identify Phi nodes with non-instruction reaching definitions and
> keep the associated source block live. Identify Phi nodes with
> multiple-live values from dead blocks
>
> 5.     Remove unreachable code discovered by post-order traversal to
> avoid.
>
>  (code is functionally correct at this point)
>
> 6.     Use post-order traversal to identify loop bottoms. By default this
> will be kept live but include switch to allow loops to be removed.
>
> 7.     Improve handling of live values out of dead regions
>
>
>
> Please respond if you are willing to help or have suggestions on staging
> or approach.
>
>
>
> 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/20160802/33719c22/attachment.html>