Paper announcement: From Polymorphic Subtyping to CFL Reachabili ty

• To: "'types@cis.upenn.edu'" <types@cis.upenn.edu>
• Subject: Paper announcement: From Polymorphic Subtyping to CFL Reachabili ty
• From: Jakob Rehof <rehof@microsoft.com>
• Date: Fri, 17 Mar 2000 17:45:13 -0800

We are pleased to announce the following paper,

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

                                       by

     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, 
{maf,rehof,manuvir}@microsoft.com


------------------------------  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
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(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
queries.

• Prev: Reasoning with Higher-Order Abstract Syntax
• Next: Postdoctoral Research Position at Yale
• Index(es):
  • Main
  • Thread