Back to series
· 11 min read

Intermediate Representation (IR)


1. What Is an Intermediate Representation (IR)

An Intermediate Representation (IR) is an internal program representation used by a compiler while it processes source code.

Source code usually carries strong language-specific characteristics, for example:

int result = a + b * c;

If a compiler generated x86 machine instructions directly from C source code, the code generation process would have to handle all of the following at once:

  • The syntactic structure of the C language.
  • The C type system.
  • The evaluation rules of expressions.
  • Variables and scopes.
  • The x86 instruction set.
  • Register allocation.
  • Memory layout.
  • The calling conventions of the target platform.

This approach makes the compiler frontend and backend highly coupled.

The core idea of IR is: first convert the source code into an intermediate form that is better suited to compiler processing, then perform optimization and target code generation based on that form.

For example:

int result = a + b * c;

can be converted into IR similar to three-address code:

t1 = b * c
t2 = a + t1
result = t2

At this point the IR no longer depends on the concrete syntactic form of the C language; instead, it expresses the computation as explicit operations.

The core value of IR lies in decoupling the programming language from the target machine, so that the compiler can reuse its analysis, optimization and code generation capabilities.

2. Why Compilers Need IR

2.1 Solving the Coupling Problem Between Frontend and Backend

Suppose a compiler needs to support:

  • C
  • C++
  • Rust
  • Swift

and at the same time needs to generate code for:

  • x86-64
  • ARM64
  • WebAssembly

If a code generator were developed directly for every target architecture from every language, a large number of combinations would have to be maintained.

For example:

Source Language x86-64 ARM64 WebAssembly
C Separate backend Separate backend Separate backend
C++ Separate backend Separate backend Separate backend
Rust Separate backend Separate backend Separate backend
Swift Separate backend Separate backend Separate backend

With M source languages and N target architectures, the size of a directly combined implementation may approach:

M \times N

Once a unified IR is introduced, frontends for different languages can generate IR, and backends for different target architectures can then process that IR.

flowchart TB
    subgraph Frontend["Compiler Frontend"]
        A["C Frontend"]
        B["C++ Frontend"]
        C["Rust Frontend"]
        D["Swift Frontend"]
    end

    E["Unified Intermediate Representation IR"]

    subgraph Backend["Compiler Backend"]
        F["x86-64 Backend"]
        G["ARM64 Backend"]
        H["WebAssembly Backend"]
    end

    A --> E
    B --> E
    C --> E
    D --> E

    E --> F
    E --> G
    E --> H

    style A fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style D fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style E fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style F fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style G fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style H fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

In this way, the frontend only needs to be responsible for converting the language into IR, and the backend only needs to be responsible for converting IR into code for the target platform.

With M frontends and N backends, the core adaptation relationships can change from a large number of pairwise combinations into separately maintained frontend and backend interfaces, and the overall scale approaches:

M + N

In real-world engineering, the semantic differences between languages and the characteristics of target platforms still require dedicated handling, but IR significantly reduces the cost of system integration.

2.2 Providing a Unified Foundation for Optimization

Different programming languages may have different syntax, but many low-level computational operations are similar.

For example:

int result = a * 2 + 10;
let result = a * 2 + 10;
int result = a * 2 + 10;

These code snippets differ at the language level, but they can be converted into a similar intermediate computational structure.

A compiler can perform the following uniformly at the IR level:

  • Constant folding.
  • Constant propagation.
  • Dead code elimination.
  • Common subexpression elimination.
  • Loop optimization.
  • Instruction scheduling.
  • Data-flow analysis.

This way, there is no need to reimplement all the low-level optimization algorithms for every programming language.

2.3 Supporting Multi-Stage Compilation and Optimization

IR usually does not come in only one form.

A compiler can use IR at different levels of abstraction at different stages:

  • High-level IR: preserves the structure and semantics of the high-level language.
  • Mid-level IR: highlights control flow, data flow, and computational operations.
  • Low-level IR: closer to machine instructions and hardware resources.

Each IR layer focuses on different optimization problems.

flowchart TB
    A["Source Code"]
    B["High-level IR"]
    C["Mid-level IR"]
    D["Low-level IR"]
    E["Target Machine Code"]

    A --> B
    B --> C
    C --> D
    D --> E

    style A fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style C fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style E fill:#FFF5DE,stroke:#E8D29A,color:#334155
    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

