Компиляция программ на своём Тьюринг-полном эзотерическом языке PPLang для собственного SPU и x86-64.
Проведено сравнение эффективности программ. Оптимизации IR ускорили выполнение на 25%. Программа работает на 14% медленнее скомпилированной при GCC -O0 и на 87% медленнее GCC -O3.
- Процесс компиляции
- Возможности и особенности языка
- Примеры программ
- Сравнение эффективности скомпилированных программ
- Заметки о разработке
- Зависимости
- Использование
- Итоги
- Источники и инструменты
- Благодарности
- Frontend - лексический разбор текста программы и создание абстрактного синтаксического дерева (AST);
- Middleend - оптимизации и преобразования AST:
- свёртка констант;
- удаление мёртвого кода;
- дифференцирование математических выражений;
- Backend - генерация линейного архитектурно-независимого промежуточного представления (IR);
- IR Backend - обработка IR:
- оптимизации:
- удаление избыточных парных перемещений данных;
- свёртка операций со стеком;
- создание бинарного исполняемого файла программы, генерация ассемблерного листинга.
- оптимизации:
Note
Компилятор состоит из 4 отдельных программ, описание которых находится ниже. Их названия обусловлены историей развития проекта. Традиционно структура компилятора несколько другая. Например, в LLVM синтаксическое дерево не выходит за пределы frontend, а части компилятора обмениваются IR. В данном проекте основной структурой является AST, поэтому IR появляется лишь на backend.
Сначала текст программы разбирается на лексемы. Такой подход позволил облегчить дальнейшую обработку конструкций языка, ввести синонимичные ключевые слова, а также игнорировать комментарии.
Note
Полный список ключевых слов. Осторожно, встречается ненормативная лексика.
Массив лексем преобразуется в абстрактное синтаксическое дерево (AST) при помощи алгоритма рекурсивного спуска. Так как реализация алгоритма тяжело читаема после написания, для верификации и дальнейшей поддержки был создан файл с формальным описанием синтаксических конструкций и приоритета операций языка.
Условные обозначения:
<expr name> := <expr>- определение нового типа выражения'<keyword>'- ключевое слово{<expr>}- скобки для обозначения приоритета!<expr>- выражение не должно встретиться<expr>?- необязательное выражение<expr>*- выражение может не встретиться или встретиться несколько раз<expr1> | <expr2>- выражение 1 или выражение 2
Фрагмент описания грамматики языка в формате, близком к РБНФ:
// 'CH_' - means that function exits without error (gives choice)
Main := {'CMD_SEPARATOR'? {CH_DefFunc | CH_DefVar} 'CMD_SEPARATOR'?}* 'TERMINATOR'
CH_DefFunc := VarName {'VAR' | 'CONST'} 'OPEN_BRACE' FuncArgsDef 'CLOSE_BRACE' 'CMD_SEPARATOR'? CH_Commands
CH_DefVar := VarName {'OPEN_INDEX_BRACE' Expr 'CLOSE_INDEX_BRACE'}? 'VAR' 'CONST'? {'ASSIGNMENT' Expr {'VAR_SEPARATOR' Expr}* }?
CH_Commands := 'OPEN_SCOPE' 'CMD_SEPARATOR'? {Command {'CMD_SEPARATOR' Command}*} 'CMD_SEPARATOR'? 'CLOSE_SCOPE'
Command := {CH_Commands | CH_DefVar | CH_CommandWithArg | CH_ComplexCommand | CH_CommandWithConstArg | SimpleCommand}
// ---------------------------------------------MATHS------------------------------------------------
Expr := {VarName {'OPEN_INDEX_BRACE' Expr 'CLOSE_INDEX_BRACE'}? {{'ASSIGNMENT' !'ASSIGNMENT'} | {{'MATH_ADD' | 'MATH_SUB' | 'MATH_MUL' | 'MATH_DIV'} 'ASSIGNMENT'}} Expr} | MathLvl1
MathLvl1 := MathLvl2 {{{{'ASSIGNMENT' | 'LOGIC_NOT' | 'LOGIC_LOWER' | 'LOGIC_GREATER'} 'ASSIGNMENT'} | {'LOGIC_LOWER' | 'LOGIC_GREATER'}} MathLvl2}*
MathLvl2 := MathLvl3 {{'MATH_ADD' | 'MATH_SUB'} MathLvl3}*
MathLvl3 := MathLvl4 {{'MATH_MUL' | 'MATH_DIV'} MathLvl4}*
MathLvl4 := MathLvl5 {'MATH_POW' MathLvl5}*
MathLvl5 := {{'MATH_SUB' MathLvl5} | {{'OPEN_BRACE' Expr 'CLOSE_BRACE'} | CH_Binary | CH_Unary | Primary}}
Для удобства разработки и поддержки был создан стандарт синтаксического дерева. Полное описание находится в отдельном репозитории.
Далее представлена таблица типов узлов дерева:
| Num | Name | Type | Description |
|---|---|---|---|
| 1 | CMD_SEPARATOR | LIST | Разделитель команд. Имитирует список. Левый потомок - команда, правого или нет, или такой же разделитель |
| 2 | VAR_DEFINITION | BINARY | Определение переменной. Слева лист типа переменная, справа либо ничего, либо выражение |
| 3 | CONST_VAR_DEF | UNARY | Опциональный родитель VAR_DEFINITION и ARRAY_DEFINITION |
| 4 | ARRAY_DEFINITION | BINARY | Определение массива. Слева поддерево: (VAR_SEPARATOR (переменная) (константное выражение - размер массива)). Справа либо ничего, либо список выражений через VAR_SEPARATOR |
| 5 | FUNC_DEFINITION | BINARY | Определение функции. Слева поддерево: (VAR_SEPARATOR (переменная) (поддерево аргументов (список из VAR_SEPARATOR))). Справа список команд через CMD_SEPARATOR |
| 6 | ASSIGNMENT | BINARY | Присваивание. Слева лист переменная, справа выражение |
| 7 | ASSIGNMENT_ADD | BINARY | |
| 8 | ASSIGNMENT_SUB | BINARY | |
| 9 | ASSIGNMENT_MUL | BINARY | |
| 10 | ASSIGNMENT_DIV | BINARY | |
| 11 | ARRAY_ELEM | BINARY | Элемент массива. Слева лист переменная - имя массива, справа выражение - индекс элемента |
| 15 | VAR_SEPARATOR | LIST | Имитатор списка для аргументов функции и т.п. |
| 16 | FUNC_CALL | BINARY | Вызов функции. Слева лист переменная, справа список выражений через VAR_SEPARATOR |
| 17 | RETURN | UNARY | Возврат из функции. Слева ничего, справа выражение |
| 20 | MATH_ADD | BINARY | Сложение |
| 21 | MATH_SUB | BINARY | Вычитание |
| 22 | MATH_MUL | BINARY | Умножение |
| 23 | MATH_DIV | BINARY | Деление |
| 24 | MATH_SQRT | UNARY | Корень |
| 25 | MATH_SIN | UNARY | Синус |
| 26 | MATH_COS | UNARY | Косинус |
| 27 | MATH_NEGATIVE | UNARY | Унарный минус |
| 28 | MATH_DIFF | BINARY | Оператор дифференцирования. Слева выражение, справа лист-переменная с номером переменной, по которой дифференцируем |
| 40 | LOGIC_GREAT | BINARY | > |
| 41 | LOGIC_LOWER | BINARY | < |
| 42 | LOGIC_NOT_EQUAL | BINARY | != |
| 43 | LOGIC_EQUAL | BINARY | == |
| 44 | LOGIC_GREAT_EQ | BINARY | >= |
| 45 | LOGIC_LOWER_EQ | BINARY | <= |
| 50 | PREFIX_ADD | BINARY | ++x 1) Слева обязательно переменная, справа, либо следующий препост-оператор, либо ничего, либо переменная (последние два варианта означают одно и то же). В таком списке операторов все переменные должны иметь один номер. Такое дублирование сделано для оптимального чтения на бекенде; 2) Сначала только префиксные операторы, потом только постфиксные. То есть префиксный не может быть потомком постфиксного. Аналогично для всех препост-операторов |
| 51 | PREFIX_SUB | BINARY | --x |
| 52 | POSTFIX_ADD | BINARY | x++ |
| 53 | POSTFIX_SUB | BINARY | x-- |
| 60 | WHILE | BINARY | while. Слева вычисляемое выражение, справа либо список команд, либо ELSE |
| 61 | DO_WHILE | BINARY | do {} while (). Аналогично, ELSE нельзя |
| 63 | IF | BINARY | Аналогично |
| 64 | DO_IF | BINARY | do {} if () - условный блок с пост-условием. В случае невыполнения программа завершается с ошибкой (вероятен segmentation fault или другое неопределённое поведение) :-D |
| 66 | ELSE | BINARY | Слева список команд, если выполняется основная ветвь, справа если else ветвь |
| 67 | BREAK | LEAF | break |
| 68 | CONTINUE | LEAF | continue |
| 69 | NEW_SCOPE | UNARY | Новая область видимости переменных. Слева ничего, справа список команд |
| 70 | IN | LEAF | Ввод числа пользователем |
| 71 | OUT | UNARY | Вывод числа для пользователя. Слева ничего, справа выражение |
| 72 | SHOW | LEAF | команда ассемблера SPU shw |
| 73 | SET_FPS | UNARY | команда ассемблера SPU fps. Слева ничего, справа выражение, которое можно вычислить во время компиляции (константное) |
Узлы могут быть 3 типов:
1- оператор. Значение - номер оператора из таблицы2- число. Значение - число3- переменная. Значение - номер переменной
Также для каждого узла хранится информация о том, какому символу исходного кода он соответствует. Это позволяет выводить информацию об ошибках, а также отлаживать кодогенератор.
Полное описание, формат текстового файла для передачи дерева и прочая информация в репозитории стандарта.
При выявлении синтаксической ошибки выводится gcc-подобное сообщение.
Данная программа использует наработки из проекта математического дифференциатора.
- свёртка константных выражений;
- упрощение математических выражений:
- удаление нейтральных элементов (
x + 0,x * 1); - свёртка выражений независимым результатом (
x * 0); - удаление парных постфиксных и префиксных операторов (
x++--);
- удаление нейтральных элементов (
- удаление мёртвого кода;
- математическое дифференцирование по произвольной переменной.
Для проведения оптимизаций введена дополнительная классификация типов узлов-операторов дерева:
| # | Name | Description |
|---|---|---|
| 0 | NO_MATH |
Не является математическим выражением |
| 1 | MATH |
Математический оператор, оба потомка являются математическими выражениями |
| 2 | MATH_L |
Не математический оператор, левый потомок - математическое выражение |
| 3 | MATH_R |
Не математический оператор, правый потомок - математическое выражение |
| 4 | MATH_L_R |
Не математический оператор, оба потомка - математические выражения |
Например, выявляются константные условные выражения и выдаются предупреждения о недостижимости участка кода:
Эта программа преобразует абстрактное синтаксическое дерево в линейное архитектурно-независимое промежуточное представление. Происходит инфиксный обход по дереву. Для упрощения написания и поддержки проекта был создан DSL. Последовательности блоков IR, в которые разворачивается каждый тип узла дерева описаны в соответствующем файле.
Аналогично стандарту AST описан и формат IR. Подробная информация в том же репозитории.
Любая программа представляет собой последовательность блоков IR. Для любого блока можно задать 2 входных и одно выходное значение (так называемое трёхадресное представление).
Далее представлена таблица типов блоков IR:
| Num | Name | src[0] | src[1] | dest | subType | Description |
|---|---|---|---|---|---|---|
| 0 | NONE | Empty block. May be used for jump destination | ||||
| 1 | START | global vars number | Program beginning, initialization and entry point start. Must be the first block | |||
| 2 | END | Entry point end | ||||
| 3 | BEGIN_FUNC_DEF | local vars number | Function definition beginning | |||
| 4 | END_FUNC_DEF | Function definition end | ||||
| 5 | CALL_FUNC | local vars number | func block index | Function call | ||
| 6 | RET | Return from function | ||||
| 7 | COUNT_ARR_ELEM_ADDR_CONST | offset | Count address of array element | |||
| 8 | ARR_ELEM_ADDR_ADD_INDEX | index source | global or local | Add value to address of array element | ||
| 9 | MOV | source | special data | destination | Mov value from src[0] to dest (stack, memory, register) | |
| 10 | SWAP | operand 1 | operand 2 | Swap 2 values from src[0] and src[1] | ||
| 11 | STORE_CMP_RES | operand 1 | operand 2 | result | CmpType |
Write bool result of comparison |
| 12 | SET_FLAGS_CMP_WITH_ZERO | operand | Compare with zero and set comparison flags | |||
| 13 | MATH_OPER | operand 1 | operand 2 | result | MathOper |
Math operation |
| 14 | JUMP | dest block index | JmpType |
Conditional or unconditional jump | ||
| 15 | READ_DOUBLE | value | Read double precision floating point number from user | |||
| 16 | PRINT_DOUBLE | value | Print double precision floating point number | |||
| 17 | SET_FPS | value | SPU: asm fps <value> - set max fps count for video mode |
|||
| 18 | SHOW_VIDEO_FRAME | SPU: asm shw - show image frame in video mode |
Типы входных и выходных значений:
| # | Имя | Описание |
|---|---|---|
| 1 | CONST |
Константное число с плавающей точкой |
| 2 | INT_CONST |
Константное целое число |
| 3 | LOCAL_VAR |
Локальная переменная |
| 4 | GLOBAL_VAR |
Глобальная переменная |
| 5 | ARG_VAR |
Аргумент функции (для передачи при вызове) |
| 6 | ARR_VAR |
Элемент массива |
| 7 | STK |
Стек |
| 8 | REG |
Регистр |
| 9 | ADDR |
Индекс другого блока IR (для вызовов функций и прыжков) |
Внутри программы последовательность блоков хранится в двусвязном списке (List). Это позволяет удобно удалять и вставлять блоки при дальнейших оптимизациях, так как тогда физические индексы блоков не меняются.
Все математические операции производятся через стек. В дальнейшем небольшая часть неоптимальных перемещений значений будет соптимизирована.
Здесь оптимизируется последовательность блоков IR и генерируется ассемблерный текст или исполняемый файл для двух архитектур: x86-64 и SPU.
Из-за стековой архитектуры вычислений часто возникают парные бессмысленные операции push и pop, а также лишние промежуточные перемещения данных.
Делается один проход оптимизации. Каждая операция push помещается в стек. При встрече pop происходит проверка: есть ли какие-то операции между данным pop и последним push. Если нет, то эти две операции либо уничтожаются, либо заменяются на одну.
Пример соптимизированных операций:
Прирост быстродействия программы на x86-64 составил порядка 25%. Подробное исследование ниже.
Ассемблерный текст очень удобен для отладки эмиттера и ABI. Поэтому каждый блок IR отмечен меткой, которая содержит его индекс.
Из линейного IR достаточно тривиально реализуется генерация ассемблерного текста программы. В IR все прыжки и вызовы функций ссылаются на другие блоки IR по их индексам. Так удаётся переложить проблему расчёта адресов на ассемблер. В дальнейшем при генерации бинарного исполняемого файла будут реализованы привязки (fixups).
Назначение регистров:
xmm0- возвращаемое значение функцииrbp- начало стекового фрейма локальных переменных функцииxmm1-xmm3,rax,rdx- вычисленияrcx- адрес элемента массива (используется для расчёта и индексации)
Соглашение о вызове функций:
- вызываемая функция должна сохранить
rspиrbp; - передача аргументов через стек:
- внутри функции формальные аргументы считаются первыми локальными переменными;
- при вызове функции происходит сохранение адреса возврата (
call) и внутри самой функции сохраняетсяrbp(enter), поэтому первый фактический аргумент кладётся по адресу[rsp - 16], второй -[rsp - 16 - 8]и так далее.
Назначение регистров:
rax- возвращаемое значение функцииrbx- начало стекового фрейма локальных переменных функцииrcx- адрес элемента массива (используется для расчёта и индексации)rdx,rex- вычисления
Соглашение о вызове функций:
- вызываемая функция обязана сохранять
rbxи стек вычислений; - передача аргументов через виртуальный стек в оперативной памяти:
- внутри функции формальные аргументы считаются первыми локальными переменными;
- первый фактический аргумент кладётся по адресу
[rbx + x], второй[rbx + x + 1]и так далее, гдеx- количество локальных переменных в вызывающей функции.
Библиотека написана на ассемблере и содержит наработки из проекта AsmPrintf. Текст библиотеки.
Она содержит 2 функции:
doubleio_in- чтение числа с плавающей точкой вxmm0изstdin;doubleio_out- печать числа с плавающей точкой с фиксированной точностью (6 знаков после запятой) изxmm0вstdout.
При генерации ассемблерного текста библиотека подключается при помощи директивы %include ассемблера nasm. Для бинарного ELF64 происходит парсинг объектного файла библиотеки, сгенерированного nasm.
Для генерации бинарного исполняемого файла требуется иметь бинарный код библиотеки, используемые ей константы и знать адреса начал функций. При "ручной линковке" необходимо откорректировать абсолютные адреса. Всю необходимую информацию содержит объектный файл в формате ELF64, который можно получить из ассемблерного кода библиотеки при помощи nasm.
Для обработки была написана небольшая библиотека. При чтении проверяются поля Ehdr. По названиям и типам в таблице сегментных заголовков ищутся нужные поля для .rodata, .data, .text, .rela.text, .symtab, .strtab. При помощи найденных заголовков производятся нужные операции и извлекается необходимая информация, которая будет использована при генерации бинарного исполняемого файла.
Сгенерированный файл имеет следующую структуру:
- Заголовок
Ehdr; - 4 заголовка
Phdrдля сегментовEhdr,.rodata,.dataи.text; - Сами сегменты:
.rodata- константы.data- глобальные переменные.text- сама программа
Во всех сегментах сначала расположены соответствующие сегменты библиотеки, затем самой программы. Это позволило упростить расчёт абсолютных адресов для библиотеки.
При генерации программы используются команды jmp и call с относительными 32-битными смещениями. Если адрес прыжка ещё неизвестен (прыжок вперёд), то в структуре блока IR, на который должен произойти прыжок, инициализируется динамический массив. В него помещается смещение от начала бинарного файла, по которому нужно записать неизвестное значение. Соответственно, когда при обходе станет известен адрес этого блока IR, по всем смещениям из этого массива будут вписаны верные значения.
Для упрощения отладки и верификации генерации бинарных команд был реализован DSL. Так же были написаны функции для автоматической генерации полей ModRM и SIB.
Проверка сгенерированных программ проводилась при помощи утилит readelf, objdump, дизассемблера ghidra и дебагера ghidra.
В целом синтаксис языка похож на C.
Символ новой строки является разделителем команд.
Переменные имеют области видимости, полностью аналогично языку C. Глобальные переменные должны быть инициализированы константными выражениями, можно использовать глобальные переменные, объявленные выше. Вызовы функций в глобальной области запрещены.
Объявление функции совпадает с её определением. Поэтому возможен вызов функции, объявление которой расположено ниже.
Исполнение программы начинается из главной функции (она должна иметь название main, остров_в_океане или министерство).
В языке есть только 1 тип переменных - числа с плавающей точкой двойной точности (64 битные IEEE 754, double из C)
<abc> означает, что на этом месте должны быть конструкция, соответствующая описанию.
abc курсив означает необязательную конструкцию
--- после черты находятся примеры использования
- Объявление переменной:
<имя> var const = <выражение> --- x var --- y var = 123 --- z var const = 123 + 456
- Объявление массива:
<имя> var const [<размер>] = <значение 1>, <значение 2>, ... --- x var [3] --- y var [] = 1, 2, 3 --- z var const [5] = 1 + 2, 3 + 4
Значений должно быть не более размера. Если размер не указан, то он соответствует количеству значений.
- Обращение к элементу массива:
<имя>[<индекс>] --- x[3] --- y[1 + 2]
- Объявление функции:
<имя> var (<аргументы через запятую (объявления переменных)>) {
<тело функции>
}
---
func1 var () {
x = 1 + 2
}
---
func2 var (x var, y var const) {
x += y
}
- Возврат значения из функции:
return <выражение> --- return x + 1
- Вызов функции:
<имя>(<выражения через запятую>) --- func1() --- x = func2(1, 2)
Возвращаемое функцией значение может быть использовано в любом выражении
-
Математические выражения:
Приоритет операций совпадает с таковым в языке
C.aиb- выражения;x- имя переменной.- Элементарные операции:
a + b a - b a * b a / b -a a ^ b log(a) sqrt(a) sin(a) cos(a)- Дифференцирование:
x- имя переменной параметра дифференцирования.diff(a, x)- Присваивания:
x = a x += a x -= a x *= a x /= a- Префиксные и постфиксные операции:
x++ x-- ++x --xТакие операции работают аналогично таковым в языке
C. Для++x,--xсначала происходит операция, затем значение возвращается; дляx++,x--наоборот.Могут использованы конструкции типа
----x++++(произойдет вычитание 2, возврат значения в выражение, прибавление 2).- Операторы сравнения:
a < b a > b a <= b a >= b a == b a != bВсе сравнения производятся через дополнительное сравнение модуля разности выражений с
EPSILON = 1e-6. Результат - это числа0.0и1.0. -
Условное выражение:
if (<выражение>) {
<блок команд>
} else {
<блок команд>
}
---
if (x + 3) {
func1()
x += 1
}
---
if (x <= 3)
x -= 3
---
if (x == 0)
x = 1
else
x = 123
Также возможна конструкция else if (<выражение>). Аналогично языку C фигурные скобки можно опустить, если блок содержит одну команду.
- Цикл:
while (<выражение>) {
<блок команд>
} else {
<блок команд>
}
---
while (x--) {
y = x + 1
func1(z = y)
}
---
while (x++) {
if (x + y < -3)
break
} else
func3(x)
Блок else выполнится в случае, если выход из цикла произойдёт из-за невыполнения выражения, а не команды break.
- Цикл с пост-условием:
do {
<блок команд>
} while (<условие>)
---
do
x = 3
while (y++ < 3)
---
do {
x *= 2
y -= 1
} while (x == --z)
- Выход из цикла:
break
- Переход на следующую итерацию цикла:
continue
- Печать числа в
stdout:
out(<выражение>) --- out(x + 3) --- out(y = 2)
- Ввод числа из
stdin:
in --- x = in --- y = in + 3
- Комментарии:
// Однострочный комментарий
/*
Многострочный комментарий
*/
Note
Примеры программ в папке /Programs. Осторожно, встречается ненормативная лексика.
В папке есть небольшой readme
Обе программы ниже распознаются как одна и та же программа. Синтаксическое дерево (AST) данной программы:
остров_в_океане мой () {
серенада(факториал(слушай))
свергаю кумира 0
}
факториал мой (счётчик мой) {
что это такое (счётчик > 1)
свергаю кумира факториал(счётчик - 1) * счётчик
свергаю кумира 1
}
main var () {
out(fact(in))
return 0
}
fact var (i var) {
if (i > 1)
return fact(i - 1) * i
return 1
}
main var() {
x var = 5
if (1) {
out(x) // 5
x var = 10
out(x) // 10
x += 10
out(x) // 20
}
out(x) // 5
return 0
}
Также для данной программы выдаётся предупреждение о бесполезности if, так как в условии стоит константное выражение. Также проверка условия вырезается из кода, но новая область видимости для условного блока сохраняется.
Для сравнения эффективности была написана программа с функцией рекурсивного расчёта факториала натурального числа. Функция вызывается 10^7 раз с аргументом 20 (расчёт 20!).
fact var (i var) {
if (i > 1)
return fact(i - 1) * i
return 1
}
main var () {
N var = 1e7
while (N-- > 0)
fact(20)
return 0
}
Для сравнения с компилятором GCC была написана аналогичная программа на C++:
#include <math.h>
const double EPS = 1e-6;
double fact(const double i) {
if (i > 1 && fabs(i - 1) >= EPS)
return fact(i - 1) * i;
return 1;
}
int main() {
double N = 1e7;
while (fabs(N) >= EPS && N-- > 0)
fact(20);
return 0;
}
Все числа типа double и сравнения через EPS = 1e-6, так как именно такие операции подставляет компилятор PPLang.
На изображении слева представлено лишь начало (сравнение числа) функции расчёта факториала, сгенерированное компилятором. Справа полный текст той же функции, полученный при помощи GCC.
Большое различие в объёме кода обусловлено отсутствием оптимизацией, а также стековой архитектурой вычислений, использованной в данном проекте.
Параметры тестовой машины:
- Компилятор:
g++ (GCC) 13.2.1 20230801 - Процессор:
Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz SkyLake - ОС:
Arch Linux, Kernel:6.6.22-1-lts (64-bit) - Профилировщик:
perf 6.7-2 - Графический интерфейс для обработки данных:
hotspot 1.4.80
| Компилятор | Быстродействие | ||
|---|---|---|---|
| Cycles * 10^7 | % от первого | % от предыдущего | |
| x86-64 | 495 +- 3 | 100% | |
| x86-64 без оптимизаций IR | 661.6 +- 1.9 | 133% | 133% |
| SPU | 12677 +- 30 | 2556% | 1916% |
| GCC -O0 | 428 +- 3 | 86% | 3% |
| GCC -O2 | 68.2 +- 0.4 | 14% | 16% |
| GCC -O3 | 66.5 +- 0.1 | 13% | 97% |
Проводилось по 3 измерения для каждого компилятора.
Ожидаемо, компилятор PPLang генерирует менее эффективный код в сравнении с GCC.
Эмуляция процессора оказалась в 25 раз медленнее прямого исполнения.
Проект создавался в конце первого семестра обучения как компилятор собственного языка для разработанного ранее программного стекового процессора (SPU). Компилятор генерировал только текстовый ассемблерный текст.
Во втором семестре была поставлена задача трансляции для x86-64. Сначала в существующий backend было добавлено создание ассемблерного текста для nasm. Выбор между двумя архитектурами был реализован через таблицу указателей на функции, что позволило очень легко интегрировать нововведения в проект.
Далее было принято решение о создании промежуточного представления для проведения некоторых оптимизаций для x86-64. Они стали возможны, так как SPU осуществляет все математические операции через стек. Соответственно некоторые действия можно свернуть или удалить.
С этого момента backend генерирует архитектурно-независимое линейное промежуточное представление программы (IR). Был создан IR backend. В нём реализованы оптимизации промежуточного представления и генерация кода для обеих архитектур. В том числе добавлено создание бинарного исполняемого файла elf64.
Для облегчения отладки были созданы несколько инструментов логирования и графические дампы некоторых структур данных:
- Stack - стек. Используется в backend для реализации областей видимости переменных и в IR backend для оптимизаций.
- Tree - бинарное дерево. Используется для работы с AST.
- List - двусвязный список. Используется для работы с IR.
Пример HTML лога, создаваемого при ошибке верификатора двусвязного списка, содержащего IR. В логе специально не используются сложные HTML структуры, так как при большом размере лога не всегда есть возможность открытия браузером. Поэтому нельзя было нарушить читаемость в текстовом виде. В конце каждого блока вставлена картинка с графическим представлением содержимого списка.
<pre>
<font color="red">!!! POISON_VAL_FOUND: There is poison value in list
</font></pre>
<pre>
<font color="red">!!! DAMAGED_PATH: List is damaged. Invalid path
</font></pre>
<pre>
list_dump() called from ../shared/List/list.cpp:51 list_dtor
r[0x7a29e7400020] initialized in ../shared/ir_reader/ir_reader.cpp:52 read_ir_process_
{
real capacity = 33
size = 2
head = 1
tail = 0
free_head = 1
is_linear = true
{
i | prev | next | elem | src[0] | src[1] | dest | subtype
0 | 0 | 1 | type = -1 | {NONE, -} | {NONE, -} | {NONE, -} |
1 | 0 | 2 | type = 1 | {NONE, -} | {NONE, -} | {NONE, -} |
2 | 1 | 3 | type = -1 | {NONE, -} | {NONE, -} | {NONE, -} |
3 | -1 | 4 | type = -1 | {NONE, -} | {NONE, -} | {NONE, -} |
4 | -1 | 5 | type = -1 | {NONE, -} | {NONE, -} | {NONE, -} |
5 | -1 | 6 | type = -1 | {NONE, -} | {NONE, -} | {NONE, -} |
...
32 | -1 | 0 | type = -1 | {NONE, -} | {NONE, -} | {NONE, -} |
}
Ordered elements: type = 1 type = -1 type = -1
Physical indexes: 1 2 3
}
</pre>
<img src="../../log/08-05-2024_02-05-45/0.svg">
Пример графического дампа AST. Картинка создана автоматически при помощи graphviz.
GNU make- система сборкиclang- компилятор - можно заменить наgcc, изменив четыреMakefilebear- необязательно (make build nobear=1) - утилита для создания файлаcompile_commands.json(нужен для языкового сервераclangd)
Treeи/илиTreeDebug- релизы - библиотека для работы с бинарными деревьями
Заменить символические ссылки в директории ./lib на папки с файлами .h и .a. Скачать их можно в разделе Releases соответствующих библиотек
iconv- используется скриптомcompiler.shдля отображения русских символов в консолиgraphviz dot- необязательно - графический дамп внутренних структур программ при ошибках (только в Debug версии)
make build <release=1> <nobear=1>
- опция компиляции
-O2.
make build release=1
- верификаторы структур данных;
- логирование внутренних ошибок;
- sanitizer;
- опция компиляции
-Og; - assert.
make build
Note
По умолчанию выбрана архитектура x86-64
./compiler.sh <file>
| Опция | Описание |
|---|---|
--help |
Вывести опции компиляции |
-o <file> |
Задать имя выходного файла |
-m={spu|x86_64} |
Выбрать архитектуру |
-l=<file> |
Задать имя объектного файла библиотеки ввода/вывода |
-S |
Включить генерацию текстового ассемблерного листинга |
Созданный язык и компилятор позволили изучить и реализовать существующие технологии, использованные в промышленных компиляторах и программах. Скомпилированные программы уступают в эффективности на 14% в сравнении с GCC -O0 и на 87% с GCC -O3. Оптимизации IR позволили ускорить программы на 25%.
- Computer Systems: A Programmer's Perspective 3rd Edition by Randal Bryant, David O'Hallaron
- Intel 64 and IA-32 Architectures Software Developer’s Manual March 2024
- Compiler explorer - godbolt.com
- Perf - perf.wiki.kernel.org
- x86 and amd64 instruction reference - felixcloutier.com/x86
- Online Assembler and Disassembler - https://shell-storm.org
- elf.h - github.com
- ELF manpage - manpages.debian.org
- GNU Binutils - gnu.org
- Ghidra Software Reverse Engineering Framework - github.com
- Jupyter Notebook - jupyter.org
- Python Matplotlib - matplotlib.org
- Преподаватель Илья Дединский aka Дед
- Ментор Алексей Дурнов
Спасибо за замечательный курс, за то, что делились опытом, и за ваше безграничное терпение! ❤️ Meow ❤️