<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><br><hr id="zwchr"><blockquote style="border-left: 2px solid 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>"Xinliang David Li" <davidxl@google.com><br><b>To: </b>"Hal Finkel" <hfinkel@anl.gov><br><b>Cc: </b>"Sean Silva" <chisophugis@gmail.com>, "llvm-dev" <llvm-dev@lists.llvm.org><br><b>Sent: </b>Thursday, June 16, 2016 12:45:50 PM<br><b>Subject: </b>Re: [llvm-dev] Intended behavior of CGSCC pass manager.<br><br><div dir="ltr"><br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);">To clarify, we're trying to provide this invariant on the "ref" graph or on the graph with direct calls only? I think the invariant need only apply to the former</div></div></blockquote><div><br></div><div id="DWT10228">More clarification needed :) What do you mean by 'invariant need only apply to the former'?</div></div></div></div></blockquote>;)<br><br>I mean that we only need to visit children in the "ref" graph before their parents. Furthermore, I'm not even sure that we need an invariant on the SCC level, but rather on the functions themselves. Meaning that I don't think we need to specify an invariant that requires revisiting once we split an SCC (it might be useful to do so, but nothing comes to mind that would require that for correctness).<br><br><blockquote style="border-left: 2px solid 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 dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);"> if we're relying on this for correctness (i.e. an analysis must visit all callees before visiting the callers).<br></div></div></blockquote><div><br></div><div><br></div><div id="DWT10229">Not necessarily. Due to lost edges (from caller to indirect callees), a callee node may be visited later. The analysis will just have to punt when a special edge to 'external' node is seen.</div></div></div></div></blockquote>Yes, but my impression is that the "ref" graph has no lost edges (it is the conservative over-approximation). Is that right?<br><br> -Hal<br><blockquote style="border-left: 2px solid 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 dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div></div><div><br></div><div>David</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid 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: 2px solid 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 class="h5"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div></div><div>Consider the pipeline `cgscc(function(...simplifications that can devirtualize...),foo-cgscc-pass)`. A possible visitation is as follows:</div><div><br></div><div>1. Visit SCC {S,T} and run `function(...simplifications that can devirtualize...)`. This reveals the call edge T->Y.</div><div>2. We continue visiting SCC {S,T} and run foo-cgscc-pass on SCC {S,T}.</div><div>3. Visit SCC {X,Y} and run `function(...simplifications that can devirtualize...)`. This reveals the call edge X->S.</div><div>4. ??? what do we do now.</div><div>Alternative 4.a) Should we continue the visitation and call foo-cgscc-pass on "SCC" {X,Y}?</div><div>Alternative 4.b) Should foo-cgscc-pass now run on SCC {S,T,X,Y}?</div><div>Alternative 4.c) Should we restart the entire outer `cgscc(...)` visitation on SCC {S,T,X,Y}?</div><div><br></div><div>(Without a cap both 4.b and 4.c could become quadratic on a graph like <a href="http://reviews.llvm.org/F2073607" target="_blank">http://reviews.llvm.org/F2073607</a>)</div><div><br></div><div>-- Sean Silva</div><div> </div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><br></div><div>thanks,</div><div><br></div><div>David</div><span><div><br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div></div><div><div>Sean:~/pg/llvm % git grep 'public CallGraphSCCPass'</div><div>include/llvm/Transforms/IPO/InlinerPass.h:struct Inliner : public CallGraphSCCPass {</div><div>lib/Transforms/IPO/ArgumentPromotion.cpp: struct ArgPromotion : public CallGraphSCCPass {</div><div>lib/Transforms/IPO/FunctionAttrs.cpp:struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {</div><div>lib/Transforms/IPO/PruneEH.cpp: struct PruneEH : public CallGraphSCCPass {</div><div>lib/Analysis/CallGraphSCCPass.cpp: class PrintCallGraphPass : public CallGraphSCCPass {<br></div><div>tools/opt/PassPrinters.cpp:struct CallGraphSCCPassPrinter : public CallGraphSCCPass {</div><div><br></div></div><div>CGSCC passes seem to have been added in what is now SVN r8247 (~Aug 2003) <a href="http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20030825/006619.html" target="_blank">http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20030825/006619.html</a> (LLVM appears to have been in CVS at the time).</div><div><br></div><div>Chris, do you remember the motivation for doing the CGSCC visitation instead of a pure post-order function visitation like David is mentioning? (or was it just an oversight / hindsight-20-20 thing?) Do you think it would make sense to replace CGSCC visitation with post-order function visitation in the current LLVM?</div><span><font color="#888888"><div><br></div><div>-- Sean Silva</div></font></span><span><div> </div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span><font color="#888888"><div><br></div><div>David</div></font></span><span><div> <br></div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span><font color="#888888"><div></div><div>-- Sean Silva</div></font></span><span><div> </div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span><font color="#888888"><div><br></div><div>David</div></font></span><span><div><br></div><div> </div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div dir="ltr"><div></div><div><br></div><div>Sorry for the wall of text.</div><span><font color="#888888"><div><br></div>
<div><br></div><div>-- Sean Silva</div></font></span></div>
</blockquote></span></div><br></div></div>
</blockquote></span></div><br></div></div>
</blockquote></span></div><br></div></div>
</blockquote></span></div><br></div></div>
</blockquote></span></div><br></div></div>
</blockquote></div><br></div></div>
<br></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="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><span class="HOEnZb"><font color="#888888"><br></font></span></blockquote><span class="HOEnZb"><font color="#888888"><br><br><br>-- <br><div><span></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span></span><br></div></font></span></div></div></blockquote></div><br></div></div>
</blockquote><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></body></html>