Daniel Berlin via llvm-dev
2016-Aug-02 15:55 UTC
[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/33719c22/attachment.html>
Das, Dibyendu via llvm-dev
2016-Aug-02 16:33 UTC
[llvm-dev] [LLVM] New Dead Code Elimination
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. 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 ). Anyway, the advanced analyses for DCE may not apply to this RFC. So we may not see any runtime benefits. 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<mailto: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<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<mailto:llvm-dev at lists.llvm.org>> Cc: Nadav Rotem <nrotem at fb.com<mailto: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<mailto: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/fd462817/attachment.html>
Daniel Berlin via llvm-dev
2016-Aug-02 16:35 UTC
[llvm-dev] [LLVM] New Dead Code Elimination
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>