Not every compiler has to use three layers of IR, nor is all IR organized according to a strict high, mid, low hierarchy. This is simply a common design approach.

3. Basic Components of IR

The specific structure of IR depends on the compiler design, but it usually needs to express the computation, data, control flow, and type information in a program.

3.1 Instructions

An instruction represents a specific operation in a program.

For example:

t1 = a + b
t2 = t1 * c

can be broken down as:

Instruction Operation Operands Result
t1 = a + b ADD a, b t1
t2 = t1 * c MUL t1, c t2

Different IRs design their instructions differently.

Some IRs use explicit opcodes, such as add, mul, load, store; others use higher-level operations, such as function calls, object creation, and exception handling.

3.2 Operands

Operands are the data required for an instruction to execute.

Common operands include:

Type Example Description
Constant 10 Fixed value
Variable count Program variable
Temporary value %1, t1 Intermediate computation result
Function argument arg0 Function input
Memory address ptr Memory access location
Global symbol global_var Global variable or symbol

For example:

%3 = add i32 %1, %2

where:

  • %3: the result value.
  • add: the addition operation.
  • i32: the operand type.
  • %1, %2: the input operands.

This is an instruction representation in the LLVM IR style.

3.3 Basic Blocks

A basic block is an important structure in a control-flow graph.

It is a contiguous sequence of instructions with a single entry and a single exit.

Typically:

  • Control flow can only enter through the entry of the basic block.
  • The instructions inside a basic block execute in order.
  • Control flow leaves through the terminator instruction at the end of the basic block.

For example:

entry:
    t1 = a + b
    t2 = t1 * c
    return t2

This sequence of instructions can form a basic block.

If a program contains conditional judgments, it is usually divided into multiple basic blocks.

3.4 Control Flow Graph (CFG)

A control flow graph uses a graph structure to describe program execution paths.

Nodes usually represent basic blocks, and edges represent possible control transfers between basic blocks.

For example:

if (x > 0) {
    y = x + 1;
} else {
    y = x - 1;
}
return y;

It can be divided into:

  • Condition check block.
  • True branch.
  • False branch.
  • Return block after the branches merge.
flowchart TB
    A["Entry"]
    B["Check x > 0"]
    C["y = x + 1"]
    D["y = x - 1"]
    E["return y"]
    F["Exit"]

    A --> B
    B -->|"True"| C
    B -->|"False"| D
    C --> E
    D --> E
    E --> F

    style A fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    style B fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style E fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style F fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

Control flow graphs are an important foundation for program analysis and optimization in compilers.

For example:

  • Determine whether a basic block is reachable.
  • Analyze loop structures.
  • Compute dominance relations.
  • Analyze data flow.
  • Perform dead code elimination.

3.5 Type Information

IR usually needs to explicitly represent data types.

For example:

%1 = add i32 %a, %b
%2 = add float %x, %y

Both instructions represent addition, but the operand types are different.

Type information can help the compiler determine:

  • Whether an instruction is valid.
  • The type of the result of an operation.
  • Data width.
  • Whether type conversion is needed.
  • How to select target machine instructions.

The type systems of different IRs vary greatly.

For example, LLVM IR uses an explicit type system, while some low-level IRs may rely more on machine-level data widths and operation constraints.

4. Main Categories of IR

IR can be classified along different dimensions.

The most common classification method is to distinguish them by their data structures and levels of abstraction.

4.1 Tree-based IR

Tree-based IR uses a tree structure to represent program computation relationships.

For example:

a + b * c

It can be represented as:

      +
     / \
    a   *
       / \
      b   c

Tree structures are suitable for expressing:

  • Nested expressions.
  • Operator precedence.
  • Computation dependencies.
  • High-level program structures.

An AST is a typical tree representation, but an AST is not completely equivalent to all tree-based IRs.

Some tree-based IRs perform further normalization on top of the AST, making expressions more suitable for optimization or code generation.

4.2 Three-Address Code (TAC)

Three-address code is a common linear IR.

It usually splits complex expressions into multiple simple instructions, each containing at most three address-related parts:

  • One result address.
  • Two source operand addresses.

For example:

result = a + b * c;

It can be converted to:

t1 = b * c
t2 = a + t1
result = t2

Here, t1 and t2 are temporary variables generated by the compiler.

