Article contents
Type-based flow analysis and context-free language reachability
Published online by Cambridge University Press: 01 October 2008
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.
- Type
- Paper
- Information
- Mathematical Structures in Computer Science , Volume 18 , Special Issue 5: Theory and applications of subtyping , October 2008 , pp. 823 - 894
- Copyright
- Copyright © Cambridge University Press 2008
References
- 5
- Cited by