Lune

PLDI2025Top-tier venue

Webs and Flow-Directed Well-Typedness Preserving Program Transformations

Benjamin Quiring, David Van Horn, John H. Reppy, Olin Shivers

Abstract

We define webs to be the collections of producers and consumers ( e.g ., functions and calls) in a program that are constrained: in higher-order languages, multiple functions can flow to the same call, all of which must agree on an interface (e.g., calling convention). We argue that webs are fundamentally the unit of transformation : a change to one member requires changes across the entire web. We introduce a web-centric intermediate language that exposes webs as annotations, and describe web-based (that is, flow-directed) transformations guided by these annotations. As they affect all members of a web, these transformations are interprocedural, operating over entire modules. Through the lens of webs we reframe and generalize a collection of transformations from the literature, including dead-parameter elimination, uncurrying, and defunctionalization, as well as describe novel transformations. We contrast this approach with rewriting strategies that rely on inlining and cascading rewrites. Webs are an over-approximation of the semantic function-call relationship produced by control-flow analyses (CFA). This information is inherently independent from the transformations; more precise analyses permit more transformations. A limitation of precise analyses is that the transformations may not maintain well-typedness, as the type system is a less-precise static analysis. Our solution is a simple and lightweight typed-based analysis that causes the flow-directed transformations to preserve well-typedness, making flow-directed, type-preserving transformations easily accessible in many compilers. This analysis builds on unification, distinguishing types that look the same from types that have to be the same. Our experiments show that while our analysis is theoretically less precise, in practice its precision is similar to CFAs.

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. Demanded abstract interpretationBenno Stein, Bor-Yuh Evan Chang, Manu SridharanPLDI 2021 · 19 citations
  2. Generating Well-Typed Terms That Are Not "Useless"Justin Frank, Benjamin Quiring, Leonidas LampropoulosPOPL 2024 · 9 citations
  3. Better Defunctionalization through Lambda Set SpecializationWilliam Brandon, Benjamin Driscoll, Frank Dai, Wilson Berkow et al.PLDI 2023 · 7 citations

Related papers

  1. Improving Indirect-Call Analysis in LLVM with Type and Data-Flow Co-AnalysisDinghao Liu, Shouling Ji, Kangjie Lu, Qinming HeUSENIX Security 2024 · 13 citations
  2. Exact Recursive Probabilistic ProgrammingDavid Chiang, Colin McDonald, Chung-chieh ShanOOPSLA 2023 · 12 citations
  3. Defunctionalization with Dependent TypesYulong Huang, Jeremy YallopPLDI 2023 · 4 citations
  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. Type-Preserving Flat Closure OptimizationAdam T. Geller, Sean Bocirnea, Chester J. F. Gould, Paulette Koronkevich et al.OOPSLA 2025
Dusk over the sea between two cliffs drawn in fine vertical lines