Title: Global Optimizations in a Prolog Compiler for the Toam
Abstract: Backtracking in the WAM may be very expensive for some kinds of programs due to the WAM's simple scheme for indexing clauses. Several compilation algorithms have been proposed for constructing sophisticated indexing code. However, these algorithms have the drawback that they may generate exponential size code for some kinds of programs. This paper presents a Prolog compiler for the TOAM (matching Tree Oriented Abstract Machine). The compiler generates code for a program that is at most linear in the size of the program. It adopts a simple algorithm for detecting the exclusiveness among clauses and the determinacy of predicates. For those predicates that are detected to be determinate, the generated code does not create any choice point. The compiler also optimizes shallow backtracking in the sense that it treats a failure caused by a test as a jump. In addition, the compiler classifies cuts into commit, shallow, and deep cuts, and optimizes the code for commit and shallow cuts. Empirical results show that these optimizations can improve the performance of compiled code significantly.