<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jun 16, 2016 at 10:48 PM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.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">Hi David,<br>
<span class=""><br>
On Thu, Jun 16, 2016 at 9:53 PM, Xinliang David Li <<a href="mailto:davidxl@google.com">davidxl@google.com</a>> wrote:<br>
>> I think the workflow in the above will (roughly) be:<br>
>><br>
>> Visit the RefSCC {X,Y,S,T}<br>
><br>
><br>
> Are we sure RefSCC has ref edges between {X, Y} and {S, T} in this case? I<br>
> may miss the code handling it.<br>
<br>
</span>I was going by the diagram -- the diagram explicitly has ref edges<br>
between {X,Y} and {S,T}.<br></blockquote><div><br></div><div>To clarify: initially the indirect calls are represented by a call edge to a dummy "unknown" node something like: <a href="http://reviews.llvm.org/F2078426">http://reviews.llvm.org/F2078426</a></div><div>These call edges to "unknown" are what force the conservative analysis.</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">
<span class=""><br>
>> Visit the SCC {X,Y} // arbitrary<br>
>> Optimize({X,Y})<br>
>> // Now there's an edge to {S,T}, invalidate<br>
>> // the analyses cached for {X,Y} and visit {S,T}<br>
><br>
><br>
> I am not sure if this makes sense. If dynamically, the call edge from {X,<br>
> Y} to {S, T} does exist, but not discovered by the analysis, then the cached<br>
> {X, Y} will still be invalid, but who is going to invalidate it?<br>
<br>
</span>I cannot answer this with authority, since I'm not the one working on<br>
the callgraph, but I'll jot down what I think is the case:<br>
<br>
Whatever you analyze on {X,Y} will have to be conservative around<br>
indirect calls that haven't yet been devirtualized. Say you're trying<br>
to prove that an SCC is readnone. With the SCC iteration order,<br>
you'll have to do:<br>
<br>
for every call site in CurrentSCC<br>
if the call is indirect, then ReadWrite, break out of loop<br>
if the call is to SSC X, then<br>
CurrentSCC.MemoryEffect.unionWith(X.MemoryEffect) // L1<br>
<br>
To avoid re-walking the call-sites in common cases like the above,<br>
we'll have to add a "HasNonAnalyzedCalls" bit on SCCs that we'll set<br>
when building the call graph (Chandler had promised this a few socials<br>
ago). That would let us directly walk the outgoing call edges (the<br>
bit would be the moral equivalent of having a call edge to<br>
"external").<br>
<br>
The invariant provided by the bottom up SCC iteration order, as I<br>
understand it, assures us that in line L1, X.MemoryEffect is as<br>
precise as it can be. When we analyze a call site and the call target<br>
is in a ReadOnly SCC, we are assured that the call target SCC could<br>
not have been proved ReadNone -- we've already tried our best. So in<br>
a way the bottom up order gives us precision, not correctness.<br></blockquote><div><br></div><div>To put this another way, if we were to use a cached SCC visitation order, then after visiting all cached SCC's we may not have incorporated all information due to devirtualized or deleted calls. We would need to recompute SCC's and do another cached visitation in order to benefit fully from the information. If multiple devirtualizations are needed to fully simplify, then multiple visitations are needed to fully propagate this information.</div><div><br></div><div>With dynamic updates to the SCC structure, we can get increased precision from a single visitation and more effective bottom-up propagation.</div><div><br></div><div>-- Sean Silva</div><div><br></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">
<span class=""><font color="#888888"><br>
-- Sanjoy<br>
</font></span></blockquote></div><br></div></div>