Язык програмирования Ü — нелёгкий путь написания самодостаточного компилятора29.09.2021 22:46

Уже несколько лет я веду разработку собственного языка программирования — Ü. Около двух лет назад я публиковал вводную статью о нём на Хабре. Компилятор этого языка написан на C++ и долгое время он таковым и оставался. Но после той публикации я пришёл к выводу, что язык Ü уже достаточно продвинут, чтобы написать на нём компилятор языка Ü. О написании этого компилятора и будет повествовать данная статья.

В данной статье описывается процесс разработки, имевший место (с перерывами) примерно с начала 2020-го года по начало лета 2021-го года. Далее я буду называть начальный компилятор, написанный на C++ «Компилятор0», а компилятор, написанный на Ü — «Компилятор1».

Логически разработку Компилятора1 можно разделить на три этапа. Первый этап — подготовительный/прототипный. Второй этап — собственно написание Компилятора1 до достижения самосборки. Третий этап — доделывание Компилятора1 и исправление недостатков.

Подготовительный этап

Данный этап проходил не сильно быстро и не интенсивно. На нём происходило больше теоретической и архитектурной работы, нежели просто написания кода.

Поддержка рекурсивных структур данных

В компиляторе почти что любого языка, да и вообще, во множестве программ, работающих с какими-либо формальными языками, широко используются рекурсивные структуры данных — напрямую или опосредованно включающие самих себя. Перед написанием Компилятора1 нужно было удостовериться, что язык и его стандартная библиотека поддерживают подобные структуры.

Оказалось, что в Компиляторе0 есть некоторые особенности, которые мешали объявлять такие структуры. Пришлось изменять некоторые аспекты и убирать из некоторых мест требование полноты типов.

Также оказалось, что даже после исправлений в Компиляторе0 не получается создать рекурсивные структуры с использованием контейнеров стандартной библиотеки box (аналог unique_ptr из C++) и vector. Первый я доработал, чтобы его можно было использовать для рекурсивных структур.

Со вторым дело обстояло сложнее. Всё дело в том, что наличие конструктора копирования у класса vector зависит от копируемости типа элемента, а его копируемость зависит от самого класса vector для рекурсивных структур. В принципе наверное можно как-то доработать vector, например, через задание пользовательских правил копируемости. Но я решил временно просто проигнорировать проблему и вручную где надо класть в vector значение, обёрнутое в box/shared_ptr.

Генерация отладочной информации

Опыт подсказывает, что написание хоть сколько нибудь сложного кода требует возможности периодически его отлаживать. Соответственно, прежде чем начать писать Компилятор1, следовало добавить в Компилятор0 возможность генерировать отладочную информацию.

Проект Ü основан на библиотеке LLVM. В ней есть встроенная поддержка генерации отладочной информации. Код фронтенда языка заполняет соответствующие структуры, детально описывая через них всё, что может быть полезно для отладки. Генератор бинарного кода LLVM способен на основе этих структур генерировать платформозависимую отладочную информацию в форматах DWARF (GCC) и CodeView (MSVC).

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

Итак, все вышеописанные я реализовал. Результат вышел вполне сносным. Стало возможным ставить точки останова в программах, смотреть значения локальных переменных, осуществлять вход/выход из функций и т. д. Возможно, это ещё не всё и есть какие-то более продвинутые механизмы отладки, для которых понадобилась бы более полная отладочная информация. Но мне хватило вышеописанного, наверное, в 95% случаев этого достаточно.

В процессе реализации генерации отладочной информации я столкнулся с, казалось бы, весьма странной ошибкой — отображение стека вызовов не работало, как надо. Оказалось, всему виною было использование атрибута nounwind у функций. Этот атрибут используется, чтобы не генерировать лишних данных для раскрутки стека, т. к. в Ü всё равно нету исключений и раскрутка стека поэтому не нужна. Но, как оказалось, информация, необходимая для раскрутки стека, используется также и отладчиком. Поэтому пришлось для случая генерации отладочной информации добавлять функциям атрибут uwtable, чтобы нормально работало отображение стека вызовов в отладчике.

