Основы компиляции с использованием инкрементного подхода в python. Глава 2

Nov 10, 2024

2. Целые Числа и Переменные

В этой главе мы рассмотрим компиляцию подмножества Python в ассемблерный код x86-64 (Intel 2015). Подмножество, названный $L_{Var}$ , включает целочисленную арифметику и локальные переменные. Мы часто будем называть x86-64 просто x86. Сначала глава описывает язык (раздел 2.1), а затем вводит ассемблер x86 (раздел 2.2). Поскольку язык ассемблера x86 велик, мы обсудим только те инструкции, которые необходимы для компиляции $L_{Var}$ . Мы представим больше инструкций x86 в последующих главах. После знакомства с $L_{Var}$ и x86 мы рассмотрим их различия и создадим план, чтобы разбить процесс перевода из $L_{Var}$ в x86 на несколько шагов (раздел 2.3). Остальная часть главы предоставляет подробные подсказки по каждому шагу. Наша цель — дать достаточно подсказок, чтобы подготовленный читатель, вместе с несколькими друзьями, мог реализовать компилятор из $L_{Var}$ в x86 за короткое время. Чтобы дать представление о масштабе этого первого компилятора, отметим, что решение инструктора для компилятора $L_{Var}$ составляет примерно 300 строк кода.

2.1 Язык $L_{Var}$

Язык $L_{Var}$ расширяет язык $L_{Int}$ переменными. Конкретный синтаксис языка $L_{Var}$ задается грамматикой, представленной на рисунке 2.1, а абстрактный синтаксис — на рисунке 2.2. Нетерминальный элемент var может быть любым идентификатором Python. Как и в $L_{Int}$ , input_int является нулевым оператором, - — унарным оператором, а + — бинарным оператором. Аналогично $L_{Int}$, абстрактный синтаксис $L_{Var}$ включает экземпляр Module, который обозначает верхнюю часть программы. Несмотря на простоту языка $L_{Var}$, он достаточно богат, чтобы продемонстрировать несколько техник компиляции.

Язык $L_{Var}$ включает оператор присваивания, который определяет переменную для использования в последующих операторах и инициализирует переменную значением выражения. Абстрактный синтаксис для присваивания определяется на рисунке 2.2. Конкретный синтаксис для присваивания выглядит так:

var = exp

Например, следующая программа инициализирует переменную x со значением 32, а затем выводит результат 10 + x, получая 42:

x = 12 + 20
print(10 + x)

exp ::= int | input_int() | - exp | exp + exp | exp - exp | (exp)
stmt ::= print(exp) | exp
__________________________________
exp  ::= var
stmt ::= var=exp
LVar ::= stmt*

Рисунок 2.1 Конкретный синтаксис $L_{Var}$

exp ::= Constant(int) | Call(Name('input_int'),[])
	| UnaryOp(USub(), exp) | BinOp(exp, Add(), exp)
	| BinOp(exp, Sub(), exp)
stmt ::= Expr(Call(Name('print'), [exp])) | Expr(exp)
________________________________
exp ::= Name(var)
stmt ::= Assign([Name(var)], exp)
LVar ::= Module(stmt∗)

Рисунок 2.2 Абстрактный синтаксис $L_{Var}$

2.1.1 Расширяемые Интерпретаторы с помощью Переопределения Методов

Чтобы подготовиться к обсуждению интерпретатора $L_{Var}$ , мы объясняем, почему мы реализуем его в объектно-ориентированном стиле. В течение всей этой книги мы определяем множество интерпретаторов — по одному для каждого языка, который мы изучаем. Поскольку каждый язык строится на основе предыдущего, существует много общего между этими интерпретаторами. Мы хотим записать общие части всего один раз, вместо того чтобы делать это много раз. Наивный интерпретатор для $L_{Var}$ обрабатывал бы случай переменных, но в остальных случаях перенаправлял бы выполнение на интерпретатор для $L_{Int}$ . Следующий код иллюстрирует эту идею. (Мы объясним параметр env в разделе 2.1.2.)

def interp_Lint(e, env):
    match e:
        case UnaryOp(USub(), e1):
            return -interp_Lint(e1, env)
        …

def interp_Lvar(e, env):
    match e:
        case Name(id):
            return env[id]
        case _:
            return interp_Lint(e, env)

Проблема с этим наивным подходом заключается в том, что он не обрабатывает ситуации, в которых особенность $L_{Var}$, такая как переменная, вложена внутри особенности $L_{Int}$ , такой как оператор -, как в следующей программе:

y = 10
print(-y)

