Intermediate Representation (IR)

An IR sits between the high-level source code and low-level machine code. Its abstraction level is a primary design choice. High-Level IRs (HIR) retain rich source-level semantics (e.g., types, control structures), while Low-Level IRs (LIR) resemble assembly with virtual registers and explicit data flow. The choice determines which optimizations are feasible; HIRs enable complex loop transformations, while LIRs facilitate precise register allocation and instruction scheduling.

IRs are structurally categorized by their representation. Graph-based IRs, like LLVM's SSA form or a Control Flow Graph (CFG), explicitly model data dependencies and program flow as nodes and edges, enabling powerful global optimizations. Linear IRs, resembling pseudo-assembly lists, are simpler and faster to process for local transformations. Modern compilers often use multiple forms, lowering from graph to linear representations in later stages.

Single Static Assignment is a pivotal property of many modern IRs where each variable is assigned exactly once. It simplifies data-flow analysis by making def-use chains explicit. Phi (φ) functions are inserted at control flow merge points to select the correct variable version. This form enables powerful optimizations like:

• Constant Propagation
• Dead Code Elimination
• Global Value Numbering LLVM IR and GCC's GIMPLE are prominent SSA-based IRs.

A core purpose of an IR is to be architecture-agnostic. It abstracts away hardware specifics like register counts, instruction sets, and memory addressing modes. This allows a frontend (e.g., for C++, Rust) to generate the same IR, and a backend to lower it to various targets (x86, ARM, NPU). The IR defines a set of virtual instructions and abstract resources that backends map to concrete hardware, separating machine-independent optimizations from target-specific code generation.

The IR is the substrate for all compiler optimizations. Its design dictates which transformations are natural and efficient. Common IR-level optimizations include:

• Loop-Invariant Code Motion: Hoists computations outside loops.
• Common Subexpression Elimination (CSE): Removes redundant calculations.
• Instruction Combining: Fuses adjacent operations (e.g., add+load).
• Inlining: Replaces function calls with the function body. A well-designed IR makes these analyses straightforward and the transformations safe and correct.

Sophisticated compilers use a series of IRs in a lowering pipeline. A program may progress from an Abstract Syntax Tree (AST) to a High-Level IR (HIR), then to a Mid-Level IR (MIR) in SSA form for optimizations, and finally to a Low-Level IR (LIR) or Machine IR for register allocation and instruction selection. Each stage reduces abstraction and incorporates more target-specific information, enabling a phased optimization strategy where high-level semantics are gradually refined into executable code.

A hierarchical tree representation of the source code's syntactic structure, where each node denotes a construct (e.g., a loop, an assignment). The AST preserves the nesting and order of the original program, making it ideal for high-level semantic analysis and refactoring but often too verbose for low-level optimizations.

• Key Use: Syntax checking, macro expansion, and initial semantic analysis.
• Limitation: Contains syntactic sugar and is closely tied to the source language.

A linear, low-level IR where each instruction typically has at most one operator and three operands (e.g., t1 = b + c). It breaks down complex expressions into simple instructions, making data flow and dependencies explicit for optimization passes.

• Key Characteristics: Uses temporary variables to hold intermediate values.
• Common Form: Often represented as quadruples (op, arg1, arg2, result).
• Optimizations Enabled: Common subexpression elimination, constant propagation, and copy propagation work directly on this form.

An IR property where each variable is assigned exactly once, and new versions (denoted by subscripts, e.g., x1, x2) are created at each assignment. Phi (φ) functions are inserted at control flow merge points to select the correct variable version.

• Primary Benefit: Makes def-use chains explicit and trivial, dramatically simplifying many optimizations.
• Critical Optimizations: SSA enables sparse conditional constant propagation and global value numbering efficiently.
• Industry Standard: Used in LLVM IR and the GCC GIMPLE IR.

A directed graph representation of a program where nodes represent basic blocks (sequences of instructions with a single entry and exit point) and edges represent possible control flow transfers (jumps, branches). It is not a standalone IR but a critical data structure built on top of a linear IR like TAC.

• Fundamental Purpose: Enables analysis and optimization of program flow, such as dead code elimination, loop detection, and dominance analysis.
• Core Concept: The foundation for understanding loops, dominance frontiers, and data flow analysis.

An IR that represents a program as a graph where nodes are operations (or values) and edges represent data dependencies and control dependencies. This representation merges the CFG and data flow graph, making implicit parallelism and scheduling constraints explicit.

• Key Advantage: Allows highly flexible, semantics-preserving code motion and optimization scheduling.
• Use in Industry: Forms the basis for the Java HotSpot Server Compiler (C2) and Google's V8 TurboFan JIT compiler.
• Ideal For: Just-in-time compilers and aggressive instruction scheduling.

A compiler optimization that merges multiple, separate computational kernels into a single, larger kernel. This reduces the overhead of repeated kernel launches and eliminates costly intermediate data transfers between global memory and on-chip storage.

• Primary Benefit: Minimizes memory bandwidth pressure, a critical bottleneck for NPU performance.
• Example: Fusing a convolution, bias addition, and ReLU activation into one kernel, avoiding writing the convolution output to memory only to immediately read it back.

A class of compiler transformations applied to nested loops within an IR to maximize data locality, parallelism, and hardware resource utilization. Key techniques include:

• Loop Tiling: Partitions iteration space to fit working sets into faster cache/scratchpad memory.
• Loop Interchange: Reorders loops to enable memory coalescing and stride-1 accesses.
• Loop Unrolling: Replicates loop body to reduce control overhead and expose Instruction-Level Parallelism (ILP). LNO is essential for transforming high-level tensor operations into efficient, hardware-aware low-level code.

An IR-level optimization that identifies and eliminates redundant computations of identical expressions. When the same value is calculated multiple times, CSE computes it once, stores the result in a temporary variable, and reuses it.

• Impact: Reduces unnecessary arithmetic operations and register pressure.
• IR Context: Works on the compiler's internal representation before code generation, analyzing dataflow to find identical expression trees.
• Example: Replacing multiple occurrences of (a * b) + c in a basic block with a single calculation.

An optimization that removes code which does not affect the program's observable output. This includes:

• Unreachable Code: Statements that can never be executed (e.g., after an unconditional return).
• Dead Stores: Computations whose results are never read by subsequent instructions. Performed on the IR, DCE reduces binary size, saves execution time, and can enable further optimizations by simplifying the control and data flow graphs.

A two-phase compilation technique that uses runtime profiling data to guide IR optimizations. First, the compiler instruments the code to collect data on branch frequency, hot code paths, and value ranges. Second, it recompiles using this profile to make informed decisions.

• Key Optimizations: Aggressive inlining of hot functions, improved branch prediction, and better block layout for cache locality.
• Use Case: Critical for optimizing AI inference engines where execution patterns are stable and known.

A compilation strategy where code is translated from an IR or bytecode to native machine code at runtime, immediately before execution. This enables optimizations that are impossible in a static, ahead-of-time (AOT) compiler.

• Advantages: Can specialize kernels based on runtime data shapes (concrete tensor dimensions) or target specific hardware features detected at launch.
• Trade-off: Introduces compilation overhead at runtime, which is often amortized over repeated kernel executions in frameworks like PyTorch or TensorFlow.