Retrofitting JIT Compilers into C Interpreters (opens in new tab)

(tratt.net)

135 pointsltratt27d ago26 comments

26 comments

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

syrusakbary25d ago

Yeah, the strategy is literally the same

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

ltrattOP26d ago

You're quite right that since we're working with LLVM IR, adapting to other languages is probably not _that_ difficult, though these things always end up taking more time than I expect! Since the majority of real-world problems in this area depend on C interpreters, we put our limited resources to that problem. You're also right that "interpreters" is a pretty vague category, and there are other parts of C (and other) programs that could be yk-ified, though I suspect it would be a fairly specialised subset of programs.

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

hencq26d ago

I think the website does an amazing job explaining it, but it basically takes an interpreter written in C and turns it into a JIT with minimal changes to the code of the interpreter (i.e. not to the code of the program you're running in the interpreter). For example they took the Lua interpreter and with minimal changes were able to turn it into a JIT, which runs Lua programs about 2x faster.

vkazanov26d ago

tracing jits are slightly harder to grasp than usual ones. The technique comes from real CPUs so the mindset of people behind the original idea is very different from the software world.

Metatracing ones are kind of an interesting twist on the original idea.

> So it takes normal interpreted code and jits it somehow?

Anyway, they use a patched LLVM to JIT-compile not just interpreted code but the main loop of the bytecode interpreter. Like, the C implementation itself.

> But you have to modify the source code of your program in some way?

Generally speaking, this is not normally the goal. All JIT-s try to support as much of the target language as possible. Some JIT-s do limit the subset of features supported.

fuhsnn26d 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.

moardiggin26d 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.

1 more reply

pjmlp26d ago

There were a couple of C interpreters since the 1990's, including with REPL support, but apparently never took off, most likely a community culture issue, that doesn't seem much value using them, beyond being in a debug session.

i_don_t_know26d ago

I used to work on LabWindows/CVI an integrated C development environment. It included an "Interactive Execution Window" where you could build programs piecemeal. You added pieces of code, ran them, then appended more code, ran the new pieces, etc. It was as text window so you had more freedom than in a simple REPL.

It integrated with "Function panels". Function panels were our attempt at documenting our library functions. See the second link below. But you could enter values, declare variables, etc and then run the function panel. Behind the scenes, the code is inserted to the interactive window and then run. Results are added back to the function panel.

These also worked while suspended on a breakpoint in your project so available while debugging.

My understanding was that these features were quite popular with customers. They also came it handy internally when we wrote examples and did manual testing.

https://www.ni.com/docs/de-DE/bundle/labwindows-cvi/page/cvi...

https://irkr.fei.tuke.sk/PPpET/_materialy/CVI/Quick_manual.p...

pjmlp26d ago

Thanks for sharing.

Yeah, I find this valuable regardless of the programming language, ideally the toolchain should be a mix of interpreter/JIT/AOT, to cherry pick depending on the deployment use case.

Naturally for dynamic languages pure AOT is not really worth it, althought a JIT cache is helpful as alternative.

fluorinerocket25d ago

There were so many things that NI did that were great. Debugging in LabVIEW was also very easy with probes, conditional breakpoints etc.

It's really too bad that it's more or less dead now

djwatson2426d 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.

hypercube3326d 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

pjmlp26d 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.

edmondx26d ago

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

measurablefunc26d ago

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

ltrattOP26d 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.

sgbeal27d 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.

throwaway149226d 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.

sgbeal26d 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

mwkaufma26d ago

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

measurablefunc26d 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.

j / k navigate · click thread line to collapse

26 comments

9fwfj9r26d ago

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

syrusakbary25d ago

Yeah, the strategy is literally the same

fuhsnn26d ago

ltrattOP26d ago

itriednfaild26d ago

hencq26d ago

vkazanov26d ago

tracing jits are slightly harder to grasp than usual ones. The technique comes from real CPUs so the mindset of people behind the original idea is very different from the software world.

Metatracing ones are kind of an interesting twist on the original idea.

> So it takes normal interpreted code and jits it somehow?

Anyway, they use a patched LLVM to JIT-compile not just interpreted code but the main loop of the bytecode interpreter. Like, the C implementation itself.

> But you have to modify the source code of your program in some way?

Generally speaking, this is not normally the goal. All JIT-s try to support as much of the target language as possible. Some JIT-s do limit the subset of features supported.

fuhsnn26d ago

moardiggin26d ago

    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

If this project would be able to detect the interpreter hotspots itself and completely automate the procedure, it would be great.

1 more reply

pjmlp26d ago

i_don_t_know26d ago

These also worked while suspended on a breakpoint in your project so available while debugging.

My understanding was that these features were quite popular with customers. They also came it handy internally when we wrote examples and did manual testing.

https://www.ni.com/docs/de-DE/bundle/labwindows-cvi/page/cvi...

https://irkr.fei.tuke.sk/PPpET/_materialy/CVI/Quick_manual.p...

pjmlp26d ago

Thanks for sharing.

Yeah, I find this valuable regardless of the programming language, ideally the toolchain should be a mix of interpreter/JIT/AOT, to cherry pick depending on the deployment use case.

Naturally for dynamic languages pure AOT is not really worth it, althought a JIT cache is helpful as alternative.

fluorinerocket25d ago

There were so many things that NI did that were great. Debugging in LabVIEW was also very easy with probes, conditional breakpoints etc.

It's really too bad that it's more or less dead now

djwatson2426d 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.

hypercube3326d 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

pjmlp26d ago

edmondx26d ago

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

measurablefunc26d ago

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

ltrattOP26d ago

sgbeal27d 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.

throwaway149226d ago

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

Pics or it didn't happen: fossil.wanderinghorse.net/r/cwal

mwkaufma26d ago

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

measurablefunc26d ago

j / k navigate · click thread line to collapse