Type-Based Flow Analysis: From Polymorphic Subtyping to CFL-Reachability

  • Manuel Fahndrich

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

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(n3), 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(n8). 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.