Tech Report CS-95-30

Source to Source Optimizations of CLP($\Re_{Lin}$)

Viswanath Ramachandran and Pascal Van Hentenryck

October 1995

Abstract:

This paper describes the design and implementation of an optimizing compiler for CLP($\Re_{Lin}$), a constraint logic programming language over linear real constraints. The compiler performs a number of source to source optimizations which aim at replacing constraint solving, the basic operation of the language, by assignments (when, at runtime, all but one variables have a fixed value) and tests (when, at runtime, all variables have a fixed value) These optimizations follow the 3R's methodology which consists of refining, reordering, and removing constraints. The compiler uses abstract interpretation to decide when and how to perform the optimizations. The resulting system (40,000 lines of C, 10,000 of which concern the optimizations) has been evaluated experimentally. Our preliminary results indicate that substantial (often asymptotic) speedups can be obtained. Most of these speedups can be made arbitrary large, since they depend on the input size. This is, to our knowledge, the first operational compiler for CLP($\Re_{Lin}$) with these functionalities and the first implementation of reordering and constraint removal. It is also a convincing demonstration that abstract interpretation can be used to produce dramatic speedups for CLP($\Re_{Lin}$) programs.

(complete text in pdf or gzipped postscript)