Paper announcement: From Polymorphic Subtyping to CFL Reachabili ty

We are pleased to announce the following paper,

     From Polymorphic Subtyping to CFL Reachability:
     Context-Sensitive Flow Analysis Using Instantiation Constraints


     Manuel Fahndrich, Jakob Rehof and Manuvir Das

     Microsoft Research Technical Report MSR-TR-99-84

available from http://research.microsoft.com/~rehof/tr-99-84-abs.html

The abstract follows below.

Best regards,

Manuel Fahndrich,  Jakob Rehof,  Manuvir Das
Microsoft Research, 

------------------------------  Abstract

We present a novel approach to computing 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
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
$O(n^8)$ to $O(n^3)$ for computing all queries. 
For intra-procedural flow restricted to
equivalence classes, our algorithm yields linear inter-procedural flow