Compiler Optimizations
Cera’s JIT compiler includes a multi-pass optimization pipeline that operates on an SSA-based intermediate language (IL). Optimizations are grouped into three levels that trade compilation speed for code quality.
Optimization Levels
| Level | Passes Included |
|---|---|
| O1 | Dead Code Elimination, Constant Folding, Copy Propagation |
| O2 | O1 + Common Subexpression Elimination, Constant Propagation, Branch Optimization |
| O3 | O2 + Function Inlining, Loop Invariant Code Motion |
Optimization Passes
Dead Code Elimination (DCE)
Mark-sweep algorithm on SSA form. All instructions are initially marked as dead. Instructions with observable side effects (returns, stores, calls) are marked as live, and liveness is propagated backward through operand definitions. Unmarked instructions and unreachable blocks are removed.
Constant Folding
Evaluates constant expressions at compile time:
- Arithmetic:
3 + 4becomes7 - Comparisons:
5 > 3becomestrue - Type conversions:
int_to_float(42)becomes42.0 - Branch simplification:
if (true)eliminates the dead branch entirely
Constant Propagation
Propagates known constant values through the program. When a variable or PHI node has all incoming values equal to the same constant, its uses are replaced with that constant. Works in conjunction with Constant Folding.
Copy Propagation
Replaces uses of copies with the original value. Detects identity operations like t1 = t0 and eliminates the copy, updating all uses of t1 to reference t0 directly. Resolves copy chains transitively.
Common Subexpression Elimination (GVN)
Global Value Numbering assigns identical expressions the same value number. When two instructions compute the same expression (e.g., a + b appears twice), the second is replaced with a reference to the first result. Processes blocks in dominator-tree order.
Loop Invariant Code Motion (LICM)
Identifies instructions inside loops whose operands are all defined outside the loop. These loop-invariant computations are hoisted to a preheader block, executing once instead of every iteration.
Function Inlining
Replaces function calls with the callee’s body. Uses size-based heuristics:
| Category | Threshold |
|---|---|
| Tiny leaf functions | Always inlined (< 32 bytes) |
| Single call-site | Inlined (< 50 bytes) |
| Frequently called leaf | Inlined (≥ 3 call sites, < 64 bytes) |
| General | code_size < 80 - depth * 25 |
Recursive, async, and closure-capturing functions are never inlined. Maximum inlining depth is 3.
Branch Optimization
Two-phase optimization:
IL phase — Computes edge probabilities using Ball-Larus-inspired heuristics:
| Pattern | Probability |
|---|---|
| Loop back-edge | 96% taken |
| Loop exit | 4% taken |
if likely (...) | 95% taken |
if unlikely (...) | 5% taken |
| Null check (non-null path) | 75% taken |
| Default | 50% |
Machine IR phase — Reorders basic blocks so the hot path falls through without extra jumps. Inverts branch conditions when the likely successor isn’t the layout-next block. Eliminates dead unconditional jumps.
SSA Destruction
Eliminates PHI nodes by inserting parallel copy instructions at the end of predecessor blocks. Handles copy cycles using temporary variables. This runs as the final pass before code generation.
Code Generation Optimizations
Jump Table Switch
Dense integer switch statements (≥ 4 cases, ≥ 50% density, range ≤ 1024) are compiled to a jump table instead of a linear comparison chain. The table stores relative offsets indexed by the normalized case value, giving O(1) dispatch.
// Compiled as a jump table — single indexed lookupswitch (day){ case 0: return "Mon"; case 1: return "Tue"; case 2: return "Wed"; case 3: return "Thu"; case 4: return "Fri"; default: return "Weekend";}Sparse switches fall back to a linear CMP + conditional jump chain.
Leaf Function Optimization
Functions that meet all of these criteria skip prologue/epilogue generation entirely:
- Expression-body syntax
- No parameters
- Leaf function (no function calls)
- Not a method
This saves 9-13 bytes per function.
Tail Call Optimization
Self-recursive tail calls reuse the current stack frame. When the last operation in a function is a call to itself, the compiler shuffles arguments and jumps back to the function entry instead of creating a new stack frame.
Branch Prediction Hints
if likely and if unlikely annotations propagate through to x86-64 branch hint prefixes (0x3E and 0x2E) and influence block layout during branch optimization.
Register Allocation
Linear scan register allocation assigns physical registers to IL temporaries based on liveness intervals. Spill slots are allocated on the stack when register pressure exceeds available registers.
Pass Infrastructure
The Pass Manager orchestrates optimization passes with:
- Dependency-based scheduling (topological sort)
- Iterative fixed-point execution until no pass reports changes
- Automatic CFG rebuilding when passes invalidate the control flow graph
- Per-pass statistics collection (functions changed, instructions eliminated, etc.)