Bekket McClane via llvm-dev
2019-Mar-28 22:28 UTC
[llvm-dev] Higher level program analysis
Hi, David: Good point, it will be interesting to see speculative compilation in this context applying on devirtualization, with high level (type) information if applicable.> On Mar 28, 2019, at 2:35 PM, preejackie <praveenvelliengiri at gmail.com> wrote: > > 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: > > Based, on analysis from call graphs select functions to compile speculatively with less aggressive optimization flags in background dedicated compiler threads. > Since it is a JIT, with the help of dynamic profiling we can find frequently executed functions and recompile them with more aggressive optimization in compile thread. > 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’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. Am I understanding correctly?> 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. >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 if(true) { // do something } Or if(1 + 2 < 6) 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. 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. The closest analysis I can come up with are probably LazyValueInfo and ScalarEvolution. You can see if they fit your need. Best, Bekket> Challenges: > > To incorporate speculation in ORC v2. > 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> <mailto: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> <mailto: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/20190328/a7be4eb9/attachment.html>
Hi Bekket, Please see the comment inline.. On 29/03/19 3:58 AM, Bekket McClane wrote:> Hi, > > David: > Good point, it will be interesting to see speculative compilation in > this context applying on devirtualization, with high level (type) > information if applicable. > >> On Mar 28, 2019, at 2:35 PM, preejackie <praveenvelliengiri at gmail.com >> <mailto:praveenvelliengiri at gmail.com>> wrote: >> >> 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’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. > Am I understanding correctly?Not exactly, My thought is to make speculative compilation available for both non-PGO & PGO cases. |--------------------------------------------------------------------------------------------| | llvm-IR ----> ORC ----> Codegen + link ---> raw executable bits| -----> Non-PGO case ORC uses program analysis information to guess functions to *compile *next. |--------------------------------------------------------------------------------------------| |--------------------------------------------------------------------------------------------------| | llvm-IR -----> ORC ----> Codegen + link -----> raw executable bits | ----> PGO case. ORC uses the profile data to find functions to compile next + optimize hot functions aggressively. |--------------------------------------------------------------------------------------------------| By this, we can't force JIT clients to use PGO, to get benefits of speculative compilation.>> 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. >> > 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 > if(true) { > // do something > } > Or > if(1 + 2 < 6) > 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. > > 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. > The closest analysis I can come up with are probably LazyValueInfo and > ScalarEvolution. You can see if they fit your need. >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? 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?> Best, > Bekket >> >> 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 >-- Have a great day! PreeJackie -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190329/a55f486d/attachment.html>
preejackie via llvm-dev <llvm-dev at lists.llvm.org> writes:> 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?I suspect this is highly code-dependent. For example, it's probably feasible to use static analysis to determine error paths, at least for fairly well-behaved programs. A whole-program analysis might be able to better determine such paths but that's likely too heavyweight for a JIT. AOT could do it and use metadata to guide the JIT. On some codes, paths within a loop may be fairly evenly distributed over iterations while for others, execution may be highly biased toward a few. This is probably going to be the most difficult thing to analyze statically without a lot of context and even then it may be determined by runtime user input and therefore unknowable statically.> 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?I'm sorry I can't really comment on that as I don't have much experience with it. From what little I've looked at the instrumentation code, it seems fairly standard, in that it tries to limit the profiling overhead using minimum spanning tree techniques. Whether that is too heavyweight for a JIT I can't really say. I suspect it would potentially severely impact performance for some codes. Of course, once a path has been determined to be hot you'd probably want to remove the instrumentation. -David