Copy-and-Patch Binary Code Generation

Abstract: Runtime compilation of runtime-constructed code is becoming standard practice in libraries, DSLs, and database management systems. Since compilation is expensive, systems that are sensitive to compile times such as relational database query compilers compile only hot code and interprets the rest with a much slower interpreter. We present a code generation technique that lowers an AST to binary code by stitching together code from a large library of binary AST node implementations. We call the implementations stencils because they have holes where values must be inserted during code generation. We show how to construct such a stencil library and describe the copy-and-patch technique that generates optimized binary code. The result is a code generator with negligible cost: it produces code from an AST in less time than it takes to construct the AST. Compared to LLVM, compilation is two orders of magnitude faster than -O0 and three orders of magnitude faster than higher optimization levels. The generated code runs an order of magnitude faster than interpretation and runs even faster than LLVM -O0. Thus, copy-and-patch can effectively replace both interpreters and LLVM -O0, making code generation more effective in compile-time sensitive applications.