Thinking About Intermediate Representations

John Rose, September 2014

Optimizing compilation requires subtle algorithms and data structures. Foremost of these is the choice of one or more intermediate representations (IR). There is a wide variety of choices available, as exemplified by JVMs (HotSpot C1 and C2, JRockit, J9), Java-on-Java compilers (Graal, Jikes), and static compilers (gcc, llvm). In this document, we compare those choices by describing common IR features. We also narrow down the choices by enumerating design requirements for a idealistic IR we would enjoy working with. We will list the requirements first, because they are the most interesting results. The rest of the document will build up terminology and rationale for these requirements.



The IR must support transformations flexibily and efficiently, on single nodes, subgraphs, and wholesale. Implementation code for transformations must be clear and concise. (It should also be unit-testable.) Put another way, the design and implementation of the IR must help programmers detect when program semantics might not be conserved under a proposed transformation. If transformations mutate the IR, the mutations must provably exclude side-effects that could change semantics.


The meaning of an IR node B must depend (as much as possible) on the meaning of nodes directly connected to it by edges A -> B and B -> A. If a node depends for its meaning somehow on non-immediate neighbors, that coupling must either be fully present in the immediate neighbors, or carefully documented and respected by all transformations.


A suite of IRs used for optimizing compilation represents a wide range of constructs, from methods to bytecodes, down to simple operations and machine primitives. The implementation code, concepts, and terms for the IRs in a JVM toolchain should be as uniform as possible, to allow engineers to learn each IR (or each level of IR) more quickly by relying on common notions and notations. (This requirement does not force or rule out a single grand unified IR.)


Some optimizations can be adequately on at or near the granularity of source code or bytecode. IR should not be prematurely lowered to idealized RISC-level or machine level until after coarse grained or source-level optimizations are finished. (This requirement requires that an IR suite be multi-level, not necessarily a single grand unified IR.)


Causal dependencies in the IR must be represented and defended explicitly. Specifically, if an IR node A performs a side effect, it must be easy to locate the frontier of nodes B which are causally effected by the first node A. (This allows transforms which replace A to find and edit all affected nodes.)


The IR must allow optimization logic to require space and time within engineered limits. Theoretical complexity of algorithms should be limited to quasi-linear in size of whole input code. Basic node-level IR operations must be quasi-linear in node complexity. Graph-level IR operations (e.g., compute and cache derived dependencies or types) must be quasi-linear in graph complexity. (Quasi-linear means we can expect O(N × polylog N) for input size N almost always. More complex algorithms, e.g., quadratic or brute force, may be squeezed in but only for limited scales.)


The IR must be implemented with a reasonably small computation cost per size unit of input code, for expected optimization loads, including operations of creation, transformation, and traversal. The IR implementation should avoid excessively diffuse or pointer-rich data structures, excessive population or allocation rate of Java objects, and excessive method polymorphism. Compilation loads can always expand (via inlining or frequent recompilation) to absorb any resource budget, so more efficient optimization directly enables more pervasive optimization.


The IR must have an efficient implementation in Java. The Java API must be well documented and natural to use and extend in normal-looking Java code. (Note: This requirement could in principle be relocated to a different language such as C++, but is a natural one for working in the context of the JVM.)


The IR must support a human-readable representation that is readily available at any point.


The IR must support a serializable representation, for unit testing and (perhaps) live replay. Read and write methods must be high-fidelity. Binary and textual forms are desirable.


Compilation pipeline

IR graph nodes

IR graph edges

Node values


IR design considerations

IR types

Control flow