<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Mar 25, 2016, at 3:30 PM, Daniel Berlin via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class="">Make most things update post-dominance info and preserve it.</div><div class=""><br class=""></div><div class="">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 class=""><br class=""></div><div class="">(Note that if you look at generic dominance code, like <a href="http://www.cs.princeton.edu/~rwerneck/dominators/" class="">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 class=""><br class=""></div><div class="">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 class=""></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 class=""></div><div>-- </div><div>Mehdi</div><div><br class=""></div><div><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On Thu, Mar 24, 2016 at 11:56 PM, Eric Christopher <span dir="ltr" class=""><<a href="mailto:echristo@gmail.com" target="_blank" class="">echristo@gmail.com</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><p dir="ltr" class="">What do you have in mind here?</p><div class="HOEnZb"><div class="h5">
<br class=""><div class="gmail_quote"><div dir="ltr" class="">On Thu, Mar 24, 2016, 7:28 PM Daniel Berlin via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="">Yeah, that was gonna be my question.<br class="">If so, my view is we should just bite the bullet and start threading post dominance through the compiler.<div class="">(assuming anyone wants to help. I'm tackling the memoryssa updating stuff with george ATM).<br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On Thu, Mar 24, 2016 at 7:04 PM, Hal Finkel <span dir="ltr" class=""><<a href="mailto:hfinkel@anl.gov" target="_blank" class="">hfinkel@anl.gov</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">[+Danny]<br class="">
<div class=""><div class=""><br class="">
----- Original Message -----<br class="">
> From: "Justin Bogner via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>><br class="">
> To: "David Callahan via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>><br class="">
> Sent: Wednesday, March 23, 2016 12:36:50 PM<br class="">
> Subject: Re: [llvm-dev] RFC: New aggressive dead code elimination pass<br class="">
><br class="">
> David Callahan via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>> writes:<br class="">
> > Hi,<br class="">
> ><br class="">
> > I have a new variant of Aggressive Dead Code Elimination that also<br class="">
> > removes dead branching. It is designed to minimize the cost of<br class="">
> > control-dependence analysis in the common case where almost the<br class="">
> > entire<br class="">
> > program is live. It also can optionally remove dead but<br class="">
> > may-be-infinite loops.<br class="">
> ><br class="">
> > When enabled for –O3 (replacing current ADCE pass) and removing<br class="">
> > loops,<br class="">
> > impact on SPEC2006 is in the noise but it impacts internal<br class="">
> > benchmarks<br class="">
> > suites 1-2% with a comparable increase in compile time. My<br class="">
> > expectation would be to enable –O3 only until we have some<br class="">
> > experience<br class="">
> > with cost but I suspect it should be fine –O2.<br class="">
><br class="">
> Just to clarify, you're saying that both runtime and compile time<br class="">
> impact<br class="">
> were in the noise on SPEC, right?<br class="">
><br class="">
> > What information would the community like to see about such a<br class="">
> > change<br class="">
> > before I put up a diff and (including tweaks to unit tests).<br class="">
><br class="">
> I'm not sure that there's much to discuss in the abstract - it's much<br class="">
> easier to evaluate this kind of thing when there's a patch to refer<br class="">
> to.<br class="">
> Presumably people will want to try the patch out on their own<br class="">
> internal<br class="">
> benchmarks as well.<br class="">
<br class="">
</div></div>+1<br class="">
<br class="">
Does it use post-dominance information?<br class="">
<br class="">
-Hal<br class="">
<div class=""><div class=""><br class="">
><br class="">
> > Thanks<br class="">
> > david<br class="">
> > _______________________________________________<br class="">
> > LLVM Developers mailing list<br class="">
> > <a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class="">
> > <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class="">
> _______________________________________________<br class="">
> LLVM Developers mailing list<br class="">
> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class="">
> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class="">
><br class="">
<br class="">
</div></div><span class=""><font color="#888888" class="">--<br class="">
Hal Finkel<br class="">
Assistant Computational Scientist<br class="">
Leadership Computing Facility<br class="">
Argonne National Laboratory<br class="">
</font></span></blockquote></div><br class=""></div>
_______________________________________________<br class="">
LLVM Developers mailing list<br class="">
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class="">
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class="">
</blockquote></div>
</div></div></blockquote></div><br class=""></div>
_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></blockquote></div><br class=""></body></html>