<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p><font face="Courier New, Courier, monospace">Hi Bekket,</font>
Please see the comment inline..<br>
</p>
<div class="moz-cite-prefix">On 29/03/19 3:58 AM, Bekket McClane
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:B6E3D1CA-9958-47B2-87B7-87A4688C0923@gmail.com">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
Hi,
<div class="">
<div><br class="">
</div>
<div>David:</div>
<div>Good point, it will be interesting to see speculative
compilation in this context applying on devirtualization, with
high level (type) information if applicable.</div>
<div><br class="">
<blockquote type="cite" class="">
<div class="">On Mar 28, 2019, at 2:35 PM, preejackie <<a
href="mailto:praveenvelliengiri@gmail.com" class=""
moz-do-not-send="true">praveenvelliengiri@gmail.com</a>>
wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<meta http-equiv="Content-Type" content="text/html;
charset=UTF-8" class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
<p class=""><font class="" face="Courier New, Courier,
monospace">Hi David & Bekket,</font></p>
<p class=""><font class="" face="Courier New, Courier,
monospace">Thanks your replies :) </font></p>
</div>
</div>
</blockquote>
<blockquote type="cite" class="">
<div class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
<p class=""><font class="" face="Courier New, Courier,
monospace"> </font></p>
<p class=""><font class="" face="Courier New, Courier,
monospace">David, Indent here is: ORC v2 JIT APIs
has initial(basic) support for concurrent
compilation in background compile threads. This
means we can speculatively compile functions before
they are even referenced by the clients. In future,
if the client refer some function and if that
function is already compiled speculatively we can
just return the address of function, if this is
correctly done we can reduce the JIT compilation
latencies. IMO, the possible candidates to
speculate(functions) are those which will be
executed next. We can use <b class="">program
analysis and dynamic profiling</b> to find such
functions.</font></p>
<p class=""><font class="" face="Courier New, Courier,
monospace">Three possible approaches are possible:</font></p>
<ol class="">
<li class=""><font class="" face="Courier New,
Courier, monospace">Based, on analysis from call
graphs select functions to compile speculatively
with less aggressive optimization flags in
background dedicated compiler threads.</font></li>
<li class=""><font class="" face="Courier New,
Courier, monospace">Since it is a JIT, with the
help of dynamic profiling we can find frequently
executed functions and <b class="">re</b>compile
them with more aggressive optimization in compile
thread.</font></li>
<li class=""><font class="" face="Courier New,
Courier, monospace">With Profile-guide
optimization results of previous executions, we
can find function that are likely to compile next
then <b class="">compile it with aggressive
optimization. </b>[PGOs are app dependent] <br
class="">
</font></li>
</ol>
<p class=""><font class="" face="Courier New, Courier,
monospace">for cases 1,2: profile guide optimization
results are not used. I hope these techniques
collectively improve program execution time in
long-time. Of course, program-based prediction is
not equal to the accuracy of profile-based
prediction, but in JIT it is useful to first compile
function speculatively by using multiple threads.<br
class="">
</font></p>
</div>
</div>
</blockquote>
I’m a little bit lost, from what I’m understanding, you’re
arguing that with the profiling data (collected from runtime),
we can make more precise prediction about callee candidates
executed next. But in the baseline(i.e. first-time execution)
stage, these profile data doesn’t exist, thus you want improve
the prediction at that stage with the help of some static
analysis.</div>
<div>Am I understanding correctly?<br class="">
</div>
</div>
</blockquote>
<p>Not exactly, My thought is to make speculative compilation
available for both non-PGO & PGO cases. <br>
</p>
<p>
|--------------------------------------------------------------------------------------------|<br>
</p>
<p> | llvm-IR ----> ORC ----> Codegen + link ---> raw
executable bits| -----> Non-PGO case</p>
<p> ORC uses program analysis information to guess functions to <b>compile
</b>next. <br>
</p>
<p>
|--------------------------------------------------------------------------------------------|<br>
</p>
<p> <br>
</p>
<p>|--------------------------------------------------------------------------------------------------|<br>
</p>
<p>| llvm-IR -----> ORC ----> Codegen + link -----> raw
executable bits | ----> PGO case.</p>
<p> ORC uses the profile data to find functions to compile next +
optimize hot functions aggressively.<br>
</p>
<p>|--------------------------------------------------------------------------------------------------|
<br>
</p>
<p>By this, we can't force JIT clients to use PGO, to get benefits
of speculative compilation.<br>
</p>
<blockquote type="cite"
cite="mid:B6E3D1CA-9958-47B2-87B7-87A4688C0923@gmail.com">
<div class="">
<div>
<blockquote type="cite" class="">
<div class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
<p class=""><font class="" face="Courier New, Courier,
monospace"> </font></p>
<p class=""><font class="" face="Courier New, Courier,
monospace">I have considered CFG as a higher level
program representation, I maybe wrong here.<br
class="">
</font></p>
<p class=""><font class="" face="Courier New, Courier,
monospace">For example: <br class="">
</font></p>
<p class=""><font class="" face="Courier New, Courier,
monospace"><code class="">void f2() {} <br class="">
</code></font></p>
<p class=""><font class="" face="Courier New, Courier,
monospace"><code class="">void f3() {}</code></font></p>
<p class=""><font class="" face="Courier New, Courier,
monospace"><code class="">void z(){</code></font></p>
<p class=""><font class="" face="Courier New, Courier,
monospace"><code class="">if(/some condition/) <br
class="">
</code></font></p>
<p class=""><font class="" face="Courier New, Courier,
monospace"><code class=""> f2();f3();</code></font></p>
<p class=""><font class="" face="Courier New, Courier,
monospace"><code class="">else <br class="">
</code></font></p>
<p class=""><font class="" face="Courier New, Courier,
monospace"><code class="">fn();</code></font></p>
<p class=""><font class="" face="Courier New, Courier,
monospace"><code class="">}<br class="">
</code></font></p>
<p class=""><font class="" face="Courier New, Courier,
monospace">Follow the control flow of z and compute
probability that one of the paths[entry to exit]
within the z that lead to a call f2, if the call to
f2 occurs in many paths, then the probability that
it will execute next is high. It will require some
control flow analysis. <br class="">
</font></p>
</div>
</div>
</blockquote>
Following my comment above, I think you have some
misunderstandings on the power of static analysis in LLVM:
LLVM of course can eliminate some trivial control flow
structure like </div>
<div>if(true) {</div>
<div> // do something</div>
<div>}</div>
<div>Or</div>
<div>if(1 + 2 < 6)</div>
<div>For these cases, you don’t even need to analyze the
probability of those branches, cause LLVM will just eliminate
and optimize the entire control structures.</div>
<div><br class="">
</div>
<div>But other than that, it’s really hard for LLVM to evaluate
the probability of certain branches statically without help
from (dynamic) data like profiling data or certain
programmer’s annotations like __builtin_expect. </div>
<div>The closest analysis I can come up with are probably
LazyValueInfo and ScalarEvolution. You can see if they fit
your need.</div>
<div><br class="">
</div>
</div>
</blockquote>
<p>Are you suggesting that static analysis is much inferior than
profiling in finding "next executing function" ? I'm stuck at
deciding which one to prefer & implement during this summer
project, Could you please help me? <br>
</p>
<p>Also if I choose to do PGO stuff with ORC, Can I able to use most
of PGO code available for AOT with the JIT. Is there any downsides
to it?<br>
</p>
<p><br>
</p>
<blockquote type="cite"
cite="mid:B6E3D1CA-9958-47B2-87B7-87A4688C0923@gmail.com">
<div class="">
<div>Best,</div>
<div>Bekket </div>
<div>
<blockquote type="cite" class="">
<div class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
<p class=""><font class="" face="Courier New, Courier,
monospace"> </font></p>
<p class="">Challenges: <br class="">
</p>
<ol class="">
<li class=""> To incorporate speculation in ORC v2.</li>
<li class=""> Making speculative decisions faster,
hence I decide to use simple heuristics. </li>
</ol>
<p class="">If you need more information / or feeling
I'm missing something, Please leave a reply :) <br
class="">
</p>
<div class="moz-cite-prefix">On 29/03/19 12:27 AM, David
Greene wrote:<br class="">
</div>
<blockquote type="cite"
cite="mid:nngva026d46.fsf@cray.com" class="">
<pre class="moz-quote-pre" wrap="">Devirtualization is an example of predicting calls and is much more
easily done on a higher-level representation. It is simply easier to
reason about certain things given information that is lost during
translation to LLVM IR. The MLIR project makes similar arguments.
It would be helpful to know what's being attempted here. I'm not sure
what the (hardware?) branch predictor has to do with making decisions
based compile-time information, unless some kind of PGO is being used.
I could imagine something that takes branch probabilities and guesses
the most likely path through a function, thus predicting certain calls
will happen over others.
-David
Bekket McClane via llvm-dev <a class="moz-txt-link-rfc2396E" href="mailto:llvm-dev@lists.llvm.org" moz-do-not-send="true"><llvm-dev@lists.llvm.org></a> writes:
</pre>
<blockquote type="cite" class="">
<pre class="moz-quote-pre" wrap="">Hi PreeJackie,
I still have difficulties associating ‘higher level program analysis’ with the possible candidate functions that will be executed next.
Call graph will definitely be your tools(and actually it’s usually not considered ‘high level’), and function attributes might help. But AFAIC, there is little ‘high level’
language constructions that can help us determinate the possible functions executed next.
Maybe you can give us some examples?
Best,
Bekket
On Mar 27, 2019, at 8:55 PM, preejackie via llvm-dev <a class="moz-txt-link-rfc2396E" href="mailto:llvm-dev@lists.llvm.org" moz-do-not-send="true"><llvm-dev@lists.llvm.org></a> wrote:
Hi all,
I'm looking for some program analysis techniques which help me to find potential functions to execute next, from the current executing function. I want to
decision based on compile time information. I consider LLVM IR is too low-level to make such analysis. So, I using call graph representation of module. I
figured out the probability of function which execute next based on the branch predictor, Call instruction distance from the entry of function. I believe that
many attributes can be derived from higher level program representation. Is there any similar work done like this? LLVM already support analysis for this?
</pre>
</blockquote>
</blockquote>
<pre class="moz-signature" cols="72">--
Have a great day!
PreeJackie</pre>
</div>
</div>
</blockquote>
</div>
<br class="">
</div>
</blockquote>
<pre class="moz-signature" cols="72">--
Have a great day!
PreeJackie</pre>
</body>
</html>