Flow-Sensitive Sub-Zero Control-Flow Analysis in Linear-Log Time

Michael D. Adams, Andrew W. Keep, Jan Midtgaard, Matthew Might, Arun Chauhan, and R. Kent Dybvig

Status: Published in SPLASH (nee OOPSLA) 2011

Links

• Paper: Current version
• Dissertation: Contains detailed math, proofs, examples and full implementation omitted from the OOPSLA 2011 version

Abstract

In an analysis like type recovery, it is often useful to take advantage of restrictive information available at function call sites. For exam- ple, after (car x), x is restricted to pairs and subsequent calls such as (cdr x) need not check that x is a pair. This can be done by adding a form of flow sensitivity to a control-flow analysis (CFA).

However, even starting with sub-0CFA, a linear-time variant of 0CFA, the obvious implementation of this sort of flow sensitivity takes quadratic time. This paper presents a method for computing this analysis in only linear-log time.

We have implemented this in a fast, production compiler where it is used to perform type recovery. It justifies the removal of almost two thirds of the run-time checks that are otherwise necessary to ensure type safety in the latently-typed language Scheme, and it processes 100,000 program nodes in less than a second.

Keywords

Keywords Control-Flow Analysis, Flow Sensitivity, Path Sensitivity, Type Recovery

Citation

BibTeX Entry

@inproceedings{adams2011cfa,
  author = {Adams, Michael D. and Keep, Andrew W. and Midtgaard, Jan and Might, Matthew and Chauhan, Arun and Dybvig, R. Kent},
  title = {Flow-Sensitive Sub-Zero Control-Flow Analysis in Linear-Log Time},
  booktitle = {Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications},
  pages = {483--498},
  year = {2011},
  series = {OOPSLA '11},
  address = {New York, NY, USA},
  publisher = {ACM},
  isbn = {978-1-4503-0940-0},
  doi = {10.1145/2048066.2048105},
}

Copyright Notice