<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Mar 25, 2016 at 3:43 PM, Mehdi Amini <span dir="ltr"><<a href="mailto:mehdi.amini@apple.com" target="_blank">mehdi.amini@apple.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"><br><div><span class=""><blockquote type="cite"><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="http://www.cs.princeton.edu/~rwerneck/dominators/" 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></span><div>Are we talking about the basic-blocks edges only? </div></div></div></blockquote><div><br></div><div>Yes. Only the successor and predecessors.</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 style="word-wrap:break-word"><div><div>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></div></blockquote><div><br></div><div>The way "edges" work right now is that it walks the use/users lists.  In the case of predecessors, it walks the user list of the bb, and sees which ones are terminator instructions, and then hands you the parent bb's of those.</div><div><br></div><div>In the case of successor, the operand array stores it, but it requires some indirect loads per successor.</div><div>  </div><div><br></div><div>The advantage to this scheme is that if you set the operand of the terminator, you've updated the edge. It requires no other work.</div><div>Chandler was strongly against edge cuts not being super-fast constant time[1] </div><div>If you move to edge arrays, it now requires finding and updating the terminators, unless you keep them both as use lists somehow (which are still about 1.5-2x as slow as straight arrays for dominators purposes), or always have the appropriate terminator around.</div><div><br></div><div>In any case,  it's really hard to have a case where you don't have to update some stuff on edge redirection, even if you can store stuff to do it in constant time.</div><div><br></div><div>For example,  you would have to keep an array of (bb, index in succ/pred array) and (terminators, operandno) or something similar to give you constant time cutting (because you have to update both ends, so you need to know where everything is both directions from whatever list you are looking at)</div><div><br></div><div>if you can deal with linear time this is much easier.</div><div><br></div><div><br></div><div>[1]I don't think it matters as much as he does. They don't happen that often, and even in the case of bugpoint, most blocks do not have a ton of edges, so it won't slow much down for bugpointing real programs.  The significantly better cache behavior may even make up for it in practice.</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"><div><span class=""><font color="#888888"><div><br></div><div>-- </div><div>Mehdi</div></font></span><div><div class="h5"><div><br></div><div><br></div><br><blockquote type="cite"><div><div dir="ltr"><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:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><p dir="ltr">What do you have in mind here?</p><div><div>
<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:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);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:0px 0px 0px 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>
----- 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>
_______________________________________________<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" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br></div></blockquote></div></div></div><br></div></blockquote></div><br></div></div>