<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jun 20, 2016 at 1:50 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"><span class="">Hi David,<br>
<br>
Xinliang David Li wrote:<br></span>
> [snip]<span class=""><br>
><br>
> However, in real applications, what I see is the following pattern (for<br>
> instances LLVM's Pass )<br>
><br>
> Caller() {<br>
>      Base *B =  Factory::create(...);<br>
>      Stash (B);  // store the object in some container to be retrieved later<br>
>    ...<br>
> }<br>
><br>
> SomeTask() {<br>
><br>
>     Base *B = findObject(...);<br>
>     B->vCall(); // do the work<br>
> }<br>
><br>
> Driver() {<br>
>       Caller();  // create objects ...<br>
>       SomeTask();<br>
> }<br>
><br>
> Set aside the fact that it is usually much harder to do<br>
> de-viritualization in this case,   assuming  the virtual call in<br>
> SomeTask can be devritualized. What we need is that the virtual<br>
> functions are processed before SomeTask node, but this is not guaranteed<br>
> unless we also model the call edge ordering imposed by control flow.<br>
<br></span>
I think the thesis here is you cannot devirtualize the call in<br>
`SomeTask` without also looking at `Caller` [0].  So the flow is:<br>
<br>
 - Optimize Caller, SomeTask independently as much as you want<br>
   * Caller -refs-> Factory::create which -refs-> the constructors<br>
     which -refs-> the various implementation of virtual functions<br>
     (based on my current understanding of how C++ vtables are<br>
     lowered); so these implementations should have been simplified by<br>
     the time we look at Caller.<br>
<br>
 - Then look at Driver.  Caller, SomeTask are all maximally<br>
   simplified.  We now (presumably) inline Caller and SomeTask,<br>
   devirtualize the B->vCall (as you said: theoretically possible, but<br>
   if findObject etc. are complex then practically maybe not), and now<br>
   inline the maximally simplified devirtualized call targets.</blockquote><div><br></div><div><br></div><div>I agree with the analysis. Practically speaking, this pretty much means the theoretical </div><div>opportunities won't be exposed until after lots of functions are inlined to the top level</div><div>functions which usually don't happen.  I have not seen some cases practically myself.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class=""><br>
<br>
> However, this is enforcing virtual methods to be processed before their<br>
> object's creators. Are there other simpler ways to achieve the effect<br>
> (if we have data to justify it)?<br>
<br></span>
Honestly: I'll have to think about it.  It is entirely possible that a<br>
(much?) simpler design will catch 99% (or even better) of the<br>
idiomatic cases, I just don't have a good mental model for what those<br>
cases are.<br>
<br>
At this point I'm waiting for Chandler to upload his patch so that we<br>
can have this discussion on the review thread. :)<br>
<br>
<br>
[0]: This breaks down when we allow "out of thin air"<br>
devirtualizations (I'm stealing this term from memory models, but I<br>
think it is appropriate here :) ), where you look at call site and<br>
"magically" (i.e. in a way not expressible in terms of "normal"<br>
optimizations like store forwarding, pre, gvn etc.) are able to<br>
devirtualize the call site.  We do this all the time in Java (we'll<br>
look at the type of the receiver object, look at the current class<br>
hierarchy and directly mandate that a certain call site has to have a<br>
certain target), but the RefSCC call graph does not allow for that.<br>
These kinds of out-of-thin-air devirtualizations will have to be<br>
modeled as ModulePass es, IIUC.</blockquote><div><br></div><div>yes, not all bottom passes have to be grouped with other SCC passes, nor are all IPA optimizations  suitable to be implemented as bottom-up passes.</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"><span class="HOEnZb"><font color="#888888"><br>
<br>
-- Sanjoy<br>
</font></span></blockquote></div><br></div></div>