Structure and Interpretation of Computer Programs

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

5.5.4  Combining Instruction Sequences

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:

42

 

---