Abstract domains for reordering CLP (R-Lin) programs

In order to address the multi-directional nature of constraint logic programs, recent optimizing compilers generate several versions of a procedure and optimize them independently. Reordering, i.e., moving constraints towards the end of a clause, plays a fundamental role in this optimization: it may lead to significant improvements in performance by bypassing the constraint solver entirely. This paper focuses on CLP over linear real constraints, and studies two abstract domains, i.e., LSign and LInt, which can be used to decide at compile time when constraints can be safely reordered. The domain LSign was originally proposed by Marriott and Stuckey. Its fundamental ideas consist of abstracting coefficients by signs and of keeping multiplicity information on constraints. LInt is a new, and infinite, domain which is similar in nature to LSign, except that signs are replaced by intervals of rational numbers. A comprehensive description of the two domains is given, together with some very preliminary evidence showing that the domains are precise enough to perform the intended optimizations on small programs. (C) 2000 Elsevier Science Inc. All rights reserved