We present a novel approach to scalable implementation of type-based flow analysis with polymorphic subtyping. By giving a new presentation of polymorphic subtyping with instantiation constraints, we are able to apply context-free language (CFL) reachability techniques to type-based flow analysis. We develop a CFL-based algorithm for computing flow information in time O(n^3), where n is the size of the typed program. The algorithm substantially improves upon the best previously known algorithm for this problem with complexity O(n^8). Our technique also yields the first demand-driven algorithm for polymorphic subtype-based flow-computation. It works directly on higher-order programs with structured data, supports context-sensitive, global flow summarization and includes polymorphic recursion.

PDF file

In: Proceedings POPL 2001, 28'th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

Details