5.5.4 · Живучесть регистров

Сохранение регистров через save и restore

Множества потребностей и модификаций последовательности команд решают, когда скомпонованный код защищает прежнее значение регистра через save и restore.

Вопрос для размышления

Когда компилятору необходимо сохранять регистр между двумя последовательностями команд?

Чтение потребностей и модификаций регистров как контрактов последовательностей
Обнаружение значения, необходимого после того, как более ранняя последовательность перезаписывает его
Вставка save и restore только вокруг этого конфликта
Обновление контракта скомпонованной последовательности после сохранения

Конфликт возникает тогда, когда второй последовательности требуется входящее значение регистра, а первая последовательность модифицирует этот регистр. Процедура preserving оборачивает первые инструкции командами save и restore, чтобы вторая последовательность видела исходное значение.

Обернутой первой последовательности теперь требуется этот регистр для его сохранения, и она больше не объявляет его модифицированным после restore. Если любая из сторон конфликта отсутствует, компоновка не генерирует никаких команд работы со стеком.

Код SICP1,789 из 1,048,576 байт UTF-8

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

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Первая программа возвращает последовательность, которая требует (env), модифицирует (val) и обрамляет первые инструкции командами (save env) и (restore env). Вторая программа возвращает (#t #f).

На что обратить внимание в трассе

Проследите за обеими проверками принадлежности перед тем, как последовательность будет обернута. Затем изучите, как difference удаляет env из открытого множества модификаций, пока генерируемый список инструкций пополняется save и restore.

Попробуйте сами

Измените программу и сравните результат.

Измените вторую последовательность так, чтобы ей требовался только val. Предскажите составные множества потребностей и модификаций, а также то, останутся ли какие-либо save или restore.

Показать подсказку

Без env во втором множестве потребностей preserving выбирает обычную ветку append-sequences.

Завершить этот урок

В этой главе пройдено 0 из 23 урока0%