Если мы вызовем interp_Lvar для этой программы, он перенаправит управление в interp_Lint для обработки оператора -, но затем рекурсивно вызовет interp_Lint снова на своем аргументе. Поскольку в interp_Lint нет случая для Name, возникает ошибка! Чтобы сделать наши интерпретаторы расширяемыми, нам понадобится то, что называется открытой рекурсией, при которой связывание рекурсивного узла откладывается до тех пор, пока функции не будут скомпонованы. Объектно-ориентированные языки предоставляют открытую рекурсию через переопределение методов. Следующий код использует переопределение методов для интерпретации $L_{Int}$ и $L_{Var}$ с помощью определений классов Python. Мы определяем один класс для каждого языка и определяем метод для интерпретации выражений внутри каждого класса. Класс для $L_{Var}$ наследует от класса для $L_{Int}$ , и метод interp_exp в $L_{Var}$ переопределяет interp_exp в $L_{Int}$ . Обратите внимание, что случай по умолчанию в interp_exp в $L_{Var}$ использует super(), чтобы вызвать interp_exp, и поскольку $L_{Var}$ наследуется от $L_{Int}$ , это перенаправляет выполнение к interp_exp в $L_{Int}$ .

class InterpLint:
    def interp_exp(self, e):
        match e:
            case UnaryOp(USub(), e1):
                return neg64(self.interp_exp(e1))
            ...
    ...

class InterpLvar(InterpLint):
    def interp_exp(self, e):
        match e:
            case Name(id):
                return env[id]
            case _:
                return super().interp_exp(e)
            ...

Вернемся к проблемному примеру, который мы уже рассматривали:

y = 10
print(-y)

Мы можем вызвать метод interp_exp для $L_{Var}$ на выражении -y, которое мы обозначим как e0, создав объект класса $L_{Var}$ и вызвав метод:

InterpLvar().interp_exp(e0)

Чтобы обработать оператор -, случай по умолчанию в interp_exp в $L_{Var}$ перенаправляет выполнение к методу interp_exp в $L_{Int}$ . Но затем для рекурсивного вызова метода выполнение перенаправляется к interp_exp в $L_{Var}$ , где узел Name обрабатывается корректно. Таким образом, переопределение методов дает нам открытую рекурсию, необходимую для реализации наших интерпретаторов в расширяемом виде.

2.1.2 Опреляющий интерпретатор для $L_{Var}$

После того как мы обосновали использование классов и методов для реализации интерпретаторов, мы вновь рассматриваем опреаляющий интерпретатор для $L_{Int}$ , показанный на рисунке 2.3, и затем расширяем его для создания интерпретатора для $L_{Var}$, который показан на рисунке 2.4. Мы изменяем метод interp_stmt в интерпретаторе для $L_{Int}$ , добавив два дополнительных параметра, названных env, которые мы обсудим в следующем абзаце, и cont для продолжения, что является техническим названием для того, что идет после определенной точки в программе. Параметр cont — это список операторов, следующих за текущим оператором. Обратите внимание, что interp_stmts вызывает interp_stmt для первого оператора и передает оставшиеся операторы в качестве аргумента для cont. Эта организация позволяет каждому оператору решать, что, если что-то, должно быть выполнено после него, например, позволяя оператору возврата (return) преждевременно выходить из функции (см. Главу 8). Интерпретатор для языка $L_{Var}$ добавляет два новых случая для переменных и присваивания. Для присваивания нам нужен способ сообщить значение, связанное с переменной, всем ее использованиям. Для достижения этой цели мы поддерживаем отображение от переменных к значениям, называемое окружением. Мы используем словарь Python для представления окружения. Функция interp_exp принимает текущее окружение, env, в качестве дополнительного параметра. Когда интерпретатор сталкивается с переменной, он ищет соответствующее значение в окружении. Если переменная отсутствует в окружении (потому что переменная не была определена), то поиск завершится неудачей, и интерпретатор остановится с ошибкой. Напомним, что компилятор не обязан компилировать такие программы (Раздел 1.5). Когда интерпретатор сталкивается с оператором присваивания, он вычисляет инициализирующее выражение, а затем связывает полученное значение с переменной в окружении. Цель этой главы — реализовать компилятор, который переводит любую программу $P_1$ , написанную на языке $L_{Var}$ , в программу на ассемблере x86 $P_2$ так, чтобы $P_2$ демонстрировала такое же поведение при выполнении на компьютере, как и программа $P_1$ , интерпретируемая с помощью interp_LVar. То есть они должны выводить одно и то же целое число n . Мы иллюстрируем этот критерий корректности на следующей диаграмме: ![[Снимок экрана 2024-11-03 в 21.17.28.png]]

Теперь мы вводим подмножество x86 под названием $x86{Int}$ , которое достаточно для компиляции $L{Var}$ .

2.2 Язык Ассемблера $x86_{int}$

