<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Apr 4, 2016 at 11:49 AM, David Callahan <span dir="ltr"><<a href="mailto:dcallahan@fb.com" target="_blank">dcallahan@fb.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">



<div style="word-wrap:break-word;color:rgb(0,0,0);font-size:14px;font-family:Calibri,sans-serif">
<div><br>
</div>
<div>I may have not correctly used the IDFCalculator. I passed in the PostDominator tree and then changed the loop over successor blocks to also be able to iterate over predecessors. I did not see anything in the interface that would let that happen but perhaps
 I don’t understand the API so I modified it to explicitly iterate over predecessors under a flag.</div></div></blockquote><div><br></div><div>Sigh.</div><div>Yes, we fixed it to take domtreebase, so it can take the postdomtree, but nobody modified it to change the calculation.</div><div>I'll fix this in a second.</div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word;color:rgb(0,0,0);font-size:14px;font-family:Calibri,sans-serif">
<div><br>
</div>
<div> I don’t have comparisons but the problem I had was it would iterative over two much of the graph when we discovered a block was live.</div></div></blockquote><div><br></div><div>So, the calculation should only happen once, and IDFCalculator should only touch each block in the CFG a maximum of once, ever.</div><div><br class="">If it's doing more than that, it's broken for post-dom.</div><div>In the forwards, problem, i've never seen the *IDF* calculation to be noticeable, only the post-dom calculation.</div><div>This would not be completely surprising if it's broken, but it would definitely be broken :)<br></div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word;color:rgb(0,0,0);font-size:14px;font-family:Calibri,sans-serif"><div>We would need to limit the processing. Perhaps the LiveInBblocks vector could be used to filter.  I will take a look
 and see if that allows an appropriate subgraph to be analyzed. The cost of building the post-dominator tree however was also noticible, but as you observe, it would remove a chunk of code.</div></div></blockquote><div><br></div><div>Yeah, the post-dom cost problem is a problem we have elsewhere, and we should just fix that in one of a myriad of ways.</div><div>  <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word;color:rgb(0,0,0);font-size:14px;font-family:Calibri,sans-serif">
<div><br>
</div>
<div>—david</div>
<div><br>
</div>
<span>
<div style="font-family:Calibri;font-size:11pt;text-align:left;color:black;border-width:1pt medium medium;border-style:solid none none;padding:3pt 0in 0in;border-top-color:rgb(181,196,223)">
<span style="font-weight:bold">From: </span>Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>><br>
<span style="font-weight:bold">Date: </span>Monday, April 4, 2016 at 10:23 AM<br>
<span style="font-weight:bold">To: </span>David Callahan <<a href="mailto:dcallahan@fb.com" target="_blank">dcallahan@fb.com</a>><br>
<span style="font-weight:bold">Cc: </span>Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>>, Mehdi AMINI <<a href="mailto:mehdi.amini@apple.com" target="_blank">mehdi.amini@apple.com</a>>, LLVM Dev Mailing list <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><div><div class="h5"><br>
<span style="font-weight:bold">Subject: </span>Re: [llvm-dev] RFC: New aggressive dead code elimination pass<br>
</div></div></div><div><div class="h5">
<div><br>
</div>
<div>
<div>
<div dir="ltr">Some question:<br>
<br>
<div>1. IDFCalculator already allows reverse graphs, and gets used for that, so what did you have to change?  (this change was made in the past year, so i wonder if you were working on a branch or something).</div>
<div><br>
</div>
<div>2. What are the actual numbers here in terms of calculation of IDF vs your method.<br>
<br>
</div>
<div>IDF calculator is linear time (Well, depends on priority queue impl, but we could fix that too), so it should not be *that* bad.</div>
<div>We can make it calculate subgraphs like you do as well.</div>
<div><br>
</div>
<div>3. </div>
<div>While i think the way you compute CD for the subset is cool, it is a bunch of code, and probably hard for the vast majority of people to understand and debug :)</div>
<div><br>
</div>
<div>So if we can make IDF (assuming postdom) within a few percent of what you are doing, we should just do it, IMHO.</div>
<div><br>
</div>
<div>If not, well, it's the old "compile time cost vs actual runtime performance improvement vs any reduced maintenance burden/stuff we can make architecturally more sound" game.</div>
<div><br>
</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Mon, Apr 4, 2016 at 9:46 AM, David Callahan <span dir="ltr">
<<a href="mailto:dcallahan@fb.com" target="_blank">dcallahan@fb.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div style="word-wrap:break-word;color:rgb(0,0,0);font-size:14px;font-family:Calibri,sans-serif">
<div>Sorry to have disappeared.</div>
<div><br>
</div>
<div>No I do not use Post-dominators. I tried building post-dominatirs and changing iterated dominance frontier to allow a reverse graph but I found it was significant more expensive than solving a custom data flow problem over the “may be dead” subset of the
 CFG. I did separately rewrite the post-dominator code to fit the new pass manager but now there are no clients for it <a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__reviews.llvm.org_D17114&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=TjhLe787EuDZv6Mmmq-6oKIeTmBGSqKpOi0Bd4C18Uk&s=DLqmvY_Iw3UrR0wZKmvHFSycRNNCEIOCFcq8QF6W104&e=" target="_blank">http://reviews.llvm.org/D17114</a></div>
<div><br>
</div>
<div>—david</div>
<div><br>
</div>
<span>
<div style="font-family:Calibri;font-size:11pt;text-align:left;color:black;border-width:1pt medium medium;border-style:solid none none;padding:3pt 0in 0in;border-top-color:rgb(181,196,223)">
<span style="font-weight:bold">From: </span>llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org" target="_blank">llvm-dev-bounces@lists.llvm.org</a>> on behalf of LLVM Dev Mailing list <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
<span style="font-weight:bold">Reply-To: </span>Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>><br>
<span style="font-weight:bold">Date: </span>Friday, March 25, 2016 at 4:05 PM<br>
<span style="font-weight:bold">To: </span>Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>><span><br>
<span style="font-weight:bold">Cc: </span>LLVM Dev Mailing list <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
</span>
<div>
<div><span style="font-weight:bold">Subject: </span>Re: [llvm-dev] RFC: New aggressive dead code elimination pass<br>
</div>
</div>
</div>
<div>
<div>
<div><br>
</div>
<div>
<div>
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Fri, Mar 25, 2016 at 3:52 PM, Hal Finkel <span dir="ltr">
<<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div>
<div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)">
<br>
<hr>
<blockquote style="border-left-width:2px;border-left-style:solid;border-left-color:rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt">
<b>From: </b>"Mehdi Amini via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
<b>To: </b>"Daniel Berlin" <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>><br>
<b>Cc: </b>"David Callahan via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
<b>Sent: </b>Friday, March 25, 2016 5:43:12 PM<span><br>
<b>Subject: </b>Re: [llvm-dev] RFC: New aggressive dead code elimination pass<br>
<br>
<br>
</span><span>
<div>
<blockquote>
<div>On Mar 25, 2016, at 3:30 PM, Daniel Berlin via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:</div>
<br>
<div>
<div dir="ltr">
<div>Make most things update post-dominance info and preserve it.</div>
<div><br>
</div>
<div>Our other alternative to not take up too much time seems to be invasive surgery on how BB successors/predecessors work so they are a constant time array.  I say this because GCC recomputes post-dominators roughly 15-19 times per compilation, and can do
 it about 3-5x faster than we can. All profiling i've done basically says all our time is spent trying to get at successors and predecessors in dominance/post-dominance respectively, which takes basically no time in gcc, because the edge lists are an array.</div>
<div><br>
</div>
<div>(Note that if you look at generic dominance code, like <a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__www.cs.princeton.edu_-257Erwerneck_dominators_&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=09bq6lIe4oGqpw_lE_NAxpN_v13km9w1s-BagEV_Qb8&s=OUaq2P8-4iXMAqcItqLccu1gA856S_ElzN0I0tNjiFk&e=" target="_blank">http://www.cs.princeton.edu/~rwerneck/dominators/</a>,
 it's much faster than what we do on the same graphs. This is true even though we use the same algorithms .....)</div>
<div><br>
</div>
<div>Given it seems unlikely we are going to change the internal representation anytime soon (or at least i've not seen a proposal), updating post-dom seems the easier answer.</div>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>Are we talking about the basic-blocks edges only? I'm not sure changing the IR for the BBs would be a lot more work than preserving dominance analysis everywhere, or I am totally underestimating one / overestimating the other?</div>
<div><br>
</div>
</div>
</span></blockquote>
<br>
I'm also curious about this, especially because I'd naively think that:<br>
<br>
  representation change == a little thinking and (potentially) a lot of typing<br>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>It also may change space characteristics for programs with lots of edges.</div>
<div><br>
</div>
<div> </div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div>
<div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)">
  preserving post dom == a lot of thinking and a little typing<br>
<br>
and, thus, while updating the analysis might be the *right* thing to do, it is probably not easier (especially once you factor in the time taken to fix bugs where we subtly get it wrong). Maybe in the long run, we should do both?<br>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>If we try to keep constant time edge redirection, both are fairly complicated in terms of thinking :)</div>
<div> </div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div>
<div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)">
<br>
 -Hal<br>
