5.5.4 · Register liveness

Save only the register the next sequence still needs.

Instruction-sequence need and modification sets can decide when composed code must protect an earlier register value with save and restore.

Guiding question

When does a compiler need to preserve a register between two instruction sequences?

Read register needs and modifications as sequence contracts
Detect a value needed after an earlier sequence overwrites it
Insert save and restore only around that conflict
Update the composed sequence contract after preservation

A conflict exists when the second sequence needs the incoming value of a register and the first sequence modifies that register. Preserving wraps the first statements with save and restore so the second sequence sees the original value.

The wrapped first sequence now needs the register in order to save it and no longer exposes that register as modified after restore. If either side of the conflict is absent, composition emits no stack instructions.

SICP code1,789 of 1,048,576 UTF-8 bytes

(begin
  (define (contains? item items)
    (cond ((null? items) #f)
          ((eq? item (car items)) #t)
          (else (contains? item (cdr items)))))
  (define (adjoin item items)
    (if (contains? item items) items (append items (list item))))
  (define (union left right)
    (if (null? right) left
        (union (adjoin (car right) left) (cdr right))))
  (define (difference left right)
    (cond ((null? left) '())
          ((contains? (car left) right)
           (difference (cdr left) right))
          (else
           (cons (car left) (difference (cdr left) right)))))
  (define (make-sequence needs modifies statements)
    (list needs modifies statements))
  (define (needs sequence) (car sequence))
  (define (modifies sequence) (cadr sequence))
  (define (statements sequence) (caddr sequence))
  (define (append-sequences first second)
    (make-sequence
      (union (needs first)
             (difference (needs second) (modifies first)))
      (union (modifies first) (modifies second))
      (append (statements first) (statements second))))
  (define (preserving register first second)
    (if (and (contains? register (needs second))
             (contains? register (modifies first)))
        (append-sequences
          (make-sequence
            (adjoin register (needs first))
            (difference (modifies first) (list register))
            (append (list (list 'save register))
                    (append (statements first)
                            (list (list 'restore register)))))
          second)
        (append-sequences first second)))
  (preserving
    'env
    (make-sequence '(env) '(env val)
                   '((assign env extended) (assign val operand)))
    (make-sequence '(env val) '(val)
                   '((perform apply)))))

(begin
  (define (contains? item items)
    (cond ((null? items) #f)
          ((eq? item (car items)) #t)
          (else (contains? item (cdr items)))))
  (define (adjoin item items)
    (if (contains? item items) items (append items (list item))))
  (define (union left right)
    (if (null? right) left
        (union (adjoin (car right) left) (cdr right))))
  (define (difference left right)
    (cond ((null? left) '())
          ((contains? (car left) right)
           (difference (cdr left) right))
          (else
           (cons (car left) (difference (cdr left) right)))))
  (define (make-sequence needs modifies statements)
    (list needs modifies statements))
  (define (needs sequence) (car sequence))
  (define (modifies sequence) (cadr sequence))
  (define (statements sequence) (caddr sequence))
  (define (append-sequences first second)
    (make-sequence
      (union (needs first)
             (difference (needs second) (modifies first)))
      (union (modifies first) (modifies second))
      (append (statements first) (statements second))))
  (define (preserving register first second)
    (if (and (contains? register (needs second))
             (contains? register (modifies first)))
        (append-sequences
          (make-sequence
            (adjoin register (needs first))
            (difference (modifies first) (list register))
            (append (list (list 'save register))
                    (append (statements first)
                            (list (list 'restore register)))))
          second)
        (append-sequences first second)))
  (preserving
    'env
    (make-sequence '(env) '(env val)
                   '((assign env extended) (assign val operand)))
    (make-sequence '(env val) '(val)
                   '((perform apply)))))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The first program returns a sequence that needs (env), modifies (val), and surrounds the first statements with (save env) and (restore env). The second returns (#t #f).

Trace focus

Follow both membership checks before the sequence is wrapped. Then inspect how difference removes env from the exposed modification set while the emitted statement list gains save and restore.

Try it yourself

Change the program and compare the result.

Change the second sequence so it needs only val. Predict the composed need and modification sets and whether any save or restore remains.

Show hint

Without env in the second need set, preserving takes the ordinary append-sequences branch.

Complete this lesson

0 of 23 lessons complete in this chapter0%