Intermediate representation

An intermediate representation is a representation of a program that sits between the source and target languages in a compiler pipeline. Its primary purpose is to decouple front-end analysis from back-end code generation, allowing a single IR to serve multiple source languages and multiple target architectures. This design enables retargetable compilers and facilitates machine-independent optimizations. IRs are typically typed and may be structured as graphs or linear instruction sequences. They must preserve the semantics of the original program while exposing opportunities for optimization, such as dead code elimination and constant propagation.

IRs vary in abstraction level. High-level IRs, like abstract syntax trees (ASTs) and control-flow graphs, retain source-level constructs and are easy to analyze for type checking and early optimizations. Low-level IRs, such as three-address code and register transfer language (RTL), resemble target machine instructions and are used for register allocation and instruction selection. Many compilers use a sequence of IRs, gradually lowering from high to low level. Static single assignment (SSA) form is a popular low-level IR that simplifies dataflow analysis by ensuring each variable is assigned exactly once, with phi functions merging values at control-flow joins.

Several IRs have become influential. The LLVM IR is a well-known low-level IR used by the LLVM compiler infrastructure, supporting both C-like and functional languages, and enabling aggressive optimizations. The Java Virtual Machine (JVM) bytecode and Microsoft's Common Intermediate Language (CIL) are stack-based IRs for managed execution environments. GCC uses a series of IRs, including GENERIC and GIMPLE, to handle multiple front-ends and back-ends. The Glasgow Haskell Compiler (GHC) uses Core, a small typed lambda calculus, and STG (Spineless Tagless G-machine) for functional languages. These IRs illustrate the trade-offs between expressiveness and optimization power.

Beyond mainstream compilers, IRs appear in specialized contexts. For example, the Ethereum Virtual Machine (EVM) uses a stack-based bytecode IR for smart contracts, and the WebAssembly (Wasm) format serves as a portable IR for web browsers. In high-performance computing, the OpenCL C kernel language is compiled to an IR called SPIR-V, which is used across GPU vendors. Historically, the UNCOL (Universal Computer Oriented Language) proposal in the 1950s envisioned a universal IR for all machines, though it was never realized. Some IRs are designed for specific analysis, such as the Program Dependence Graph (PDG) used in parallelization. The concept of IR also extends to query languages, like the relational algebra used in database query optimization.

Abstract syntax tree

A tree representation of the syntactic structure of source code.

Static single assignment

A property of an IR where each variable is assigned exactly once.

Three-address code

A low-level IR where each instruction has at most three operands.