Первый код Компилятора1 и первые проблемы

Итак, я начал писать код Компилятора1. Начал я с кода разбора исходного текста программы на лексемы. И в первых же нескольких сотнях строк кода я выявил несколько ошибок в Компиляторе0.

Первая ошибка была примерно в следующем коде:

type Iterator = ust::array_view_imut;
fn ParseIdentifier( Iterator &mut it ) : Lexem
{
    ReadNextUTF8Char( it );

    var Lexem mut result;
    result.lexem_type= Lexem::Type::Identifier;

    while( !it.empty() )
    {
        auto mut it_next= it;
        if( !IsIdentifierChar( ReadNextUTF8Char( it_next ) ) )
        {
            break;
        }
        it= it_next; // Вот здесь Компилятор1 порождал ошибку
    }

    return result;
}

В чём же была проблема? А проблема была в коде контроля ссылок. Компилятор считал, что переменная it внутри хранит ссылку на некоторые данные. При этом изменяемость этой ссылки не была известна на уровне типа, считалось, что все переменные, хранящие внутри ссылки, могут содержать изменяемую ссылку. Так вот, при попытке вызвать оператор = для переменных it и it_next, компилятор обнаружил, что при вызове в него могут передастся две изменяемые ссылки на некую переменную, на которую указывает it, что не допустимо правилами языка.

Обдумав, я принял решение несколько изменить дизайн языка — сделать изменяемость внутренних ссылок свойством типа. К примеру:

struct RefImut // тип с неизменяемой ссылкой внутри
{
    i32 &imut r;
}

struct RefMut // тип с изменяемой ссылкой внутри
{
    i32 &mut r;
}

struct NonRef // тип без ссылок внутри
{
    i32 x;
}

Данное решение в дизайне языка в целом себя хорошо оправдало и до сих пор используется.

Ошибка исправлена? Не совсем. Как оказалось, код выше выявил ещё одну проблему. В коде Компилятора0 локальные переменные и ссылки контролировались структурой типа ациклического направленного графа — для целей того самого контроля ссылок. Но, как оказалось, граф таки может содержать циклы.

В примере выше переменная it держит ссылку на некие данные, переменная it_next ссылается на внутреннюю ссылку в it, а при присваивании it = it_next внутренняя ссылка переменной it начинает указывать на внутреннюю ссылку в it_next, тем самым создав цикл в графе ссылок. Данный код вызывал падение Компилятора0 с ошибкой переполнения стека, т. к. алгоритмы работы с графом ссылок предполагали его ацикличность. Подумав, я осознал, что циклы в графе — необходимость и стоит скорректировать алгоритмы работы с ним с учётом их наличия.

Взаимодействие с библиотекой LLVM

Лексический и синтаксический разбор текста программы — это всего лишь малая часть работы фронтенда компилятора. В Ü, например, код лексического/синтаксического разбора занимает лишь 20–25% объёма. Основная же часть фронтенда компилятора занимается построением промежуточного представления. В случае Ü это IR код LLVM.

В Компиляторе0 (на C++) промежуточный код строится непосредственно через соответствующие классы/функции библиотеки LLVM. Спрашивается, можно ли делать то же самое на Ü, или на каком-то другом языке, отличном от C++? Ответ положительный — да, можно. Авторы LLVM предусмотрели такое использование библиотеки и поэтому написали биндинги на чистом Си для построения IR кода (и не только).

Я решил взять за основу эти Си биндинги для написания Компилятора1. Но как же вызывать Си функции из Ü?

В начале у меня были планы автоматически сгенерировать Ü биндинги из Си биндингов. И у меня для этого даже есть преобразователь заголовочных файлов Си в Ü, написанный с использованием библиотеки ClangTooling. Но, как оказалось, выдаёт он весьма посредственный результат, который нельзя использовать напрямую. Автоматически преобразованные файлы в большинстве случаев оказывались нерабочими и требовали ручной доводки.

