Comments 33
Кстати, для решения задачи перевода из инфиксной нотации в постфиксную есть «алгоритм сортировочной станции» придуманый Дейкстрой. Думаю, построение дерева с рекурсивным спуском — более сложный и потенциально более глючный метод.
0
По теме компиляции выражений с языка высокого уровня в машинный код есть очень интересный и сравнительно простой учебник от проекта LLVM, использующий, конечно же, фреймворк LLVM: Kaleidoscope: Implementing a Language with LLVM. Написано без всей этой заумности Dragon Book, для первого знакомства очень удобно.
Поскольку LLVM решает проблемы кодогенерации для целевой архитектуры, в этом учебнике больше уделяется внимания написанию рекурсивного парсера, перевода кода в промежуточное представление (AST, LLVM IR) и простых преобразований над ним.
Поскольку LLVM решает проблемы кодогенерации для целевой архитектуры, в этом учебнике больше уделяется внимания написанию рекурсивного парсера, перевода кода в промежуточное представление (AST, LLVM IR) и простых преобразований над ним.
+3
Вы замучаетесь JIT делать на LLVM.
-3
А какие можете посоветовать альтернативные «лёгкие» способы это сделать? Из моего опыта так создание и поддержка компилятора любого типа (с ЯВО или двоичного кода) никогда не было лёгкой задачей. Появление LLVM дало надежду на создание хоть какого-то общего фундамента.
+2
В случае JIT я никакого зрелого проекта не знаю, к сожалению. Здесь уж кто во что горазд. Могу порекомендовать незрелый (см. ниже).
Для AOT я с вами согласен, создание фронтенда для LLVM проще, чем для gcc, но стоит один раз разобраться (https://gcc.gnu.org/wiki/WritingANewFrontEnd) и вам предоставятся огромные возможности gcc. Например, поддержка распарелелливания на GPU «из коробки» с помощью аннотаций (в LLVM вам придется явно генерировать такой код), лучшая кодогенерация, и т. п. Если вас не пугает статус альфа, то вот вам еще и JIT: gcc.gnu.org/wiki/JIT.
На мой взгляд, gcc гораздо удобнее для расширения. Что в LLVM приходится делать на интринсиках, в gcc можно делать еще добавлением нового типа ноды дерева AST. Кстати, это, имхо, еще один плюс gcc: вам не нужно генерировать SSA форму, только AST, все делает компилятор сам.
Разумеется, у gcc есть и минусы. И самые главные из них, на мой взгляд — очень высокий порог входа и очень скудная документация.
Для AOT я с вами согласен, создание фронтенда для LLVM проще, чем для gcc, но стоит один раз разобраться (https://gcc.gnu.org/wiki/WritingANewFrontEnd) и вам предоставятся огромные возможности gcc. Например, поддержка распарелелливания на GPU «из коробки» с помощью аннотаций (в LLVM вам придется явно генерировать такой код), лучшая кодогенерация, и т. п. Если вас не пугает статус альфа, то вот вам еще и JIT: gcc.gnu.org/wiki/JIT.
На мой взгляд, gcc гораздо удобнее для расширения. Что в LLVM приходится делать на интринсиках, в gcc можно делать еще добавлением нового типа ноды дерева AST. Кстати, это, имхо, еще один плюс gcc: вам не нужно генерировать SSA форму, только AST, все делает компилятор сам.
Разумеется, у gcc есть и минусы. И самые главные из них, на мой взгляд — очень высокий порог входа и очень скудная документация.
+3
Нет желания написать сравнительную статью? Просто мне действительно странно такое слышать, учитывая, что llvm в качестве бэкенда использует Rust, на пример. Не глупые же там ребята сидят, не думаю что дело в том, что gcc не осилили.
+2
Если хорошо помните свои первые (и не только) шаги в участии в разработке GCC, подумайте о том, чтобы изложить это в статье. Я думаю, не мне одному было бы интересно почитать.
+3
Вы замучаетесь JIT делать на LLVM.Аргументируйте, пожалуйста, свою позицию. Да, действительно, LLVM изначально не предназначался для JIT, но поддержка такого режима в нем есть. Даже две.
Ничего катастрофически сложного в этом нет. Нарисовать компилятор как в статье — это всего несколько часов работы. Притом обретая огромные возможности по оптимизации, векторизации и последующему расширению.
Вообще, утверждения «замучаетесь писать под LLVM» и «очень высокий порог вхождения в gcc» как-то не очень коррелируют.
0
Спасибо большое за совет! Обязательно посмотрю.
Честно сказать, в момент написания статьи меня как раз интересовали конкретные машинные команды под конкретную архитектуру — хотелось посмотреть, как меняется производительность в зависимости от использованных инструкций.
Честно сказать, в момент написания статьи меня как раз интересовали конкретные машинные команды под конкретную архитектуру — хотелось посмотреть, как меняется производительность в зависимости от использованных инструкций.
0
Безусловно, кодогенерация под целевую архитектуру — не менее важный и захватывающий вопрос в построении JIT.
В Вашем подходе я вижу пару моментов, которые, возможно, ограничивают скорость генерированного кода или гибкость подхода в целом.
1. Использование x87 инструкций для работы с Float-числами. x87 — довольно старое расширение, не самое удобное для программирования и возможно не самое быстрое. Можно попробовать заменить целевой набор инструкций на какой-нибудь вариант SSE. Причём не с целью использовать их «векторность», а для облегчения программируемости; да и ядру их будет легче планировать.
2. Максимально использовать регистры для хранения промежуточных результатов. Обращения к памяти дорогого стоит, и это ограничивает скорость. Это потребует хотя бы тривиального распределения регистров при работе; возможно, просто организация программного стека с верхушкой на регистрах, а хвостом в памяти с автоматической подкачкой/выкачкой нужных значений.
В Вашем подходе я вижу пару моментов, которые, возможно, ограничивают скорость генерированного кода или гибкость подхода в целом.
1. Использование x87 инструкций для работы с Float-числами. x87 — довольно старое расширение, не самое удобное для программирования и возможно не самое быстрое. Можно попробовать заменить целевой набор инструкций на какой-нибудь вариант SSE. Причём не с целью использовать их «векторность», а для облегчения программируемости; да и ядру их будет легче планировать.
2. Максимально использовать регистры для хранения промежуточных результатов. Обращения к памяти дорогого стоит, и это ограничивает скорость. Это потребует хотя бы тривиального распределения регистров при работе; возможно, просто организация программного стека с верхушкой на регистрах, а хвостом в памяти с автоматической подкачкой/выкачкой нужных значений.
+3
К сожалению, пример Kaleidoscope мало что проясняет. То есть, он конечно очень хорош и нужен, но уж слишком мало он охватывает. Браться реализовать что-либо серьезное после него совершенно невозможно. Например, он никак не показывает, как быть, если функция должна принимать не простые числа, а какие-то структуры данных. Причем хотелось бы эти структуры связать с API на C++, возможно, даже с шаблонными структурами.
Например, есть прекрасный проект генерации PEG-парсеров на JavaScript: PEG.js. У меня давно витает идея попробовать написать компилятор грамматики в машинный код с использованием LLVM. Но пока для меня это непосильная задача.
Вот бы написал кто такую статью, где был бы показан реальный пример хотя бы с парой сложных типов, а не простой числодробилки.
Например, есть прекрасный проект генерации PEG-парсеров на JavaScript: PEG.js. У меня давно витает идея попробовать написать компилятор грамматики в машинный код с использованием LLVM. Но пока для меня это непосильная задача.
Вот бы написал кто такую статью, где был бы показан реальный пример хотя бы с парой сложных типов, а не простой числодробилки.
0
Вот бы написал кто такую статью, где был бы показан реальный пример хотя бы с парой сложных типов, а не простой числодробилки.Осмелюсь в очердной раз предложить к рассмотрению проект llst.org :)
По моему нескромному мнению, на данный момент это лучший проект для первоначального знакомства с LLVM. Не слишком игрушечный (Kaleidoscope), чтобы раскрыть базовые принципы. И не слишком суровый (Rust), чтобы не заблудиться в дебрях.
Наш проект хорошо подходит на роль песочницы, по многим причинам.
Во-первых, Smalltalk — язык с очень простой грамматикой. Прочитав мою вторую статью, вы легко сможете читать 90% конструкций. Во-вторых, я старался оформить код виртуальной машины максимально аккуратно, с использованием подходящих абстракций. Логика происходящего должна быть понятна и без углубления в тонкости C++. В-третьих, Smalltalk буквально написан сам на себе. Поэтому понимая логику языка будет очень легко заметить те же концепции в коде виртуальной машины.
Возвращаясь к вашему вопросу:
1. Можно почитать мою статью про внутреннее устройство рантайма Smalltalk.
2. Заглянуть в заголовочный файл types.h, в котором описаны базовые структуры-классы для управления объектами Smalltalk из виртуальной машины, написанной C++. Там есть много комментариев.
3. Наконец, заглянуть в Core.ll, представляющий ядро модуля JIT, на которое потом навешиваются генерируемые методы.
4. Дальше можно посмотреть реализацию софтовой VM, что даст представление о том как VM реагирует на те или иные байт-коды.
5. Разобраться, как происходит трансляция байт-кодов Smalltalk в IR код LLVM. Это лучше делать на ветке 32, поскольку там сейчас применен новый подход генерации с помощью графов управления. Сам кодировщик покоится в MethodCompiler.cpp. В работе использует абстракцию над байт-кодами Smalltalk — instructions.h. В процессе разбора потоки инструкций преобразуются в граф управления средствами анализатора из analysis.h.
P.S.: Версия 0.4 практически готова, скоро будет очередная статья.
+4
Ну, статьи конечно, немного не о том, что нужно, но реализацию обязательно посмотрю. Размер позволяет надеяться, что все будет понятно :). Пока статьи еще нет, что планируете осветить?
Кстати, в предыдущих статьях есть ссылки на репу на битбакете — я так понимаю, они безнадежно устарели? Аналогичных веток, упоминаемых в них, на гитхабе не нашел.
Кстати, в предыдущих статьях есть ссылки на репу на битбакете — я так понимаю, они безнадежно устарели? Аналогичных веток, упоминаемых в них, на гитхабе не нашел.
0
Как раз вчера сидел исправлял ссылки. Если обнаружите еще — пишите пожалуйста в личку.
Статьи я старался писать так, чтобы изложение опиралось на уже известные темы. Smalltalk не настолько популярный язык, чтобы предполагать, что читатель с ним знаком. Посему старался подготовить фундамент для предметного повествования и возможности сослаться на предыдущий материал.
Последующие статьи я буду делать так, чтобы они параллельно освещали как логику виртуальной машины, так и детали реализации применительно к LLVM. В стиле: «у нас есть такая функциональность, давайте подумаем, как ее можно реализовать средствами LLVM». Опросы показали, что читателям интересны оба направления.
Следующая статья будет сконцентрирована вокруг графов выполнения и того, как управляющие конструкции Smalltalk преобразовываются в IR код LLVM. Если хватит объема статьи, расскажу и об оптимизациях, которые становятся возможными благодаря построению CFG для байт-кодов Smalltalk. Собственно это та работа, которая была проделана за последний год. Есть много материала, можно налепить красивых картинок с графами и преобразованиями.
Если есть конкретные темы, которые хотелось бы услышать, пишите — возможно это удастся органично вплести в текст.
Статьи я старался писать так, чтобы изложение опиралось на уже известные темы. Smalltalk не настолько популярный язык, чтобы предполагать, что читатель с ним знаком. Посему старался подготовить фундамент для предметного повествования и возможности сослаться на предыдущий материал.
Последующие статьи я буду делать так, чтобы они параллельно освещали как логику виртуальной машины, так и детали реализации применительно к LLVM. В стиле: «у нас есть такая функциональность, давайте подумаем, как ее можно реализовать средствами LLVM». Опросы показали, что читателям интересны оба направления.
Следующая статья будет сконцентрирована вокруг графов выполнения и того, как управляющие конструкции Smalltalk преобразовываются в IR код LLVM. Если хватит объема статьи, расскажу и об оптимизациях, которые становятся возможными благодаря построению CFG для байт-кодов Smalltalk. Собственно это та работа, которая была проделана за последний год. Есть много материала, можно налепить красивых картинок с графами и преобразованиями.
Если есть конкретные темы, которые хотелось бы услышать, пишите — возможно это удастся органично вплести в текст.
+1
Если вы под Windows пишете, что мешает генерировать дотнетовский байт-код, который дотнетовский же компилятор заджитит? Там может применяться масса полезных оптимизаций, о которых вы даже не подозревали (в том числе специфичных для конкретного процессора).
-1
Я тоже занимался компиляцией математических выражений под .NET, причем с упрощением, производными: Математические в .NET. Может найдете что-нибудь полезное.
+2
Как бы выглядел код, если бы мы знали выражение ещё на этапе сборки?
float calcExpression(float x)
{
return x * x + 5 * x — 2;
}
Запишите этот код в файлик, скомпилируйте в dll и загрузите функцию в программу. Зачем вы компилятор пишите, если он уже написан?
-5
Не разобрался с комментариями, промахнулся и ответил вам ниже:
habrahabr.ru/post/254831/#comment_8361237
habrahabr.ru/post/254831/#comment_8361237
0
Ваш вариант несомненно рабочий, но во-первых, он немного проиграет в скорости, ведь все описанные вами операции недёшевы с точки зрения времязатрат, а во-вторых, он не очень интересен с точки зрения реализации.
Пришлось бы озаглавить статью так: «Генерация кода во время исполнения или Конкатенация строк, запись в файл, вызов внешней программы» :)
P.S. Мимо. Хотел ответить AtomKreig
Пришлось бы озаглавить статью так: «Генерация кода во время исполнения или Конкатенация строк, запись в файл, вызов внешней программы» :)
P.S. Мимо. Хотел ответить AtomKreig
0
Недёшевы при однократном запуске на малых данных. Но обычно такие вещи делают для повторяющихся событий и данных?
+1
Да, поэтому вариант AtomKrieg вполне осуществим.
Плюсы:
1)Легко реализовать — конкатенация строк, запись в файл, вызов компилятора, загрузка библиотеки
2)Кроссплатформенность из коробки
Минусы:
1)Над таскать с собой компилятор для каждой платформы
2)Невозможно контролировать процесс генерации
3)Получающийся код жёстко привязан к своему местоположению т.е. если его скопировать по другому адресу он скорее всего не сможет нормально работать.
Плюсы:
1)Легко реализовать — конкатенация строк, запись в файл, вызов компилятора, загрузка библиотеки
2)Кроссплатформенность из коробки
Минусы:
1)Над таскать с собой компилятор для каждой платформы
2)Невозможно контролировать процесс генерации
3)Получающийся код жёстко привязан к своему местоположению т.е. если его скопировать по другому адресу он скорее всего не сможет нормально работать.
0
А почему push ebp и pop ebp, но add esp, 0xC?
Можно ли было использовать push esp и pop esp?
Можно ли было использовать push esp и pop esp?
+1
Дело в том, команды push и pop используют esp. esp — указатель вершины стека
Когда выполняется push, из esp вычитается размер аргумента в байтах (зависит от ширины стека) и по получившемуся адресу записывается значение-аргумент.
Когда выполняется pop, считывается значение по адресу, лежащему в esp, записывается в приёмник-аргумент, к esp прибавляется, опять таки, размер считанных данных.
В коде мы кладём в стек три аргумента (0xC байт в сумме) т.е. esp = esp — 0xC. esp указывает на первый аргумент, мы никак не можем считать ничего другого из стека. Поэтому мы прибавляем 0xC — теперь esp указывает на значение ebp, положенное в стек до аргументов функции.
Когда выполняется push, из esp вычитается размер аргумента в байтах (зависит от ширины стека) и по получившемуся адресу записывается значение-аргумент.
Когда выполняется pop, считывается значение по адресу, лежащему в esp, записывается в приёмник-аргумент, к esp прибавляется, опять таки, размер считанных данных.
В коде мы кладём в стек три аргумента (0xC байт в сумме) т.е. esp = esp — 0xC. esp указывает на первый аргумент, мы никак не можем считать ничего другого из стека. Поэтому мы прибавляем 0xC — теперь esp указывает на значение ebp, положенное в стек до аргументов функции.
+1
JIT компиляция стороннего языка интересно, конечно, но ново. Интересно было бы придумать JIT внутри самого C++. Например, продвижение констант после определенной точки (чтения конфига, например), прямые вызовы вместо виртуальных…
0
А если попробовать прикрутить кэширование результата для вызова функции, скажем, помнить последние 32 вызова, помним последние 128 функций, насколько это благотворно может сказаться на результате?
0
Такой подход называется мемоизация. Он активно применяется в функциональном программировании и там, где можно доказать, что значение функции зависит только от аргументов и не имеет побочных эффектов.
Однако польза в каждом случае должна оцениваться отдельно. Для простых операций стоимость обращения к памяти будет дороже перевычисления. При этом даже один промах кэша может перекрыть по времени все остальные попадания.
Однако польза в каждом случае должна оцениваться отдельно. Для простых операций стоимость обращения к памяти будет дороже перевычисления. При этом даже один промах кэша может перекрыть по времени все остальные попадания.
0
Sign up to leave a comment.
Генерация кода во время исполнения или «Пишем свой JIT-компилятор»