Рисунок 2.5 определяет конкретный синтаксис для $x86_{int}$ . Мы используем синтаксис AT&T, ожидаемый от компилятора GNU. Программа начинается с метки main, за которой следует последовательность инструкций. Директива globl делает основную процедуру видимой извне, чтобы операционная система могла вызвать её. Программа x86 хранится в памяти компьютера. Для наших целей память компьютера представляет собой отображение 64-битных адресов на 64-битные значения. У компьютера есть счетчик команд (PC), хранящийся в регистре rip, который указывает на адрес следующей инструкции, которая должна быть выполнена. Для большинства инструкций счетчик команд увеличивается после выполнения инструкции, так что он указывает на следующую инструкцию в памяти. Большинство инструкций x86 принимают два операнда, каждый из которых может быть целочисленной константой (называемой непосредственным значением), регистром или ячейкой памяти.

class InterpLint:
    def interp_exp(self, e, env):
        match e:
            case BinOp(left, Add(), right):
                l = self.interp_exp(left, env)
                r = self.interp_exp(right, env)
                return add64(l, r)
            case BinOp(left, Sub(), right):
                l = self.interp_exp(left, env)
                r = self.interp_exp(right, env)
                return sub64(l, r)
            case UnaryOp(USub(), v):
                return neg64(self.interp_exp(v, env))
            case Constant(value):
                return value
            case Call(Name('input_int'), []):
                return int(input())
    
    def interp_stmt(self, s, env, cont):
        match s:
            case Expr(Call(Name('print'), [arg])):
                val = self.interp_exp(arg, env)
                print(val, end='')
                return self.interp_stmts(cont, env)
            case Expr(value):
                self.interp_exp(value, env)
                return self.interp_stmts(cont, env)
            case _:
                raise Exception('error in interp_stmt, unexpected ' + repr(s))

    def interp_stmts(self, ss, env):
        match ss:
            case []:
                return 0
            case [s, *ss]:
                return self.interp_stmt(s, env, ss)
    
    def interp(self, p):
        match p:
            case Module(body):
                self.interp_stmts(body, {})

def interp_Lint(p):
    return InterpLint().interp(p)

Рисунок 2.3 Интерпретатор для $L_{Int}$ как класса.

class InterpLvar(InterpLint):
    def interp_exp(self, e, env):
        match e:
            case Name(id):
                return env[id]
            case _:
                return super().interp_exp(e, env)

    def interp_stmt(self, s, env, cont):
        match s:
            case Assign([Name(id)], value):
                env[id] = self.interp_exp(value, env)
                return self.interp_stmts(cont, env)
            case _:
               return super().interp_stmt(s, env, cont)

def interp_Lvar(p):
    return InterpLvar().interp(p)

Рисунок 2.4 Интерпретатор для языка $L_{Var}$ .

reg ::= rsp | rbp | rax | rbx | rcx | rdx | rsi | rdi |
        r8  | r9  | r10 | r11 | r12 | r13 | r14 | r15

arg ::= $int | %reg | int(%reg)
instr ::= addq arg,arg | subq arg,arg | negq arg | movq arg,arg |
          callq label | pushq arg | popq arg | retq
x86Int ::= .globl main
			main: instr∗

Рисунок 2.5 Синтаксис ассемблерного языка $x86_{int}$ (синтаксис AT&T).

Регистры — это особый вид переменной, который хранит 64-битное значение. В компьютере имеется 16 регистров общего назначения; их названия приведены на рисунке 2.5. Регистры записываются с предшествующим знаком процента, %, за которым следует их имя, например, %rax. Непосредственное значение записывается с помощью обозначения $ n, где n — это целое число. Обращение к памяти задается с помощью синтаксиса n(%r), который получает адрес, хранящийся в регистре r, и затем добавляет n байтов к этому адресу. Полученный адрес используется для загрузки или сохранения в памяти в зависимости от того, встречается ли он в качестве исходного или целевого аргумента инструкции.

.globl main
main:
    movq $10, %rax   # Загружаем 10 в регистр rax
    addq $32, %rax   # Прибавляем 32 к значению в rax
    retq              # Возвращаемся из функции

Рисунок 2.6 x86 программа, которая вычисляет 10 + 32.

