Making Set-Constraint Program Analyses Scale

Manuel Fahndrich and Alex Aiken

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-96-917
September 1996

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/CSD-96-917.pdf

Constraint-based program analyses are appealing because elaborate analyses can be described with a concise and simple set of constraint generation rules. Constraint resolution algorithms have been developed for many kinds of constraints, conceptually allowing an implementation of a constraint-based program analysis to reuse large pieces of existing code. In practice, however, new analyses often involve re-implementing new, complex constraint solving frameworks, tuned for the particular analysis in question. This approach wastes development time and interferes with the desire to experiment quickly with a number of different analyses.

We believe that implementing an analysis should require writing only the code to generate the constraints, and that a well engineered-library can take care of constraint representation, resolution, and transformation. Writing such a library capable of handling small programs is not too difficult, but scaling to large programs is hard. Toward this goal, we are developing a scalable, expressive framework for solving a class of set constraints. Scalability is achieved through four techniques: polymorphism, simplification, separation, and sparse representation of constraints.


BibTeX citation:

@techreport{Fahndrich:CSD-96-917,
    Author = {Fahndrich, Manuel and Aiken, Alex},
    Title = {Making Set-Constraint Program Analyses Scale},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1996},
    Month = {Sep},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/5815.html},
    Number = {UCB/CSD-96-917},
    Abstract = {Constraint-based program analyses are appealing because elaborate analyses can be described with a concise and simple set of constraint generation rules. Constraint resolution algorithms have been developed for many kinds of constraints, conceptually allowing an implementation of a constraint-based program analysis to reuse large pieces of existing code. In practice, however, new analyses often involve re-implementing new, complex constraint solving frameworks, tuned for the particular analysis in question. This approach wastes development time and interferes with the desire to experiment quickly with a number of different analyses. 

 We believe that implementing an analysis should require writing only the code to generate the constraints, and that a well engineered-library can take care of constraint representation, resolution, and transformation. Writing such a library capable of handling small programs is not too difficult, but scaling to large programs is hard.  Toward this goal, we are developing a scalable, expressive framework for solving a class of set constraints. Scalability is achieved through four techniques: polymorphism, simplification, separation, and sparse representation of constraints.}
}

EndNote citation:

%0 Report
%A Fahndrich, Manuel
%A Aiken, Alex
%T Making Set-Constraint Program Analyses Scale
%I EECS Department, University of California, Berkeley
%D 1996
%@ UCB/CSD-96-917
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/5815.html
%F Fahndrich:CSD-96-917