  Fast compilation is important when compilation occurs at runtime, such as
query compilers in modern database systems and WebAssembly virtual machines in
modern browsers. We present copy-and-patch, an extremely fast compilation
technique that also produces good quality code. It is capable of lowering both
high-level languages and low-level bytecode programs to binary code, by
stitching together code from a large library of binary implementation variants.
We call these binary implementations stencils because they have holes where
missing values must be inserted during code generation. We show how to
construct a stencil library and describe the copy-and-patch algorithm that
generates optimized binary code.
  We demonstrate two use cases of copy-and-patch: a compiler for a high-level
C-like language intended for metaprogramming and a compiler for WebAssembly.
Our high-level language compiler has negligible compilation cost: it produces
code from an AST in less time than it takes to construct the AST. We have
implemented an SQL database query compiler on top of this metaprogramming
system and show that on TPC-H database benchmarks, copy-and-patch generates
code two orders of magnitude faster than LLVM -O0 and three orders of magnitude
faster than higher optimization levels. The generated code runs an order of
magnitude faster than interpretation and 14% faster than LLVM -O0. Our
WebAssembly compiler generates code 4.9X-6.5X faster than Liftoff, the
WebAssembly baseline compiler in Google Chrome. The generated code also
outperforms Liftoff's by 39%-63% on the Coremark and PolyBenchC WebAssembly
benchmarks.
