Structure and Interpretation of Computer Programs (106 page)

The primitive and compound branches, like the true
and false branches in
compile-if
, are appended using
parallel-instruction-sequences
rather than the ordinary
append-instruction-sequences
, because they will
not be executed sequentially.

The code that handles procedure application is the most subtle part of
the compiler, even though the instruction sequences it generates are
very short. A compiled procedure (as constructed by
compile-lambda
) has an entry point, which is a label that designates
where the code for the procedure starts. The code at this entry point
computes a result in
val
and returns by executing the
instruction
(goto (reg continue))
. Thus, we might expect the
code for a compiled-procedure application (to be generated by
compile-proc-appl
) with a given target and linkage to look like this
if the linkage is a label

 (assign continue (label proc-return))
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
proc-return
 (assign <
target
> (reg val))   
; included if target is not 
val
 (goto (label <
linkage
>))   
; linkage code

or like this if the linkage is
return
.

 (save continue)
 (assign continue (label proc-return))
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
proc-return
 (assign <
target
> (reg val))   
; included if target is not 
val
 (restore continue)
 (goto (reg continue))   
; linkage code

This code sets up
continue
so that the procedure will return to a
label
proc-return
and jumps to the procedure's entry point. The code
at
proc-return
transfers the procedure's result from
val
to the target register (if necessary) and then jumps to
the location specified by the linkage.
(The linkage is always
return
or a label, because
compile-procedure-call
replaces a
next
linkage for the
compound-procedure branch by an
after-call
label.)

In fact, if the target is not
val
, that is exactly the code our
compiler will generate.
³⁹
Usually, however, the target is
val
(the only time the compiler
specifies a different register is when targeting the evaluation of an
operator to
proc
), so the procedure result is put directly into
the target register and there is no need to return to a special
location that copies it. Instead, we simplify the code by
setting up
continue
so that the procedure will “return”
directly to the place specified by the caller's linkage:

<
set up 
continue
 for linkage
>
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))

If the linkage is a label, we set up
continue
so that the procedure will return to
that label. (That is, the
(goto (reg continue))
the procedure
ends with becomes equivalent to the
(goto (label <
linkage
>))
at
proc-return
above.)

(assign continue (label <
linkage
>))
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))

If the linkage is
return
, we don't need to set up
continue
at all: It already holds the desired location. (That is, the
(goto (reg continue))
the procedure ends with goes directly to the
place where the
(goto (reg continue))
at
proc-return
would
have gone.)

(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))

With this implementation of the
return
linkage, the compiler
generates tail-recursive code. Calling a procedure as the final step
in a procedure body does a direct transfer, without saving any
information on the stack.

Suppose instead that we had handled the case of a procedure call with
a linkage of
return
and a target of
val
as shown above for
a non-
val
target. This would destroy tail recursion. Our
system would still give the same value for any expression. But each
time we called a procedure, we would save
continue
and return
after the call to undo the (useless) save. These extra saves would
accumulate during a nest of procedure calls.
⁴⁰

Compile-proc-appl
generates the above procedure-application code by
considering four cases, depending on whether the target for the call
is
val
and whether the linkage is
return
.
Observe that the instruction sequences are
declared to modify all the registers, since executing the procedure
body can change the registers in arbitrary ways.
⁴¹
Also note that the code sequence for the case with target
val
and linkage
return
is declared to need
continue
: Even
though
continue
is not explicitly used in the two-instruction
sequence, we must be sure that
continue
will have the correct
value when we enter the compiled procedure.

(define (compile-proc-appl target linkage)
  (cond ((and (eq? target 'val) (not (eq? linkage 'return)))
         (make-instruction-sequence '(proc) all-regs
           `((assign continue (label ,linkage))
             (assign val (op compiled-procedure-entry)
                         (reg proc))
             (goto (reg val)))))
        ((and (not (eq? target 'val))
              (not (eq? linkage 'return)))
         (let ((proc-return (make-label 'proc-return)))
           (make-instruction-sequence '(proc) all-regs
            `((assign continue (label ,proc-return))
              (assign val (op compiled-procedure-entry)
                          (reg proc))
              (goto (reg val))
              ,proc-return
              (assign ,target (reg val))
              (goto (label ,linkage))))))
        ((and (eq? target 'val) (eq? linkage 'return))
         (make-instruction-sequence '(proc continue) all-regs
          '((assign val (op compiled-procedure-entry)
                        (reg proc))
            (goto (reg val)))))
        ((and (not (eq? target 'val)) (eq? linkage 'return))
         (error "return linkage, target not val -- COMPILE"
                target))))

This section describes the details on how instruction sequences are
represented and combined. Recall from
section 
5.5.1
that an instruction sequence
is represented as a list of the registers needed, the registers
modified, and the actual instructions. We will also consider a label
(symbol) to be a degenerate case of an instruction sequence, which doesn't
need or modify any registers.
So to determine the registers needed
and modified by instruction sequences we use the selectors

