JITtting with limited knowledge of the target architecture

Question

I've implemented a little bytecode interpreter using computed goto (see here if not familiar).

It would seem that perhaps it's possible to do simple JITting by copying the memory between labels, thus optimizing out the jumps. For example, say I've got the following in my interpreter:

op_inc: val++; DISPATCH();

I would change this to:

op_inc: val++;
op_inc_end:

When JITting, I would append memory between the labels to my output:

memcpy(jit_code+offset, &&op_inc, &&op_inc_end - &&op_inc);

(jit_code is marked executable using mmap)

Finally, I would use computed goto to jump to the beginning of the copied machine code:

goto *(void*)jit_code

Will this work? Is there something missing in my mental model of machine code that would thwart this idea?

Let's assume that code and data share the same address space. Let's also assume PIC.

Update

Looking at the example in linked article, after removing DISPATCH, we have:

        do_inc:
            val++;
        do_dec:
            val--;
        do_mul2:
            val *= 2;
        do_div2:
            val /= 2;
        do_add7:
            val += 7;
        do_neg:
            val = -val;
        do_halt:
            return val;

The generated code for do_inc (no optimization) is simply:

Ltmp0:                                  ## Block address taken
## %bb.1:
    movl    -20(%rbp), %eax
    addl    $1, %eax
    movl    %eax, -20(%rbp)

(followed directly by do_dec). It looks like this little snippet could be clipped out.

Answer 1

Here's another reason this won't work on one architecture:

ARM Thumb code uses out-of-line immediate values with PC-relative addressing. An operation like

a += 12345;

could be compiled as:

ldr  r3, [pc, #<offset to constant>]
adds r0, r4, r3

… other unrelated code …

bx   lr      ; end of the function
.word 12345  ; oh, and here's the constant

Copying a fragment of this function would leave the reference to the constant unresolved; it'd end up using an unexpected value from elsewhere in memory.

Answer 2

No, this won't work in general. Here's just one of many reasons why:

Consider the AVR architecture. It's a Harvard architecture, so code and data don't live in the same address space. On it, your code will make a copy of whatever data happens to live in the data memory with the same address as the code memory you meant to copy, but will then ignore that anyway, and run whatever code is in the code memory with the same address as the data memory's destination location.

Answer 3

Not only do underlying instruction set architectures not work that way (as other answers have noted); C doesn't work that way. There's nothing to constrain the compiler to placing source-level code paths contiguously in the same pattern as labels between them. It's free to make all sorts of transformations including common subexpression elimination across different paths, outlining, etc. And of course it can also use the assumption that the code is executing in the function it's written as part of, rather than in some other context, to derive invariants that take part in transformations.

TL;DR: C is not "high-level assembly" and therefore you can't use it where an assembler is needed.

Answer 4

Update ... It looks like this little snippet could be clipped out.

Yes it could be clipped out because you compiled with no optimization, and the code is only accessing a local on the stack.

But only if jumped to with the same stack layout as this function, which precludes calling it as a function. But yes with a computed goto I guess that works.

If you were accessing anything in static storage (constants or global/static variables), x86-64 compilers would use RIP-relative addressing modes like var(%rip), which would break if you changed the position of the code relative to the data.

Calls to other functions will also break, because they'll compile to call rel32 where the target address is encoded relative to the call site.

---

Overall this is hardly useful. Anything you could do by copying around blocks of un-optimized code could probably be done more efficiently by writing an interpreter in portable C. Your idea will very easily break with optimization enabled.

For example, if you wanted to increment n times, introducing a store/reload cycle adds about 5 cycles of store-forwarding latency into the critical path if you just copy this block n times.

Also, you need __builtin___clear_cache on the range you copied if you were to enable optimization. And yes this applies even on x86, where it doesn't actually clear cache but does still stop dead-store elimination from removing the memcpy.

---

If you want to spend more time up front to make non-terrible machine code, use a JIT engine like LLVM.

Your idea is viable as a toy / experiment in some limited cases, but I would highly recommend against using it for any real use, especially if performance is your goal.

Answer 5

Will this work?

Yes; this can work.

However, it can only work for very limited cases where:

• there's no arguments to your functions. For example, if you're JITting a language like brainfuck (see https://en.wikipedia.org/wiki/Brainfuck ) then you might have functions like "void increment(void); and void putchar(void) which modify global state (e.g. struct machine_state { void * ptr; }).

• There is either no position independence (the address of the global state is a fixed/constant address), or you can tell the compiler to reserve a register to use as "pointer to global state" (which is something that GCC supports).

• The target machine supports some way to treat data as code. Note: This is relatively irrelevant (if a machine can't do this somehow, then you wouldn't be able to execute files either).

• You use barriers to prevent the compiler from shifting code out of your labels. Note: This is also relatively irrelevant (e.g. if you use inline assembly to define the label and mark the inline assembly as volatile, and put everything in the clobber list, then..).

• You're not using "pure portable C". Note: You're already using compiler specific extensions (computed goto) so I assume this is also relatively irrelevant.

For all of these limitations; the only one that's likely to matter in practice is the first one - anything worth JITting will be too complicated (e.g. you'll want functions like void add(int register_number_1, int register_number_2);), and as soon as you try to pass arguments to your functions you'll end up depending on target specific calling conventions.