Арифметическая инструкция, такая как addq s, d, считывает данные из источника s и назначения d, выполняет арифметическую операцию и затем записывает результат обратно в d. Инструкция перемещения movq s, d считывает данные из s и сохраняет результат в d. Инструкция callq label переходит к процедуре, указанной меткой, а retq возвращает управление из процедуры ее вызывающей программе. Мы более подробно обсуждаем вызовы процедур позже в этой главе и в главе 8. Последняя буква q указывает на то, что эти инструкции работают с кватерниками, которые представляют собой значения размером 64 бита. В Приложении A.1 содержится справочник всех инструкций x86, используемых в этой книге. Рисунок 2.6 изображает x86 программу, которая вычисляет 10 + 32. Инструкция movq $10, %rax помещает 10 в регистр rax, а затем addq $32, %rax добавляет 32 к 10 в rax и помещает результат, 42, обратно в rax. Последняя инструкция retq завершает функцию main, возвращая целое число в rax операционной системе. Операционная система интерпретирует это целое число как код завершения программы. По соглашению, код завершения 0 указывает, что программа завершилась успешно, а все остальные коды завершения указывают на различные ошибки. Мы продемонстрируем использование памяти для хранения промежуточных результатов в следующем примере. Рисунок 2.7 содержит x86 программу, которая вычисляет 52 + -10. Эта программа использует область памяти, называемую стеком вызовов процедур (сокращенно стек). Стек состоит из отдельного фрейма для каждого вызова процедуры. Расположение в памяти для отдельного фрейма показано на рисунке 2.8. Регистр rsp называется указателем стека и содержит адрес элемента, находящегося на вершине стека. В общем, мы используем термин “указатель” для обозначения чего-либо, что содержит адрес. Стек растет вниз по памяти, поэтому мы увеличиваем размер стека, вычитая из указателя стека. В контексте вызова процедуры адрес возврата — это расположение инструкции, которая следует сразу за инструкцией вызова на стороне вызывающего кода. Инструкция вызова функции callq помещает адрес возврата в стек перед тем, как перейти к процедуре. Регистр rbp — это базовый указатель, который используется для доступа к переменным, хранящимся в фрейме текущего вызова процедуры. Базовый указатель вызывающего кода сохраняется сразу после адреса возврата. Рисунок 2.8 показывает расположение памяти фрейма с хранением для n переменных, которые нумеруются от 1 до n. Переменная 1 хранится по адресу -8(%rbp), переменная 2 — по адресу -16(%rbp) и так далее. В программе, представленной на рисунке 2.7, рассмотрим, как управление передается от операционной системы к функции main. Операционная система выполняет инструкцию callq main, которая помещает адрес возврата в стек, а затем переходит к main. В x86-64 указатель стека rsp должен быть кратен 16 байтам перед выполнением любой инструкции callq, чтобы при переходе управления в main он находился на 8 байт с выходом из согласования (так как callq сохраняет адрес возврата на стеке). Первые три инструкции представляют собой стандартный пролог для процедуры.

.globl main
main:
    pushq %rbp                ; Сохраняем указатель базового кадра текущего вызова
    movq %rsp, %rbp          ; Устанавливаем базовый указатель
    subq $16, %rsp            ; Выделяем место для переменных
    movq $10, -8(%rbp)       ; Сохраняем 10 в переменную 1
    negq -8(%rbp)            ; Меняем значение переменной 1 на -10
    movq -8(%rbp), %rax      ; Перемещаем -10 в регистр rax
    addq $52, %rax           ; Прибавляем 52 к значению в rax
    addq $16, %rsp           ; Восстанавливаем указатель стека
    popq %rbp                ; Восстанавливаем базовый указатель
    retq                     ; Возвращаемся из функции

Рисунок 2.7 Программа для x86, которая вычисляет 52 + -10.

- `8(%rbp)` — адрес возврата
- `0(%rbp)` — старое значение `rbp`
- `-8(%rbp)` — переменная 1
- `-16(%rbp)` — переменная 2
- ...
- `0(%rsp)` — переменная n

Рисунок 2.8 Схема памяти кадра.

Инструкция pushq %rbp сначала вычитает 8 из указателя стека rsp, а затем сохраняет указатель базы вызывающей функции по адресу rsp в стеке. Следующая инструкция movq %rsp, %rbp устанавливает указатель базы в текущее положение указателя стека, который теперь указывает на место старого указателя базы. Инструкция subq $16, %rsp перемещает указатель стека вниз, чтобы освободить достаточно места для хранения переменных. Эта программа нуждается в одной переменной (8 байт), но мы округляем до 16 байт, чтобы rsp был выровнен по 16 байтам, и затем мы готовы вызывать другие функции. Первая инструкция после прелюдии — movq $10, -8(%rbp), которая сохраняет значение 10 в переменной 1. Инструкция negq -8(%rbp) изменяет содержимое переменной 1 на –10. Следующая инструкция перемещает значение –10 из переменной 1 в регистр rax. Наконец, addq $52, %rax добавляет 52 к значению в rax, обновляя его содержимое до 42. Заключительная часть основной функции состоит из последних трех инструкций. Первые две восстанавливают регистры rsp и rbp в их состояние в начале процедуры. В частности, addq $16, %rsp перемещает указатель стека так, чтобы он указывал на старый указатель базы. Затем команда popq %rbp восстанавливает старый базовый указатель в rbp и добавляет 8 к указателю стека.

