COMPONENTIAL SET-BASED ANALYSIS

Set-based analysis is a constraint-based whole program analysis that i s applicable to functional and object-oriented programming languages. Unfortunately, the analysis is useless for large programs, since it ge nerates descriptions of data how relationships that grow quadratically in the size of the program. This paper presents componential set-base d analysis, which is faster and handles larger programs without any lo ss of accuracy over set-based analysis. The design of the analysis exp loits a number of theoretical results concerning constraint systems, i ncluding a completeness result and a decision algorithm concerning the observable equivalence of constraint systems. Experimental results va lidate the practicality of the analysis.