5.5 · 레지스터 생존성

다음 명령열이 아직 필요로 하는 레지스터만 저장한다.

명령열의 need와 modify 집합을 사용하면 합성 코드가 이전 값을 save/restore로 보호해야 하는 시점을 판단할 수 있습니다.

생각해 볼 질문

두 명령열 사이에서 컴파일러는 언제 레지스터를 보존해야 할까요?

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 코드SICP에 필요한 Scheme 호환 문법을 리스펙스 SICP 프로필로 실행합니다.

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

리스펙스 학습용 런타임리스펙스 SICP 프로필 1.0.0

리스펙스 SICP 런타임 불러오는 중

리스펙스 · SICP 코드UTF-8 1,789 / 1,048,576바이트

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

예제

결과—

출력: —
값: —
진단: —

보이는 실행 흐름0 / 0 개의 실행 이벤트

이 브라우저 결과는 리스펙스 바우치나 권한이 아닙니다.wasm —

예상 관찰

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

실행 흐름에서 볼 점

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.

직접 해보기

힌트를 보기 전에 프로그램을 바꿔 보세요.

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

힌트 하나 보기

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