preejackie via llvm-dev
2019-Mar-23 20:57 UTC
[llvm-dev] GSoC- Speculative compilation support in ORC v2 , looking for mentors!
Hi all, I would like to propose "Speculative compilation support in ORC v2 JIT API" for this year GSoC summer project. Project Description: Speculative compilation support. One of the selling points of the concurrent ORC APIs is that you can start compiling a function before you need it, in the hope that by the time that you do need it it is already compiled. However, if we just speculatively compile everything we're quickly going to overload our memory/CPU resources, which will be lousy for performance. What we really want to do is to take into account any information we have (from high level program representations, e.g. ASTs or CFGs, or from profiling data from previous executions) to try to guess what functions are worth speculatively compiling next. Idea is proposed by Lang Hames. Current Status of ORC v2: 1. ORC currently supports concurrent compilation and Lazy (on request compilation), trunk contains default new ORC JIT implementations as LLJIT, LLLazyJIT. 2. [WIP] Jit-linker a drop-in-replacement for RuntimeDyld atleast for MachO in ORC JIT. 3. Primitive code to handle speculative is in trunk. But it needs to refactored & designed to get generalized, simple APIs to support speculation. 4. Currently, no heuristics to support speculation in trunk. Proposed Solution: 1. New APIs in ORC v2 to support speculation compilation of LLVM bitcode. LLSpecJIT - subtype of LLJIT, default JIT with speculation support in trunk. 2. Heuristics to guide speculation - Currently, I’m going through some literature/research papers to find good basic heuristics. We can derive useful information from Control flow graphs, IR etc. So far I figured out that Region-based compilation is more appropriate for speculation. Since, unit of compilation (granularity) is key good dynamic compilation, region based compilation address that by forming frequently executed code as a region (unit), this can be basic block, function or group of functions. But since, LLVM JIT API needs interoperates with static compiler, unit of compilation here is a complete module. The plan in mind is to break the module into regions and compile regions speculatively using multiple JIT backend light weight threads. I’m still not sure, how this can be done, I would highly appreciate the feedback from community in deciding the heuristics & granularity to compile. 3.Practical example with benchmarks: To my best of knowledge PostgreSQL using ORC API, it would be easier to get postgresql queries to get compile speculatively and compare results with baseline (concurrent compiler without speculation). 4. Unit tests + documentation. Benefits: 1. We can full use of multiple compilation threads, to compile code upfront with minimum false positive. 2. Stabilize JIT APIs which most clients looking for when transitioning to newer versions. Further Opportunities : We can also use thinlto summaries in module to decide which code is worthier to compile next, based on this lighting LLVM Dev talk by Stefan <https://www.youtube.com/watch?v=ZCnHxRhQmvs>. Profile guided optimization - information will be helpful in this, provide further room for improvement. I would highly appreciate the community feedback & suggestions :) I will try my best to address all the comments in the proposal. I'm currently familiarizing myself with new APIs and learning heuristics. I will try to get the draft proposal by next week. References: HHVM JIT: A profile-Guided, Region-Based Compiler for PHP & Hack [paper <https://dl.acm.org/citation.cfm?id=3192374>]. PostgreSQL [JIT <https://doxygen.postgresql.org/structLLVMJitHandle.html>] Execution Engine [ORC <https://reviews.llvm.org/diffusion/L/browse/llvm/trunk/lib/ExecutionEngine/Orc/>] -- Have a great day! PreeJackie -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190324/fbf56f0c/attachment-0001.html>
Bekket McClane via llvm-dev
2019-Mar-24 05:00 UTC
[llvm-dev] GSoC- Speculative compilation support in ORC v2 , looking for mentors!
Hi, This idea sounds pretty cool Just some quick comments inlined below:> On Mar 23, 2019, at 1:57 PM, preejackie via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > Hi all, > > I would like to propose "Speculative compilation support in ORC v2 JIT API" for this year GSoC summer project. > > Project Description: > Speculative compilation support. One of the selling points of the concurrent ORC APIs is that you can start compiling a function before you need it, in the hope that by the time that you do need it it is already compiled. However, if we just speculatively compile everything we're quickly going to overload our memory/CPU resources, which will be lousy for performance. What we really want to do is to take into account any information we have (from high level program representations, e.g. ASTs or CFGs, or from profiling data from previous executions) to try to guess what functions are worth speculatively compiling next. > Idea is proposed by Lang Hames. > > Current Status of ORC v2: > > ORC currently supports concurrent compilation and Lazy (on request compilation), trunk contains default new ORC JIT implementations as LLJIT, LLLazyJIT. > [WIP] Jit-linker a drop-in-replacement for RuntimeDyld atleast for MachO in ORC JIT. > Primitive code to handle speculative is in trunk. But it needs to refactored & designed to get generalized, simple APIs to support speculation. > Currently, no heuristics to support speculation in trunk. > > Proposed Solution: > New APIs in ORC v2 to support speculation compilation of LLVM bitcode. LLSpecJIT - subtype of LLJIT, default JIT with speculation support in trunk. > Heuristics to guide speculation - > Currently, I’m going through some literature/research papers to find good basic heuristics. We can derive useful information from Control flow graphs, IR etc. So far I figured out that Region-based compilation is more appropriate for speculation.Can you justify your point? What do you mean by saying “appropriate”? Is it easy to implement or have better performance on the generated code? Just a FYI: The JIT compilation community has been debating over which compilation region should be chosen for quite some time. The TL;DR answer is: there is NO single answer, all depends on the usages and engineering efforts. Just give you examples on two of the most adopted methods: trace-based(kind of similar to region based) and function-based. Famous users of trace-based JIT are early versions of SpiderMonkey(i.e. JS engine in Firefox) and Dalvik VM(i.e. the old VM in Android). This approach can record hot path across functions, and just like the old saying: global optimizations are always preferred. However, it requires more engineering efforts and profiling/tracing is almost mandatory. Function-based JIT is used by V8 and ART(Android Runtime, the current VM in Android), to name a few. The biggest advantage is that it’s pretty easy to implement. And the performance is actually not bad in most of the cases. The downside is , of course, it will loose some global optimization opportunities. Be honestly I’m pretty surprised you didn’t mention any of the above projects. Of course, none of them use LLVM, but all of them are outstanding JIT engines with huge amount of users and tested by time. Some of them are even important milestones in the history of dynamic compilation. I believe you can learn the key insight of choosing a specific compilation region from them.> Since, unit of compilation (granularity) is key good dynamic compilation, region based compilation address that by forming frequently executed code as a region (unit), this can be basic block, function or group of functions. But since, LLVM JIT API needs interoperates with static compiler, unit of compilation here is a complete module.> The plan in mind is to break the module into regions and compile regions speculatively using multiple JIT backend light weight threads. I’m still not sure, how this can be done, I would highly appreciate the feedback from community in deciding the heuristics & granularity to compile. > 3.Practical example with benchmarks: To my best of knowledge PostgreSQL using ORC API, it would be easier to get postgresql queries to get compile speculatively and compare results with baseline (concurrent compiler without speculation). > 4. Unit tests + documentation. > > Benefits: > We can full use of multiple compilation threads, to compile code upfront with minimum false positive. > Stabilize JIT APIs which most clients looking for when transitioning to newer versions. > > Further Opportunities : > We can also use thinlto summaries in module to decide which code is worthier to compile next, based on this lighting LLVM Dev talk by Stefan <https://www.youtube.com/watch?v=ZCnHxRhQmvs>. > Profile guided optimization - information will be helpful in this, provide further room for improvement. > > I would highly appreciate the community feedback & suggestions :) > I will try my best to address all the comments in the proposal. I'm currently familiarizing myself with new APIs and learning heuristics. I will try to get the draft proposal by next week. > > References: HHVM JIT: A profile-Guided, Region-Based Compiler for PHP & Hack [paper <https://dl.acm.org/citation.cfm?id=3192374>]. > PostgreSQL [JIT <https://doxygen.postgresql.org/structLLVMJitHandle.html>] > Execution Engine [ORC <https://reviews.llvm.org/diffusion/L/browse/llvm/trunk/lib/ExecutionEngine/Orc/>] >Best, Bekket> -- > Have a great day! > PreeJackie > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190323/3e8ce720/attachment-0001.html>
preejackie via llvm-dev
2019-Mar-24 20:47 UTC
[llvm-dev] GSoC- Speculative compilation support in ORC v2 , looking for mentors!
Hi Bekket, Sorry for the delayed reply. By appropriate, I mean performance of compiled native code. I was referring other JIT implementations like LuaJIT & webkit FTL JIT to see how they implement their JIT. I have gone through the design of Spider Monkey & Android runtime (ART) JIT. As, you said both region based and method based compilation unit have their own advantage & disadvantage. Both make use of profile generation for hot-code regions/functions. I have planned to rethink my idea of implementing "function based" instead of "region based" compilation unit. Because, trace-based jit requires considerable development time & time taken to find hot code region from IR with profile support is high. In my opinion these are difficult to get implemented within 11 weeks (summer time) and make a way to trunk for real use by people. Also, LLVM ORC v2 resembles more like a function based approach. I think it would be easier to built a runtime profiler around it and make use of that profile data in compilelayer of ORC to recompile hot functions speculatively with more optimization. As far as I know, many JIT implementations uses profilers to decide hot code functions than information from their intermediate representation because of the dynamic nature of compiled/interpreting source language. This make me focus more runtime profilers than analysis on IR. Of course, analysis from IR will be useful in start phase of JIT compilation. I find IntelJITEvents in Execution Engine, is there any documentation on it's use cases? If you have thoughts over it, please share :) Thanks On 24/03/19 10:30 AM, Bekket McClane wrote:> Hi, > > This idea sounds pretty cool > Just some quick comments inlined below: > >> On Mar 23, 2019, at 1:57 PM, preejackie via llvm-dev >> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: >> >> Hi all, >> >> I would like to propose "Speculative compilation support in ORC v2 >> JIT API" for this year GSoC summer project. >> >> Project Description: >> Speculative compilation support. One of the selling points of the >> concurrent ORC APIs is that you can start compiling a function before >> you need it, in the hope that by the time that you do need it it is >> already compiled. However, if we just speculatively compile >> everything we're quickly going to overload our memory/CPU resources, >> which will be lousy for performance. What we really want to do is to >> take into account any information we have (from high level program >> representations, e.g. ASTs or CFGs, or from profiling data from >> previous executions) to try to guess what functions are worth >> speculatively compiling next. >> Idea is proposed by Lang Hames. >> >> Current Status of ORC v2: >> >> 1. >> ORC currently supports concurrent compilation and Lazy (on >> request compilation), trunk contains default new ORC JIT >> implementations as LLJIT, LLLazyJIT. >> 2. >> [WIP] Jit-linker a drop-in-replacement for RuntimeDyld atleast >> for MachO in ORC JIT. >> 3. >> Primitive code to handle speculative is in trunk. But it needs to >> refactored & designed to get generalized, simple APIs to support >> speculation. >> 4. >> Currently, no heuristics to support speculation in trunk. >> >> >> Proposed Solution: >> >> 1. >> New APIs in ORC v2 to support speculation compilation of LLVM >> bitcode. LLSpecJIT - subtype of LLJIT, default JIT with >> speculation support in trunk. >> 2. >> Heuristics to guide speculation - >> >> Currently, I’m going through some literature/research papers to find >> good basic heuristics. We can derive useful information from Control >> flow graphs, IR etc. So far I figured out that Region-based >> compilation is more appropriate for speculation. > > Can you justify your point? What do you mean by saying “appropriate”? > Is it easy to implement or have better performance on the generated code? > > Just a FYI: > The JIT compilation community has been debating over which compilation > region should be chosen for quite some time. > The TL;DR answer is: there is NO single answer, all depends on the > usages and engineering efforts. > Just give you examples on two of the most adopted methods: > trace-based(kind of similar to region based) and function-based. > Famous users of trace-based JIT are early versions of > SpiderMonkey(i.e. JS engine in Firefox) and Dalvik VM(i.e. the old VM > in Android). This approach can record hot path across functions, and > just like the old saying: global optimizations are always preferred. > However, it requires more engineering efforts and profiling/tracing is > almost mandatory. > Function-based JIT is used by V8 and ART(Android Runtime, the current > VM in Android), to name a few. The biggest advantage is that it’s > pretty easy to implement. And the performance is actually not bad in > most of the cases. The downside is , of course, it will loose some > global optimization opportunities. > > Be honestly I’m pretty surprised you didn’t mention any of the above > projects. Of course, none of them use LLVM, but all of them are > outstanding JIT engines with huge amount of users and tested by time. > Some of them are even important milestones in the history of dynamic > compilation. I believe you can learn the key insight of choosing a > specific compilation region from them. > >> Since, unit of compilation (granularity) is key good dynamic >> compilation, region based compilation address that by forming >> frequently executed code as a region (unit), this can be basic block, >> function or group of functions. But since, LLVM JIT API needs >> interoperates with static compiler, unit of compilation here is a >> complete module. > >> The plan in mind is to break the module into regions and compile >> regions speculatively using multiple JIT backend light weight >> threads. I’m still not sure, how this can be done, I would highly >> appreciate the feedback from community in deciding the heuristics & >> granularity to compile. >> 3.Practical example with benchmarks: To my best of knowledge >> PostgreSQL using ORC API, it would be easier to get postgresql >> queries to get compile speculatively and compare results with >> baseline (concurrent compiler without speculation). >> 4. Unit tests + documentation. >> >> Benefits: >> >> 1. >> We can full use of multiple compilation threads, to compile code >> upfront with minimum false positive. >> 2. >> Stabilize JIT APIs which most clients looking for when >> transitioning to newer versions. >> >> >> Further Opportunities : >> We can also use thinlto summaries in module to decide which code is >> worthier to compile next, based on this lighting LLVM Dev talk by >> Stefan <https://www.youtube.com/watch?v=ZCnHxRhQmvs>. >> Profile guided optimization - information will be helpful in this, >> provide further room for improvement. >> >> I would highly appreciate the community feedback & suggestions :) >> I will try my best to address all the comments in the proposal. I'm >> currently familiarizing myself with new APIs and learning heuristics. >> I will try to get the draft proposal by next week. >> >> References: HHVM JIT: A profile-Guided, Region-Based Compiler for PHP >> & Hack [paper <https://dl.acm.org/citation.cfm?id=3192374>]. >> PostgreSQL [JIT >> <https://doxygen.postgresql.org/structLLVMJitHandle.html>] >> Execution Engine [ORC >> <https://reviews.llvm.org/diffusion/L/browse/llvm/trunk/lib/ExecutionEngine/Orc/>] >> >> > > Best, > Bekket > >> -- Have a great day! PreeJackie >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> >> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >-- Have a great day! PreeJackie -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190325/d5cd4cc3/attachment.html>