[llvm-dev] Higher level program analysis

[preejackie via llvm-dev]

Hi David & Bekket,

Thanks your replies :)

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 
*program analysis and dynamic profiling* to find such functions.

Three possible approaches are possible:

 1. Based, on analysis from call graphs select functions to compile
    speculatively with less aggressive optimization flags in background
    dedicated compiler threads.
 2. Since it is a JIT, with the help of dynamic profiling we can find
    frequently executed functions and *re*compile them with more
    aggressive optimization in compile thread.
 3. With Profile-guide optimization results of previous executions, we
    can find function that are likely to compile next then *compile it
    with aggressive optimization. *[PGOs are app dependent]

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.

I have considered CFG as a higher level program representation, I maybe 
wrong here.

For example:

|void f2() {}
|

|void f3() {}|

|void  z(){|

|if(/some condition/)
|

| f2();f3();|

|else
|

|fn();|

|}
|

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.

Challenges:

 1.     To incorporate speculation in ORC v2.
 2.     Making speculative decisions faster, hence I decide to use
    simple heuristics.

If you need more information / or feeling I'm missing something, Please 
leave a reply :)

On 29/03/19 12:27 AM, David Greene wrote:
> 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 <llvm-dev at lists.llvm.org> writes:
>
>> 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 <llvm-dev at lists.llvm.org> 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?

-- 
Have a great day!
PreeJackie

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190329/5eca40bc/attachment.html>