reg ::= 'rsp' | 'rbp' | 'rax' | 'rbx' | 'rcx' | 'rdx' | 'rsi' | 'rdi' |
        'r8' | 'r9' | 'r10' | 'r11' | 'r12' | 'r13' | 'r14' | 'r15'
arg ::= Immediate(int) | Reg(reg) | Deref(reg,int)
instr ::= Instr('addq',[arg,arg]) | Instr('subq',[arg,arg])
        | Instr('movq',[arg,arg]) | Instr('negq',[arg])
        | Instr('pushq',[arg]) | Instr('popq',[arg])
        | Callq(label,int) | Retq() | Jump(label)
x86Int ::= X86Program(instr∗)

Рисунок 2.9 Абстрактный синтаксис ассемблера $x86_{int}$.

Последняя инструкция retq возвращает управление в процедуру, которая вызвала текущую, и добавляет 8 к указателю стека. Нашему компилятору нужен удобный способ представления для манипуляции программами на x86, поэтому мы определяем абстрактный синтаксис для x86, который показан на рисунке 2.9. Мы называем этот язык $x86{int}$ . Основное отличие между ним и конкретным синтаксисом $x86{int}$ (рисунок 2.5) заключается в том, что метки, имена инструкций и имена регистров явно представлены строками. Что касается абстрактного синтаксиса для callq, узел AST Callq включает целое число, представляющее арити функции, то есть количество аргументов, что полезно знать во время распределения регистров (глава 4).

2.3 Планирование перехода на x86

Чтобы скомпилировать один язык на другой, полезно сосредоточиться на различиях между двумя языками, поскольку компилятору нужно будет преодолеть эти различия. Какие различия существуют между $L_{Var}$ и ассемблером x86? Вот некоторые из наиболее важных:

Арифметические инструкции x86 обычно имеют два аргумента и обновляют второй аргумент на месте. В отличие от этого, арифметические операции $L_{Var}$ принимают два аргумента и производят новое значение. Инструкция x86 может иметь не более одного аргумента, связанного с памятью. Более того, некоторые инструкции x86 накладывают специальные ограничения на свои аргументы.
Аргумент оператора $L_{Var}$ может быть глубоко вложенным выражением, тогда как инструкции x86 ограничивают свои аргументы целыми числами, регистрами и адресами памяти.
Программа на $L_{Var}$ может содержать любое количество переменных, в то время как x86 имеет только 16 регистров и стек вызовов процедур.

Мы облегчаем задачу компиляции из $L_{Var}$ в x86, разделяя проблему на несколько шагов, каждый из которых справляется с этими различиями поочередно. Каждый из этих шагов называется проходом компилятора. Этот термин указывает на то, что каждый шаг «проходит» или «перебирает» AST программы. Кроме того, мы следуем подходу нано-проходов, что означает, что на каждом проходе мы стремимся достичь одной четкой цели, а не двух или трех одновременно. Сначала мы набрасываем, как могли бы реализовать каждый проход, и даем каждому проходу имя. Затем мы определяем порядок выполнения проходов и язык ввода/вывода для каждого из них. Первым языком ввода служит $L_{Var}$ , а последним — $x86{int}$ . Между этими двумя проходами мы можем выбрать любой язык, который наиболее удобен для выражения вывода каждого прохода, будь то $L{Var}$ , $x86{int}$ или новый промежуточный язык, который мы разработаем. Наконец, для реализации каждого прохода мы пишем одну рекурсивную функцию на каждый нетерминальный элемент в грамматике входного языка прохода. Наш компилятор для $L{Var}$ состоит из следующих проходов:

remove_complex_operands — гарантирует, что каждый подвыражение примитивной операции или вызова функции является переменной или целым числом, то есть атомарным выражением. Мы относимся к неатомарным выражениям как к сложным. Этот проход вводит временные переменные для хранения результатов сложных подвыражений.
select_instructions — обрабатывает разницу между операциями $L_{Var}$ и инструкциями x86. Этот проход преобразует каждую операцию $L_{Var}$ в короткую последовательность инструкций, которая выполняет ту же задачу.
assign_homes — заменяет переменные регистрами или стековыми областями.