Казалось бы, что мешает доработать преобразователь? В принципе, думаю его можно доработать до более-менее вменяемого состояния. Но эту задачу я счёл слишком трудоёмкой для того, чтобы преобразовать только лишь один или два файла. Вместо этого для написания Компилятора1 я вручную написал биндинги для нужных LLVM функций. Результирующий файл с биндингами вышел примерно в 500 строк размером, да и писался не за один раз, а постепенно.

Кроме написания биндингов к уже имеющемуся Си интерфейсу LLVM пришлось вручную реализовать ряд биндингов, отсутствующих в нём. Это довольно специфичные функции, так что в принципе логично, что их нету в Си интерфейсе.

В дополнении к этим функциям по ходу написания Компилятора1 понадобилось реализовывать ещё немного функций на C++ — там, где по той или иной причине это было невозможно сделать с использованием Ü.

Адаптация тестов

Перед разработкой Компилятора1 для Компилятора0 было написано уже достаточно много тестов — около двух тысяч. Чуть менее половины этих тестов написаны на C++ и запускаются как исполняемый файл. Чуть более половины тестов — это тесты, написанные на Python и запускающиеся с использованием разделяемой библиотеки, реализующей функционал компилятора. Ещё несколько тестов — это тесты с полноценной компиляцией в бинарные файлы и компоновкой.

Такое странное разделение родилось исторически. Сначала тесты писались на C++, потом, чтобы ускорить перезапуск тестов при их правке, было принято решение писать их на Python. Тесты на компоновку нужны там, где не достаточно просто запустить интерпретатор LLVM для IR кода тестируемой программы.

Итак, перед написанием Компилятора1 все эти тесты надо было адаптировать для Компилятора0. Для C++ тестов была добавлена относительно тонкая абстракция над библиотекой компилятора. Для Python тестов была написана отдельная разделяемая библиотека с кодом Компилятора1. Тесты компоновки же были переделаны на двукратный запуск — с Компилятором⁰ и Компилятором¹.

Ещё одна проблема была в том, что не возможно за один мах написать весь Компилятор1. Надо было, чтобы в ходе его разработки были включены только те тесты, что тестируют уже созданный функционал. Эту проблему я решил через белый список тестов, которые стоит запускать в Компиляторе1. В начале белый список был пуст, в последствии он всё более и более пополнялся. Под самый конец разработки, когда в этом списке было уже более 90% тестов, белый список был заменён чёрным списком — с тестами, которые ещё не проходят. По правде говоря, даже сейчас в чёрном списке тестов Компилятора1 кое-что остаётся — в основном для экспериментального/сомнительного функционала.

Доказательство возможности

Исправив наиочевиднейшие ошибки в Компиляторе0 и стандартной библиотеке, выполнив ряд приготовлений я продолжил написание Компилятора1. Сразу писать весь Компилятор1 от начала и до конца я считал несколько рискованным. Поэтому я решил написать только небольшую его часть чтобы проверить, что это вообще возможно на текущем уровне развития языка. Целью было написать (недо)компилятор с минимумом базовых возможностей, проверяемых сотней-другой тестов. Сомнения были в возможности создать нужные компилятору структуры данных и в наличии необходимых для разработки конструкций языка и кода стандартной библиотеки.

Как читатель уже наверное догадывается, первая стадия написания Компилятора1 удалась. Оказалось, что имеющихся конструкций языка (за некоторым исключением) вполне достаточно для написания C++-подобного кода. Имеющихся контейнеров стандартной библиотеки — box, optional, vector, unordered_map, shared_ptr* тоже оказалось достаточно для создания внутренних структур данных компилятора.

Также уже на этом этапе обнаружились некоторые особенности языка, которые потребовали несколько иного подхода к организации структур данных в Компиляторе1 по сравнению с Компилятором⁰. Основные отличия были следующие:

