The University of Arizona
banner image

  Register Allocation in a Prolog Machine

Saumya Debray
Department of Computer Science
SUNY at Stony Brook
Stony Brook, NY 11794, U.S.A.
 

Abstract
We consider the Prolog Engine described by D. H. D. Warren. An interesting feature of this machine is its parameter passing mechanism, which uses register k to pass the kth parameter to a procedure. Warren distinguishes between temporary variables, which can be kept in registers in such a machine, and permanent variables, which must be allocated in memory. The issue in register allocation here is one of minimizing data movement, and is somewhat different from that of minimizing the number of loads and stores, as in a conventional machine. We describe three register allocation algorithms for such a machine. These strategies rely on a high-level analysis of the source program to compute information which is then used for register allocation during code generation. The algorithms are simple yet quite efficient, and produce code of good quality.