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

Tue Aug 2 09:35:43 PDT 2016

On Tue, Aug 2, 2016 at 9:33 AM, Das, Dibyendu <Dibyendu.Das at amd.com> wrote:

> I don’t think its true for all kinds of dead code elimination
>
because there may be instructions which do execute but can be proven to be
> redundant/dead.
>

This definition of dead code covers all redundant code (IE subsumes
redundancy elimination of literally all forms).
I'd agree that under this definition, you can improve runtime.

>
> Lets say you do a bit-width analysis ( something along the lines of
> http://www.cs.cmu.edu/~seth/papers/budiu-tr00.pdf ). You may be able to
> remove some instructions and get runtime benefit ( which may have nothing
> to do with IC miss behavior because these were instructions that were
> getting executed ).
>

I personally would not class this as dead code elimination :)

>
>
> Anyway, the advanced analyses for DCE may not apply to this RFC. So we may
> not see any runtime benefits.
>

It would not apply in all versions of this patch so far, so unless David
has other tricks up his sleeve :)

>
>
> *From:* Daniel Berlin [mailto:dberlin at dberlin.org]
> *Sent:* Tuesday, August 02, 2016 9:26 PM
> *To:* Das, Dibyendu <Dibyendu.Das at amd.com>
> *Cc:* David Callahan <dcallahan at fb.com>; llvm-dev at lists.llvm.org; Nadav
> Rotem <nrotem at fb.com>
> *Subject:* Re: [llvm-dev] [LLVM] New Dead Code Elimination
>
>
>
> 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/5b33e25a/attachment.html>