3 R's of optimizing constraint logic programs: Refinement, removal and reordering

Abstract

Central to constraint logic programming (CLP) languages is the notion of a global constraint solver which is queried to direct execution and to which constraints are monotonically added. We present a methodology for use in the compilation of CLP languages which is designed to reduce the overhead of the global constraint solver. This methodology is based on three optimizations. The first, refinement, involves adding new constraints, which in effect make information available earlier in the computation, guiding subsequent execution away from unprofitable choices. The second, removal, involves eliminating constraints from the solver when they are redundant. The last, reordering, involves moving constraint addition later and constraint removal earlier in the computation. Determining the applicability of each optimization requires sophisticated global analysis. These analyses are based on abstract interpretation and provide information about potential and definite interaction between constraints.