Allocation Characterizes Polyvariance: A Unified Methodology for Polyvariant Control-Flow Analysis
The polyvariance of a static analysis is the degree to which it structurally differentiates approximations of program values. Polyvariant techniques come in a number of different flavors that represent alternative heuristics for managing the trade-off an analysis strikes between precision and complexity. For example, call sensitivity supposes that values will tend to correlate with recent call sites, object sensitivity supposes that values will correlate with the allocation points of related objects, the Cartesian product algorithm supposes correlations between the values of arguments to the same function, and so forth.
In this paper, we describe a unified methodology for implementing and understanding polyvariance in a higher-order setting (i.e., for control-flow analyses). We do this by extending the method of abstracting abstract machines (AAM), a systematic approach to producing an abstract interpretation of abstract-machine semantics. AAM eliminates recursion within a language’s semantics by passing around an explicit store, and thus places importance on the strategy an analysis uses for allocating abstract addresses within the abstract heap or store. We build on AAM by showing that the design space of possible abstract allocators exactly and uniquely corresponds to the design space of polyvariant strategies. This allows us to both unify and generalize polyvariance as tunings of a single function. Changes to the behavior of this function easily recapitulate classic styles of analysis and produce novel variations, combinations of techniques, and fundamentally new techniques.
Wed 21 SepDisplayed time zone: Osaka, Sapporo, Tokyo change
13:30 - 14:45
Session 10Research Papers at Noh Theater
Chair(s): John Reppy University of Chicago
|Hierarchical Memory Management for Parallel Programs|
Ram Raghunathan Carnegie Mellon University, USA, Stefan K. Muller Carnegie Mellon University, USA, Umut A. Acar Carnegie Mellon University, Guy Blelloch Carnegie Mellon University, USADOI
|Allocation Characterizes Polyvariance: A Unified Methodology for Polyvariant Control-Flow Analysis|
Thomas Gilray University of Utah, USA, Michael D. Adams University of Utah, USA, Matthew Might University of Utah, USADOI
|A Fully Concurrent Garbage Collector for Functional Programs on Multicore Processors|
Katsuhiro Ueno Tohoku University, Japan, Atsushi Ohori Tohoku University, JapanDOI