after-call20

(assign argl (op list) (reg val)) (restore env)

(assign val (op lookup-variable-value) (const x) (reg env)) (assign argl (op cons) (reg val) (reg argl)) (restore proc) (restore continue)

(test (op primitive-procedure?) (reg proc))

(branch (label primitive-branch25)) compiled-branch24

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val)) primitive-branch25

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

(goto (reg continue)) after-call23 after-lambda15

(perform (op define-variable!) (const f) (reg val) (reg env)) (assign val (const ok))

Рис. 5.18: Пример вывода компилятора (продолжение).

(из которых только одна будет выполняться). Мы не показали ту часть контроллера, которая реализует примитивы, но мы предполагаем, что эти команды используют элементарные арифметические операции в путях данных машины. Рассмотрим, насколько меньше кода будет порождаться, если компилятор сможет вставлять примитивы в виде явного кода (open coding) - то есть порождать код, который прямо использует эти машинные операции. Выражение (+ a 1) можно было бы скомпилировать в простую последовательность вроде43

(assign val (op lookup-variable-value) (const a) (reg env)) (assign val (op +) (reg val) (const 1))

В этом упражнении мы расширим компилятор так, чтобы он поддерживал явное кодирование отдельных примитивов. При обращениях к этим примитивам будет порождаться специально написанный код, а не общий код для вызова процедуры. Для того, чтобы поддержать такую работу, мы дополним машину специальными регистрами для аргументов arg1 и arg2. Элементарные арифметические операции машины будут принимать свои аргументы в arg1 и arg2. Они могут помещать результаты в val, arg1 или arg2.

Компилятор должен уметь распознавать вызов явно кодируемого примитива в исходной программе. Мы дополним распознаватель в процедуре compile, так, чтобы он узнавал имена этих примитивов в дополнение к зарезервированным словам (особым формам), которые он узнает сейчас.44 Для каждой особой формы в компиляторе есть свой генератор кода. В этом упражнении мы построим семью генераторов кода для явно кодируемых примитивов.

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

44 Вообще говоря, превращение примитивов в зарезервированные слова - плохая идея, потому что тогда пользователь не может связать эти имена с другими процедурами. Более того, если мы добавим зарезервированные слова в компилятор, который уже используется, перестанут работать существующие программы, которые определяют процедуры с такими именами. Идеи, как можно избежать этой проблемы, можно найти в упражнении 5.44.

a.В отличие от особых форм, явно кодируемые примитивы требуют, чтобы их аргументы вычислялись. Напишите генератор кода spread-arguments, который будут использовать генераторы явного кода. Spread-arguments должен принимать список операндов и компилировать данные ему операнды, направляя их в последовательные аргументные регистры. Заметим, что операнд может содержать вызов явно кодируемого примитива, так что во время вычисления операндов придется сохранять аргументные регистры.

b.Для каждой из элементарных процедур =, *, - и + напишите по генератору кода, который принимает комбинацию, содержащую этот оператор вместе с целевым регистром и описателем связи, и порождает код, который раскидывает аргументы по регистрам, а затем проводит операцию с данным целевым регистром и указанным типом связи. Достаточно обрабатывать только выражения с двумя операндами. Заставьте compile передавать управление этим генераторам кода.

c.Опробуйте обновленный компилятор на примере с процедурой factorial. Сравните полученный результат с результатом, который получается без открытого кодирования.

d.Расширьте свои генераторы кода для + и * так, чтобы они могли обрабатывать выражения с произвольным числом операндов. Выражение, в котором операндов больше двух, придется компилировать в последовательность операций, каждая из которых работает с двумя входами.

5.5.6 Лексическая адресация

Одна из наиболее часто встречающихся в компиляторах оптимизаций связана с поиском переменных. В нынешнем виде наш компилятор использует операцию lookup-variable-value машины-вычислителя. Эта операция ищет переменную, сравнивая ее со всеми переменными, связанными в данный момент, и проходя кадр за кадром по окружению, имеющемуся во время выполнения. Если кадр глубоко вложен или если имеется много переменных, этот поиск может оказаться дорогим. Рассмотрим, например, задачу поиска значения x при вычислении выражения (* x y z) внутри процедуры, возвращаемой при вычислении

(let ((x 3) (y 4))

(lambda (a b c d e)

(let ((y (* a b x))

(z (+ c d x))) (* x y z))))

Поскольку выражение let - всего лишь синтаксический сахар для комбинации lambda, это выражение равносильно

((lambda (x y)

(lambda (a b c d e)

((lambda (y z) (* x y z))

(* a b x) (+ c d x))))

3

4)

Каждый раз, когда lookup-variable-value ищет x, она должна убедиться, что символ x не равен (через eq?) ни y, ни z (в первом кадре), ни a, b, c, d, ни

e (во втором). Предположим, временно, что в наших программах не используется define - что переменные связываются только через lambda. Поскольку в нашем языке лексическая сфера действия, во время выполнения окружение любого выражения будет иметь структуру, параллельную лексической структуре программы, в которой это выражение встречается.45 Таким образом, компилятор при анализе вышеуказанного выражения может узнать, что каждый раз, когда процедура применяется, переменная с именем x будет найдена на два кадра выше текущего, и в этом кадре будет первая.

Мы можем это использовать и ввести новый вид операции поиска переменной, lexical-address-lookup, который в качестве аргументов берет окружение и лексический адрес (lexical address), состоящий из двух чисел: номера кадра (frame number), который показывает, сколько кадров надо пропустить, и смещения (displacement number), которое показывает, сколько переменных нужно пропустить в этом кадре. Lexical-address-lookup будет возвращать значение переменной, которая имеет указанный лексический адрес по отношению к текущему окружению. Добавив в свою машину lexical-address-lookup, мы можем научить компилятор порождать код, который обращается к переменным через эту операцию, а не через lookup-variable-value. Подобным образом, скомпилированный код может использовать новую операцию lexical-address-set! вместо set-variable-value!.

Для того, чтобы порождать такой код, компилятор должен уметь определять лексический адрес переменной, ссылку на которую он намерен скомпилировать. Лексический адрес переменной зависит от того, где она находится в коде. Например, в следующей программе адрес x в выражении (el) есть (2,0) - на два кадра назад и первая переменная в кадре. В этом же месте y имеет адрес (0,0), а c - адрес (1,2). В выражении (e2) x имеет адрес (1,0), y адрес (1,1), а c адрес (0,2).

((lambda (x y)

(lambda (a b c d e) ((lambda (y z) (el)) (e2)

(+ c d x))))

3

4)

Один из способов породить в компиляторе код, который использует лексическую адресацию, состоит в поддержании структуры данных, называемой окружение времени компиляции (compile-time environment). Она следит за тем, какие переменные в каких позициях и в каких кадрах будут находиться в окружении времени выполнения, когда будет выполняться определенная операция доступа к переменной. Окружение времени компиляции представляет собой список кадров, каждый из которых содержит список переменных. (Разумеется, с переменными не будет связано никаких значений, поскольку во время компиляции значения не вычисляются.) Окружение времени компиляции становится дополнительным аргументом процедуры compile и передается всем генераторам кода. Вызов compile верхнего уровня использует пустое окружение времени компиляции. Когда компилируется тело lambda, compile-lambda-body расширяет это окружение кадром, содержащим параметры процедуры,

45Это не так, если мы разрешаем внутренние определения и если мы от них не избавляемся. См. упражнение 5.43.