Range-Analysis-Based Optimization for SML/NJ
summary
Range analysis runs on SML/NJ’s CPS IR using extended SSA in CPS and interval constraints to prove when overflow and array-bounds checks are unnecessary, with a hypergraph-based solver that applies SCC decomposition plus widening/narrowing. The implementation targets SML/NJ 2025.2 using LOVM, treats array lengths as symbolic bounds, falls back to LU for escaping calls, and uses an unsigned-comparison trick for subscripts; a microbenchmark shows a 57% speedup on 250k element array summation.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 2:11Range analysis history
- 5:01Extended SSA and CPS
- 6:49Interval lattice basics
- 9:59Abstract bounds and constraints
- 12:48Constraint generation
- 16:20Function join constraints
- 19:09Solving constraints
- 23:49Analysis for optimizations
- 26:21Implementation in SML/NJ 2025.2
- 27:47Future optimizations
- 28:10Q&A
related talks
21mFlow-Analysis-Based Closure Optimization
34mModernizing Standard ML of New Jersey: A Status Report
17mA New Match Compiler for Standard ML of New Jersey
15mScaling Optimization Over Uncertainty via Compilation
13mProgram Analysis via Efficient Symbolic Abstraction
11mExtending the Scope of the Array Abstraction beyond Sparsity
19mMinotaur: A SIMD-Oriented Synthesizing Superoptimizer
25mThe Road Not Taken: Exploring Alias Analysis Based Optimizations Missed by the Compiler