<blockquote style="border-left-width:2px;border-left-style:solid;border-left-color:rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt">
<div>
<div></div>
<div>-- </div>
<div>Mehdi</div>
<div><br>
</div>
<div><br>
</div>
<br>
<blockquote>
<div>
<div dir="ltr">
<div><br>
</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote"><span>On Thu, Mar 24, 2016 at 11:56 PM, Eric Christopher
<span dir="ltr"><<a href="mailto:echristo@gmail.com" target="_blank">echristo@gmail.com</a>></span> wrote:<br>
</span>
<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<span>
<p dir="ltr">What do you have in mind here?</p>
</span>
<div>
<div><br>
<div class="gmail_quote"><span>
<div dir="ltr">On Thu, Mar 24, 2016, 7:28 PM Daniel Berlin via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br>
</div>
</span>
<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<span>
<div dir="ltr">Yeah, that was gonna be my question.<br>
If so, my view is we should just bite the bullet and start threading post dominance through the compiler.
<div>(assuming anyone wants to help. I'm tackling the memoryssa updating stuff with george ATM).<br>
</div>
<div><br>
</div>
<div><br>
</div>
</div>
</span>
<div class="gmail_extra"><br>
<div class="gmail_quote"><span>On Thu, Mar 24, 2016 at 7:04 PM, Hal Finkel <span dir="ltr">
<<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span> wrote:<br>
</span>
<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
[+Danny]<br>
<div>
<div><br>
<hr>
<div>
<div><br>
> From: "Justin Bogner via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
> To: "David Callahan via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
> Sent: Wednesday, March 23, 2016 12:36:50 PM<br>
> Subject: Re: [llvm-dev] RFC: New aggressive dead code elimination pass<br>
><br>
> David Callahan via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> writes:<br>
> > Hi,<br>
> ><br>
> > I have a new variant of Aggressive Dead Code Elimination that also<br>
> > removes dead branching. It is designed to minimize the cost of<br>
> > control-dependence analysis in the common case where almost the<br>
> > entire<br>
> > program is live. It also can optionally remove dead but<br>
> > may-be-infinite loops.<br>
> ><br>
> > When enabled for –O3 (replacing current ADCE pass) and removing<br>
> > loops,<br>
> > impact on SPEC2006 is in the noise but it impacts internal<br>
> > benchmarks<br>
> > suites 1-2% with a comparable increase in compile time.  My<br>
> > expectation would be to enable –O3 only until we have some<br>
> > experience<br>
> > with cost but I suspect it should be fine –O2.<br>
><br>
> Just to clarify, you're saying that both runtime and compile time<br>
> impact<br>
> were in the noise on SPEC, right?<br>
><br>
> > What information would the community like to see about such a<br>
> > change<br>
> > before I put up a diff and (including tweaks to unit tests).<br>
><br>
> I'm not sure that there's much to discuss in the abstract - it's much<br>
> easier to evaluate this kind of thing when there's a patch to refer<br>
> to.<br>
> Presumably people will want to try the patch out on their own<br>
> internal<br>
> benchmarks as well.<br>
<br>
</div>
</div>
</div>
</div>
<div>
<div>+1<br>
<br>
Does it use post-dominance information?<br>
<br>
 -Hal<br>
<div>
<div><br>
><br>
> > Thanks<br>
> > david<br>
> > _______________________________________________<br>
> > LLVM Developers mailing list<br>
> > <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
> > <a href="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=09bq6lIe4oGqpw_lE_NAxpN_v13km9w1s-BagEV_Qb8&s=cHLE-CvXoQpfSfgjfaPlgAD2ZL_0oH1rLGQWZ3AYeT4&e=" rel="noreferrer" target="_blank">
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
> <a href="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=09bq6lIe4oGqpw_lE_NAxpN_v13km9w1s-BagEV_Qb8&s=cHLE-CvXoQpfSfgjfaPlgAD2ZL_0oH1rLGQWZ3AYeT4&e=" rel="noreferrer" target="_blank">
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
><br>
<br>
</div>
</div>
<span><font color="#888888">--<br>
Hal Finkel<br>
Assistant Computational Scientist<br>
Leadership Computing Facility<br>
Argonne National Laboratory<br>
</font></span></div>
</div>
</blockquote>
</div>
<br>
</div>
<div>
<div>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="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=09bq6lIe4oGqpw_lE_NAxpN_v13km9w1s-BagEV_Qb8&s=cHLE-CvXoQpfSfgjfaPlgAD2ZL_0oH1rLGQWZ3AYeT4&e=" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
</div>
<br>
</div>
<div>
<div>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="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=09bq6lIe4oGqpw_lE_NAxpN_v13km9w1s-BagEV_Qb8&s=cHLE-CvXoQpfSfgjfaPlgAD2ZL_0oH1rLGQWZ3AYeT4&e=" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</div>
</div>
</div>
</blockquote>
</div>
<div>
<div><br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="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=09bq6lIe4oGqpw_lE_NAxpN_v13km9w1s-BagEV_Qb8&s=cHLE-CvXoQpfSfgjfaPlgAD2ZL_0oH1rLGQWZ3AYeT4&e=" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</div>
</div>
</blockquote>
<div>
<div><br>
<br>
<br>
-- <br>
<div><span name="x"></span>Hal Finkel<br>
Assistant Computational Scientist<br>
Leadership Computing Facility<br>
Argonne National Laboratory<span name="x"></span><br>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<br>
</div>
</div>
</div>
</div>
</div>
</div>
</span></div>
</blockquote>
</div>
<br>
</div>
</div>
</div>
</div></div></span>
</div>

</blockquote></div><br></div></div>