Llvm: компилятор своими руками. введение

С++ Concept-Based Polymorphism в продуктовом коде: PassManager в LLVM

Сегодня речь пойдет про одну интересную идиому, которую ввел Шон Парент (Adobe) — известный деятель в C++-сообществе. Он часто выступает с докладами и публикует цикл статей Better Code. Одна из его идей, которую используют в Photoshop — это Concept-Based Polymorphism. Это когда мы реализуем полиморфизм не через явное наследование, а с помощью техники, включающей обобщенное программирование, и по итогам получаем некоторые дополнительные преимущества. Статья устроена следующим образом:

  1. Что вообще такое Concept-Based Polymorphism и зачем он нужен
  2. Немного про LLVM и ее устройство
  3. Пример Concept-Based Polymorphism в LLVM PassManager
  4. Преимущества подхода

Чтение строки

Чтение строки из стандартного потока ввода — это вроде бы просто, но в C это может вызвать много хлопот. Беда в том, что никто не знает заранее, сколько текста пользователь введет в командную оболочку. Нельзя просто выделить блок и надеяться, что пользователи не выйдут за него. Вместо этого нужно перераспределять выделенный блок памяти, если пользователи выйдут за его пределы. Это стандартное решение в C, и именно оно будет использоваться для реализации .


В первой части много объявлений. Стоит отметить, что в коде используется старый стиль C, а именно объявление переменных до основной части кода. Основная часть функции находится внутри, на первый взгляд, бесконечного цикла . В цикле символ считывается и сохраняется как , а не (EOF — это целое число, а не символ, поэтому для проверки используйте ). Если это символ перевода строки или EOF, мы завершаем текущую строку и возвращаем ее. В обратном случае символ добавляется в существующую строку.

Затем мы проверяем, выходит ли следующий символ за пределы буфера. Если это так, то перераспределяем буфер (при этом проверяем его на наличие ошибок распределения) и продолжаем исполнение.

Те, кто знаком с новыми версиями стандартной библиотеки C, могут заметить, что в есть функция , которая выполняет большую часть работы, реализованной в коде выше. Эта функция была расширением GNU для библиотеки C до 2008 года, а затем была добавлена в спецификацию, поэтому большинство современных Unix-систем уже идут с ней в комплекте.  С  функция становится тривиальной:

Базовый цикл командной оболочки

В первую очередь нам нужно подумать о том, как программа должна запускаться

И здесь важно понимать, что делает оболочка во время цикла. Простой способ обработки команд состоит из трех шагов:

  1. Чтение: считывание команды со стандартных потоков.
  2. Парсинг: распознавание программы и аргументов во входной строке.
  3. Исполнение: запуск распознанной команды.

Эта идея реализована в функции :

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

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

Атрибут cleanup

Цитата из документации GCC :Атрибут cleanup предназначен для запуска функции, когда переменная выходит из области видимости. Этот атрибут может быть применён только к auto-переменным, и не может быть использован с параметрами или с static-переменными. Функция должна принимать один параметр, указатель на тип, совместимый с переменной. Возвращаемое значение функции, если оно есть, игнорируется. Если включена опция -fexceptions, то функция cleanup_function запускается при раскрутке стека, во время обработки исключения. Отметим, что атрибут cleanup не перехватывает исключения, он только выполняет действие. Если функция cleanup_function не выполняяет возврат нормальным образом, поведение не определено. Атрибут cleanup поддерживается компиляторами gcc и clang. В этой статье я приведу описание различных вариантов практического использования атрибута cleanup и рассмотрю внутреннее устройство библиотеки, которая использует cleanup для реализации аналогов std::unique_ptr и std::shared_ptr на языке C.

Полноценная IDE

Ребята из Kodingen, задумавшие реализовать полноценную среду разработки в вебе, выбрали очень правильный сценарий развития.


Вместо того чтобы изобретать велосипед, разрабатывая еще один редактор кода, который претендовал на универсальность, они просто встроили имеющиеся замечательные разработки в свой продукт! А сами тем временем сосредоточились на создании других необходимых для IDE опций, в том числе для совместной работы!

Сервис находится в состоянии активного развития и носит статус беты, а разработчики каждый месяц подкармливают появившуюся армию поклонников новыми фишками. Уже сейчас над любым проектом можно работать в команде. И если на текущем этапе colaboration поддерживается только средствами самого сервиса, то на подходе поддержка всех популярных систем для контроля версий: svn, git, mercirual! Уже сейчас можно прописать у себя в профиле учетные записи для доступа к хостингу по FTP и сразу заливать обновленные сорцы на сервер. А хочешь — можешь хоститься прямо в Kodingen. Всем желающим создатели предоставляют хостинг в своем облаке (по крайней мере, пока). Еще одна интересная опция — шелл-доступ своим файлом прямо из веб-интерфейса, не надо даже коннектиться по SSH! Одним словом — супервещь!