• В Компиляторе1 более распространено использование shared_ptr-подобных контейнеров, которые переносят правила контроля ссылок на время выполнения. В C++, к примеру, можно итерироваться по коллекции с целью изменить её элементы и в то же время иметь к ней доступ на чтение из кода, который эти элементы изменяет. Статический контроль ссылок в Ü такого не позволяет. Использование же shared_ptr-подобных контейнеров для элементов коллекции позволяет по этой коллекции итерироваться логически не изменяя её, но при этом изменяя элементы внутри shared_ptr.
• Описанная несколькими разделами ранее проблема с vector для рекурсивных структур была отчасти решена через использование box для элементов vector-а.
• Опережающее объявление в C++ позволяет использовать неполный тип в гораздо больших контекстах, чем это позволено в Ü. Из-за этого пришлось объявлять почти все внутренние структуры компилятора в одном файле.
• В структурах построителя промежуточного кода в Компиляторе0 местами есть сырые ссылки/указатели на соответствующие структуры синтаксического дерева. В Компиляторе1 из-за того самого контроля ссылок такое было сделать проблематично. Вместо этого в структурах построителя промежуточного кода используется контейнер shared_ptr_final, являющийся облегченной версией shared_ptr для неизменяемых данных. Накладные расходы на его использование не сильно выше использования сырых ссылок/указателей в аналогичном C++ коде, но зато есть гарантия времени компиляции, что ссылка не протухнет (чего нельзя сказать о подобных гарантиях в C++).

Доделывание Компилятора1

Самая долгая, трудоёмкая и (относительно) скучная часть работы по написанию Компилятора1 состояла в реализации всех необходимых возможностей. Но даже про эту часть работы есть чего рассказать. Как оказалось, даже на этапе доделывания Компилятора1 в Компиляторе0 выявился ряд недостатков, один серьёзный и ряд более мелких.

Отлавливание не очевидных ошибок Компилятора0

Несколько раз при написании Компилятора1 я замечал странное — код вёл себя не так, как ожидалось. После некоторого времени, потраченного на отладку, я локализовывал ошибку в конкретном месте и не мог найти, что же в этом коде не так. Прибегнув в просмотру ассемблерного кода, я находил, в чём же дело.

Оказывалось, что ассемблерный код не соответствовал исходному. В одном из случаев я обнаружил ошибку, когда Компилятор0 пропускал ошибку с отсутствием return в функции, из-за этого функция возвращала мусор. В другом случае я обнаружил отсутствие вызова деструктора там, где это было необходимо.

Ещё несколько раз я натыкался на ошибки контроля ссылок, возникающие на пустом месте. В последствии оказывалось, что виною всему ошибки в Компиляторе0. В одном из таких случаев я обнаружил, что связывание ссылок проверяется не перед каждым оператором return, а только в конце тела функции, что было методологически неверно, но что самое болезненное, приводило иногда к падениям компилятора, когда последним элементом тела функции не был оператор return.

О вычислителе constexpr функций

Реализация большинства возможностей Компилятора1 не представляла особых проблем. Но одним из немногим исключений оказался вычислитель constexpr функций.

Что же это такое? Это специальный компонент, задача которого, исполнять во время компиляции constexpr функции. В Ü constexpr функции это специальный класс функций, имеющий некоторые ограничения позволяющие им выдавать детерминированный результат, и как следствие, позволяющие вызывать эти функции на этапе компиляции, чтобы использовать результаты такого вызова в качестве констант времени компиляции. К примеру, можно вычислить достаточно сложным образом число, которое будет использовано как размер массива.

Так вот, по своей сути этот компонент представляет собой свою реализацию интерпретатора некоторого подмножества IR кода. Продвинутый читатель спросит, а зачем он нужен, если в библиотеке LLVM уже есть подобный интерпретатор? Ответ следующий — он не подошёл, т. к. завязан на параметры системы, на которой запускается интерпретатор, а не целевой системы. В Компиляторе это критично — размер указателя, выравнивание структур, порядок байт при вычислении constexpr функций должны совпадать с таковыми на целевой системе.

С этим компонентом проблема оказалась следующая — он слишком завязан на структуры данных LLVM, полный доступ к которым не возможен через Си биндинги. Написать этот компонент на Ü было весьма проблематичным. Оказалось, что гораздо проще переиспользовать его как есть в Компиляторе1, написав соответствующие прокладки. Кода прокладок вышло всего несколько десятков строк.

