Lune

PLDI2026Top-tier venue

SSA without Dominance for Higher-Order Programs

Roland Leißa, Johannes Griebler

Abstract

Dominance is a fundamental concept in compilers based on static single assignment (SSA) form. It underpins a wide range of analyses and transformations and defines a core property of SSA: every use must be dominated by its definition. We argue that this reliance on dominance has become increasingly problematic—both in terms of precision and applicability to modern higher-order languages. First, control flow overapproximates data flow, which makes dominance-based analyses inherently imprecise. Second, dominance is well-defined only for first-order control-flow graphs (CFGs). More critically, higher-order programs violate the assumptions underlying SSA and classic CFGs: without an explicit CFG, the very notion that all uses of a variable must be dominated by its definition loses meaning. We propose an alternative foundation based on free variables. In this view, ϕ -functions and function parameters directly express data dependencies, enabling analyses traditionally built on dominance while improving precision and naturally extending to higher-order programs. We further present an efficient technique for maintaining free-variable sets in a mutable intermediate representation (IR). For analyses requiring additional structure, we introduce the nesting tree —a relaxed analogue of the dominator tree constructed from variable dependencies rather than control flow. Our benchmarks demonstrate that the algorithms and data structures presented in this paper scale log-linearly with program size in practice.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on3

  1. SSA Translation Is an Abstract InterpretationMatthieu LemerrePOPL 2023 · 7 citations
  2. Asymptotically Better Query Optimization Using Indexed AlgebraPhilipp Fent, Guido Moerkotte, Thomas NeumannVLDB 2023 · 5 citations
  3. MimIR: An Extensible and Type-Safe Intermediate Representation for the DSL AgeRoland Leißa, Marcel Ullrich, Joachim Meyer, Sebastian HackPOPL 2025 · 1 citation

Related papers

  1. Compiling with Abstract InterpretationDorian Lesbre, Matthieu LemerrePLDI 2024 · 6 citations
  2. Differentially-Private Control-Flow Node Coverage for Software Usage AnalysisHailong Zhang, Sufian Latif, Raef Bassily, Atanas RountevUSENIX Security 2020
  3. Flow-Analysis-Based Closure OptimizationJohn H. Reppy, Olin Shivers, Byron ZhongPLDI 2026 · 1 citation
  4. Graph IRs for Impure Higher-Order Languages: Making Aggressive Optimizations Affordable with Precise Effect DependenciesOliver Bracevac, Guannan Wei, Songlin Jia, Supun Abeysinghe et al.OOPSLA 2023 · 14 citations
  5. Efficient Abstract Interpretation via Selective WideningJiawei Wang, Xiao Cheng, Yulei SuiOOPSLA 2025
Dusk over the sea between two cliffs drawn in fine vertical lines