Intermediate Code Generation

In the architecture of a modern compiler, Intermediate Code Generation (ICG) serves as the critical bridge between the h

In the architecture of a modern compiler, Intermediate Code Generation (ICG) serves as the critical bridge between the high-level source language and the low-level machine code. Positioned after semantic analysis and before target code generation, this phase transforms the validated source program into an Intermediate Representation (IR). This IR is designed to be machine-independent (or weakly dependent), preserving the original semantics of the program while providing a structured format that is far more conducive to optimization than a raw Abstract Syntax Tree (AST).
Rather than being a mere stepping stone, the design of the IR is a strategic decision that dictates the efficiency and flexibility of the entire compiler. The primary objectives of using an IR include:

  • Facilitating Optimization: A well-structured IR allows the compiler to perform sophisticated transformations such as constant folding, common subexpression elimination, and dead code elimination. Because the IR is more regular than source code, these algorithms can be applied more effectively.
  • Enhancing Portability: By decoupling the "front-end" (which handles language-specific syntax and semantics) from the "back-end" (which handles machine-specific instruction sets), developers can support multiple architectures. A single front-end can generate a universal IR, which can then be consumed by different back-ends for various CPUs.
  • Reducing Complexity: ICG separates the concerns of language analysis from the complexities of hardware constraints (like register allocation and instruction scheduling). This modularity makes the compiler easier to design, maintain, and extend.
  • Supporting Multi-Language Ecosystems: A common IR allows different programming languages to share the same optimization and code generation infrastructure, significantly reducing the effort required to build new compilers.

The fundamental challenge in designing an IR lies in the trade-off between expressive power and generation efficiency. An IR that is too high-level may lack the granularity needed for deep optimization, while an IR that is too low-level may lose the semantic context necessary to perform meaningful transformations.

Common Forms of Intermediate Representation

There is no single "correct" way to represent intermediate code; instead, different compilers use different formats depending on their specific goals.

Three-Address Code (TAC)

Three-address code is perhaps the most widely recognized form of IR. In TAC, each instruction typically involves at most three operands: two for the source values and one for the result. The general format is:
x = y op z

Other common forms include:

  • x = op y (unary operations)
  • x = y (assignment)
  • goto L (unconditional jump)
  • if x relop y goto L (conditional jump)

TAC closely resembles assembly language but remains abstract by using symbolic names for variables and temporaries rather than physical registers.

Quadruples

A quadruple is a structured representation consisting of four fields: (op, arg1, arg2, result). For example, the expression a = b + c * d might be decomposed into:

  1. (*, c, d, t1)
  2. (+, b, t1, t2)
  3. (assign, t2, _, a)

The uniform structure of quadruples makes them highly efficient to store in arrays or tables, facilitating easy traversal during optimization.

Triples

To save space, triples reduce the number of fields to three: (op, arg1, arg2). Instead of explicitly naming a result variable, the result of an operation is referred to by its position (index) in the instruction sequence.
Example:

  • (0) (*, c, d)
  • (1) (+, b, (0))
  • (2) (assign, a, (1))

While triples are more compact, they present a significant drawback: if an instruction is moved during optimization, all subsequent references to its index must be updated, making instruction reordering difficult.

Indirect Triples

To mitigate the reordering issues of triples, indirect triples use a separate execution pointer table. The triples themselves remain in a fixed order, while the pointer table dictates the actual sequence of execution. This allows the compiler to reorder instructions by simply swapping pointers in the table, rather than rewriting the entire instruction set.

Control Flow Graphs (CFG) and Basic Blocks

For programs involving complex logic, IR is often organized into Basic Blocks. A basic block is a sequence of instructions with a single entry point (no jumps into the middle) and a single exit point (no jumps out except at the end). These blocks are then linked together to form a Control Flow Graph (CFG), where nodes represent basic blocks and edges represent the flow of control (jumps and branches). The CFG is the essential foundation for data-flow analysis and global optimization.

Static Single Assignment (SSA) Form

Modern high-performance compilers (like LLVM) heavily rely on Static Single Assignment (SSA). In SSA, every variable is assigned exactly once. If a variable is modified in the source code, the compiler creates a new version of that variable (e.g., $x_1, x_2, x_3$). When multiple control flow paths merge, a special $\phi$ (phi) function is used to select the correct version of the variable. SSA significantly simplifies many optimization tasks, such as constant propagation and dead code elimination, by making the relationship between definitions and uses explicit.

The Intermediate Code Generation Process

The generation of IR is typically integrated with the traversal of the Abstract Syntax Tree (AST). The process generally follows these steps:

  1. AST Traversal: The generator performs a recursive walk of the AST, processing expressions, statements, and declarations according to their hierarchical structure.
  2. Semantic Action Execution: As the generator visits nodes, it performs "semantic actions"—creating temporary variables and emitting the corresponding IR instructions.
  3. Symbol Table Management: The generator constantly interacts with the symbol table to verify variable types, check scopes, and determine memory requirements.
  4. Control Flow Handling: For constructs like if-else, while, or for loops, the generator emits labels and jump instructions to transform high-level logic into a linear sequence of instructions.
  5. Local Consistency Checks: The generator may perform final checks, such as ensuring type consistency or propagating array boundary information.

Example: Conditional Logic

Consider the following C code:
if (a < b) x = 1; else x = 2;

In Three-Address Code, this would be represented as:

t1 = a < b
if t1 goto L1
goto L2
L1: x = 1
goto L3
L2: x = 2
L3:

This transformation turns a high-level branching structure into a series of linear instructions and jumps, which can then be analyzed by the optimizer.

Conclusion: The Bridge to Optimization

Intermediate Code Generation is not an isolated phase; its quality directly impacts the performance of the entire compilation pipeline. An IR that generates an excessive number of temporary variables may increase register pressure in the back-end, while an IR that loses type information too early may prevent the optimizer from performing critical transformations.

Ultimately, the ICG acts as the vital link: it takes the high-level intent of the programmer and refines it into a structured, mathematical representation that the optimizer can manipulate and the back-end can eventually translate into efficient machine code.