Compiler IR

Compiler IR (Intermediate Representation)

Compiler's internal representation of code with SSA form.

Overview

The Compiler IR (Intermediate Representation) provides JNode's JIT compilation pipeline with an optimized, architecture-independent representation of Java bytecode. It bridges the gap between the stack-based Java bytecode and the register-based x86 native machine code. The IR uses Static Single Assignment (SSA) form, where each variable is assigned exactly once, enabling precise data flow analysis and sophisticated optimizations.

The IR is primarily used by the L2 (Level 2) optimizing compiler, while the L1 compiler takes a faster, non-optimizing path directly from bytecode to native code. This tiered approach balances compilation speed with execution performance.

Key Components

Class / File	Role
core/src/core/org/jnode/vm/compiler/ir/IRControlFlowGraph.java	Main IR container - holds basic blocks, performs dominance analysis, SSA construction
core/src/core/org/jnode/vm/compiler/ir/IRBasicBlock.java	Single basic block with quads, predecessors/successors, dominance info
core/src/core/org/jnode/vm/compiler/ir/IRGenerator.java	Bytecode-to-IR translation - creates quads from bytecode instructions
core/src/core/org/jnode/vm/compiler/ir/Variable.java	Virtual register representation with SSA versioning
core/src/core/org/jnode/vm/compiler/ir/LinearScanAllocator.java	Register allocation using linear scan algorithm
core/src/core/org/jnode/vm/compiler/ir/RegisterPool.java	Physical register management during code generation
core/src/core/org/jnode/vm/compiler/ir/quad/Quad.java	Base class for all IR instructions (three-address code)
core/src/core/org/jnode/vm/compiler/ir/SSAStack.java	Stack-based helper for SSA variable renaming
core/src/core/org/jnode/vm/compiler/ir/PhiOperand.java	Represents phi functions for SSA merge points

How It Works

IR Construction Pipeline

The IR is built from Java bytecode through a multi-phase process:

1. Basic Block Identification: The BytecodeParser analyzes bytecode and identifies branch targets, exception handler entry points, and method entry to determine basic block boundaries. The IRBasicBlockFinder class collects these boundaries.

2. Control Flow Graph Building: The IRControlFlowGraph constructor creates an IRBasicBlock for each identified block and links them with predecessor/successor edges based on branch instructions.

3. Quad Generation: The IRGenerator walks the bytecode and emits corresponding IR quads. Each quad is a simple operation in three-address code form (e.g., result = op1 + op2). This transforms the stack-based bytecode into a flat sequence of operations.

4. Live Variable Analysis: Before optimization, the IR computes which variables are live at each program point using computeLiveVariables(). This information is critical for register allocation and dead code elimination.

SSA Transformation

The L2 compiler converts the IR to SSA form using these steps:

1. Dominance Analysis: Computes immediate dominators for each basic block using the algorithm in doComputeDominance(). This builds a dominator tree that identifies which blocks unconditionally execute before others.

2. Phi Placement: At dominance frontiers (blocks with multiple predecessors), phi functions are inserted to merge variable values from different control flow paths using placePhiFunctions().

3. Variable Renaming: The renameVariables() method traverses the dominator tree, assigning new SSA versions to each variable definition. The SSAStack tracks the current version at each point.

Optimization Passes

Once in SSA form, the L2 compiler runs several optimizations:

• Constant Folding: Quad.doPass2() evaluates expressions with known constant operands
• Dead Code Elimination: removeUnusedVars() removes assignments whose results are never used
• Copy Propagation: removeDefUseChains() eliminates unnecessary temporary variables

After optimization, deconstrucSSA() converts back from SSA form, replacing phi functions with explicit control flow code (copy assignments).

Register Allocation

The LinearScanAllocator assigns physical x86 registers to virtual registers based on live range analysis. When insufficient registers exist, it spills values to the stack frame, generating load/store instructions as needed.

Native Code Generation

The final phase translates optimized IR to x86 machine code. Each quad subclass implements generateCodeForX86() to emit appropriate instructions, handling register allocation results from the RegisterPool.

Gotchas & Non-Obvious Behavior

• IR is L2-only: The L1 compiler uses a completely different architecture that emits code as it parses bytecode, without building any IR graph. This is why L1 is fast but less optimized.

• Type inference from bytecode: Bytecode doesn't carry type information for local variables and stack slots. The IR generator must infer types from how values are used (e.g., if loaded as int, stored as int).

• SSA memory overhead: Converting to SSA form creates multiple versions of each variable, significantly increasing memory usage. This is acceptable for L2's optimize-then-compile approach but unsuitable for L1's quick compilation.

• Exception edges are critical: Exception handlers become basic blocks with specific dominance properties. The IR must correctly model these edges, or stack unwinding will fail.

• Stack slots are aliasable: Java's operand stack can hold multiple values simultaneously. The StackVariable class tracks these, and the IR must handle cases where the same stack slot holds different types at different times.

Related Pages

• JIT-Compilers — Overview of the tiered compilation pipeline
• L2-Compiler-Deep-Dive — Detailed look at the L2 optimizer that uses IR
• JIT-Compiler-IR — Related page on JIT IR implementation details
• L1-Compiler — The fast, non-optimizing compiler path
• Stack-Frame-Layout — Stack frame layout for compiled code