Создание компилятора

ANTLRграмматикStringTemplatesдокументацииThe ANTLR Mega Tutorial

  • Грамматика MySQL на ANTLR 4
  • Обработка древовидных структур и унифицированное AST

Создание проекта на Node.js с использованием ANTLR

JavaScript runtimeJavaScript target for ANTLR 4

ECMAScript.g4

Кстати, на сайте ANTLR в разделе Development Tools можно найти ссылки на плагины для таких IDE как Intellij, NetBeans, Eclipse, Visual Studio Code, and jEdit. Цветовые темы, проверка семантических ошибок, визуализация с помощью диаграмм облегчают написание и тестирование грамматик.

  • ECMAScriptLexer.js разбивает поток символов исходного кода на поток токенов в соответствии с правилами, указанными в грамматике.
  • ECMAScriptParser.js из потока токенов строит абстрактную связную древовидную структуру, называемую деревом разбора.
  • ECMAScriptVisitor.js отвечает за обход построенного дерева. Теоретически, мы могли бы самостоятельно обработать данное дерево с помощью рекурсивного обхода потомков в глубину. Однако при большом количестве типов узлов и сложной логике их обработки, лучше посещать каждый тип узла своим уникальным методом, как это делает визитор.

Antlr4 — Visitor vs Listener Pattern

  • Анализ исходного кода.
  • Построение синтаксического дерева.
  • Генерация нового кода.

Генерация кода

четыре специальных паблик метода

  • visit() отвечает за обход дерева.
  • visitChildren() отвечает за обход узлов.
  • visitTerminal() отвечает за обход токенов.
  • visitErrorNode() отвечает за обход некорректных токенов.

Как командные оболочки запускают процессы

Теперь мы добрались до самой сути того, что делает оболочка. Запуск процессов — это основная функция командных оболочек. Поэтому если вы создаёте оболочку, то должны точно знать, что происходит с процессами и как они запускаются. Именно поэтому сейчас мы поговорим о процессах в Unix.

В Unix есть только два способа запуска процессов. Первый (который не будем брать в счет) — это . Видите ли, когда загружается Unix-система, загружается её ядро. После загрузки и инициализации ядро запускает только один процесс, который называется . Этот процесс выполняется в течение всего времени работы компьютера, и  управляет загрузкой остальных процессов, которые необходимы для его работы.

Поскольку все остальные процессы не , остаётся только один практический способ запуска процессов: системный вызов . Когда эта функция вызывается, операционная система делает дубликат процесса и запускает их параллельно. Первоначальный процесс называется «родительским», а новый — «дочерним». Дочернему процессу  возвращает , а родителю — идентификатор процесса (PID) его дочернего элемента. Таким образом, любой новый процесс можно создать только из копии уже существующего.

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

Благодаря этим двум системным вызовам и возможен запуск большинства программ в Unix. Сперва существующий процесс раздваивается на родительский и дочерний, а затем дочерний процесс использует для замены себя новой программой. Родительский процесс может продолжать делать другие вещи, а также следить за своими дочерними элементами, используя системный вызов .


Да уж, информации немало. Давайте посмотрим на код запуска программы:

Эта функция принимает список аргументов, которые мы создали ранее. Затем она разворачивает процесс и сохраняет возвращаемое значение. Как только возвращает значение, мы получаем два параллельных процесса. Дочернему процессу соответствует первое условие (где ).

В дочернем процессе мы хотим запустить команду, заданную пользователем. Поэтому мы используем один из вариантов системного вызова , . Разные варианты делают разные вещи. Одни принимают переменное количество строковых аргументов, другие берут список строк, а третьи позволяют указать окружение, в котором выполняется процесс. Этот конкретный вариант принимает имя программы и массив (также называемый вектором, отсюда ) строковых аргументов (первым должно быть имя программы).  означает, что вместо предоставления полного пути к файлу программы для запуска мы укажем только её имя, а также кажем операционной системе искать её самостоятельно.

Если команда возвращает (или любое другое значение), значит, произошла ошибка. Таким образом, мы используем для вывода сообщения об ошибке вместе с именем программы, чтобы было понятно, где произошла ошибка. Затем мы завершаем процесс, но так, чтобы программная оболочка продолжала работать.

Второе условие () проверяет, произошла ли в процессе выполнения  ошибка. Если ошибка есть, мы выводим сообщение об этом на экран, но программа продолжает работать.

