Finite-state code generation

This paper describes GBURG, which generates tiny, fast code generators base d on finite-state machine pattern matching. The code generators translate p ostfix intermediate code into machine instructions in one pass (except, of course, for backpatching addresses). A stack-based virtual machine-known as the Lean Virtual Machine (LVM)-tuned for fast code generation is also desc ribed. GBURG translates the two-page LVM-to-x86 specification into a code g enerator that fits entirely in an 8 KB I-cache and that emits x86 code at 3 .6 MB/sec on a 266-MHz P6. Our just-in-time code generator translates and e xecutes small benchmarks at speeds within a factor of two of executables de rived from the conventional compile-time code generator on which it is base d.