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:
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:
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:
- Push
aonto the stack. - Push
bonto the stack. - Push
conto the stack. - Perform multiplication, pop
bandc, and push the result onto the stack. - Perform addition, pop
aand 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
xon 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,
x2is selected. - If control enters from the second branch,
x3is 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:
x1depends onaandb.x2depends onx1andc.x3depends onx2andd.
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: