6 ms·

Retrofitting JIT Compilers into C Interpreters

135 points by ltratt 6mo ago

sgbeal 6mo ago
i tend to think of myself as a computing nerd, but posts like this one make me realize that i don't even rate on the computing nerd scale.
- throwaway1492 6mo ago
  Do you always make things about yourself? Have you written a parser or interpreter? You should, it’s an interesting exercise. The idea is to add meta tracing to the interpreter (the c code) that allows hot paths to be compiled to machine code and be then executed instead of being interpreted.
  - sgbeal 6mo ago
    > Do you always make things about yourself? That's an abrasive question but i dare say that we all do. It's our only constant point of reference. > Have you written a parser or interpreter? i have written many parsers, several parser generators, and a handful of programming languages. This article, however, covers a whole other level, way over my head (or well beyond any of my ambitions, in any case). Pics or it didn't happen: fossil.wanderinghorse.net/r/cwal
mwkaufma 6mo ago
TL;DR compile with a fork of LLVM that enables runtime IR tracing. Very clever!
- measurablefunc 6mo ago
  That's not what they're doing. They're directly modifying the IR to convert it into a tracing JIT. The final artifact is a binary w/ no IR. The problem is of course not introducing any subtle bugs in the process b/c they'd have to prove the modification they're making do not change actual runtime semantics for the final binary artifact.
fuhsnn 6mo ago
Took me a while to figure out whether it's interpreters for C programs or if there's a particular class of interpreters called "C". Turns out it's about interpreters implemented in C that they use modified LLVM to do the retrofitting, but couldn't it be applicable for other languages with LLVM IR, or other switch-in-a-loop patterns in C?
- itriednfaild 6mo ago
  I've been a low level C and C++ programmer for 30 years. Even with your explanation and having read the webpage twice I have no idea what this technology does or how it works. So it takes normal interpreted code and jits it somehow? But you have to modify the source code of your program in some way?
  - fuhsnn 6mo ago
    I don't fully grasp it either, the most appropriate analogy I can think of is like how OpenMP turns #pragma annotated loops into multi-threading, this work turns bytecode interpreting loops into JIT VM.
    - moardiggin 6mo ago
      It's a promising technology, but it's still in the research domain. It's not an automated procedure. You need to use the yk fork of LLVM to compile and link your code, and you have to manually annotate and alter a fair amount of your interpreter loop with yk macros in non-trivial ways: while (true) { __yk_tracebasicblock(0); Instruction i = code[pc]; switch (GET_OPCODE(i)) { case OP_LOOKUP: __yk_tracebasicblock(1); push(lookup(GET_OPVAL())); pc++; break; ... case OP_INT: push(yk_promote(constant_pool[GET_OPVAL(i)])); pc++; break; Knowledge of tracing compilers, LLVM and SSA are needed by the user. > added about 400LoC to PUC Lua, and changed under 50LoC Lua 5.5.0 has 32106 lines of code including comments and empty lines. The changes amount to 1.4% of the code base. And then there's the code changes in the yk LLVM fork that you'd have to maintain which I'm guessing would be a few orders of magnitude larger. If this project would be able to detect the interpreter hotspots itself and completely automate the procedure, it would be great.
djwatson24 6mo ago
It's quite impressive they're able to take nearly arbitrary C and do this! Very similar to what pypy is doing here, but for C, and not a python subset. However not without downsides. It sounds like average code is only 2x faster than Lua, vs. LuaJit which is often 5-10x faster.
- hypercube33 6mo ago
  Hmm I'm wondering how hard it would be to redo the old timey Microsoft jvm from the 90s for modern days....java > .net assembly runtime
- linzhangrun 6mo ago
  [flagged]
linzhangrun 6mo ago
[flagged]
measurablefunc 6mo ago
Why do they need to change LLVM? Why can't they make this another LLVM IR pass?
- ltratt 6mo ago
  Our fork of LLVM does add a pass, amongst other changes, but we also have to do things like change stackmaps in a way that breaks compatibility. Whether stackmaps in their current incarnation are worth retaining compatibility for is above my pay grade! So some of our changes are probably upstreamable, but some might be considered too niche for wider integration.
9fwfj9r 6mo ago
Those interested in this type of work can also visit https://cfallin.org/blog/2024/08/28/weval/ https://cfallin.org/blog/2024/08/28/weval/. The difference is that they use this technique to derive an AOT compiler.
- syrusakbary 6mo ago
  Yeah, the strategy is literally the same
pjmlp 6mo ago
I find rather strange the complaint about compatibility across JIT implementations, there is exactly the same problem across any programming language with multiple implementations, interpreters, compilers, JIT, whatever.
edmondx 6mo ago
Sounds very promising. Although right now I’m working on a project together with MLIR.

