language: en

[LISP AND SYMBOLIC COMPUTATION: An International Journal, 5, 191-221, 1992]

[c 1992 Kluwer Academic Publishers Manufactured in The Netherlands]

Callee-save Registers in Continuation-passing Style

ANDREW W. APPEL
(appel@princeton.edu)
ZHONG SHAO
(zsh@princeton.edu)
Department of Computer Science, Princeton University,
Princeton, NJ 08544-2087
Keywords: Register Allocation, Continuation-passing Style, Procedure Call

Abstract. Continuation-passing style (CPS) is a good abstract representation to use for compilation and optimization: it has a clean semantics and is easily manipulated. We examine how CPS expresses the saving and restoring of registers in source-language procedure calls. In most CPS-based compilers, the context of the calling procedure is saved in a "continuation closure"|a single variable that is passed as an argument to the function being called. This closure is a record containing bindings of all the free variables of the continuation; that is, registers that hold values needed by the caller "after the call" are written to memory in the closure, and fetched back after the call. Consider the procedure-call mechanisms used by conventional compilers. In particular, registers holding values needed after the call must be saved and later restored. The responsibility for saving registers can lie with the caller (a "caller-saves" convention) or with the called function ("callee-saves"). In practice, to optimize memory traffic, compilers find it useful to have some caller-saves registers and some callee-saves. "Conventional" CPS-based compilers that pass a pointer to a record containing all the variables needed after the call (i.e., the continuation closure), are using a caller-saves convention. We explain how to express callee-save registers in Continuation-Passing Style, and give measurements showing the resulting improvement in execution time.

1. Introduction