Оператор for в стиле Си

В ходе разработки Компилятора1 я обнаружил, что набор базовых конструкций языка всё-же не совсем достаточен. Оказалось, что цикла while не достаточно для всех случаев. Проблема оказалась в том, что цикл while не позволяет выполнить какие-то действия на каждой итерации цикла, включая переход к следующей итерации через continue. А выполнять такие действия оказалось необходимо, например, в циклах итерирования по коллекциям.

Данную проблему я посчитал весьма серьёзной — она мешала использовать continue в циклах и вынуждала писать плохо читаемые комбинации if-else. Поэтому, прямо по ходу разработки Компилятора1, пришлось добавлять в язык/Компилятор0 поддержку такой конструкции цикла, которая бы не обладала таким недостатком. Я решил не изобретать велосипед и просто позаимствовал классический цикл for из Си — с объявлением переменных, условием продолжения цикла и набором операций конца итерации. После реализации такого цикла я переделал макрос цикла foreach с while на for, что позволило упростить код многих циклов в Компиляторе1.

Достижение самосборки

В какой-то момент я реализовал большинство возможностей языка в Компиляторе1. Возможность собрать Компилятор2 (собранный Компилятором¹ из исходного кода Компилятора1) показалась на горизонте.

Но всё оказалось не столь простым. Удивительно, но в Компиляторе1 оказалось какое-то количество ошибок, которые не выявились юнит-тестами. Часть этих ошибок выявилась при запуске тестов стандартной библиотеки через Компилятор1. Исправление этих ошибок заняло какое-то время. Часть ошибок выявилась при попытке таки собрать Компилятор2, их тоже какое-то время пришлось исправлять.

Но и это ещё не всё. Отладочная сборка работала, но не работала выпускная сборка — она падала где-то в оптимизаторах IR кода в недрах библиотеки LLVM. Оказалось, что кое-где Компилятор1 генерирует не совсем правильный IR код. Это пришлось исправлять.

Наконец, спустя несколько месяцев активной разработки, мне удалось собрать Компилятор2. После этого я для проверки, что всё в порядке, по такой же схеме собрал ещё и Компилятор3.

Послесамосборочные исправления

Оказалось, что достижение самосборки — это ещё не конец. В процессе были выявлены недостатки как Компилятора0, так и самого языка. Это всё надо было исправлять.

Многократное ускорение сборки

По ходу разработки Компиятора1 я замечал, как всё медленнее и медленнее он собирается. К моменту достижения самосборки Компилятор1 собирался с нуля несколько минут, против нескольких десятков секунд Компилятора0 (на C++). Я стал искать причину столь долгой сборки.

Ключ к решению проблемы дало наблюдение размера объектных файлов, созданных Компилятором¹. Они оказались на порядки более объёмными и содержали кратно больше символов, чем аналогичные файлы Компилятора0. Анализ показал, что подавляющее большинство этих символов это методы шаблонных классов, шаблонные функции, сгенерированные конструкторы/операторы присваивания/деструкторы. Наличие этих символов казалось вполне логичным — для них ведь, как и для других символов используется публичная видимость.

Когда я писал Компилятор0 и даже Компилятор1 я об этом не задумывался. Использование публичной видимости символов казалось само собою разумеющимся. Я решил пересмотреть этот подход. Оказалось, что для шаблонных/сгенерированных символов публичная видимость и не нужна, т. к. они по необходимости генерируются в каждой единице компиляции. Поэтому, сначала в качестве эксперимента, я изменил видимость таких символов на приватную.

И это сработало! Оказалось, что проходы оптимизации LLVM выбрасывают приватные символы, если они не используются (были встроены), после чего генератор кода не создаёт для них бинарный код и в результирующий объектный файл они тоже не записываются. Компиляция Компилятора1 (и последующих поколений) кратно ускорилась и стала сравнимой по времени с компиляцией Компилятора0. Объектные файлы сильно потеряли в размере и их размер стал сравним с таковыми файлами Компиялтора0.

