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

Michael D. Adams

Status: Published

  • Dissertation: Contains detailed math, proofs and examples omitted from the OOPSLA 2011 version
  • Dissertation: ProQuest page
  • OOPSLA 2011 paper
  • Implementation: Supports full R6RS and Chez Scheme. This code is provided for informative purposes only and should be considered research quality software. It includes both instrumentation code and code that needs performance tuning. It is not production ready software.

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, this dissertation presents 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 into 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 bench-marks. 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. This compile-time performance and scalability is achieved through a novel combination of data structures and algorithms.

Citation

Michael D. Adams. Flow-Sensitive Control-Flow Analysis in Linear-Log Time. Ph.D. thesis, Indiana University, 2011.

BibTeX Entry

@phdthesis{adams2011cfa,
  author = {Adams, Michael D.},
  title = {Flow-Sensitive Control-Flow Analysis in Linear-Log Time},
  school = {Indiana University},
  year = {2011},
  isbn = {978-1-267-07777-6},
}