Structure and Interpretation of Computer Programs

(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.

(define (parallel-instruction-sequences seq1 seq2)

  (make-instruction-sequence

   (list-union (registers-needed seq1)

               (registers-needed seq2))

   (list-union (registers-modified seq1)

               (registers-modified seq2))

   (append (statements seq1) (statements seq2))))

5.5.5  An Example of Compiled Code

Now that we have seen all the elements of the compiler, let us examine an example of compiled code

to see how things fit together. We will compile the definition of a recursive 

factorial

 procedure by

calling 

compile

:

---

(compile

 ’(define (factorial n)

    (if (= n 1)

        1

        (* (factorial (- n 1)) n)))

 ’val

 ’next)

We have specified that the value of the 

define

 expression should be placed in the 

val

 register. We

don’t care what the compiled code does after executing the 

define

, so our choice of 

next

 as the

linkage descriptor is arbitrary.

Compile

 determines that the expression is a definition, so it calls 

compile-definition

 to

compile code to compute the value to be assigned (targeted to 

val

), followed by code to install the

definition, followed by code to put the value of the 

define

 (which is the symbol 

ok

) into the target

register, followed finally by the linkage code. 

Env

 is preserved around the computation of the value,

because it is needed in order to install the definition. Because the linkage is 

next

, there is no linkage

code in this case. The skeleton of the compiled code is thus

  <save env if modified by code to compute value>

  <compilation of definition value, target val, linkage next>

  <restore env if saved above>

  (perform (op define-variable!)

           (const factorial)

           (reg val)

           (reg env))

  (assign val (const ok))

The expression that is to be compiled to produce the value for the variable 

factorial

 is a 

lambda

expression whose value is the procedure that computes factorials. 

Compile

 handles this by calling 

compile-lambda

, which compiles the procedure body, labels it as a new entry point, and generates

the instruction that will combine the procedure body at the new entry point with the run-time

environment and assign the result to 

val

. The sequence then skips around the compiled procedure

code, which is inserted at this point. The procedure code itself begins by extending the procedure’s

definition environment by a frame that binds the formal parameter 

n

 to the procedure argument. Then

comes the actual procedure body. Since this code for the value of the variable doesn’t modify the 

env

register, the optional 

save

 and 

restore

 shown above aren’t generated. (The procedure code at 

entry2

 isn’t executed at this point, so its use of 

env

 is irrelevant.) Therefore, the skeleton for the

compiled code becomes

  (assign val (op make-compiled-procedure)

              (label entry2)

              (reg env))

  (goto (label after-lambda1))

entry2

  (assign env (op compiled-procedure-env) (reg proc))

  (assign env (op extend-environment)

              (const (n))

              (reg argl)

              (reg env))

  <compilation of procedure body>

---