<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="http://www.cs.princeton.edu/~rwerneck/dominators/">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><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">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><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><p dir="ltr">What do you have in mind here?</p><div class="HOEnZb"><div class="h5">
<br><div class="gmail_quote"><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><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><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><div class="gmail_extra"><br><div class="gmail_quote">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><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">[+Danny]<br>
<div><div><br>
----- Original Message -----<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>+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="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" 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="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" 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></blockquote></div><br></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="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>
</div></div></blockquote></div><br></div>