128 Компилятор
АССЕМБЛЕР
После завершения этих стадий компиляции у компилятора имеется список блоков (frame blocks), каждый из которых содержит список инструкций и указатель на следующий блок. Ассемблер выполняет поиск в глубину (DFS, Depth-First Seach) по базовым блокам и объединяет инструкции в одну последовательность байт-кода.
Структура данных ассемблера
Структура данных ассемблера assembler объявляется в файле Python compile.c и содержит следующие поля.
ПОЛЕ |
ТИП |
НАЗНАЧЕНИЕ |
a_bytecode |
PyObject * (str) |
Строка, содержащая байт-код |
a_lineno |
int |
Последнее значение lineno сгенерированной |
|
|
инструкции |
a_lineno_off |
int |
Смещение последней lineno в байт-коде |
a_lnotab |
PyObject * (str) |
Строка, содержащая lnotab |
a_lnotab_off |
int |
Смещение в lnotab |
a_nblocks |
int |
Количество достижимых блоков1 |
a_offset |
int |
Смещение в байт-коде |
a_postorder |
basicblock ** |
Список блоков в обратном порядке DFS |
Алгоритм поиска в глубину
Ассемблер использует поиск в глубину (DFS) для обхода узлов в графе базовых блоков. Алгоритм DFS не является специфическим для CPython, но часто используется при обходе графов.
Если CST и AST являются структурами деревьев, то состояние компилятора является структурой графа, в которой узлам соответствуют базовые блоки, содержащие инструкции.
1 Блоки, для которых существуют пути между парами вершин. — Примеч. ред.
Книги для программистов: https://t.me/booksforits
Ассемблер 129
Базовые блоки связываются двумя графами. В одном графе используется обратный порядок создания, основанный на свойстве b_list каждого блока. Серия базовых блоков с именами от A до O будет выглядеть так:
A 
B 
C 
D 
E
F 
G 
H 
I 
J
K 
L 
M 
N 
O
Граф, созданный на b_list, используется для последовательного обхода всех блоков в единице компиляции.
Второй граф использует свойство b_next каждого блока. Этот список представляет поток управления. Вершины графа создаются вызовами compiler_ use_next_block(c, next), где next — следующий блок, для которого будет создана вершина, связанная ребром с текущим блоком (c->u->u_curblock).
Граф узла цикла for может выглядеть примерно так:
|
|
|
|
End |
|
|
|
FOR_LOOP |
|
|
|
A |
B |
C |
Start |
D |
E |
|
|||||
|
Body |
OrElse |
|
Cleanup |
|
|
|
|
|
|
|
F |
G |
H |
|
I |
J |
K |
L |
M |
|
N |
O |
Используются оба графа — как последовательный, так и потока управления, — но реализация DFS использует граф потока управления.
Книги для программистов: https://t.me/booksforits
130 Компилятор
API ассемблера на C
API ассемблера содержит точку входа assemble(), которая решает следующие задачи:
zz Вычисляет количество блоков для выделения памяти.
zz Гарантирует, что каждый блок, выходящий за границу, возвращает None.
zz Выполняет разрешение всех смещений команд перехода, помеченных как относительные.
zz Вызывает dfs() для выполнения обхода блоков в глубину. zz Генерирует все инструкции для компилятора.
zz Вызывает makecode() с состоянием компилятора для генерирования
PyCodeObject.
Python compile.c, строка 6010
static PyCodeObject *
assemble(struct compiler *c, int addNone)
{
...
if (!c->u->u_curblock->b_return) { NEXT_BLOCK(c);
if (addNone)
ADDOP_LOAD_CONST(c, Py_None); ADDOP(c, RETURN_VALUE);
}
...
dfs(c, entryblock, &a, nblocks);
/* Байт-код не может изменяться после вычисления смещений */ assemble_jump_offsets(&a, c);
/* Сгенерировать код в обратном порядке */ for (i = a.a_nblocks - 1; i >= 0; i--) {
b = a.a_postorder[i];
for (j = 0; j < b->b_iused; j++)
if (!assemble_emit(&a, &b->b_instr[j])) goto error;
}
...
co = makecode(c, &a); error:
assemble_free(&a); return co;
}
Книги для программистов: https://t.me/booksforits
Создание объекта кода 131
Поиск в глубину
Поиск в глубину выполняется функцией dfs() в Python compile.c. Эта функция переходит по указателям b_next в каждом из блоков, помечает их как просмотренные, изменяя значение b_seen, после чего добавляет их в список a_postorder ассемблера в обратном порядке.
Функция в цикле перебирает обратный список ассемблера и для каждого блока, если он содержит операцию перехода, рекурсивно вызывает dfs() для этого перехода:
Python compile.c, строка 5441
static void
dfs(struct compiler *c, basicblock *b, struct assembler *a, int end)
{
int i, j;
/* Исключение рекурсии для обычного потока управления.
Так как количество блоков ограничено, неиспользуемое пространство в a_postorder (от a_nblocks до end) может использоваться
как стек для еще не упорядоченных блоков */ for (j = end; b && !b->b_seen; b = b->b_next) {
b->b_seen = 1; assert(a->a_nblocks < j); a->a_postorder[--j] = b;
}
while (j < end) {
b = a->a_postorder[j++];
for (i = 0; i < b->b_iused; i++) { struct instr *instr = &b->b_instr[i]; if (instr->i_jrel || instr->i_jabs)
dfs(c, instr->i_target, a, j);
}
assert(a->a_nblocks < j); a->a_postorder[a->a_nblocks++] = b;
}
}
После того как ассемблер построит граф в CFG при помощи поиска в глубину, можно переходить к созданию объекта кода.
СОЗДАНИЕ ОБЪЕКТА КОДА
Задача функции makecode() — перебрать состояние компилятора и некоторых свойств ассемблера и поместить их в PyCodeObject вызовом PyCode_New().
Книги для программистов: https://t.me/booksforits
132 Компилятор
Имена переменных и констант помещаются в объект кода как свойства:
Python compile.c, строка 5893
static PyCodeObject *
makecode(struct compiler *c, struct assembler *a)
{
...
consts = consts_dict_keys_inorder(c->u->u_consts); names = dict_keys_inorder(c->u->u_names, 0); varnames = dict_keys_inorder(c->u->u_varnames, 0);
...
cellvars = dict_keys_inorder(c->u->u_cellvars, 0);
...
freevars = dict_keys_inorder(c->u->u_freevars,
PyTuple_GET_SIZE(cellvars));
...
flags = compute_code_flags(c); if (flags < 0)
goto error;
bytecode = PyCode_Optimize(a->a_bytecode, consts, names, a->a_lnotab);
...
co = PyCode_NewWithPosOnlyArgs( posonlyargcount+posorkeywordargcount, posonlyargcount, kwonlyargcount, nlocals_int, maxdepth, flags, bytecode, consts, names, varnames, freevars, cellvars, c->c_filename, c->u->u_name, c->u->u_firstlineno, a->a_lnotab);
...
return co;
}
Возможно, вы заметите, что байт-код передается PyCode_Optimize() перед отправкой PyCode_NewWithPosOnlyArgs(). Эта функция является частью процесса оптимизации байт-кода в Python peephole.c.
Оптимизатор глазка перебирает инструкции байт-кода и в некоторых случаях заменяет их другими инструкциями. Например, существует оптимизатор, который удаляет все недостижимые инструкции после команды return.
Книги для программистов: https://t.me/booksforits