Mathematical Structures in Computer Science

Table of Contents - 2008 - Volume 18, Special Issue 05 (Theory and applications of subtyping)  

Paper

Type-based flow analysis and context-free language reachability

MANUEL FÄHNDRICHa1 and JAKOB REHOFa2

a1 One Microsoft Way, Redmond WA 98052, U.S.A. Email: maf@microsoft.com

a2 One Microsoft Way, Redmond WA 98052, U.S.A.

Abstract

We present a novel approach to computing the context-sensitive flow of values through procedures and data structures. Our approach combines and extends techniques from two seemingly disparate areas: polymorphic subtyping and interprocedural dataflow analysis based on context-free language reachability. The resulting technique offers several advantages over previous approaches: it works directly on higher-order programs; provides demand-driven interprocedural queries; and improves the asymptotic complexity of a known algorithm based on polymorphic subtyping from O(n8) to O(n3) for computing all queries. For intra-procedural flow restricted to equivalence classes, our algorithm yields linear inter-procedural flow queries.

(Received February 15 2006)

(Revised January 17 2007)