У продвинутого читателя может возникнуть вопрос —, а зачем вообще на уровне фронтенда компилятора генерировать символы, которые не используются? Для шаблонных классов это сознательное решение в дизайне языка. В отличие от C++, где методы шаблонных файлов генерируются лениво, в Ü они генерируются сразу, чтобы убедиться в консистентности кода для заданных аргументов шаблона. Если какой-то метод не нужен в конкретных условиях, его можно явно отключить через enable_if. Для методов это просто упрощение кода компилятора, проще сгенерировать методы сразу, чем делать это отложенно.

Ведёт ли вышеописанный подход к снижению производительности компилятора? Да, в некоторой степени. Но как будет показано ниже, влияние его на производительность незначительно. Всё-же на всякий случай перед запуском оптимизирующих проходов библиотеки LLVM я добавил запуск прохода на удаление неиспользуемых символов, чтобы для них не запускались непосредственно проходы оптимизации.

Реализация недостающих возможностей

После достижения самосборки осталось реализовать в Компиляторе1 ещё ряд возможностей, которые не были необходимы для неё.

Во-первых оставалось доделать создание отладочной информации. Не без проблем, но я это сделал.

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

В-третьих, пришлось добавить генерацию ряда служебных символов (номера версии, поколения компилятора) в результирующие объектные файлы. Это нужно, иногда, для отладки.

Облагораживание массивов

Исторически так сложилось, что типы массивов были не совсем полноценными — их нельзя было передавать в функцию по значению и возвращать из функции, их нельзя было присваивать и инициализировать копией. Я решил, что такая дискриминация ни к чему и реализовал все эти возможности для массивов.

Подобное изменение дало возможность использовать типы массивов, например, в шаблонах и работать в с ними так же, как и с любыми другими типами.

Сырые указатели

В языке до этого не было указателей, только ссылки. Там, где всё же были нужны указатели (в недрах стандартной библиотеки) использовался шаблонный класс, реализованный через целочисленный тип и преобразования число < — > ссылка. Такой подход порождал не совсем удобочитаемый IR код (с множеством операций inttoptr/ptrtoint). Но что более существенно, он потенциально мог вредить будущему внедрению type based alias analysis (TBAA).

Поэтому я решил реализовать типы сырых указателей на уровне языка. Данный класс типа предназначен для небезопасного кода и реализации всяческих контейнеров, для написания прикладного кода он не нужен. Использование этого типа не дозволено в constexpr функциях, разыменование указателя позволено только в unsafe коде. Синтаксически работу с сырыми указателями я сделал специально непохожей на таковую в C++, чтобы отвадить ими пользоваться.

Переделка типа void

Долгое время тип void в Ü был похожим на таковой в C++ — использовался для возвращаемого значения функций и в качестве типа для указателей/ссылок на нетипизированные данные. Но, как оказалось, такой тип не очень то удобен и я решил его изменить.

Во-первых я сделал данный тип полноценным, чтобы можно было объявлять переменные/поля этого типа, инициализировать/копировать значения этого типа, явно передавать их в функцию, сравнивать на равенство. Данное изменение позволило использовать этот тип наравне со всеми другими типами в шаблонном коде. К примеру, после этого изменения я реализовал библиотечный контейнер unordered_set через unordered_map с void в качестве значения.

Во-вторых, я убрал возможность неявных преобразований ссылок в void. Это было сделано, т. к. я счёл неверным и небезопасным считать тип void базовым для всех других типов. Вместо этого я планирую в будущем ввести некоторый другой тип для этого, который бы подобно char в C++ мог пересекаться с любым другим типом.

Доработка контроля ссылок

В ходе разработки Компилятора1 я периодически писал примерно такой код:

fn Foo(T& x, T& y);
///
var [ T, 2 ] mut arr= zero_init;
Foo( arr[0], arr[1] );

