I am interested in writing a JIT that makes use of on-stack replacement. This essentially means that the JIT must be able to compile new versions of already compiled functions (eg: more optimized versions) and ensure that the code for the new functions is executed. I was wondering if LLVM offers any support for this. Suppose a function f calls a function g, and f is recompiled while g is running, I would need to be able, when returning from g to f, to jump to the updated code for f. So, one way to implement this would be to insert a jump after every call in the body of the old function f, that jump to the corresponding point in the body of the new function. This would require me to overwrite some of the code of f. If LLVM has no direct support for this, I could potentially create auxiliary "call handler" functions which can do a long jump to the proper code on return. So what I would like to know is: 1. Does LLVM support code patching? By this, I mean overwriting some instructions 2. Does LLVM support long jumps? 3. Has anyone here implemented code patching or on-stack replacement in LLVM? Another potential issue is that if I recompile some function, I would ideally want to keep the same stack representation for both. This could potentially be quite tricky. Any advice on how to go about this? -- View this message in context: http://old.nabble.com/On-Stack-Replacement---Code-Patching-tp27855179p27855179.html Sent from the LLVM - Dev mailing list archive at Nabble.com.
On Wed, Mar 10, 2010 at 3:11 PM, Nyx <mcheva at cs.mcgill.ca> wrote:> > I am interested in writing a JIT that makes use of on-stack replacement. This > essentially means that the JIT must be able to compile new versions of > already compiled functions (eg: more optimized versions) and ensure that the > code for the new functions is executed. I was wondering if LLVM offers any > support for this. > > Suppose a function f calls a function g, and f is recompiled while g is > running, I would need to be able, when returning from g to f, to jump to the > updated code for f. So, one way to implement this would be to insert a jump > after every call in the body of the old function f, that jump to the > corresponding point in the body of the new function. This would require me > to overwrite some of the code of f. If LLVM has no direct support for this, > I could potentially create auxiliary "call handler" functions which can do a > long jump to the proper code on return. > > So what I would like to know is: > > 1. Does LLVM support code patching? By this, I mean overwriting some > instructionsYou can call recompileAndRelinkFunction, which patches the stub of a function with a jump to the new function body.> 2. Does LLVM support long jumps?You can use a tail call to accomplish this.> 3. Has anyone here implemented code patching or on-stack replacement in > LLVM?Our plan in unladen swallow for recompilation is to to generate a new function each time. We don't want to worry about other threads that may be executing machine code while we're patching it, so the simple design is that every snippet of code has an object that owns it. Each frame executing that code increments the refcount before entering it, and decrefs after exit. This is basically the call wrapper that you're talking about. This doesn't do on-stack replacement, but it may help you solve some of your problems.> > Another potential issue is that if I recompile some function, I would > ideally want to keep the same stack representation for both. This could > potentially be quite tricky. Any advice on how to go about this?I'm pretty sure there's no way to guarantee that the stack frame representation in LLVM is going to be the same. Your best bet would be to maintain your own representation of the stack frame on the side which you can save to and restore from on your entry and exit code paths. If you have an interpreter that you're interfacing with, you will probably need to do this already. Reid
>> You can use a tail call to accomplish this.Would this allow me to jump from some point in the body of a function A to another point in the body of another function B, and then have B to the caller of A? -- View this message in context: http://old.nabble.com/On-Stack-Replacement---Code-Patching-tp27855179p27856680.html Sent from the LLVM - Dev mailing list archive at Nabble.com.
On Wed, Mar 10, 2010 at 21:11, Nyx <mcheva at cs.mcgill.ca> wrote:> > I am interested in writing a JIT that makes use of on-stack replacement. This > essentially means that the JIT must be able to compile new versions of > already compiled functions (eg: more optimized versions) and ensure that the > code for the new functions is executed. I was wondering if LLVM offers any > support for this. > > Suppose a function f calls a function g, and f is recompiled while g is > running, I would need to be able, when returning from g to f, to jump to the > updated code for f. So, one way to implement this would be to insert a jump > after every call in the body of the old function f, that jump to the > corresponding point in the body of the new function. This would require me > to overwrite some of the code of f. If LLVM has no direct support for this, > I could potentially create auxiliary "call handler" functions which can do a > long jump to the proper code on return. > > So what I would like to know is: > > 1. Does LLVM support code patching? By this, I mean overwriting some > instructions > 2. Does LLVM support long jumps? > 3. Has anyone here implemented code patching or on-stack replacement in > LLVM?We have implemented on-stack replacement for switching from an optimized code base to an unoptimized code base (maybe containing additional runtime checks). The basic idea is to prepare both code bases BEFORE applying any further instrumentation (optimization or adding runtime checks). We present the details about our LLVM-pass at CGO this year in a paper called "Prospect: A Compiler Framework for Speculative Parallelization". If you are interested in the paper, please contact me off-line of the mailing list. Martin> > Another potential issue is that if I recompile some function, I would > ideally want to keep the same stack representation for both. This could > potentially be quite tricky. Any advice on how to go about this? > -- > View this message in context: http://old.nabble.com/On-Stack-Replacement---Code-Patching-tp27855179p27855179.html > Sent from the LLVM - Dev mailing list archive at Nabble.com. > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Martin Süßkraut Dresden University of Technology, Computer Science Department Systems Engineering Group Dresden, Germany http://wwwse.inf.tu-dresden.de
(Sorry for answering to the wrong message, but there's a foulup on my side and I don't have the original message anymore.) I'm sceptical that what you want is even logically possible, Nyx. Even if you just recompile f with better optimization, the call site for g might have gone away. For example, g might have been inlined into f, or a loop might have been unrolled and now there are a dozen call site, or the call to g might have moved out of a loop because the compiler has determined it's invariant (but now you need to restart the function because the new loop code assumes the result of g is available right from the start of the loop and now halfways through the loop body). If you want to exchange code while the system is running, my advice would be: * create new versions of the functions to be replaced * new calls run the new code, old calls complete using the old code, garbage collect the old code when the last stack frame that uses it goes away * write small, short-lived functions so the turnover is quick * break tasks that run for a long time into a loop doing short calls, so the actual work is still done in short-lived functions * prevent LLVM from inlining into long-lived functions Entire million-LoC systems have been built that way. See Joe Armstrong's PhD thesis for patterns that are useful with such a style. (I don't agree with him that everything should be a concurrent process, but if you replace "process" with "function" and "message send/receive" with "subroutine call", you would get the same ability to upgrade the system while it's running. Only the top-level loops and long-running functions would need to be written in the everything-is-a-tight-loop pattern that's so prevalent in the system he's describing.) Just a suggestion that may or may not fit your situation. Regards, Jo