Третье условие означает, что вызов  выполнен успешно. Там находится родительский процесс. Мы знаем, что потомок собирается исполнить процесс, поэтому родитель должен дождаться завершения команды. Мы используем для ожидания изменения состояния процесса. К сожалению, у есть много опций (например, ). Процессы могут изменять свое состояние множеством способов, и не все состояния означают, что процесс завершился. Процесс может либо завершиться обычным путём (успешно либо с кодом ошибки), либо быть остановлен сигналом. Таким образом, мы используем макросы, предоставляемые , чтобы убедиться, что процесс завершен. Затем функция возвращает  как сигнал вызывающей функции, что она снова может вывести приглашение ввода.

Примечания

  1. ГОСТ 19781-83 // Вычислительная техника. Терминология: Справочное пособие. Выпуск 1 / Рецензент канд. техн. наук Ю. П. Селиванов. — М.: Издательство стандартов, 1989. — 168 с. — 55 000 экз. — ISBN 5-7050-0155-X.; см. также ГОСТ 19781-90
  2. Першиков В. И., Савинков В. М. Толковый словарь по информатике / Рецензенты: канд. физ.-мат. наук А. С. Марков и д-р физ.-мат. наук И. В. Поттосин. — М.: Финансы и статистика, 1991. — 543 с. — 50 000 экз. — ISBN 5-279-00367-0.
  3. ↑ СТ ИСО 2382/7-77 // Вычислительная техника. Терминология. Указ. соч.
  4. Борковский А. Б. Англо-русский словарь по программированию и информатике (с толкованиями). — М.: Русский язык, 1990. — 335 с. — 50 050 (доп,) экз. — ISBN 5-200-01169-3.
  5. Толковый словарь по вычислительным системам = Dictionary of Computing / Под ред. В. Иллингуорта и др.: Пер. с англ. А. К. Белоцкого и др.; Под ред. Е. К. Масловского. — М.: Машиностроение, 1990. — 560 с. — 70 000 (доп,) экз. — ISBN 5-217-00617-X (СССР), ISBN 0-19-853913-4 (Великобритания).
  6. Н. А. Криницкий, Г. А. Миронов, Г. Д. Фролов. Программирование / Под ред. М. Р. Шура-Бура. — М.: Государственное издательство физико-математической литературы, 1963.

Code Generation

Now that we’ve built an AST, we’re ready to generate some assembly! Like we saw before, we only need to emit four lines of assembly. To emit it, we’ll traverse the AST in roughly the order that the program executes. That means we’ll visit, in order:

  • The function name (not really a node, but the first thing in the function definition)
  • The return value
  • The return statement

Note that we often (though not always) traverse the tree in , visiting a child before its parent. For example, we need to generate the return value before it’s referenced in a return statement. In later posts, we’ll need to generate the operands of arithmetic expressions before generating the code that operates on them.

Here’s the assembly we need:

  1. To generate a function (e.g. function “foo”):
  2. To generate a return statement (e.g. ):

Task:

Write a generate function that accepts an AST and generates assembly. It can return the assembly as a string or write it directly to a file. It should generate correct assembly for all valid stage 1 examples.

Генерация кода

Генерация машинного кода

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

Результат компиляции — исполнимый программный модуль — обладает максимально возможной производительностью, однако привязан к конкретной операционной системе (семейству или подсемейству ОС) и процессору (семейству процессоров) и не будет работать на других.

Для каждой целевой машины (IBM, Apple, Sun, Эльбрус и т. д.) и каждой операционной системы или семейства операционных систем, работающих на целевой машине, требуется написание своего компилятора. Существуют также так называемые кросс-компиляторы, позволяющие на одной машине и в среде одной ОС генерировать код, предназначенный для выполнения на другой целевой машине и/или в среде другой ОС. Кроме того, компиляторы могут оптимизировать код под разные модели из одного семейства процессоров (путём поддержки специфичных для этих моделей особенностей или расширений наборов команд). Например, код, скомпилированный под процессоры семейства Pentium, может учитывать особенности распараллеливания инструкций и использовать их специфичные расширения — MMX, SSE и т. п.

Некоторые компиляторы переводят программу с языка высокого уровня не прямо в машинный код, а на язык ассемблера. (Пример: PureBasic, транслирующий бейсик-код в ассемблер FASM.) Это делается для упрощения части компилятора, отвечающей за генерацию кода, и повышения его переносимости (задача окончательной генерации кода и привязки его к требуемой целевой платформе перекладывается на ассемблер), либо для возможности контроля и исправления результата компиляции (в том числе ручной оптимизации) программистом.

Генерация байт-кода