На последней строке я получал ошибку контроля ссылок. В чём же дело? Оператор [] для изменяемого массива создавал в графе ссылок (внутренней структуре данных компилятора) узел — изменяемую ссылку на arr. Далее для аргумента функции создавался узел неизменяемой ссылки, связанный с предыдущим узлом. При вычислении второго аргумента оператор [] уже не мог создать узла изменяемой ссылки, т. к. уже имелась одна изменяемая ссылка для arr. Чтобы обойти подобную проблему, приходилось писать код так:

Foo( cast_imut(arr)[0], cast_imut(arr)[1] );

Оператор cast_imut преобразовывал ссылку в неизменяемую, после чего оператор [] тоже создавал неизменяемую ссылку и ошибок контроля ссылок далее не возникало.

Я счёл, что необходимость написания данного кода — недостаток языка и от него необходимо избавится. Решил я эту проблему следующим способом — промежуточные узлы графа ссылок удалялись, после того, как стали ненужными. В примере в начале узел изменяемой ссылки, созданной оператором [] удалялся после создания узла неизменяемой ссылки аргумента функции.

Внесение данного исправления позволило упростить подобные места в Компиляторе1, а также избавиться от ложных ошибок контроля ссылок в будущем.

Замеры производительности

Я произвёл замеры производительности Компилятора0 и Компилятора1. Для замеров использовался инструмент Valgrind. Компилятор0 был скомпилирован при помощи GCC. Компилятор1 был скомпилирован Компилятором⁰. В обоих случаях использовался уровень оптимизации -O2.

Замеры производились путём компиляции одного из файлов Компилятора1. Ниже представлена таблица с результатами — общим временем работы компилятора, временем, затраченным на фронтенд компилятора и на бекенд (оптимизации, генерацию бинарного кода).

В целом Компилятор1 работает дольше Компилятора0 на ~5.5%. Но при этом собственно работа фронтенда (отличающегося в разных компиляторах) занимает только 31–36% времени. Так что если сравнить производительность фронтендов, то в Компиляторе1 он работает дольше на 21%.

С одной стороны это хорошо, что Компилятор1 по порядку производительности близок к Компилятору0. Но стоит ещё учесть, что даже во фронтенде Компилятора1 значительная часть исполняемого кода — это код на C++ внутри библиотеки LLVM. Так что сравнение чисто кода на Ü по отношению к коду на C++ может дать ещё большее отставание первого.

Вопрос — в чём же дело? Откуда такое отставание? Я предполагаю следующие причины:

• Отсутствие TBAA в компиляторе Ü. В C++ эта оптимизация есть и потенциально может давать прирост производительности в несколько процентов.
• Отсутствие оптимизации коротких строк в стандартной библиотеке Ü. Там, где на C++ часто не нужно выделения памяти для строки в куче, в Компиляторе1 она всегда выделяется.
• Контейнер для большинства структур данных в Компиляторе1 это unordered_map с string ключём. unordered_map кривовато написан, да и вся связка может работать медленно. В Компиляторе0, для сравнения, используется llvm::StringMap — специально оптимизированный контейнер.
• Несколько более частое использование shared_ptr-подобных типов в Компиляторе0, по сравнению с Компилятором¹.
• Использование C API библиотеки LLVM из Ü не позволяет использовать встраивание функций, тогда как в Компиляторе0 вызовы LLVM функций/методов могут быть легко встроены. Проблему могло бы решить использование кросс-языковой оптимизации времени компоновки, но ею я ещё не занимался.

Заключение

В результате долгой и упорной работы самодостаточный (почти) компилятор таки был создан. В процессе сам язык был немного исправлен и дополнен. Изначальный компилятор (на C++) был местами доработан и исправлен.

В дальнейшем я пока планирую продолжить поддержку двух версий компилятора. Это даёт некоторые преимущества вроде кросс-верификации и сравнения производительности. Да и чисто технически отказ от Компилятора0 пока что не возможен. Отказаться от начального компилятора можно будет только когда (и если) язык Ü и его компилятор станут достаточно распространены, чтобы было можно разрабатывать Компилятор1 собирая его собранной ранее предыдущей версией себя же.

Ссылки

Ü на GithHub, код Компилятора1

Документация

© Habrahabr.ru