SDI Seminar

Speaker: Mark Leone, CMU (joint work with Peter Lee)

A Declarative Approach to Run-Time Code Generation

Date: February 15, 1996

Abstract: Run-time code generation promises to improve the performance and reliability of current and future systems. Optimizations performed at run time make use of values and invariants that cannot be exploited at compile time, yielding code that is superior to statically optimal code.

Most previous approaches to run-time code generation have been _imperative_. The programmer is responsible for specifying the code to be optimized at run time (often as a "template" of machine code), performing certain optimizations, insuring that dynamically constructed code is well formed, invoking a compiler and dynamically linking to the resulting code, and insuring correctness by invalidating or updating code when the values used to optimize it change.

Each of these duties is laborious and error prone. Various ad-hoc techniques have been suggested to ameliorate the situation, but we believe that this imperative approach is inherently clumsy and unsafe.

We advocate a _declarative_ approach to run-time code generation: the programmer should express algorithms in a high-level language that permits the _compiler_ to discover and safely exploit opportunities for dynamic optimization. The key benefits of a declarative approach to run-time code generation are:

  • Safety: the programmer does not write explicit code for generating code, but instead submits an ordinary program to the compiler
  • Portability: the compiler encapsulates all of the details of run-time code generation
  • Speed: the compiler can use semantics-based transformation techniques to specialize run-time code generators, reducing code generation time by an order of magnitude over previous imperative approaches.
Our goals may appear to be impossibly lofty; on the contrary, we have early evidence from experiments with a prototype compiler that automatic run-time code generation can be practical. Our compiler, called Fabius, compiles ordinary programs written in a subset of Standard ML into code that generates and executes native code at run time.