Pushdown control-flow analysis for free
Abstract
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(2^n), PDCFA is in O(n^6), and AAC is in O(n^8). 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(n^3) in the monovariant case. We present the intuitions behind this development, benchmarks demonstrating its efficacy, and a proof of the precision of this analysis.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jan 11, 2016
- Source ID
- 10.1145/2914770.2837631
Entities
People
- David Van Horn
- Matthew Might
- Michael D. Adams
- Steven Lyde
- Thomas Gilray
Organizations
- Defense Advanced Research Projects Agency
- National Science Foundation
- University of Maryland
- University of Utah