Abstract domains for reordering CLP (R-Lin) programs

In order to address the multi-directional nature of constraint logic progra ms, recent optimizing compilers generate several versions of a procedure an d 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 constrain t 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 t o decide at compile time when constraints can be safely reordered. The doma in LSign was originally proposed by Marriott and Stuckey. Its fundamental i deas consist of abstracting coefficients by signs and of keeping multiplici ty 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.