The main advantages of three-address code are:

  • Simple instruction structure.
  • Clear computation order.
  • Easy to perform local optimization.
  • Convenient to convert to machine instructions.
  • Convenient for analyzing data dependencies.

Note that three-address code is an abstract form and does not require every instruction to strictly contain three addresses. Instructions such as assignment, jump, and function call usually have different operand forms.

4.3 Stack-based IR

Stack-based IR uses an operand stack to hold intermediate computation results.

For example:

a + b * c

It can be represented as:

PUSH a
PUSH b
PUSH c
MUL
ADD

Execution process:

  1. Push a onto the stack.
  2. Push b onto the stack.
  3. Push c onto the stack.
  4. Perform multiplication, pop b and c, and push the result onto the stack.
  5. Perform addition, pop a and the multiplication result, and push the final result onto the stack.

Characteristics of stack-based IR:

  • Instructions usually do not need to explicitly specify all operands.
  • Operands are passed implicitly through the top-of-stack position.
  • Instruction encoding can be relatively compact.
  • Execution requires maintaining the operand stack state.

Java bytecode and WebAssembly both have obvious stack-based operation characteristics, but they are not exactly the same IR and also have their own types, control flow, and validation rules.

4.4 SSA Form (Static Single Assignment)

SSA (Static Single Assignment) is a very important IR representation.

It requires that each variable be assigned only once in the static program representation.

For example, in ordinary form:

x = 10
x = x + 1
x = x * 2

Converted to SSA form:

x1 = 10
x2 = x1 + 1
x3 = x2 * 2

Each assignment produces a new variable version.

This allows data dependencies to be expressed explicitly.

SSA form is an important foundation for optimization in modern compilers.

V. How Three-Address Code Works

Three-address code is one of the most intuitive ways to understand IR.

5.1 Splitting Complex Expressions into Simple Instructions

Consider:

int result = (a + b) * (c - d);

The original expression contains:

  • Addition.
  • Subtraction.
  • Multiplication.
  • The final assignment.

Converted to three-address code:

t1 = a + b
t2 = c - d
t3 = t1 * t2
result = t3

The complex expression is split into multiple simple calculation steps.

5.2 The Role of Temporary Variables

Temporary variables are used to hold intermediate calculation results.

For example:

t1 = a + b
t2 = t1 * c
t3 = t2 - d

Temporary variables can help the compiler:

  • Make calculation dependencies explicit.
  • Analyze data flow.
  • Determine variable lifetimes.
  • Perform register allocation.
  • Perform common subexpression elimination.

Temporary variables do not necessarily correspond to real memory variables in the final machine code.

In subsequent optimizations, the compiler may map them directly to registers or even eliminate them entirely.

5.3 Instruction Types of Three-Address Code

Common instructions include:

Instruction category Example Purpose
Arithmetic operations t1 = a + b Addition, subtraction, multiplication, division
Logical operations t1 = a && b Logical operation
Comparison operations t1 = a > b Conditional evaluation
Assignment operations x = t1 Data assignment
Conditional jump if t1 goto L1 Conditional branching
Unconditional jump goto L2 Control transfer
Function call call foo Call a function
Return operation return t1 Function return
Memory access t1 = load p Read from memory
Memory write store t1, p Write to memory

The IR instruction sets of different compilers are not exactly the same.

VI. SSA: Static Single Assignment Form

SSA is an extremely important IR form in modern compilers.

Understanding SSA requires grasping two core concepts:

  • Each variable is defined only once.
  • Use special merge nodes to handle values produced by different control-flow paths.

6.1 Why SSA Is Needed

Consider:

int x = 10;

if (condition) {
    x = 20;
} else {
    x = 30;
}

return x;

In ordinary variable representation, x is assigned multiple times on different paths.

The compiler needs to analyze:

  • What is the value of x on the current path?
  • Which assignment affects the final return result?
  • How are assignments from different paths merged?

SSA converts each assignment into an independent version:

x1 = 10

if condition:
    x2 = 20
else:
    x3 = 30

x4 = phi(x2, x3)

return x4

Here, x4 is produced by the Phi function.

6.2 Phi Function (φ Function)

The Phi function is used at a control-flow merge point to select the corresponding variable value according to the actual execution path.

For example:

x4 = phi(x2, x3)

