Register Allocation in a Prolog Machine
Department of Computer Science
SUNY at Stony Brook
Stony Brook, NY 11794, U.S.A.
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.