Flow-sensitive type recovery in linear-log time

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

Status: Published

Abstract

The flexibility of dynamically typed languages such as JavaScript, Python, Ruby, and Scheme comes at the cost of run-time type checks. Some of these checks can be eliminated via control-flow analysis. However, traditional control-flow analysis (CFA) is not ideal for this task as it ignores flow-sensitive information that can be gained from dynamic type predicates, such as JavaScript’s ’instanceof’ and Scheme’s ’pair?’, and from type-restricted operators, such as Scheme’s ’car’. Yet, adding flow-sensitivity to a traditional CFA worsens the already significant compile-time cost of traditional CFA. This makes it unsuitable for use in just-in-time compilers.

In response, we have developed a fast, flow-sensitive type-recovery algorithm based on the linear-time, flow-insensitive sub–0CFA. The algorithm has been implemented as an experimental optimization for the commercial Chez Scheme compiler, where it has proven to be effective, justifying the elimination of about 60% of run-time type checks in a large set of benchmarks. The algorithm processes on average over 100,000 lines of code per second and scales well asymptotically, running in only O(n log n) time. We achieve this compile-time performance and scalability through a novel combination of data structures and algorithms.

Keywords

control-flow analysis; flow sensitivity; path sensitivity; type recovery

Citation

Michael D. Adams, Andrew W. Keep, Jan Midtgaard, Matthew Might, Arun Chauhan, and R. Kent Dybvig. Flow-sensitive type recovery in linear-log time. In Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA ’11, pages 483–498. ACM, New York, NY, USA, October 2011. ISBN 978-1-4503-0940-0. doi: 10.1145/2048066.2048105.

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 type recovery 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},
  month = oct,
  publisher = {ACM},
  isbn = {978-1-4503-0940-0},
  doi = {10.1145/2048066.2048105},
}

Copyright Notice

© ACM, 2011. This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications, (2011). http://doi.acm.org/10.1145/2048066.2048105.