Следующий вопрос: в каком порядке следует применять эти проходы? Этот вопрос может быть сложным, потому что трудно заранее знать, какие порядки будут лучше (то есть проще в реализации, производить более эффективный код и так далее), и поэтому порядок часто определяется методом проб и ошибок. Тем не менее, мы можем заранее спланировать и сделать обоснованные выборы относительно порядка. Проходы select_instructions и assign_homes переплетаются. В главе 8 мы узнаем, что в x86 регистры используются для передачи аргументов функциям и что предпочтительно присваивать параметры соответствующим регистрам. Это предполагает, что было бы лучше начать с прохода select_instructions, который генерирует инструкции для передачи аргументов, прежде чем выполнять выделение регистров. С другой стороны, если мы сначала выберем инструкции, мы можем столкнуться с тупиком в assign_homes. Напомним, что только один аргумент инструкции x86 может быть обращением к памяти, но assign_homes может быть вынужден присваивать оба аргумента адресам памяти. Сложный подход заключается в том, чтобы повторить оба прохода до тех пор, пока не будет найдено решение. Тем не менее, чтобы сократить сложность реализации, мы рекомендуем сначала разместить select_instructions, затем assign_homes, а затем третий проход под названием patch_instructions, который использует зарезервированный регистр для устранения оставшихся проблем. Рисунок 2.10 представляет порядок проходов компилятора и идентифицирует входные и выходные языки для каждого прохода. Выход прохода select_nstructions — это язык $x86{Var}$, который расширяет $x86{int}$ неограниченным числом переменных области программы и убирает ограничения по аргументам инструкций. Последним проходом является prelude_and_conclusion, который помещает инструкции программы внутри функции main с инструкциями для прелюдии и заключения. Оставшаяся часть этой главы предоставляет рекомендации по реализации каждого из проходов компилятора, представленных на рисунке 2.10. ![[Снимок экрана 2024-11-03 в 23.09.12.png]]

atm ::= Constant(int) | Name(var)
exp ::= atm | Call(Name('input_int'),[])
	| UnaryOp(USub(),atm) | BinOp(atm,Add(),atm)
	| BinOp(atm,Sub(),atm)
