From generic to specific: off-line optimization for a general constraint solver

Abstract

A general constraint solver simplifies the implementation of program analyses because constraint generation can then be separated from constraint solving. In return, a general solver often needs to sacrifice performance for generality. We describe a strategy that given a set of constraints first performs off-line optimizations (performed before the execution of the solver) which enable a solver to find (potential) equivalences between analysis variables so as to reduce the problem space and thus improve performance. The idea is that different analyses use different subsets of constraints. As a result, a specific property may hold for the subsets and a specific optimization can be conducted on the constraints.