Compiler Pass Interaction and Adaptation

Experiment: exp_compiler_passes.sx  |  Validates: Theorems 9, 10 (Compiler Optimisation)

Hypothesis

Compiler optimisation passes (inline, unroll, SIMD vectorise, dead code elimination) interact in program-dependent ways that can be discovered by the interaction matrix. Per-program adaptation should outperform a fixed pass ordering. The convergence score \(S\) can serve as a stopping criterion for iterative pass application.

Method

1. Passes: 4 compiler passes operating on a 6-dimensional cost vector (instruction count, branch count, memory ops, register pressure, code size, estimated cycles).
2. Programs: Three program archetypes:
   • Loop-heavy: nested loops, high iteration counts
   • Call-heavy: deep call chains, many small functions
   • Math-heavy: arithmetic-intensive, few branches
3. Run pass interaction discovery for each program type. Measure the \(4 \times 4\) interaction matrix \(\alpha_{ij}\).
4. Apply iterative pass scheduling with \(S\)-based stopping: halt when \(S < 0.001\).

Results

Per-Program Interaction Matrices

Loop-Heavy Program

Unroll and inline cooperate (\(\alpha = 0.42\)). SIMD is independent (\(\alpha = 0\) with all others) because the loop structure does not benefit from vectorisation.

Call-Heavy Program

Inline and DCE cooperate strongly (\(\alpha = 0.67\)): inlining exposes dead code. SIMD is again independent (\(\alpha = 0\)).

Math-Heavy Program

All passes have \(\alpha = 0\) with SIMD. The math operations are scalar; vectorisation provides no benefit. Inline and unroll cooperate weakly (\(\alpha = 0.22\)).

SIMD Independence

Across all three program types, SIMD has \(\alpha = 0\) with every other pass. This is correct: SIMD operates on data parallelism orthogonal to control-flow transformations (inline, unroll, DCE).

Convergence Stopping

\(S < 0.001\) is reached by cycle 17 at the latest. Continuing beyond this point yields no further improvement (verified by running to cycle 50 with 0% additional gain).

Fixed vs Adaptive Ordering

Analysis

• The interaction matrix correctly identifies pass dependencies: inline+DCE cooperate in call-heavy code, inline+unroll cooperate in loop-heavy code, and SIMD is universally independent of control-flow passes.
• Per-program adaptation outperforms fixed ordering by 8 percentage points on average. The largest gain is on call-heavy programs where inline-then-DCE is critical.
• \(S < 0.001\) is a reliable stopping criterion: it stops iteration precisely when no further improvement is possible, avoiding wasted compile time.
• The 6D cost vector provides richer information than a scalar cost, enabling the interaction matrix to distinguish cooperation along different dimensions (e.g., inline reduces branch count but increases code size).

Conclusion

Theorems 9 and 10 are validated. Compiler pass interactions are program-dependent and discoverable by the interaction matrix. Adaptive pass scheduling outperforms fixed ordering. \(S\) provides an effective stopping criterion for iterative compilation.

Reproducibility

../simplex/build/sxc exp_compiler_passes.sx -o build/exp_compiler_passes.ll

OPENSSL_PREFIX=$(brew --prefix openssl)
clang -O2 build/exp_compiler_passes.ll \
  ../simplex/runtime/standalone_runtime.c \
  -o build/exp_compiler_passes \
  -lm -lssl -lcrypto -L${OPENSSL_PREFIX}/lib

./build/exp_compiler_passes

Related Theorems

• Theorem 9 — Compiler Pass Interaction
• Theorem 10 — Adaptive Pass Scheduling
• Theorem 8 — Code Gate Convergence
• Theorem 4 — Interaction Matrix