135 points by ltratt 6mo ago

i tend to think of myself as a computing nerd, but posts like this one make me realize that i don't even rate on the computing nerd scale.

throwaway1492 6mo ago
Do you always make things about yourself? Have you written a parser or interpreter? You should, it’s an interesting exercise. The idea is to add meta tracing to the interpreter (the c code) that allows hot paths to be compiled to machine code and be then executed instead of being interpreted.
- sgbeal 6mo ago
  > Do you always make things about yourself? That's an abrasive question but i dare say that we all do. It's our only constant point of reference. > Have you written a parser or interpreter? i have written many parsers, several parser generators, and a handful of programming languages. This article, however, covers a whole other level, way over my head (or well beyond any of my ambitions, in any case). Pics or it didn't happen: fossil.wanderinghorse.net/r/cwal

mwkaufma 6mo ago

TL;DR compile with a fork of LLVM that enables runtime IR tracing. Very clever!

measurablefunc 6mo ago
That's not what they're doing. They're directly modifying the IR to convert it into a tracing JIT. The final artifact is a binary w/ no IR. The problem is of course not introducing any subtle bugs in the process b/c they'd have to prove the modification they're making do not change actual runtime semantics for the final binary artifact.

fuhsnn 6mo ago

Took me a while to figure out whether it's interpreters for C programs or if there's a particular class of interpreters called "C". Turns out it's about interpreters implemented in C that they use modified LLVM to do the retrofitting, but couldn't it be applicable for other languages with LLVM IR, or other switch-in-a-loop patterns in C?

itriednfaild 6mo ago
I've been a low level C and C++ programmer for 30 years. Even with your explanation and having read the webpage twice I have no idea what this technology does or how it works. So it takes normal interpreted code and jits it somehow? But you have to modify the source code of your program in some way?
- fuhsnn 6mo ago
  I don't fully grasp it either, the most appropriate analogy I can think of is like how OpenMP turns #pragma annotated loops into multi-threading, this work turns bytecode interpreting loops into JIT VM.
  - moardiggin 6mo ago
    It's a promising technology, but it's still in the research domain. It's not an automated procedure. You need to use the yk fork of LLVM to compile and link your code, and you have to manually annotate and alter a fair amount of your interpreter loop with yk macros in non-trivial ways: while (true) { __yk_tracebasicblock(0); Instruction i = code[pc]; switch (GET_OPCODE(i)) { case OP_LOOKUP: __yk_tracebasicblock(1); push(lookup(GET_OPVAL())); pc++; break; ... case OP_INT: push(yk_promote(constant_pool[GET_OPVAL(i)])); pc++; break; Knowledge of tracing compilers, LLVM and SSA are needed by the user. > added about 400LoC to PUC Lua, and changed under 50LoC Lua 5.5.0 has 32106 lines of code including comments and empty lines. The changes amount to 1.4% of the code base. And then there's the code changes in the yk LLVM fork that you'd have to maintain which I'm guessing would be a few orders of magnitude larger. If this project would be able to detect the interpreter hotspots itself and completely automate the procedure, it would be great.

djwatson24 6mo ago

It's quite impressive they're able to take nearly arbitrary C and do this! Very similar to what pypy is doing here, but for C, and not a python subset. However not without downsides. It sounds like average code is only 2x faster than Lua, vs. LuaJit which is often 5-10x faster.

hypercube33 6mo ago
Hmm I'm wondering how hard it would be to redo the old timey Microsoft jvm from the 90s for modern days....java > .net assembly runtime
linzhangrun 6mo ago
[flagged]

linzhangrun 6mo ago

[flagged]

measurablefunc 6mo ago

Why do they need to change LLVM? Why can't they make this another LLVM IR pass?

ltratt 6mo ago
Our fork of LLVM does add a pass, amongst other changes, but we also have to do things like change stackmaps in a way that breaks compatibility. Whether stackmaps in their current incarnation are worth retaining compatibility for is above my pay grade! So some of our changes are probably upstreamable, but some might be considered too niche for wider integration.

9fwfj9r 6mo ago

Those interested in this type of work can also visit https://cfallin.org/blog/2024/08/28/weval/ https://cfallin.org/blog/2024/08/28/weval/. The difference is that they use this technique to derive an AOT compiler.

syrusakbary 6mo ago
Yeah, the strategy is literally the same

pjmlp 6mo ago

I find rather strange the complaint about compatibility across JIT implementations, there is exactly the same problem across any programming language with multiple implementations, interpreters, compilers, JIT, whatever.

edmondx 6mo ago

Sounds very promising. Although right now I’m working on a project together with MLIR.