<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 David &
Bekket,</font></p>
<p><font face="Courier New, Courier, monospace">Thanks your replies
:) <br>
</font></p>
<p><font 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>program analysis and dynamic
profiling</b> to find such functions.</font></p>
<p><font face="Courier New, Courier, monospace">Three possible
approaches are possible:</font></p>
<ol>
<li><font 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><font face="Courier New, Courier, monospace">Since it is a
JIT, with the help of dynamic profiling we can find frequently
executed functions and <b>re</b>compile them with more
aggressive optimization in compile thread.</font></li>
<li><font 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>compile
it with aggressive optimization. </b>[PGOs are app
dependent] <br>
</font></li>
</ol>
<p><font 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>
</font></p>
<p><font face="Courier New, Courier, monospace">I have considered
CFG as a higher level program representation, I maybe wrong
here.<br>
</font></p>
<p><font face="Courier New, Courier, monospace">For example: <br>
</font></p>
<p><font face="Courier New, Courier, monospace"><code>void f2() {} <br>
</code></font></p>
<p><font face="Courier New, Courier, monospace"><code>void f3() {}</code></font></p>
<p><font face="Courier New, Courier, monospace"><code>void z(){</code></font></p>
<p><font face="Courier New, Courier, monospace"><code>if(/some
condition/) <br>
</code></font></p>
<p><font face="Courier New, Courier, monospace"><code> f2();f3();</code></font></p>
<p><font face="Courier New, Courier, monospace"><code>else <br>
</code></font></p>
<p><font face="Courier New, Courier, monospace"><code>fn();</code></font></p>
<p><font face="Courier New, Courier, monospace"><code>}<br>
</code></font></p>
<p><font 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>
</font></p>
<p>Challenges: <br>
</p>
<ol>
<li> To incorporate speculation in ORC v2.</li>
<li> Making speculative decisions faster, hence I decide to use
simple heuristics. </li>
</ol>
<p>If you need more information / or feeling I'm missing something,
Please leave a reply :) <br>
</p>
<div class="moz-cite-prefix">On 29/03/19 12:27 AM, David Greene
wrote:<br>
</div>
<blockquote type="cite" cite="mid:nngva026d46.fsf@cray.com">
<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"><llvm-dev@lists.llvm.org></a> writes:
</pre>
<blockquote type="cite">
<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"><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>
</body>
</html>