lacc
1.0.0
Это мой игрушечный проект, с целью создания компилятора для C, написанного в C, который способен компилировать себя.
Клонировать и построить из источника, а бинарник будет помещен в bin/lacc .
git clone https://github.com/larmel/lacc.git
cd lacc
./configure
make
make install
Конфигурация по умолчанию включает в себя некоторое базовое исследование среды, чтобы определить, для какого машины и LIBC мы компилируемся. Распознанные платформы в настоящее время включают Linux с Glibc или Musl, а также OpenBSD.
Некоторые стандартные заголовки библиотеки, такие как stddef.h и stdarg.h , содержат определения, которые по своей природе являются специфичными для компилятора и предоставляются специально для LACC в рамках Lib/. Если вы хотите использовать bin/lacc непосредственно без установки заголовков, вы можете переопределить местоположение, установив --libdir , чтобы указать на эту папку напрямую.
Цель install скопирует двоичный файл и заголовки в обычные местоположения или как настроено с помощью --prefix или --bindir . Есть также возможность установить DESTDIR . Выполнить make uninstall , чтобы удалить все файлы, которые были скопированы.
См ./configure --help
Интерфейс командной строки хранится аналогично GCC и другим компиляторам, используя в основном подмножество тех же флагов и опций.
-E Output preprocessed.
-S Output GNU style textual x86_64 assembly.
-c Output x86_64 ELF object file.
-dot Output intermediate representation in dot format.
-o Specify output file name. If not speficied, default to input file
name with suffix changed to '.s', '.o' or '.dot' when compiling
with -S, -c or -dot, respectively. Otherwise use stdout.
-std= Specify C standard, valid options are c89, c99, and c11.
-I Add directory to search for included files.
-w Disable warnings.
-g Generate debug information (DWARF).
-O{0..3} Set optimization level.
-D X[=] Define macro, optionally with a value. For example -DNDEBUG, or
-D 'FOO(a)=a*2+1'.
-f[no-]PIC Generate position-independent code.
-v Print verbose diagnostic information. This will dump a lot of
internal state during compilation, and can be useful for debugging.
--help Print help text.
Аргументы, которые не соответствуют каким -либо варианту, принимаются в качестве входных файлов. Если режим компиляции не указан, LACC будет действовать как обертка для системного линкера /bin/ld . Некоторые общие флаги линкера поддерживаются.
-Wl, Specify linker options, separated by commas.
-L Add linker include directory.
-l Add linker library.
-shared Passed to linker as is.
-rdynamic Pass -export-dynamic to linker.
В качестве примера вызов здесь является компиляцией тестирования/c89/fact.c для объектного кода, а затем использует системный линкер для создания окончательного исполняемого файла.
bin/lacc -c test/c89/fact.c -o fact.o
bin/lacc fact.o -o fact
Программа является частью тестового набора, вычисляя 5! Использование рекурсии и выход с ответом. Запуск ./fact с последующим echo $? должен печатать 120 .
Компилятор записан в C89, в целом считая около 19 тыс. Линий кода. Нет внешних зависимостей, за исключением стандартного C -Libary C, и некоторых системных вызовов, необходимых для вызова линкера.
Реализация организована в четыре основных частях; Препроцессор, анализатор, оптимизатор и бэкэнд, каждый в своем собственном каталоге под SRC/. В целом, каждый модуль (файл .c обычно в сочетании с файлом .h , определяющим общедоступный интерфейс), зависит в основном от заголовков в их собственном поддере. Декларации, которые разделяются на глобальном уровне, находятся на включении/LACC/. Именно здесь вы найдете основные структуры данных, и интерфейсы между предварительной обработкой, анализом и генерацией кода.
Предварительная обработка включает в себя чтение файлов, токенизацию, расширение макросов и обработку директивы. Интерфейс к препроцессору: peek(0) , peekn(1) , consume(1) , try_consume(1) и next(0) , который смотрит на поток предварительно обработанных объектов struct token . Они определены в включении/lacc/token.h.
Обработка ввода выполняется полностью лениво, приводящую в действие синтаксический анализатор, вызывая эти функции для потребления большего количества ввода. Буфер предварительно обработанных токенов сохраняется для получения наказчивания и заполняется по требованию, когда заглядывает вперед.
Код моделируется как график потока управления базовыми блоками, каждый из которых удерживает последовательность операторов кода с тремя ададрессами. Каждая внешняя переменная или определение функции представлена объектом struct definition , определяя один struct symbol и CFG, удерживающий код. Структуры данных, поддерживающие промежуточное представление, можно найти в включении/lacc/ir.h.
Визуализация промежуточного представления является отдельной целью выходной цели. Если опция -dot указана, текстовый файл форматированного точки создается в качестве вывода.
bin/lacc -dot -I include src/backend/compile.c -o compile.dot
dot -Tps compile.dot -o compile.ps
Ниже приведен пример из функции, найденной в SRC/Backend/Compile.c, показывающий срез полного графика. Полный вывод может быть сгенерирован как файл PostScript, запустив показанные команды.
Каждый базовый блок в графике имеет список операторов, чаще всего IR_ASSIGN , который присваивает выражение ( struct expression ) переменной ( struct var ). Выражения также содержат переменные операнды, которые могут кодировать местоположения памяти, адреса и указатели с неочиненными привязками на высоком уровне.
DIRECT операнды относятся к памяти AT *(&symbol + offset) , где символ является переменной или временной в определенном месте в памяти (например, стек).ADDRESS операнды точно представляют собой адрес DIRECT операнда, а именно (&symbol + offset) .DEREF относятся к памяти, на которую указывает символ (который должен быть типа указателя). Выражение - *(symbol + offset) , которое требует двух операций нагрузки для карты в сборку. Только DEREF и DIRECT переменные могут быть целевыми для назначения или L-значения.IMMEDIATE операнды удерживают постоянное число или строку. Оценка непосредственных операндов выполняет постоянное складывание автоматически.Сигсерчик представляет собой кодируемый вручную рекурсивный спуск, с основными частями, разделенными на SRC/Parser/Declaration.c, SRC/Parser/Pinitiazer.c, SRC/PARSER/Expression.c и SRC/PARSER/ratement.c. Текущий график потока управления функцией и текущий активный базовый блок на этом графике передается в качестве аргументов для каждого производства. График постепенно построен, так как в текущий блок добавляются новые инструкции по коду с тремя адресами.
В следующем примере показано правило анализа для бить или выражения, которое добавляет новую операцию IR_OP_OR к текущему блоку. Логика в eval_expr обеспечит, чтобы value операндов и block->expr действительны, завершая в случае ошибки.
static struct block *inclusive_or_expression(
struct definition *def,
struct block *block)
{
struct var value;
block = exclusive_or_expression(def, block);
while (try_consume('|')) {
value = eval(def, block, block->expr);
block = exclusive_or_expression(def, block);
block->expr = eval_or(def, block, value, eval(def, block, block->expr));
}
return block;
}
Последний результат оценки всегда хранится в block->expr . Ветвление осуществляется путем создания новых основных блоков и поддержания указателей. Каждый базовый блок имеет истинный и ложный указатель ветви на другие блоки, как моделируются ветви и GOTO. Обратите внимание, что ни в коем случае не строится какая -либо структура синтаксиса. Он существует только косвенно в рекурсии.
Основная мотивация для построения графика потока управления - иметь возможность провести анализ и оптимизацию данных. Текущие возможности здесь все еще ограничены, но их можно легко расширить с помощью дополнительного и более продвинутого анализа и проходов оптимизации.
Анализ Livensy используется для выяснения, на каждом утверждении, который впоследствии можно прочитать символы. Алгоритм потока данных реализуется с использованием битовых масок для представления символов, насчитывая их 1-63. Как следствие, оптимизация работает только на функциях с менее чем 64 переменными. Алгоритм также должен быть очень консервативным, так как нет анализа псевдонима указателя (пока).
Используя информацию о жизни, проход преобразования, выполняющий устранение мертвого хранилища, может удалить узлы IR_ASSIGN , которые доказуемо ничего не делают, уменьшая размер сгенерированного кода.
Существует три целевых измерения: код текстовой сборки, объектные файлы ELF и DOT для промежуточного представления. Каждый объект struct definition , полученный из анализатора, передается в модуль src/backend/compile.c. Здесь мы делаем отображение из промежуточного представления потока управления до более низкого уровня IR, уменьшая код до чего -то, что напрямую представляет инструкции x86_64. Определение для этого можно найти в SRC/Backend/x86_64/Encoding.h.
В зависимости от указателей функций, установленных при запуске программы, инструкции отправляются либо на бэкэнд ELF, либо на текстовую сборку. Следовательно, код для вывода текста очень прост, более или менее просто отображение между низкоуровневыми инструкциями ИК и их кодом сборки синтаксиса GNU. См. SRC/Backend/x86_64/Assemble.c.
Выход DOT - это отдельный трубопровод, который не нуждается в низком уровне IR, который будет генерироваться. Модуль компиляции просто пересынет CFG в SRC/Backend/Graphviz/Dot.c.
Тестирование проводится путем сравнения вывода времени выполнения программ, скомпилированных с LACC и системным компилятором (CC). Набор небольших автономных программ, используемых для проверки, можно найти в рамках теста/ каталога. Тесты выполняются с использованием check.sh, которая будет проверять предварительную обработку, сборку и эльфийские выходы.
$ test/check.sh bin/lacc test/c89/fact.c
[-E: Ok!] [-S: Ok!] [-c: Ok!] [-c -O1: Ok!] :: test/c89/fact.c
Полный тест компилятора проводится путем прохождения всех тестовых случаев на самостоятельной версии LACC.
make -C test
Сначала он будет использовать уже построенный bin/lacc для производства bin/bootstrap/lacc , который, в свою очередь, используется для построения bin/selfhost/lacc . Между этапами начальной загрузки и самостоятельно промежуточные объектные файлы сравниваются для равенства. Если все работает правильно, эти этапы должны создавать идентичные двоичные файлы. Компилятор - «хорошо», когда все тесты проходят бинар Selfhost. Это всегда должно быть зеленым, на каждом коммите.
Трудно придумать хороший тестовый набор, охватывающий все возможные случаи. Чтобы отсеять ошибки, мы можем использовать CSMith для генерации случайных программ, которые подходят для проверки.
./csmith.sh
Сценарий CSMith.SH запускает CSMITH для генерации бесконечной последовательности случайных программ, пока что -то не удастся в испытательном жгуте. Обычно он проведет тысячи тестов без сбоя.
Программы, генерируемые CSMITH, содержат набор глобальных переменных и функции, создающие мутации на них. В конце концов, контрольная сумма полного состояния всех переменных - вывод. Эта контрольная сумма можно сравнить с различными компиляторами, чтобы найти расхождения или ошибки. См. Doc/random.c для примера программы, сгенерированной CSMITH, которая также правильно составлена LACC.
Когда обнаруживается ошибка, мы можем использовать Creduce, чтобы сделать минимальную резо. Это тогда в конечном итоге станет новым тестовым примером в обычном наборе тестов.
Были приложены некоторые усилия по созданию самого компилятора (хотя сгенерированный код все еще очень нептимизирован). Служив в качестве теста на контроль производительности и правильной теста, мы используем двигатель базы данных SQLite. Исходный код распространяется как один ~ 7 МБ (7184634 байт), большой C -файл, охватывающий более 200 К (включая комментарии и пробелы), что идеально подходит для стресс -тестирования компилятора.
Следующие эксперименты проводились на ноутбуке с процессором I5-7300U, составляющей версию 3.20.1 SQLite3. Измерения сделаны от компиляции до объектного кода (-c).
Для составления файла с LACC требуется менее 200 мс, но вместо времени мы смотрим на более точную выборку циклов ЦП и выполненных инструкций. Данные счетчика аппаратной производительности собираются со perf stat , а распределения памяти с valgrind --trace-children=yes . В Valgrind мы подсчитываем только вклады от самого компилятора (исполняемый файл cc1 ) при запуске GCC.
Числа для LACC принадлежит оптимизированной сборке, созданной make CC='clang -O3 -DNDEBUG' bin/lacc . Каждый компилятор используется с аргументами -c sqlite/sqlite3.c -o foo.o
| Компилятор | Цикл | Инструкции | Распределения | Байты выделены | Результат размер |
|---|---|---|---|---|---|
| LACC | 412,334,334 | 619 466,003 | 49 020 | 24 244,107 | 1590 482 |
| TCC (0,9,27) | 245,142,166 | 397 514,762 | 2909 | 23 020 917 | 1 409 716 |
| GCC (9.3.0) | 9 958 514 599 | 14 524 274 665 | 1546 790 | 1111 331 606 | 1 098 408 |
| Clang (10.0.0) | 4,351,456,211 | 5 466 808 426 | 1 434 072 | 476 529 342 | 1116 992 |
Еще предстоит сделать работу, чтобы приблизиться к TCC, что, вероятно, является одним из самых быстрых компиляторов C. Тем не менее, мы находимся на разумном расстоянии от производительности TCC, и порядок лучше, чем GCC и Clang.
Из приведенной выше таблицы мы видим, что размер файла объекта SQLite, сгенерированный LACC, больше, чем те, которые генерируются другими компиляторами, что позволяет предположить, что мы выводим менее оптимальный код.
Чтобы сравнить относительное качество кода, генерируемого из LACC и GCC, мы можем посмотреть на количество динамических инструкций, выполняемых бинарным и двоичным, построенным BCC. Мы запускаем тот же тест, что и выше, компилируя SQLite в объектный код. Целью для теста является сборщик компилятора по умолчанию ( bin/lacc ), произведенный GCC, и бинарный разум ( bin/selfhost/lacc ), произведенный LACC. Обе эти цели производятся без какой -либо оптимизации, и без определения NDEBUG .
| Компилятор | Цикл | Инструкции |
|---|---|---|
| LACC | 946 315 653 | 1 481 608 726 |
| LACC (SelfHost) | 1 417,112,690 | 2 046,996,115 |
Самоустремленный двоичный файл медленнее для компиляции SQLite, чем компилятор, построенный GCC, показывая, что LACC действительно генерирует довольно неэффективный код. Улучшение бэкэнда с лучшим выбором инструкций является приоритетом, поэтому эти цифры должны быть, мы надеемся, что в будущем должно быть ближе.
Это некоторые полезные ресурсы для построения компилятора C, нацеленного на x86_64.