stmt ::= Expr(Call(Name('print'),[atm])) | Expr(exp)
	| Assign([Name(var)], exp
LmonVar ::= Module(stmt∗)

Изображение 2.11 $L^{mon}{Var}$ это $L{Var}$ с операндами, ограниченными атомарными выражениями.

2.4 Процесс remove_complex_operands

Проход remove_complex_operands компилирует программы $L_{Var}$ в ограниченную форму, в которой аргументы операций являются атомарными выражениями. Иными словами, этот проход удаляет сложные операнды, такие как выражение -10 в следующей программе. Это достигается за счет введения новой временной переменной, присваивания сложного операнда этой новой переменной и последующего использования новой переменной вместо сложного операнда, как показано в выводе remove_complex_operands снизу.

x = 42 + -10
print(x + 10)

tmp_0 = -10
x = 42 + tmp_0
tmp_1 = x + 10
print(tmp_1)

Рисунок 2.11 представляет грамматику для вывода этого прохода, языка $L^{mon}_{Var}$ .

Единственное различие заключается в том, что аргументы операторов ограничены атомарными выражениями, которые определяются нетерминальным элементом atm . В частности, целочисленные константы и переменные являются атомарными. Атомарные выражения являются чистыми (они не вызывают и не зависят от побочных эффектов), тогда как сложные выражения могут иметь побочные эффекты, такие как Call(Name('input_int'),[]). Язык с такой разницей между чистыми выражениями и выражениями с побочными эффектами называется языком в монадической нормальной форме (Moggi 1991; Danvy 2003), что объясняет префикс “mon” в названии $L^{mon}{Var}$ . Важным инвариантом прохода remove_complex_operands является то, что относительный порядок среди сложных выражений не меняется, однако относительный порядок между атомарными выражениями и сложными выражениями может изменяться, и часто это происходит. Эти изменения сохраняют поведение, потому что атомарные выражения являются чистыми. Мы рекомендуем реализовать этот проход с помощью вспомогательного метода, называемого rco_exp, с двумя параметрами: выражением $L{Var}$ и логическим значением, которое указывает, нужно ли превратить выражение в атомарное. Метод rco_exp должен возвращать пару, состоящую из нового выражения и списка пар, связывающих новые временные переменные с их инициализирующими выражениями. Возвращаясь к примеру программы с выражением 42 + -10, подвыражение -10 должно обрабатываться с использованием функции rco_exp с True в качестве второго аргумента, поскольку -10 является аргументом оператора + и, следовательно, должно стать атомарным. Вывод rco_exp, примененного к -10, будет следующим:

-10

tmp_1
[(tmp_1, -10)]

Особое внимание стоит уделить программам, таким как следующая, которые присваивают атомарное выражение переменной. Вам следует оставлять такие присвоения без изменений, как показано в программе снизу:

a = 42
b = a
print(b)

a = 42
b = a
print(b)

Неосторожная реализация может привести к следующему выводу с ненужными временными переменными:

tmp_1 = 42
a = tmp_1
tmp_2 = a
b = tmp_2
print(b)

Упражнение 2.1 Реализуйте проход remove_complex_operands в compiler.py, создавая вспомогательные функции для каждого нетерминала в грамматике, а именно rco_exp и rco_stmt. Мы рекомендуем вам использовать функцию utils.generate_name() для генерации свежих имен из строки-заглушки.

Упражнение 2.2 Создайте пять программ $L_{Var}$ , которые протестируют наиболее интересные части прохода remove_complex_operands. Пять программ должны быть размещены в подкаталоге tests/var, а имена файлов должны заканчиваться на .py.

Запустите скрипт run-tests.py в коде поддержки, чтобы проверить, производят ли выходные программы тот же результат, что и входные программы.

2.5 Выбор Инструкций (select_instructions)

На этапе select_instructions мы начинаем работу по переводу в $x86{Var}$ . Целевой язык этого прохода — это вариант x86, который все еще использует переменные, поэтому мы добавляем узел AST в виде Variable(var) в нетерминальный arg абстрактного синтаксиса $x86{int}$ (см. рисунок 2.9). Мы рекомендуем реализовать вспомогательную функцию с именем select_stmt для нетерминального элемента stmt. Далее рассмотрим случаи для нетерминального stmt, начиная с арифметических операций. Например, рассмотрим следующую операцию сложения с левой стороны. (Пусть arg1 и arg2 — это переводы atm1 и atm2, соответственно.) В x86 есть инструкция addq, но она выполняет обновление на месте. Мы можем переместить arg1 в регистр rax, затем добавить arg2 к rax, а затем, наконец, переместить rax в var:

var = atm1 + atm2

movq arg1, %rax
addq arg2, %rax
movq %rax, var

Однако, проявив осторожность, мы можем сгенерировать более короткие последовательности инструкций. Предположим, что один или несколько из аргументов сложения являются той же переменной, что и левая часть присваивания. Тогда оператор присваивания можно перевести в единую инструкцию addq, следующим образом:

var = atm1 + var

addq arg1, var

С другой стороны, если atm2 не является той же переменной, что и левая часть, тогда мы можем переместить arg1 в левую переменную var, а затем добавить arg2 в var:

var = atm1 + atm2

movq arg1, var
addq arg2, var

Операция input_int не имеет прямого аналога в ассемблере x86, поэтому мы предоставляем эту функциональность с помощью функции read_int в файле runtime.c, написанного на C (Kernighan и Ritchie 1988). В общем, мы называем всю функциональность в этом файле системой времени выполнения или просто «временем выполнения» для краткости. При компиляции сгенерированного вами кода на ассемблере x86 вам нужно скомпилировать runtime.c в runtime.o (объектный файл, используя gcc с опцией -c) и связать его с исполняемым файлом. Для наших целей генерации кода все, что вам нужно сделать — это перевести присваивание input_int в вызов функции read_int, за которым следует перемещение из rax в переменную левой стороны. (Возвращаемое значение функции помещается в rax):

var = input_int();

callq read_int
movq %rax, var

Аналогично, мы переводим операцию print, представленную ниже, в вызов функции print_int, определенной в runtime.c. В x86 первые шесть аргументов функции передаются в регистрах, причем первый аргумент помещается в регистре rdi. Таким образом, мы перемещаем аргумент в rdi и затем вызываем print_int, используя инструкцию callq.

print(atm)

movq arg, %rdi
callq print_int

Мы рекомендуем использовать функцию utils.label_name для преобразования строк в метки, например, в целевой инструкции callq. Эта практика делает ваш компилятор портируемым между Linux и Mac OS X, которые требуют перед началом всех меток символа подчеркивания.

Упражнение 2.3 Реализуйте проход select_instructions в файле compiler.py. Создайте три новых примера программ, которые предназначены для проверки всех интересных случаев в этом проходе. Запустите скрипт run-tests.py, чтобы проверить, производят ли выходные программы тот же результат, что и исходные.

2.6 Назначение Домов (assign_homes)

Проход assign_homes компилирует программы $x86{Var}$ в программы $x86{Var}$ , которые больше не используют переменные программы. Таким образом, проход assign_homes отвечает за размещение всех переменных программы в регистрах или на стеке. Для эффективного выполнения лучше всего размещать переменные в регистрах, но поскольку регистров всего шестнадцать, некоторые программы обязательно должны размещать некоторые переменные на стеке. В этой главе мы сосредотачиваемся на механике размещения переменных на стеке. Мы изучим алгоритм размещения переменных в регистрах в главе 4.

Рассмотрим еще раз следующую программу $L_{Var}$ из раздела 2.4:

a = 42
b = a
print(b)

Выход select_instructions показан сверху, а выход assign_homes — снизу. В этом примере мы назначаем переменной a стековую локацию -8(%rbp) и переменной b локацию -16(%rbp).

movq $42, a
movq a, b
movq b, %rax

movq $42, -8(%rbp)
movq -8(%rbp), -16(%rbp)
movq -16(%rbp), %rax

Проход assign_homes должен заменить все использования переменных на стековые локации. В процессе назначения переменных к стековым локациям вам будет удобно вычислить и сохранить размер фрейма (в байтах) в поле stack_space узла X86Program, что будет необходимо позже для генерации завершения основной процедуры. Стандарт x86-64 требует, чтобы размер фрейма был кратным 16 байтам.

Упражнение 2.4 Реализуйте проход assign_homes в файле compiler.py, определив вспомогательные функции для каждого из нетерминалов в грамматике x86Var. Мы рекомендуем, чтобы вспомогательные функции принимали дополнительный параметр, который сопоставляет имена переменных с местами хранения (пока это будут стековые локации). Запустите скрипт run-tests.py, чтобы проверить, дают ли выходные программы тот же результат, что и входные программы.

2.7 Инструкции патча (patch_instructions)

Проход patch_instructions компилирует из $x86{Var}$ в $x86{int}$ , проверяя, что каждая инструкция соответствует ограничению, согласно которому не более одного аргумента инструкции может быть ссылкой на память.

Вернемся к следующему примеру:

a = 42  
b = a  
print(b)  

Проход assign_homes производит следующий перевод:

movq $42, -8(%rbp)  
movq -8(%rbp), -16(%rbp)  
movq -16(%rbp), %rdi  
callq print_int

Вторая инструкция movq вызывает проблемы, так как оба аргумента являются стековыми локациями. Мы предлагаем решить эту проблему, переместив значение из исходного местоположения в регистр rax, а затем из rax в целевое местоположение, как показано ниже:

movq -8(%rbp), %rax  
movq %rax, -16(%rbp)

Существует также аналогичный крайний случай, который нужно учитывать. Если один аргумент — это немедленное целое число, большее чем $2^{16}$ , а другой — ссылка на память, то инструкция будет недействительной. Это можно исправить, например, сначала переместив немедленное целое число в rax, а затем используя rax вместо целого числа.

Упражнение 2.5 Реализуйте проход patch_instructions в compiler.py. Создайте три новых примера программ, которые направлены на проверку всех интересных случаев в этом проходе. Запустите скрипт run-tests.py, чтобы проверить, дают ли выходные программы тот же результат, что и входные программы.

2.8 Генерация преамбулы и заключения

Последний шаг компилятора из $L_{Var}$ в x86 — это генерация главной функции с преамбулой и заключением, которые окружают остальную часть программы, как показано на рисунке 2.7 и обсуждено в разделе 2.2. При запуске на Mac OS X ваш компилятор должен добавлять подчеркивание к именам всех меток (например, изменяя main на _main). Функция platform.system в Python возвращает ‘Linux’, ‘Windows’ или ‘Darwin’ (для Mac).

Упражнение 2.6 Реализуйте проход prelude_and_conclusion в compiler.py. Запустите скрипт run-tests.py, чтобы проверить, дают ли выходные программы тот же результат, что и входные программы. Этот скрипт переводит сгенерированный вами x86 AST в строку, вызывая метод repr, который реализован в классах x86 AST в x86_ast.py.

2.9 Испытание: Частичный вычислитель для $L_{Var}$

Этот раздел описывает два необязательных упражнения, которые включают адаптацию и улучшение частичного вычислителя для $L_{Int}$ , представленного в разделе 1.6.

Упражнение 2.7 Адаптируйте частичный вычислитель из раздела 1.6 (рисунок 1.5) так, чтобы он работал с программами $L_{Var}$ , а не $L_{Int}$ . Напомним, что $L_{Var}$ добавляет переменные и присваивание в язык $L_{Int}$ , поэтому вам нужно будет добавить кейсы для них в функции pe_exp и pe_stmt. После завершения добавьте проход частичного вычислителя в начало вашего компилятора и проверьте, что ваш компилятор по-прежнему проходит все тесты.

Упражнение 2.8 Улучшите частичный вычислитель, заменив вспомогательные функции pe_neg и pe_add функциями, которые более осведомлены об арифметике. Например, ваш частичный вычислитель должен преобразовывать

1 + (input_int() + 1) => 2 + input_int()

Для этого функция pe_exp должна производить вывод в виде остаточного нетерминального элемента следующей грамматики. Идея заключается в том, что при обработке выражения сложения мы всегда можем получить одно из следующих: (1) целочисленную константу, (2) выражение сложения с целочисленной константой с левой стороны, но не с правой, или (3) выражение сложения, в котором ни одно из подвыражений не является константой.

inert ::= var | input_int() | -var | -input_int() | inert + inert 
residual ::= int | int + inert | inert

Функции pe_add и pe_neg могут предполагать, что их входные данные являются остаточными выражениями, и они должны возвращать остаточные выражения. После завершения улучшений убедитесь, что ваш компилятор по-прежнему проходит все тесты. В конце концов, быстрый код бесполезен, если он выдает некорректные результаты!