<div dir="ltr"><br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:#000000">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>More clarification needed :) What do you mean by 'invariant need only apply to the former'?</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:#000000"> 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>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><br></div><div>David</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:#000000"><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 name="x"></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></font></span></div></div></blockquote></div><br></div></div>