Cambridge Journals Online

Articles

Exploiting reachability and cardinality in higher-order flow analysis

MATTHEW MIGHTa1 and OLIN SHIVERSa2 a1 Diagis, LLC, Atlanta, GA, USA (e-mail: matt@diagis.com) a2 Northeastern University, Boston, MA, USA (e-mail: shivers@ccs.neu.edu)

Article author query might m  shivers o

Abstract

We present two complementary improvements for abstract-interpretation-based flow analysis of higher-order languages: (1) abstract garbage collection and (2) abstract counting. Abstract garbage collection is an analog to its concrete counterpart: the analysis determines when an abstract resource has become unreachable, and then, re-allocates it as fresh. This prevents flow sets from joining during abstract interpretation, which has two immediate effects: (1) the precision of the interpretation increases and (2) its running time often falls. In abstract counting, the analysis tracks how many times an abstract resource has been allocated. A count of one implies that the abstract resource momentarily represents only one concrete resource. This knowledge, in turn, drives environment analysis, expanding the kind (rather than just the degree) of optimization available to the compiler.