<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:0 0 0 .8ex;border-left:1px #ccc solid;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>
<span class=""><br></span></blockquote><div><br></div><div>Ok -- I thought the example is showing indirect calls across {X, Y} and {S, T}, and call graph builder magically discovered the ref edges between them.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">
>> 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></blockquote><div><br></div><div>yes, ff RefSCC has such special edge to 'unknown' node to model icall, there is no problem, or the analysis still has to walk through the IR? </div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<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></blockquote><div><br></div><div>There is a disadvantage of setting bit on SCC compared with special call edge -- the later can be per-callsite, so elimination of the last such edge automatically makes caller 'clean'. With the special bit, it is not so easy to get rid of it.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<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>you mean 'correctness' not 'precision'? </div><div><br></div><div>thanks,</div><div><br></div><div>David</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="HOEnZb"><font color="#888888">
-- Sanjoy<br>
</font></span></blockquote></div><br></div></div>