Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 33
Кстати, для решения задачи перевода из инфиксной нотации в постфиксную есть «алгоритм сортировочной станции» придуманый Дейкстрой. Думаю, построение дерева с рекурсивным спуском — более сложный и потенциально более глючный метод.
По теме компиляции выражений с языка высокого уровня в машинный код есть очень интересный и сравнительно простой учебник от проекта LLVM, использующий, конечно же, фреймворк LLVM: Kaleidoscope: Implementing a Language with LLVM. Написано без всей этой заумности Dragon Book, для первого знакомства очень удобно.
Поскольку LLVM решает проблемы кодогенерации для целевой архитектуры, в этом учебнике больше уделяется внимания написанию рекурсивного парсера, перевода кода в промежуточное представление (AST, LLVM IR) и простых преобразований над ним.
Поскольку LLVM решает проблемы кодогенерации для целевой архитектуры, в этом учебнике больше уделяется внимания написанию рекурсивного парсера, перевода кода в промежуточное представление (AST, LLVM IR) и простых преобразований над ним.
Вы замучаетесь JIT делать на LLVM.
А какие можете посоветовать альтернативные «лёгкие» способы это сделать? Из моего опыта так создание и поддержка компилятора любого типа (с ЯВО или двоичного кода) никогда не было лёгкой задачей. Появление LLVM дало надежду на создание хоть какого-то общего фундамента.
В случае 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 есть и минусы. И самые главные из них, на мой взгляд — очень высокий порог входа и очень скудная документация.
Нет желания написать сравнительную статью? Просто мне действительно странно такое слышать, учитывая, что llvm в качестве бэкенда использует Rust, на пример. Не глупые же там ребята сидят, не думаю что дело в том, что gcc не осилили.
Если хорошо помните свои первые (и не только) шаги в участии в разработке GCC, подумайте о том, чтобы изложить это в статье. Я думаю, не мне одному было бы интересно почитать.
Вы замучаетесь JIT делать на LLVM.Аргументируйте, пожалуйста, свою позицию. Да, действительно, LLVM изначально не предназначался для JIT, но поддержка такого режима в нем есть. Даже две.
Ничего катастрофически сложного в этом нет. Нарисовать компилятор как в статье — это всего несколько часов работы. Притом обретая огромные возможности по оптимизации, векторизации и последующему расширению.
Вообще, утверждения «замучаетесь писать под LLVM» и «очень высокий порог вхождения в gcc» как-то не очень коррелируют.
Спасибо большое за совет! Обязательно посмотрю.
Честно сказать, в момент написания статьи меня как раз интересовали конкретные машинные команды под конкретную архитектуру — хотелось посмотреть, как меняется производительность в зависимости от использованных инструкций.
Честно сказать, в момент написания статьи меня как раз интересовали конкретные машинные команды под конкретную архитектуру — хотелось посмотреть, как меняется производительность в зависимости от использованных инструкций.
Безусловно, кодогенерация под целевую архитектуру — не менее важный и захватывающий вопрос в построении JIT.
В Вашем подходе я вижу пару моментов, которые, возможно, ограничивают скорость генерированного кода или гибкость подхода в целом.
1. Использование x87 инструкций для работы с Float-числами. x87 — довольно старое расширение, не самое удобное для программирования и возможно не самое быстрое. Можно попробовать заменить целевой набор инструкций на какой-нибудь вариант SSE. Причём не с целью использовать их «векторность», а для облегчения программируемости; да и ядру их будет легче планировать.
2. Максимально использовать регистры для хранения промежуточных результатов. Обращения к памяти дорогого стоит, и это ограничивает скорость. Это потребует хотя бы тривиального распределения регистров при работе; возможно, просто организация программного стека с верхушкой на регистрах, а хвостом в памяти с автоматической подкачкой/выкачкой нужных значений.
В Вашем подходе я вижу пару моментов, которые, возможно, ограничивают скорость генерированного кода или гибкость подхода в целом.
1. Использование x87 инструкций для работы с Float-числами. x87 — довольно старое расширение, не самое удобное для программирования и возможно не самое быстрое. Можно попробовать заменить целевой набор инструкций на какой-нибудь вариант SSE. Причём не с целью использовать их «векторность», а для облегчения программируемости; да и ядру их будет легче планировать.
2. Максимально использовать регистры для хранения промежуточных результатов. Обращения к памяти дорогого стоит, и это ограничивает скорость. Это потребует хотя бы тривиального распределения регистров при работе; возможно, просто организация программного стека с верхушкой на регистрах, а хвостом в памяти с автоматической подкачкой/выкачкой нужных значений.
К сожалению, пример Kaleidoscope мало что проясняет. То есть, он конечно очень хорош и нужен, но уж слишком мало он охватывает. Браться реализовать что-либо серьезное после него совершенно невозможно. Например, он никак не показывает, как быть, если функция должна принимать не простые числа, а какие-то структуры данных. Причем хотелось бы эти структуры связать с API на C++, возможно, даже с шаблонными структурами.
Например, есть прекрасный проект генерации PEG-парсеров на JavaScript: PEG.js. У меня давно витает идея попробовать написать компилятор грамматики в машинный код с использованием LLVM. Но пока для меня это непосильная задача.
Вот бы написал кто такую статью, где был бы показан реальный пример хотя бы с парой сложных типов, а не простой числодробилки.
Например, есть прекрасный проект генерации PEG-парсеров на JavaScript: PEG.js. У меня давно витает идея попробовать написать компилятор грамматики в машинный код с использованием LLVM. Но пока для меня это непосильная задача.
Вот бы написал кто такую статью, где был бы показан реальный пример хотя бы с парой сложных типов, а не простой числодробилки.
Вот бы написал кто такую статью, где был бы показан реальный пример хотя бы с парой сложных типов, а не простой числодробилки.Осмелюсь в очердной раз предложить к рассмотрению проект 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 практически готова, скоро будет очередная статья.
Ну, статьи конечно, немного не о том, что нужно, но реализацию обязательно посмотрю. Размер позволяет надеяться, что все будет понятно :). Пока статьи еще нет, что планируете осветить?
Кстати, в предыдущих статьях есть ссылки на репу на битбакете — я так понимаю, они безнадежно устарели? Аналогичных веток, упоминаемых в них, на гитхабе не нашел.
Кстати, в предыдущих статьях есть ссылки на репу на битбакете — я так понимаю, они безнадежно устарели? Аналогичных веток, упоминаемых в них, на гитхабе не нашел.
Как раз вчера сидел исправлял ссылки. Если обнаружите еще — пишите пожалуйста в личку.
Статьи я старался писать так, чтобы изложение опиралось на уже известные темы. Smalltalk не настолько популярный язык, чтобы предполагать, что читатель с ним знаком. Посему старался подготовить фундамент для предметного повествования и возможности сослаться на предыдущий материал.
Последующие статьи я буду делать так, чтобы они параллельно освещали как логику виртуальной машины, так и детали реализации применительно к LLVM. В стиле: «у нас есть такая функциональность, давайте подумаем, как ее можно реализовать средствами LLVM». Опросы показали, что читателям интересны оба направления.
Следующая статья будет сконцентрирована вокруг графов выполнения и того, как управляющие конструкции Smalltalk преобразовываются в IR код LLVM. Если хватит объема статьи, расскажу и об оптимизациях, которые становятся возможными благодаря построению CFG для байт-кодов Smalltalk. Собственно это та работа, которая была проделана за последний год. Есть много материала, можно налепить красивых картинок с графами и преобразованиями.
Если есть конкретные темы, которые хотелось бы услышать, пишите — возможно это удастся органично вплести в текст.
Статьи я старался писать так, чтобы изложение опиралось на уже известные темы. Smalltalk не настолько популярный язык, чтобы предполагать, что читатель с ним знаком. Посему старался подготовить фундамент для предметного повествования и возможности сослаться на предыдущий материал.
Последующие статьи я буду делать так, чтобы они параллельно освещали как логику виртуальной машины, так и детали реализации применительно к LLVM. В стиле: «у нас есть такая функциональность, давайте подумаем, как ее можно реализовать средствами LLVM». Опросы показали, что читателям интересны оба направления.
Следующая статья будет сконцентрирована вокруг графов выполнения и того, как управляющие конструкции Smalltalk преобразовываются в IR код LLVM. Если хватит объема статьи, расскажу и об оптимизациях, которые становятся возможными благодаря построению CFG для байт-кодов Smalltalk. Собственно это та работа, которая была проделана за последний год. Есть много материала, можно налепить красивых картинок с графами и преобразованиями.
Если есть конкретные темы, которые хотелось бы услышать, пишите — возможно это удастся органично вплести в текст.
Если вы под Windows пишете, что мешает генерировать дотнетовский байт-код, который дотнетовский же компилятор заджитит? Там может применяться масса полезных оптимизаций, о которых вы даже не подозревали (в том числе специфичных для конкретного процессора).
Я тоже занимался компиляцией математических выражений под .NET, причем с упрощением, производными: Математические в .NET. Может найдете что-нибудь полезное.
Как бы выглядел код, если бы мы знали выражение ещё на этапе сборки?
float calcExpression(float x)
{
return x * x + 5 * x — 2;
}
Запишите этот код в файлик, скомпилируйте в dll и загрузите функцию в программу. Зачем вы компилятор пишите, если он уже написан?
Не разобрался с комментариями, промахнулся и ответил вам ниже:
habrahabr.ru/post/254831/#comment_8361237
habrahabr.ru/post/254831/#comment_8361237
Ваш вариант несомненно рабочий, но во-первых, он немного проиграет в скорости, ведь все описанные вами операции недёшевы с точки зрения времязатрат, а во-вторых, он не очень интересен с точки зрения реализации.
Пришлось бы озаглавить статью так: «Генерация кода во время исполнения или Конкатенация строк, запись в файл, вызов внешней программы» :)
P.S. Мимо. Хотел ответить AtomKreig
Пришлось бы озаглавить статью так: «Генерация кода во время исполнения или Конкатенация строк, запись в файл, вызов внешней программы» :)
P.S. Мимо. Хотел ответить AtomKreig
Недёшевы при однократном запуске на малых данных. Но обычно такие вещи делают для повторяющихся событий и данных?
Да, поэтому вариант AtomKrieg вполне осуществим.
Плюсы:
1)Легко реализовать — конкатенация строк, запись в файл, вызов компилятора, загрузка библиотеки
2)Кроссплатформенность из коробки
Минусы:
1)Над таскать с собой компилятор для каждой платформы
2)Невозможно контролировать процесс генерации
3)Получающийся код жёстко привязан к своему местоположению т.е. если его скопировать по другому адресу он скорее всего не сможет нормально работать.
Плюсы:
1)Легко реализовать — конкатенация строк, запись в файл, вызов компилятора, загрузка библиотеки
2)Кроссплатформенность из коробки
Минусы:
1)Над таскать с собой компилятор для каждой платформы
2)Невозможно контролировать процесс генерации
3)Получающийся код жёстко привязан к своему местоположению т.е. если его скопировать по другому адресу он скорее всего не сможет нормально работать.
А почему push ebp и pop ebp, но add esp, 0xC?
Можно ли было использовать push esp и pop esp?
Можно ли было использовать push esp и pop esp?
Дело в том, команды 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, положенное в стек до аргументов функции.
JIT компиляция стороннего языка интересно, конечно, но ново. Интересно было бы придумать JIT внутри самого C++. Например, продвижение констант после определенной точки (чтения конфига, например), прямые вызовы вместо виртуальных…
А если попробовать прикрутить кэширование результата для вызова функции, скажем, помнить последние 32 вызова, помним последние 128 функций, насколько это благотворно может сказаться на результате?
Такой подход называется мемоизация. Он активно применяется в функциональном программировании и там, где можно доказать, что значение функции зависит только от аргументов и не имеет побочных эффектов.
Однако польза в каждом случае должна оцениваться отдельно. Для простых операций стоимость обращения к памяти будет дороже перевычисления. При этом даже один промах кэша может перекрыть по времени все остальные попадания.
Однако польза в каждом случае должна оцениваться отдельно. Для простых операций стоимость обращения к памяти будет дороже перевычисления. При этом даже один промах кэша может перекрыть по времени все остальные попадания.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Генерация кода во время исполнения или «Пишем свой JIT-компилятор»