Michael D. Adams, Andrew W. Keep, Jan Midtgaard, Matthew Might, Arun Chauhan, and R. Kent Dybvig. Flow-sensitive sub-zero control-flow analysis in linear-log time. Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications, OOPSLA '11, pages 483-498,. October, 2011. (bibtex).

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 elim- inated via control-flow analysis. Traditional control-flow analysis (CFA) is not ideal for this task, however, as it ig- nores flow-sensitive information that can be gained from dy- namic type predicates, such as JavaScript's instanceof or 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 incorporated into 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. In practice, the algorithm processes on average over 75,000 lines of code per second and scales well asymptotically, run- ning in only O(n log n) time. We achieve this compile-time performance and scalability through a novel combination of data structures and algorithms.