Pushdown control-flow analysis for free

Academic Article


  • Traditional control-flow analysis (CFA) for higher-order languages introduces spurious connections between callers and callees, and different invocations of a function may pollute each other's return flows. Recently, three distinct approaches have been published that provide perfect call-stack precision in a computable manner: CFA2, PDCFA, and AAC. Unfortunately, implementing CFA2 and PDCFA requires significant engineering effort. Furthermore, all three are computationally expensive. For a monovariant analysis, CFA2 is in O(2n), PDCFA is in O(n6), and AAC is in O(n8). In this paper, we describe a new technique that builds on these but is both straightforward to implement and computationally inexpensive. The crucial insight is an unusual state-dependent allocation strategy for the addresses of continuations. Our technique imposes only a constant-factor overhead on the underlying analysis and costs only O(n3) in the monovariant case. We present the intuitions behind this development, benchmarks demonstrating its efficacy, and a proof of the precision of this analysis.
  • Authors

    Digital Object Identifier (doi)

    Author List

  • Gilray T; Lyde S; Adams MD; Might M; Van Horn D
  • Start Page

  • 691
  • End Page

  • 704
  • Volume

  • 20-22-January-2016