On-Stack Replacement & Code Patching

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?

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

You 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?

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

(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