Componential set-based analysis

1 May 1997

journal article
Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices

Vol. 32 (5) , 235-248
https://doi.org/10.1145/258916.258937

Abstract

Set based analysis is a constraint-based whole program analysis that is applicable to functional and object-oriented programming language. Unfortunately, the analysis is useless for large programs, since it generates descriptions of data flow relationships that grow quadratically in the size of the program.This paper presents componential set-based analysis, which is faster and handles larger programs without any loss of accuracy over set-based analysis. The design of the analysis exploits a number of theoretical results concerning constraint systems, including a completeness result and a decision algorithm concerning the observable equivalance of constraint systems. Experimental results validate the practically of the analysis.

Keywords

This publication has 13 references indexed in Scilit:

Catching bugs in the web of program invariants
Published by Association for Computing Machinery (ACM) ,1996
Simple imperative polymorphism
Higher-Order and Symbolic Computation, 1995
Sound polymorphic type inference for objects
Published by Association for Computing Machinery (ACM) ,1995
Closure analysis in constraint form
ACM Transactions on Programming Languages and Systems, 1995
A type system equivalent to flow analysis
Published by Association for Computing Machinery (ACM) ,1995
Formal language, grammar and set-constraint-based program analysis by abstract interpretation
Published by Association for Computing Machinery (ACM) ,1995
A Syntactic Approach to Type Soundness
Information and Computation, 1994
Type inference for polymorphic references
Information and Computation, 1990
A flexible approach to interprocedural data flow analysis and programs with recursive data structures
Published by Association for Computing Machinery (ACM) ,1982
AN n log n ALGORITHM FOR MINIMIZING STATES IN A FINITE AUTOMATON
Published by Elsevier ,1971