Manuel Fahndrich and Alex Aiken

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-96-917

, 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},
    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