Transforming C Interpreters into JIT Compilers with yk

C interpreters, while foundational for languages like Lua, Ruby, and Python, are notoriously slow compared to JIT compiler-powered implementations. However, by modifying a small portion of the code, we can transform these interpreters into JIT compiling virtual machines using yk, a system we've developed. Although yk is still in its alpha stage and not yet production-ready, it shows promise in enhancing performance while maintaining compatibility with reference implementations.

The yk system allows for automatic conversion of C interpreters into JIT compilers, offering a new point in the language performance design space. This is demonstrated with yklua, a fork of PUC Lua, which shows significant performance improvements with minimal code changes. While yklua doesn't match the performance of LuaJIT, it easily tracks updates to PUC Lua, unlike LuaJIT, which is stuck in the past.

yk is not limited to Lua. We've also adapted it for MicroPython, creating ykmicropython, which, despite some performance issues due to unsupported idioms, still shows meaningful improvements. The ultimate goal is for yk to enable any C interpreter to add a JIT with minimal effort.

JIT compilers are complex and costly to develop, requiring expertise across multiple domains. They optimize programs by speculating on future execution patterns, which can lead to performance gains or losses. The challenge lies in maintaining compatibility with evolving language specifications, a problem yk aims to solve by deriving JIT compilers directly from C interpreters.

Meta-tracing, the technique yk employs, is a sophisticated form of tracing JIT compilation. It records the actions of a host language interpreter while executing a guest language, allowing for automatic optimization and code generation. This approach, while challenging, enables significant performance improvements by aggressively inlining function calls and optimizing beyond the core interpreter loop.

The process involves using a fork of LLVM, ykllvm, to compile interpreters, adding trace recording capabilities and enabling deoptimization. Optimization techniques like constant folding and dead load/store analysis enhance performance further. Interpreter authors can assist the optimizer by providing additional knowledge about the guest language and interpreter, using features like promotion and idempotent functions.

yk also employs backwards code generation, inspired by LuaJIT, to improve register allocation and eliminate dead code. This approach simplifies the generation of efficient machine code and enhances performance.

Despite its current limitations, yk represents a promising advancement in language performance optimization. With continued development, it has the potential to significantly benefit a wide range of languages and users.