Компиляция того же самого выражения с типом связи return должна породить команды

(assign val (const 5)) (goto (reg continue))

В первом случае выполнение продолжится на следующей команде последовательности. Во втором мы вернемся из процедуры. В обоих случаях значение выражения будет помещено в целевой регистр val.

Последовательности команд и использование стека

Каждый генератор кода возвращает последовательность команд (instruction sequence), содержащую порожденный для выражения объектный код. Порождение кода для составных выражений достигается путем сочетания более простых сегментов, порожденных генераторами кода для подвыражений, так же, как вычисление составного выражения проходит через вычисление подвыражений.

Простейший способ сочетания последовательностей команд - процедура под названием append-instruction-sequences. Она принимает в качестве аргументов произвольное число последовательностей команд, которые надо выполнить одну за другой. Процедура склеивает их и возвращает полученную последовательность. А именно, если (посл]) и (посл) - последовательности команд, то вычисление

(append-instruction-sequences (посл]) (посл)

вернет последовательность

(посл]) (посл2)

Когда требуется сохранять регистры, генераторы кода используют preserving, более сложный метод сочетания последовательностей команд. Preserving принимает три аргумента: множество регистров и две последовательности, которые требуется выполнить одна за другой. Эта процедура склеивает последовательности таким образом, что содержимое всех регистров из множества сохраняется во время выполнения первой последовательности, если оно нужно при выполнении второй. Таким образом, если первая последовательность изменяет регистр, а второй последовательности нужно его исходное содержимое, preserving оборачивает вокруг первой последовательности команды save и restore для этого регистра, прежде чем склеить последовательности. В противном случае она просто возвращает склеенные последовательности команд. Так, например,

(preserving (list (рев]) (рев2)) (посл]) (посл)

порождает одну из следующих четырех последовательностей команд, в зависимости от того, как (посл]) и (посл) используют (рег]) и (рег):

(посл]) ( посл2 )

или

(save (рее)) (посл

(restore (рее) или

(save (рее2)) ( посл1 )

(restore (рее2)) ( посл2 )

или

(save (рее2)) (save реец)) ( посл1 )

(restore (рее1)) (restore (рее2))

(посл2)

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

В принципе мы могли бы представлять последовательность команд просто как список отдельных команд. В таком случае append-instruction-se-quences могла бы склеивать последовательности с помощью обычного append для списков. Однако тогда preserving оказалась бы более сложной операцией, поскольку ей пришлось бы исследовать каждую последовательность команд и выяснять, как там используются регистры. Preserving была бы при этом сложной и неэффективной, поскольку она анализировала бы каждый из своих аргументов-последовательностей, при том, что сами эти последовательности могли быть созданы вызовами preserving, и в этом случае их части были бы уже проанализированы. Чтобы избежать такого многократного анализа, мы с каждой последовательностью команд будем связывать некоторую информацию о том, как она использует регистры. При порождении элементарной последовательности мы будем указывать эту информацию явно, а процедуры, сочетающие последовательности, будут выводить информацию об использовании регистров для составной последовательности из информации, связанной с ее последовательностями-компонентами.

Последовательность команд будет содержать три вида информации:

•множество регистров, которые должны быть инициализированы, прежде чем выполняются команды из последовательности (говорится, что последовательность нуждается (needs) в этих регистрах),

•множество регистров, значения которых последовательность изменяет, и

•сами команды (называемые также предложениями (statements)) в последовательности.

Мы будем представлять последовательность команд в виде списка из трех частей. Таким образом, конструктор для последовательностей команд таков:

(define (make-instruction-sequence needs modifies statements) (list needs modifies statements))

Например, последовательность из двух команд, которая ищет значение переменной x в текущем окружении, присваивает его val, а затем возвращается, требует, чтобы были проинициализированы регистры env и continue, и изменяет регистр val. Следовательно, эту последовательность можно построить так:

(make-instruction-sequence (env continue) (val) ((assign val

(op lookup-variable-value) (const x) (reg env)) (goto (reg continue))))

Иногда нам нужно будет строить последовательность без команд:

(define (empty-instruction-sequence)

(make-instruction-sequence () () ()))

Процедуры для сочетания последовательностей команд приведены в разделе 5.5.4.

Упражнение 5.31.

Во время вычисления вызова процедуры вычислитель с явным управлением всегда сохраняет и восстанавливает регистр env при вычислении оператора, сохраняет и восстанавливает env при вычислении каждого операнда (кроме последнего), сохраняет и восстанавливает argl при вычислении каждого операнда, а также сохраняет и восстанавливает proc при вычислении последовательности операндов. Для каждой из следующих комбинаций скажите, какие из этих операций save и restore излишни и могут быть исключены с помощью механизма preserving:

(f x y)

((f) x y)

(f (g x) y) (f (g x) y)

Упражнение 5.32.

С помощью механизма preserving компилятор сможет избежать сохранения и восстановления env при вычислении оператора комбинации в случае, если это символ. Такие оптимизации можно было бы встроить и в интерпретатор. В сущности, вычислитель с явным управлением из раздела 5.4 уже проводит одну подобную оптимизацию, поскольку рассматривает комбинацию без операндов как особый случай.

a.Расширьте вычислитель с явным управлением так, чтобы он как особый случай рассматривал комбинации, в которых оператором является символ, и при вычислении таких выражений использовал это свойство оператора.

b.Лиза П. Хакер говорит, что если заставить интерпретатор рассматривать все больше особых случаев, то можно включить в него все оптимизации компилятора, и при этом все преимущество компиляции пропадет. Каково Ваше мнение?