Результатом работы компилятора может быть программа на специально созданном низкоуровневом языке двоично-кодовых команд, выполняемых виртуальной машиной. Такой язык называется псевдокодом или байт-кодом. Как правило, он не есть машинный код какого-либо компьютера и программы на нём могут исполняться на различных архитектурах, где имеется соответствующая виртуальная машина, но в некоторых случаях создаются аппаратные платформы, напрямую выполняющие псевдокод какого-либо языка. Например, псевдокод языка Java называется байт-кодом Java и выполняется в Java Virtual Machine, для его прямого исполнения была создана спецификация процессора picoJava. Для платформы .NET Framework псевдокод называется Common Intermediate Language (CIL), а среда исполнения — Common Language Runtime (CLR).

Некоторые реализации интерпретируемых языков высокого уровня (например, Perl) используют байт-код для оптимизации исполнения: затратные этапы синтаксического анализа и преобразование текста программы в байт-код выполняются один раз при загрузке, затем соответствующий код может многократно использоваться без перекомляции.

Динамическая компиляция

Основная статья: Динамическая компиляция (англ.)

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

Наиболее популярной разновидностью динамической компиляции является JIT. Другой разновидностью является .

CIL-код также компилируется в код целевой машины JIT-компилятором, а библиотеки .NET Framework компилируются заранее.

Putting it all together

Task:

Write a program that accepts a C source file and outputs an executable. The program should:

  1. Read in the file
  2. Lex it
  3. Parse it
  4. Generate assembly
  5. Write the assembly to a file
  6. Invoke GCC command to convert the assembly to an executable:

    In this command, “assembly.s” is the name of the assembly file and “out” is the name of the executable you want to generate. The option tells GCC to build a 32-bit binary. You can omit that option and build 64-bit binaries if you want, but you’ll need to make some changes to the code generation steps later on (e.g. using 64-bit registers).

  7. (Optional) Delete the assembly file.

Раздельная компиляция

Раздельная компиляция (англ. separate compilation) — трансляция частей программы по отдельности с последующим объединением их компоновщиком в единый загрузочный модуль.

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

Появление раздельной компиляции и выделение компоновки как отдельной стадии произошло значительно позже создания компиляторов. В связи с этим вместо термина «компилятор» иногда используют термин «транслятор» как его синоним: либо в старой литературе, либо когда хотят подчеркнуть его способность переводить программу в машинный код (и наоборот, используют термин «компилятор» для подчёркивания способности собирать из многих файлов один). Вот только использование в таком контексте терминов «компилятор» и «транслятор» неправильно. Даже если компилятор выполняет трансляцию программы самостоятельно, поручая компоновку вызываемой внешней программе-компоновщику, такой компилятор не может считаться разновидностью транслятора, — транслятор выполняет трансляцию исходной программы и только. И уж тем более не являются трансляторами компиляторы вроде системной утилиты-компилятра make, имеющейся во всех UNIX-системах. Утилита

Собственно утилита make — яркий пример довольно удачной реализации раздельной компиляции. Работа утилиты make управляется сценарием на интерпретируемым утилитой входном языке, известном как makefile, содержащемся в задаваемом при запуске утилиты входном текстовом файле. Сама утилита не выполняет ни трансляцию ни компоновку, — де-факто утилита make функционирует как диспетчер процесса компиляции, организующий компиляцию программы в соответствии с заданным сценарием. В частности в ходе компиляции целевой программы утилита make вызывает трансляторы с языков программирования транслирующие разные части исходной программы в объектный код, и уже после этого вызывается тот или иной компоновщик, компонующий конечный исполняемый программный или библиотечный программный модуль. При этом разные части программы, оформляемые в виде отдельных файлов исходно текста, могут быть написаны как на одном языке программирования так и на разных языках программирования. В процессе перекомпиляции программы транслируются только измененные части-файлы исходного текста программы, в следствие чего длительность перекомпиляции программы значительно (порой на порядок) сокращается.

Делимся кодом

Если редактировать код вместе не нужно, а нужно поделиться исходниками, какими-нибудь конфигами, XML-ками, дампами или просто текстовыми файлами, пригодится инструмент, о котором мы недавно говорили в WWW2 — Pastie (pastie.org). Все, что требуется — это скопипастить в форму текст и указать его тип (скажем, исходник на C++ или Python). Сервис выдаст короткий линк, перейдя по которому, любой увидит исходный текст с красиво подсвеченным синтаксисом. Всего сервис поддерживает 38 различных языков программирования, файлов-конфигураций и вывода некоторых программ. Во время просмотра можно изменить тему для отображения так, чтобы было максимально похоже на привычную среду разработки. Сам проект написан на Ruby, причем правила для подсветки синтаксиса были позаимствованы у TextMate. Помимо Pastie есть еще один интересный сервис, нацеленный на обмен сниппетами. В публичном репозитории кода Snipplr хранится огромное количество исходников и сниппетов на разные темы. Обязательное требование к заметке — четкое описание и теги, поэтому в репозитории очень легко найти нужные участки кода.


С этим читают