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).
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.