(define (registers-needed s)
  (if (symbol? s) '() (car s)))
(define (registers-modified s)
  (if (symbol? s) '() (cadr s)))
(define (statements s)
  (if (symbol? s) (list s) (caddr s)))

and to determine whether a given
sequence needs or modifies a given register we use the predicates

(define (needs-register? seq reg)
  (memq reg (registers-needed seq)))
(define (modifies-register? seq reg)
  (memq reg (registers-modified seq)))

In terms of these predicates and selectors, we can implement the
various instruction sequence combiners used throughout the compiler.

The basic combiner is
append-instruction-sequences
. This takes as
arguments an arbitrary number of instruction sequences that are to be executed
sequentially and returns an instruction sequence whose statements are the
statements of all the sequences appended together. The subtle point is to
determine the registers that are needed and modified by the resulting
sequence. It modifies those registers that are modified by any of the
sequences; it needs those registers that must be initialized before the first
sequence can be run (the registers needed by the first sequence), together
with those registers needed by any of the other sequences that are not
initialized (modified) by sequences preceding it.

The sequences are appended two at a time by
append-2-sequences
. This
takes two instruction sequences
seq1
and
seq2
and returns the
instruction sequence whose statements are the statements of
seq1
followed by the statements of
seq2
, whose modified registers are those
registers that are modified by either
seq1
or
seq2
, and whose
needed registers are the registers needed by
seq1
together with those
registers needed by
seq2
that are not modified by
seq1
. (In terms
of set operations, the new set of needed registers is the union of the set of
registers needed by
seq1
with the set difference of the registers needed
by
seq2
and the registers modified by
seq1
.) Thus,
append-instruction-sequences
is implemented as follows:

(define (append-instruction-sequences . seqs)
  (define (append-2-sequences seq1 seq2)
    (make-instruction-sequence
     (list-union (registers-needed seq1)
                 (list-difference (registers-needed seq2)
                                  (registers-modified seq1)))
     (list-union (registers-modified seq1)
                 (registers-modified seq2))
     (append (statements seq1) (statements seq2))))
  (define (append-seq-list seqs)
    (if (null? seqs)
        (empty-instruction-sequence)
        (append-2-sequences (car seqs)
                            (append-seq-list (cdr seqs)))))
  (append-seq-list seqs))

This procedure uses some simple operations for manipulating sets
represented as lists, similar to the (unordered) set representation
described in section 
2.3.3
:

(define (list-union s1 s2)
  (cond ((null? s1) s2)
        ((memq (car s1) s2) (list-union (cdr s1) s2))
        (else (cons (car s1) (list-union (cdr s1) s2)))))
(define (list-difference s1 s2)
  (cond ((null? s1) '())
        ((memq (car s1) s2) (list-difference (cdr s1) s2))
        (else (cons (car s1)
                    (list-difference (cdr s1) s2)))))

Preserving
, the second major instruction sequence combiner, takes a list
of registers
regs
and two instruction sequences
seq1
and
seq2
that are to be executed sequentially. It returns an instruction
sequence whose statements are the statements of
seq1
followed by the
statements of
seq2
, with appropriate
save
and
restore
instructions around
seq1
to protect the registers in
regs
that are
modified by
seq1
but needed by
seq2
. To accomplish this,
preserving
first creates a sequence that has the required
save
s
followed by the statements of
seq1
followed by the required
restore
s. This sequence needs the registers being saved and restored in
addition to the registers needed by
seq1
, and modifies the registers
modified by
seq1
except for the ones being saved and restored. This
augmented sequence and
seq2
are then appended in the usual way. The
following procedure implements this strategy recursively, walking down the
list of registers to be preserved:
⁴²

(define (preserving regs seq1 seq2)
  (if (null? regs)
      (append-instruction-sequences seq1 seq2)
      (let ((first-reg (car regs)))
        (if (and (needs-register? seq2 first-reg)
                 (modifies-register? seq1 first-reg))
            (preserving (cdr regs)
             (make-instruction-sequence
              (list-union (list first-reg)
                          (registers-needed seq1))
              (list-difference (registers-modified seq1)
                               (list first-reg))
              (append `((save ,first-reg))
                      (statements seq1)
                      `((restore ,first-reg))))
             seq2)
            (preserving (cdr regs) seq1 seq2)))))

Another sequence combiner,
tack-on-instruction-sequence
,
is used by
compile-lambda
to append a procedure body to another
sequence. Because the procedure body is not “in line” to be
executed as part of the combined sequence, its register use has no
impact on the register use of the sequence in which it is embedded.
We thus ignore the procedure body's sets of needed and modified
registers when we tack it onto the other sequence.

(define (tack-on-instruction-sequence seq body-seq)
  (make-instruction-sequence
   (registers-needed seq)
   (registers-modified seq)
   (append (statements seq) (statements body-seq))))

Compile-if
and
compile-procedure-call
use a special
combiner called
parallel-instruction-sequences
to append the two
alternative branches that follow a test. The two branches will never be
executed sequentially; for any particular evaluation of the test, one
branch or the other will be entered. Because of this, the registers
needed by the second branch are still needed by the combined sequence,
even if these are modified by the first branch.