Optimizing compilation of CLP( R )

ABSTRACT

Constraint Logic Programming (CLP) languages extend logic programming by allowing the use of constraints from different domains such as real numbers or Boolean functions. They have proved to be ideal for expressing problems that require interactive mathematical modeling and complex combinatorial optimization problems. However, CLP languages have mainly been considered as research systems, useful for rapid prototyping, by not really competitive with more conventional programming languages where efficiency is a more important consideration. One promising approach to improving the performance of CLP systems is the use of powerful program optimizations to reduce the cost of constraint solving. We extend work in this area by describing a new optimizing compiler for the CLP language CLP( R ). The compiler implements six powerful optimizations: reordering of constraints, removal of redundant variables, and specialization of constraints which cannot fail. Each program optimization is designed to remove the overhead of constraint solving when possible and keep the number of constraints in the store as small as possible. We systematically evaluate the effectiveness of each optimization in isolation and in combination. Our empirical evaluation of the compiler verifies that optimizing compilation can be made efficient enough to allow compilation of real-world programs and that it is worth performing such compilation because it gives significant time and space performance improvements.

REFERENCES

• 1: Hassan Aït-Kaci, Warren's abstract machine: a tutorial reconstruction, MIT Press, Cambridge, MA, 1991
• 2: ARMSTRONG, T., MARRIOTT, I~., SCHACHTE, P., AND SONDERGAARD, H. 1994. Boolean functions for dependency analysis: Algebraic properties and efficient representation. In Proceedings of the 1st International Static Analysis Symposium, B. Le Charlier, Ed. Lecture Notes in Computer Science, vol. 864. Springer-Verlag, Berlin, 266-280.
• 3: Patrick Cousot , Rahida Cousot, Abstract interpretation and application to logic programs, Journal of Logic Programming, v.13 n.2-3, p.103-179, July 1992 [doi>10.1016/0743-1066(92)90030-7]
• 4: Lobel Crnogorac , Andrew D. Kelly , Harald Søndergaard, A Comparison of Three Occur-Check Analysers, Proceedings of the Third International Symposium on Static Analysis, p.159-173, September 24-26, 1996
• 5: M. Garcia de la Banda , M. Hermenegildo , M. Bruynooghe , V. Dumortier , G. Janssens , W. Simoens, Global analysis of constraint logic programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.5, p.564-614, Sept. 1996 [doi>10.1145/232706.232734]
• 6: Manuel V. Hermenegildo, Some Methodological Issues in the Design of CIAO, a Generic, Parallel Concurrent Constraint Logic Programming System, Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, p.123-133, May 02-04, 1994
• 7: HERMENEGILDO, M., PUEBLA, G., MARRIOTT, I~., AND STUCKEY, P. 1995. Incremental analysis of logic programs. In Logic Programming: Proceedings of the 12th International Conference, L. Sterling, Ed. MIT Press, Cambridge, Mass., 797-814.
• 8: Joxan Jaffar , Peter J. Stuckey , Spiro Michaylov , Roland H. C. Yap, An abstract machine for CLP(R), Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.128-139, June 15-19, 1992, San Francisco, California, United States
• 9: Joxan Jaffar , Spiro Michaylov , Peter J. Stuckey , Roland H. C. Yap, The CLP( R ) language and system, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.3, p.339-395, July 1992 [doi>10.1145/129393.129398]
• 10: JORGENSEN, N., MARRIOTT, I~., AND MICHAYLOV, S. 1991. Some global compile-time optimizations for CLP(/E). In Logic Programming: Proceedings of the 1991 International Symposium, V. Saraswat and K. Ueda, Eds. MIT Press, Cambridge, Mass., 420-434.
• 11: Andrew D. Kelly , Andrew D. Macdonald , Kim Marriott , Harald Søndergaard , Peter J. Stuckey , Roland H. C. Yap, An Optimizing Compiler for CLP(R), Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.222-239, September 19-22, 1995
• 12: KELLY, A., MACDONALD, A., MARRIOTT, I~., STUCKEY, P., AND YAP, R. 1996. Effectiveness of optimizing compilation of CLP(/E). In Logic Programming: Proceedings of the 1992 Joint International Conference and Symposium, M. Maher, Ed. MIT Press, Cambridge, Mass., 37-51.
• 13: KELLY, A., MARRIOTT, I~., SONDERGAARD, H., AND STUCKEY, P. 1997. A generic object oriented incremental analyser for constraint logic programs. In Proceedings of the 20th Australasian Computer Science Conference. 92-101.
• 14: Baudouin Le Charlier , Pascal Van Hentenryck, Experimental evaluation of a generic abstract interpretation algorithm for PROLOG, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.1, p.35-101, Jan. 1994 [doi>10.1145/174625.174627]
• 15: Andrew D. Macdonald , Peter J. Stuckey , Roland H. C. Yap, Redundancy of variables in CLD R , Proceedings of the 1993 international symposium on Logic programming, p.75-93, December 1993, Vancouver, British Columbia, Canada
• 16: Kim Marriott , Harald Søndergaard, Analysis of constraint logic programs, Proceedings of the 1990 North American conference on Logic programming, p.531-547, January 1990, Austin, Texas, United States
• 17: MARRIOTT, I~., SONDERGAARD, H., STUCKEY, P. J., AND YAP, R. 1994. Optimizing compilation for CLP(/E). In Proceedings of the 17th Australian Computer Science Conference, G. Gupta, Ed. 551-560.
• 18: Kimball G. Marriott , Peter J. Stuckey, The 3 R's of optimizing constraint logic programs: refinement, removal and reordering, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.334-344, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158685]
• 19: MARRIOTT, I~. AND STUCKEY, P. 1998. Programming with Constraints: an Introduction. MIT Press, Cambridge, Mass.
• 20: K. Muthukumar , M. Hermenegildo, Compile-time derivation of variable dependency using abstract interpretation, Journal of Logic Programming, v.13 n.2-3, p.315-347, July 1992 [doi>10.1016/0743-1066(92)90035-2]
• 21: Germán Puebla , Manuel Hermenegildo, Implementation of multiple specialization in logic programs, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.77-87, June 21-23, 1995, La Jolla, California, United States [doi>10.1145/215465.215561]
• 22: German Puebla , Manuel V. Hermenegildo, Abstract Specialization and Its Application to Program Parallelization, Proceedings of the 6th International Workshop on Logic Programming Synthesis and Transformation, p.169-186, August 28-30, 1996
• 23: Viswanath Ramachandran , Pascal Van Hentenryck, Source to Source Optimizations of CLP($\Re_{Lin}$), Brown University, Providence, RI, 1995
• 24: H Sondergaard, An application of abstract interpretation of logic programs: occur check reduction, Proc. of the European symposium on programming on ESOP 86, p.327-338, March 1986, Saarbru:9Aicken, Germany
• 25: Andrew Taylor, LIPS on MIPS: results from Prolog compiler for a RISC, Logic programming, MIT Press, Cambridge, MA, 1990
• 26: Peter Van Roy , Alvin M. Despain, The benefits of global dataflow analysis for an optimizing Prolog compiler, Proceedings of the 1990 North American conference on Logic programming, p.501-515, January 1990, Austin, Texas, United States
• 27: Will Winsborough, Multiple specialization using minimal-function graph semantics, Journal of Logic Programming, v.13 n.2-3, p.259-290, July 1992 [doi>10.1016/0743-1066(92)90033-Y]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Constraint and logic languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Languages, Performance

Keywords:
compilation, constraint logic programming, program analysis, program optimization, source-to-source program transformation