means:

  • If control enters from the first branch, x2 is selected.
  • If control enters from the second branch, x3 is selected.

The Phi function is not an ordinary mathematical function call.

It represents a data-selection relationship at a control-flow merge point.

It can be understood with the following structure:

flowchart TB
    A["Entry"]
    B["Check condition"]
    C["x2 = 20"]
    D["x3 = 30"]
    E["x4 = phi(x2, x3)"]
    F["return x4"]

    A --> B
    B -->|"True"| C
    B -->|"False"| D
    C --> E
    D --> E
    E --> F

    style A fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    style B fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style E fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style F fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

The arguments of a Phi function are associated with the predecessor basic blocks of the control flow, rather than directly executing a function call according to an ordinary runtime conditional expression.

In concrete SSA implementations, the operands of a Phi node are usually organized according to the corresponding predecessor basic blocks.

6.3 Core Advantages of SSA

SSA makes the relationship between variable definitions and uses clearer.

For example:

x1 = a + b
x2 = x1 * c
x3 = x2 + d

From this, one can directly obtain:

  • x1 depends on a and b.
  • x2 depends on x1 and c.
  • x3 depends on x2 and d.

This explicit data-dependency relationship facilitates:

  • Constant propagation.
  • Dead code elimination.
  • Common subexpression elimination.
  • Global value numbering.
  • Data-flow analysis.
  • Variable liveness analysis before register allocation.

SSA does not mean that each variable can be modified only once when the program runs. What it constrains is the form of definitions in the compiler's static representation, not the runtime behavior of variables in the source language.

7. IR Optimization Techniques

One of the important values of IR is that it provides a unified foundation for compiler optimization.

Common optimizations include:

7.1 Constant Folding

If all operands in an expression are constants known at compile time, the compiler can compute the result in advance.

Before optimization:

t1 = 10 * 20
t2 = t1 + 5

After optimization:

t2 = 205

Constant folding reduces runtime computation.

7.2 Constant Propagation

If the compiler can determine the value of a variable, it can propagate that value to subsequent use sites.

Before optimization:

x = 10
y = x + 5
z = y * 2

After optimization:

x = 10
y = 15
z = 30

Constant propagation and constant folding are often used together.

7.3 Common Subexpression Elimination

If the same expression is computed repeatedly, and the relevant operands do not change between the two computations in a way that affects the result, the previous computation result can be reused.

Before optimization:

t1 = a * b
t2 = a * b
result = t1 + t2

After optimization:

t1 = a * b
result = t1 + t1

This optimization can reduce repeated computation.

However, one cannot assume that reuse is valid merely because the expression text is the same. Factors such as memory reads and writes, side effects, floating-point arithmetic rules, and exception behavior may all affect whether the optimization is legal.

7.4 Dead Code Elimination

If the result of an instruction will never be used, and the instruction has no side effects that must be preserved, it can be deleted.

Before optimization:

t1 = a + b
t2 = c * d
return t1

If t2 is not used elsewhere and the computation has no side effects:

t1 = a + b
return t1

Note that function calls, memory writes, exception triggering, and synchronization operations may have side effects and cannot simply be deleted just because their return values are unused.

7.5 Strength Reduction

Replace more expensive operations with equivalent lower-cost operations.

For example, provided that integer semantics and overflow rules are satisfied:

x = i * 8

it may be transformed into:

x = i << 3

On modern processors, multiplication instructions are not necessarily slower than shift instructions, so whether a compiler performs this transformation must be judged in light of the target architecture and cost model.

7.6 Loop Optimization

Loops are often an important part of a program's execution time.

A compiler can perform the following on loops:

  • Loop-invariant code motion.
  • Loop unrolling.
  • Loop fusion.
  • Loop vectorization.
  • Induction variable optimization.

For example:

for (int i = 0; i < n; i++) {
    int factor = a * b;
    result[i] = factor + i;
}

If a and b do not change during loop execution, the compiler can move the multiplication computation outside the loop.

After optimization:

int factor = a * b;

for (int i = 0; i < n; i++) {
    result[i] = factor + i;
}

This type of optimization is called Loop-Invariant Code Motion.

8. The Overall Process of IR Optimization

A compiler usually does not perform optimization only once; rather, it runs multiple optimization passes.

Each pass is responsible for a certain kind of analysis or transformation.

For example: