Что такое llvm

Что такое LLVM?

Чтобы попробовать llvm на Ubuntu, можно собрать и запустить простой пример sample.c.

#include int main()

clang sample.c -S -emit-llvm 

Файл sample.ll (с сокращениями).

; ModuleID = 'sample.bc' target datalayout = ". " target triple = "i386-linux-gnu" @.str = private constant [7 x i8] c"sample\00", align 1 ; <[7 x i8]*>[#uses=1] define i32 @main() nounwind < entry: %0 = tail call i32 @puts(i8* getelementptr inbounds ([7 x i8]* @.str, i32 0, i32 0)) nounwind ; [#uses=0] ret i32 0 > declare i32 @puts(i8* nocapture) nounwind 

clang sample.c -c -emit-llvm lli sample.bc 

Отслеживать
71.1k 12 12 золотых знаков 90 90 серебряных знаков 180 180 бронзовых знаков
ответ дан 18 окт 2010 в 16:20
34.5k 25 25 золотых знаков 97 97 серебряных знаков 214 214 бронзовых знаков

Внести правку, пожалуйста, LLVM это не виртуальная машина. Выдержка из первого абзаца с официального веб-сайта: Despite its name, LLVM has little to do with traditional virtual machines. The name «LLVM» itself is not an acronym; it is the full name of the project.

10 мая 2018 в 19:10
Да и не байткод там конечно же, а биткод
10 мая 2018 в 19:11

Хочу добавить к ответу что не только байт-код генерируется, но и компилируется в исполняемый машинный-код на почти все виды процессоров и на почти все виды ОС.

LLVM дает возможность выбирать в какой код генерировать.

LLVM генерирует промежуточный assembler подобный код для анализа того во что превратиться ваш высокоуровневый код написанный как на C, C++, Fortran, Ada и т.д.

Видел и JAVA, Python, Ruby т.е. LLVM дает возможность писать на чем хочешь, и на что хочешь получая очень высокоскоростной код, который еще можно оптимизировать на Assembler уровне.

Проект поддерживается такими гигантами как . а вы и так из википедии дальше знаете.

Что такое LLVM и зачем он нужен?

Всем привет! Думаю, у многих сразу возник другой вопрос — а зачем вообще нужна ещё одна статья про LLVM, ведь на хабре их и так больше сотни? Моей задачей было написать «введение в тему» for the rest of us — профессиональных разработчиков, не планирующих создавать компиляторы и совершенно не интересующихся особенностями устройства LLVM IR. Насколько я знаю, подобного ещё не было.

Главное, что интересует практически всех — и о чём я планирую рассказать — вынесено в заголовок статьи. Зачем нужен LLVM, когда есть GCC и Visual C++? А если вы не программируете на C++, вам стоит беспокоиться? И вообще, LLVM это Clang? Или нет? И что эти четыре буквы на самом деле означают?

Что в имени тебе моём?

Начнём с последнего вопроса. Что скрывается за буквами L-L-V-M? Когда-то давно они были акронимом для «Low Level Virtual Machine», а в наше время означают… ровным счётом ничего.

LLVM родился как исследовательский проект Криса Латнера (тогда ещё студента-магистра в Университете штата Иллинойс в Урбана-Шампейн) и Викрама Адве (тогда и по сию пору профессора в том же университете). Целью проекта было создание промежуточного представления (intermediate representation, IR) программ, позволяющего проводить «агрессивную оптимизацию в течение всего времени жизни приложения» — что-то вроде Java байт-кода, только круче. Основная идея — сделать представление, одинаково хорошо подходящее как для статической компиляции (когда компилятор получает на вход программу, написанную на языке высокого уровня, например C++, переводит её в LLVM IR, оптимизирует, и получает на выходе быстрый машинный код), так и динамической (когда runtime система получает на вход машинный код вместе с LLVM IR, сохранённым в объектном файле во время статической компиляции, оптимизирует его — с учётом собранного к этому времени динамического профиля — и получает на выходе ещё более быстрый машинный код, для которого можно продолжать собирать профиль, оптимизировать, и так до бесконечности).

Интересно? Хотите узнать подробности? Диссертация Криса Латнера доступна онлайн.

Вот картинка из неё, иллюстрирующая принципы работы «оптимизации в течение всего времени жизни приложения»:

Эта картинка, конечно же, про LLVM — но совершенно не про то, что под словом «LLVM» понимается сейчас. Больше того! — на сайте llvm.org написано, что LLVM это не о виртуальных машинах, и вовсе даже не акроним, а просто такое вот название проекта.

Как так получилось? В 2005 году Крис защитил кандидатскую диссертацию и переехал из Иллинойса в Кремниевую долину.

Apple, Google и все-все-все

Примерно в то же время Apple начала задумываться о создании своего собственного компилятора Objective-C и решила сделать ставку на Криса Латнера и его (в то время по сути ещё академический) проект LLVM. Зачем Apple понадобился собственный компилятор? Прежде всего, Apple хорошо известна как компания, стремящаяся контролировать весь технологический стек. Кроме того, у Apple были большие проблемы с инструментами разработки для ранних Маков на основе PowerPC, когда выбранный партнёр (Symantec) не сумел выпустить хороший компилятор вовремя, что поставило под риск будущее всей компании.

В 2005 году Apple уже достаточно долгое время инвестировала в разработку GCC, но как и многие другие, была сильно недовольна лицензией GPL. Особенно GPLv3, на которую перешёл GCC начиная с версии GCC 4.3. Недовольство Apple было так велико, что последней версией GCC, поставляемой в составе XCode, так и осталась GCC 4.2. Главная проблема GPL для компаний, выпускающих секретное «железо»: если бинарии для этого железа генерируются с помощью GCC, то исходный код компилятора, в том числе и секретную часть, надо открыть — и ваше секретное железо теперь совсем не секретное! Проект LLVM всегда был под «либеральной» лицензией (вначале UIUC, потом Apache 2.0), которая не накладывает столь жёстких ограничений, и позволяет свободно комбинировать в одном продукте открытый и закрытый код.

Apple был нужен обычный статический компилятор, а не система для «оптимизации в течение всего времени жизни приложения», и поэтому Крис Латтнер переделал LLVM в бэк-энд для GCC. «Бэк-эндом» называется та часть компилятора, что выполняет оптимизации и генерирует машинный код; есть ещё «фронт-энд» — принимающая на вход пользовательскую программу на языке высокого уровня и переводящая её в промежуточное представление, например LLVM IR. Комбинация GCC-фронт-энда и LLVM-бэк-энда работала неплохо, но не без проблем — соединение двух больших и независимых проектов, преследующих разные цели, всегда чревато появлением лишних ошибок и обрекает на вечную игру в «догонялки». Вот почему уже в 2006 году Крис начал работать над новым проектом, получившим название «Clang».

Происхождение имени «clang» интуитивно понятно — это комбинация слов «C» и «language». «C» указывает на семейство C-образных языков, куда кроме самого C входят также C++ и Objective-C. Кстати говоря, «clang» произносится как «к-ланг», а не как «си-ланг»! — не повторяйте популярную ошибку!

Комбинация фронт-энда Clang и бэк-энда LLVM называется Clang/LLVM или просто Clang. Сейчас это один из самых популярных (если не самый популярный!) компилятор C++ в мире.

Большую роль в развитии и росте популярности LLVM и Clang сыграла компания Google. В отличие от Apple, Google выбрала LLVM в основном по техническим причинам — GCC очень старый проект, который сложно модифицировать и расширять. Для Google всегда были важны надёжность и безопасность программ — например, одно из правил компании требует обязательного добавления статической проверки в компилятор для каждой новой ошибки, обнаруженной в продакшене. Добавить подобного рода проверку в Clang гораздо проще. Ещё один аргумент в пользу Clang — поддержка Windows. GCC органически не подходит для Windows, и хотя есть версия GCC и для этой операционной системы, серьёзную разработку с её помощью вести нельзя. Некоторые вещи, например поддержку отладочной информации в формате PDB, в GCC в принципе невозможно добавить — всё из-за тех же лицензионных ограничений.

Внутренние команды Google всегда были вольны в праве выбора компилятора, и большая часть из них использовала GCC; кто-то применял коммерческие компиляторы от Intel и Microsoft. Постепенно практически весь Google всё-таки перешёл на Clang. Большими вехами стали появление полнокровной поддержки Windows (которую сделала сама Google, причём для компиляции всего-навсего двух программ: Chromium и Google Earth) и переход на LLVM в качестве основного компилятора операционной системы Android. Причину перехода лучше всего объяснили сами разработчики Android: «Пришло время перейти на единый компилятор для Android. Компилятор, способный помочь найти (и устранить) проблемы безопасности.»

После того, как переход сделала Google, рост популярности LLVM было уже не остановить. Всё больше и больше компаний и академических организаций начали делать ставку на LLVM: ARM, IBM, Sony, Samsung, NXP, Facebook, Argonne National Lab… это именно тот случай, когда «всех не перечесть». Некоторые компании продолжают поддерживать GCC, но в значительно большей степени инвестируют именно в LLVM — например, так поступают Intel и Qualcomm. Наплыв инвестиций создал «восходящую спираль роста» — когда новые улучшения LLVM привлекают новых пользователей, те инвестируют в дополнительные улучшения, те в свою очередь приводят ещё больше новых пользователей и инвестиций, и так далее.

LLVM против GCC

Возможно, к этому моменту вы уже начали задаваться вопросом: «ну хорошо, причины, побудившие к переходу Apple и Google, понятны… но мне-то что за дело? Почему лично я должен переходить на LLVM? Чем GCC плох?»

Ответ — абсолютно ничем! GCC продолжает быть отличным компилятором, в который вложены многие годы труда. Да, его сложно расширять, и да, над его развитием работает не так много людей, и да, лицензия GPL серьёзно сужает круг проектов, которые можно сделать на основе кодовой базы GCC — но всё это проблемы разработчиков GCC, а не ваши, ведь так?

К сожалению, проблемы развития проекта GCC в итоге замечают и конечные пользователи — ведь постепенно GCC начинает отставать от LLVM. Все основные «игроки» мира ARM (Google, Samsung, Qualcomm и собственно компания ARM) сфокусированы на развитии прежде всего LLVM — а значит, поддержка новых процессоров на основе архитектуры ARM появляется в LLVM раньше и включает больше оптимизаций и более тщательный «тюнинг» производительности, чем в GCC.

То же самое касается поддержки языка C++. Ричард Смит, инженер компании Google, выступающий секретарём комитета ISO по стандартизации C++ — иными словами, тот человек, кто собственно пишет текст всех дополнений стандарта своими руками — является маинтейнером фронт-энда Clang. Многие другие заметные участники комитета также являются активными разработчиками Clang / LLVM. Сложите эти два факта, и вывод очевиден: поддержка новых дополнений в языке C++ раньше всего появляется именно в Clang’е.

Ещё одно важное преимущество Clang — и как мы знаем, главная причина перехода команды Android на LLVM — развитая поддержка статической верификации. Говоря простыми словами, Clang находит больше warning’ов, чем GCC, и делает это лучше. Кроме того, есть специальный написанный на основе Clang’а инструмент, под названием Clang Static Analyzer, включающий в себя богатую коллекцию сложных проверок, анализирующих больше чем одну строку кода, и выявляющих проблемы использования языка С++, работы с нулевыми указателями и нарушения безопасности.

В проект LLVM входит много разных инструментов, являющихся лидерами в своей области: коллекция динамических верификаторов под названием «санитайзеры», рантайм-библиотека OpenMP (лучшая на рынке), lld (сверх-быстрый линковщик), libc++ (наиболее полная реализация стандартной библиотеки C++). Все они могут использоваться независимо от LLVM — в том числе и с GCC тоже, как минимум в теории. На практике же у каждого компилятора есть множество небольших отличий и особенностей, и потому все эти инструменты лучше всего работают именно с LLVM — ведь они разрабатываются, тестируются и выпускаются все вместе.

Clang разрабатывался как полностью совместимая замена GCC, так что в стандартном проекте для перехода достаточно просто поменять имя компилятора. На практике возможны сюрпризы — от новых ошибок на этапе компиляции до неожиданных падений при тестировании. Обычно это означает, что в проекте есть код, полагающийся на аспекты стандартов C и C++ с «неопределённым поведением» — которое может трактоваться компиляторами GCC и Clang по-разному.

Например, бесконечные циклы. Как вы думаете, что должно случиться после компиляции и выполнения такой программы?

 #include static void die() < while(1) ; >int main()

Попробуйте откомпилировать её с помощью «gcc -O2» и «clang -O2» — результат может вас удивить. Причина в «неопределённом поведении» для бесконечных циклов в стандарте языка C (есть лишний час в запасе? — можете узнать подробности). Раз поведение «неопределено», компилятор волен делать с бесконечными циклами вообще всё, что угодно — даже «выпускать из ноздрей летающих демонов»! (это выражение стало мемом в сообществе C разработчиков). Как можно убедиться, Clang и GCC просто поступают по разному. Конечно же, основывать логику программы на неопределённом поведении не лучшая практика (кто захочет испускать демонов из носа?) и такой код должен исправляться, как и любая другая ошибка.

Я рекомендую попробовать заменить «gcc» на «clang» (или «g++» на «clang++» в случае C++) в каком-то из ваших проектов. Кто знает? — может вам удастся увидеть летающих демонов?

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

«Зонтик» LLVM

Проект LLVM вырос за рамки компилятора C++. Один из важных принципов разработки LLVM — написание кода как набора переиспользуемых библиотек, которые можно соединять разным образом и для разных целей — привёл к появлению множества интересных новых инструментов. Часть из них была добавлена к проекту, так что LLVM со временем превратился в «зонтик» для нескольких совершенно разных подпроектов. Ещё больше инструментов развиваются за пределами проекта LLVM, но полагаются на библиотеки LLVM для анализа и оптимизации программ, а также генерации кода.

Я уже упоминал Clang Static Analyzer, санитайзеры, OpenMP, libc++ и lld — это инструменты, более всего интересные C++ разработчикам. Компилятор языка Rust также основан на LLVM — решение, позволившее Rust задействовать всю мощь LLVM оптимизатора для генерации быстрого кода для множества аппаратных платформ с самого начала существования языка! Помимо C++ и Rust, LLVM используется в компиляторах (как статических, так и динамических) для таких разных языков как D, Fortran, Haskell, Julia, Kotlin, Lua, PHP, Python. Создателю нового языка достаточно написать фронт-энд, переводящий программы в формат LLVM IR, чтобы воспользоваться оптимизатором и генератором кода мирового уровня! Лёгкость использования LLVM в этом качестве дала толчок появлению новых разработок в области языков программирования.

Одна из важных областей применения LLVM — это тензорные компиляторы, многократно ускоряющие задачи машинного обучения. Два из самых популярных ML фреймворков — TensorFlow компании Google и PyTorch от Facebook — полагаются именно на LLVM для генерации быстрого кода.

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

Всё это сделало LLVM критически важным проектом для основных игроков в индустрии — ведь каждый новый патч в «core» библиотеки LLVM влияет на сотни инструментов! Список спонсоров LLVM Developers’ Meeting читается как справочник «кто есть кто» мира IT. Компания, в которой я работаю, Huawei, также является спонсором — ведь как любая большая и разносторонняя организация, мы используем LLVM в большом числе своих продуктов.

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

Я был и остаюсь вовлечён в разработку LLVM в течение многих лет (сначала в Intel, затем в NXP и теперь в Huawei), так что этот проект очень близок моему сердцу. Раскрою карты! — у статьи была и вторая, секретная цель: заразить энтузиазмом и верой в LLVM всех читателей. Что скажете? — удалось? 🙂

LLVM: инфраструктура для разработки компиляторов

LLVM (Low Level Virtual Machine, низкоуровневая виртуальная машина)– новейший фреймворк для разработки компиляторов. Благодаря простоте расширения и организации в виде множества библиотек, LLVM легко поддается освоению даже начинающими программистами, вопреки устоявшемуся мнению о сложности разработки компиляторов. Сначала эта книга покажет, как настроить, собрать и установить библиотеки, инструменты и внешние проекты LLVM. Затем вы познакомитесь с архитектурой LLVM и особенностями работы всех компонентов компилятора: анализатора исходных текстов, генератора кода промежуточного представления, генератора выполняемого кода, механизма JIT-компиляции, возможностями кросс-компиляции и интерфейсом расширений. На множестве наглядных примеров и фрагментов исходного кода книга поможет вам войти в мир разработки компиляторов на основе LLVM.

Эта книга адресована энтузиастам, студентам, изучающим информационные технологии, и разработчикам компиляторов, интересующимся фреймворком LLVM. Читатели должны знать язык программирования C++ и, желательно, некоторые представления о теории компиляции. И для начинающих, и для опытных специалистов эта книга послужит практическим введением в LLVM, не содержащим сложных сценариев. Если вас интересует данная технология, тогда эта книга определенно для вас.

• Настройка, сборка и установка дополнительных открытых проектов LLVM, включая инструменты Clang, статический анализатор, Compiler-RT, LLDB, LLDB, DragonEgg, libc++ и комплект тестов для LLVM;
• Архитектура библиотек LLVM и особенности взаимодействий между библиотеками и автономными инструментами.
• Стадии обработки исходного программного кода и порядок выполнения лексического, синтаксического и семантического анализа анализатором исходного кода Clang.
• Как создаются и обрабатываются файлы LLVM IR с промежуточным представлением, а также разработка собственных проходов анализа и трансформации IR-кода.
• Создание инструментов для использования средств динамической компиляции LLVM (Just-in-Time, JIT).
• Поиск ошибок и оптимизация кода с помощью статического анализатора.
• Анализ архитектуры исходного кода и создание инструментов его преобразования с использованием LibClang, LibTooling и интерфейса расширений Clang.

• Доставка и оплата
• Отзывы и рецензии

Оплата

Наш интернет-магазин работает только по предоплате!
Мы принимаем следующие виды оплаты:

• Банковские карты
• Яндекс.Деньги
• Наличными через кассы и терминалы
• WebMoney
• Сбербанк Онлайн
• Сбербанк смс-оплата
• Альфа-клик
• Интернет-банк Промсвязьбанк
• QIWI Wallet
• Доверительный платеж («Куппи.ру»)

Вы так же можете выбрать оплату по платежной квитанции и оплатить по ней покупку в отделении любого банка.
Юридические лица могут выбрать счёт на оплату.
Возврат денежных средств возможен в случаях:

• Отсутствие книг на складе издательства более 14 дней с момента поступления оплаты;

Возврат не проводится в случаях:

• Отказа покупателя от оплаченного заказа; по договоренности с покупателем возможна замена книг;

Для оформления возврата обращайтесь по электронной почте dmkpress.help@gmail.com.

Доставка:

Курьерская доставка по Москве в течение 7 дней после оплаты заказа.
Стоимость доставки:

• При заказе до 3000 рублей – 300 рублей.
• При заказе свыше 3000 рублей – бесплатно.

Самовывоз возможен в течение суток после оплаты.
Адрес для самовывоза:
115487, г. Москва, проспект Андропова, 38
Доставка почтой России: от 7 до 28 дней с момента оплаты заказа.
Стоимость доставки:

• В пределах России – от 300 рублей
• По миру – от 1400 рублей.

Обзор LLVM

LLVM (Low Level Virtual Machine) — это универсальная система анализа, трансформации и оптимизации программ или, как её называют разработчики, «compiler infrastucture».

LLVM — не просто очередной академический проект. Его история началась в 2000 году в Университете Иллинойса, а теперь LLVM используют такие гиганты индустрии как Apple и Adobe. В частности, на LLVM основана подсистема OpenGL в MacOS X 10.5, а iPhone SDK использует GCC с бэкэндом на LLVM. Apple является одним из основных спонсоров проекта, а вдохновитель LLVM — Крис Латтнер — теперь работает в Apple.

В основе LLVM лежит промежуточное представление кода (intermediate representation, IR), над которым можно производить трансформации во время компиляции, компоновки (linking) и выполнения. Из этого представления генерируется оптимизированный машинный код для целого ряда платформ, как статически, так и динамически (JIT-компиляция). LLVM поддерживает генерацию кода для x86, x86-64, ARM, PowerPC, SPARC, MIPS, IA-64, Alpha.

LLVM написана на C++ и портирована на большинство *nix-систем и Windows. Система имеет модульную структуру и может расширяться дополнительными алгоритмами трансформации (compiler passes) и кодогенераторами для новых аппаратных платформ. Пользовательский фронтенд, как правило, линкуется с LLVM и использует C++ API для генерации кода и его преобразований. Однако LLVM включает в себя и standalone утилиты.

Для тех, кто не без оснований считает C++ не лучшим языком для написания компиляторов, с недавних пор в LLVM включена обертка API для OCaml.

Чтобы понять, что можно сделать с помощью LLVM, и на каком уровне придётся работать, давайте разберёмся, что из себя представляет LLVM IR. В одном предложении его можно охарактеризовать как типизированный трёхадресный код в SSA-форме.

Здесь и далее мы будем использовать текстовую форму записи промежуточного кода, своеобразный «ассемблер» LLVM. На практике для хранения кода используется эффективное бинарное представление (bitcode). Генерировать же код обычно удобнее всего не в текстовой форме, и тем более не в бинарной, а с помощью специального API. До биткода в этом случае может и не доходить: код формируется в виде внтуренних структур в памяти, над которыми и проводятся все операции, вплоть до генерации машинного кода.

Типы данных

Целые числа произвольной разрядности:

i1 ; булево значение — 0 или 1
i32 ; 32-разрядное целое
i17 ; даже так
i256 ; ого!

тип*
i32* ; указатель на 32-битное целое

[число элементов x тип]
[10 x i32]
[8 x double]

i32 (i32, i32)
float (< float, float >, < float, float >)

Операции

Большинство инструкций в LLVM принимают два аргумента (операнда) и возвращают одно значение (трёхадресный код). Значения определяются текстовым идентификатором. Локальные значения обозначаются префиксом % , а глобальные — @ . Локальные значения также называют регистрами, а LLVM — виртуальной машиной с бесконечным числом регистров. Пример:

%sum = add i32 %n, 5
%diff = sub double %a, %b
%z = add %v1, %v2 ; поэлементное сложение
%cond = icmp eq %x, %y ; Сравнение целых чисел. Результат имеет тип i1.
%success = call i32 @puts(i8* %str)

Тип операндов всегда указывается явно, и однозначно определяет тип результата. Операнды арифметических инструкций должны иметь одинаковый тип, но сами инструкции «перегружены» для любых числовых типов и векторов.

Вместо утомительного перечисления инструкций (всего их 52) скажем, что LLVM поддерживает полный набор арифметических операций, побитовых логических операций и операций сдвига, а также специальные инструкции для работы с векторами.

LLVM IR строго типизирован, поэтому не обойтись без приведений типов, которые явно кодируются специальными инструкциями. Набор из 9 инструкций покрывает всевозможные приведения между различными числовыми типами: целыми и с плавающей точкой, со знаком и без, различной разрядности и пр. Кроме этого есть инструкции преобразования между целыми и указателями, а так же инструкция bitcast , которая приведёт всё ко всему, но за результат вы отвечаете сами.

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

; x = (a + b) * c — d / e
%tmp1 = add float %a, %b
%tmp2 = mul float %tmp1, %c
%tmp3 = fdiv float %d, %e
%x = sub float %tmp2, %tmp3

Забегая вперёд, за пределы этой статьи, заметим, что при использовании LLVM API для генерации кода всё становится ещё проще, потому что оно следует принципу «инструкция — это значение». Нам не придётся заниматься генерацией уникальных имён для промежуточных значений: функция, генерирующая инструкцию, возвращает значение (объект C++), которое может быть передано как аргумент в другие такие функции.

SSA

SSA (static single assignment form) — это такая форма промежуточного представления кода, в которой любое значение присваивается только один раз. Таким образом, нельзя написать:

%z = sum i32 %x, %y
%z = sum i32 %z, 5

Новое значение должно получить новое имя:

%z.1 = sum i32 %z, 5

Однако, спросите вы, как быть, если одна и та же переменная должна получить разные значения в зависимости от какого-то условия? Или как организовать переменную цикла?

• ret типзначение — возврат значения из функции
• br i1 условие, label метка_1, label метка_2 — условный переход. Например:

define float @max(float %x, float %y)
<
%cond = fcmp ogt float %x, %y
br i1 %cond, label %IfTrue, label %IfFalse
IfTrue:
ret float %x
IfFalse:
ret float %y
>

(Синтаксис определения функции, думаю, очевиден).
Есть также форма безусловного перехода:

br label метка

switch i32 %n, label %Default, [i32 0, label %IfZero i32 5, label %IfFive]

В LLVM этой функции соответствует инструкция phi, которая имеет следующую форму:

phi тип, [значение_1, label метка_1], . [значение_N, label метка_N]

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

int factorial(int n)
<
int result = n;
int i;
for (i = n — 1; i > 1; —i)
result *= i;
return result;
>

Примечание: блок, который начинается с входа в функцию обозначается %0 .

define i32 @factorial(i32 %n)
<
%i.start = sub i32 %n, 1
br label %LoopEntry
LoopEntry:
%result = phi i32 [%n, %0], [%result.next, %LoopBody]
%i = phi i32 [%i.start, %0], [%i.next, %LoopBody]
%cond = icmp sle i32 %i, 1
br i1 %cond, label %Exit, label %LoopBody
LoopBody:
%result.next = mul i32 %result, %i
%i.next = sub i32 %i, 1
br label %LoopEntry
Exit:
ret i32 %result
>

Пусть вас не смущают бессмысленные на первый взгляд переходы на метку, следующую сразу за инструкцией перехода. Как мы уже сказали, базовый блок обязан заканчиваться явной передачей управления. LLVM также требует, чтобы все phi-инструкции шли в начале блока, и до них не было никаких других инструкций.
Здесь, наверное, многие воскликнут: но это же ужасно неудобно! Действительно, хотя SSA-форма позволяет производить много полезных трансформаций, непосредственно генерировать её из кода на императивном языке затруднительно, хотя есть хорошо известные алгоритмы преобразования в SSA. К счастью, при написании компилятора на основе LLVM нет никакой необходимости заниматься этим, потому что система умеет генерировать SSA самостоятельно. Как и из чего, мы сейчас узнаем.

Память

Помимо значений-регистров, в LLVM есть и работа с памятью. Значения в памяти адресуются типизированными указателями, о которых мы говорили выше. Обратиться к памяти можно только с помощью двух инструкций, названия которых говорят сами за себя: load и store . Например:

%x = load i32* %x.ptr ; загрузили значение типа i32 по указателю %x.ptr
%tmp = add i32 %x, 5 ; прибавили 5
store i32 %tmp, i32* %x.ptr ; и положили обратно

Но чтобы пользоваться указателями, надо как-то выделять память под значения, на которые они указывают.

Инструкция malloc транслируется в вызов одноименной системной функции и выделяет память на куче, возвращая значение — указатель определенного типа. В паре с ней конечно же идёт инструкция free .

%struct.ptr = malloc < double, double >
%string = malloc i8, i32 %length
%array = malloc [16 x i32]
free i8* %string

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

А вот инструкция alloca незаменима и очень важна. Она имеет такой же формат, но выделяет память на стеке.

%x.ptr = alloca double ; %x.ptr имеет тип double*
%array = alloca float, i32 8 ; %array имеет тип float*, а не [8 x float]!

Память, выделенная alloca , автоматически освобождается при выходе из функции при помощи инструкций ret или unwind .
С помощью alloca , load и store мы можем пользоваться локальными переменными так же, как и в любом императивном языке. Например, наша многострадальная функция факториала:

define i32 @factorial(i32 %n)
<
%result.ptr = alloca i32 ; выделить память под result
%i.ptr = alloca i32 ; и под i
store i32 %n, i32* %result.ptr ; инициализация result = n
%tmp1 = sub i32 %n, 1
store i32 %tmp1, i32* %i.ptr ; i = n — 1
br label %Loop
Loop:
%i = load i32* %i.ptr ; загружаем значение i
%cond = icmp sle i32 %i, 1 ; и проверяем условие i br i1 %cond, label %Exit, label %LoopBody ; если да, переход к возврату значения
LoopBody:
%tmp2 = load i32* %result.ptr
%tmp3 = mul i32 %tmp2, %i
store i32 %tmp3, i32* %result.ptr ; result *= i
%i.next = sub i32 %i, 1
store i32 %i.next, i32* %i.ptr ; —i
br label %Loop
Exit:
%result = load i32* %result.ptr
ret i32 %result ; return result
>

Достаточно многословно, но скажите, где ещё кроме подобной статьи вы будете писать код на LLVM вручную? 🙂
Хорошая новость в том, что из подобного кода LLVM умеет строить SSA-форму. Этот процесс называется «promote memory to register». Вот что получится из функции factorial после прохода этого алгоритма:

define i32 @factorial(i32 %n) <
; :0
%tmp1 = sub i32 %n, 1
br label %Loop
Loop:
%i.ptr.0 = phi i32 [ %tmp1, %0 ], [ %i.next, %LoopBody ]
%result.ptr.0 = phi i32 [ %n, %0 ], [ %tmp3, %LoopBody ]
%cond = icmp sle i32 %i.ptr.0, 1
br i1 %cond, label %Exit, label %LoopBody
LoopBody:
%tmp3 = mul i32 %result.ptr.0, %i.ptr.0
%i.next = sub i32 %i.ptr.0, 1
br label %Loop
Exit:
ret i32 %result.ptr.0
>

Операции с указателями

Массивы в LLVM очень похожи на таковые в Си, но адресной арифметики, как в Си, нет. То есть нельзя написать:

%ptr = add i32* %array, i32 %index

Для вычисления адресов элементов массивов, структур и т. д. с правильной типизацией есть специальная инструкция getelementptr .

%array = alloca i32, i32 %size
%ptr = getelementptr i32* %array, i32 %index ; значение типа i32*

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

struct s <
int n;
char *a[4];
>;
struct *s = . ;
char c = s->a[2][5];

будет сгенерирована такая последовательность инструкций:

%ptr = getelementptr < i32, [4 x i8*] >* %s, i32 1, i32 2, i32 5
%c = load i8* %ptr

Как вы заметили, индексы отсчитываются от нуля.
Есть очень похожая на getelementptr пара инструкций extractvalue и insertvalue . Они отличаются тем, что принимают не указатель на агрегатный тип данных (массив или структуру), а самое значение такого типа. extractvalue возвращает соответственное значение подэлемента, а не указатель на него, а insertvalue порождает новое значение агрегатного типа.

%n = extractvalue < i32, [4 x i8*] >%s, 0
%tmp = add i32 %n, 1
%s.1 = insertvalue < i32, [4 x i8*] >%s, i32 %tmp, 0

Встроенные функции и аннотации

Ряд примитивов представляются в LLVM не инструкциями, а встроенными функциями (intrinsic functions). Например, некоторые математические функции: @llvm.sqrt.* , @llvm.sin.* и т. д. Есть также примитивы для атомарных операций и некоторые другие.

Интересно то, что вызовы этих функций в промежуточном коде вовсе не обязаны превращаться в вызовы функций в машинном коде, или даже в инлайн-подстановки функций. Они могут просто нести служебную информацию для какой-то подсистемы компилятора. Например, так организована генерация отладочной информации в формате DWARF: в IR вставляются вызовы функций %llvm.dbg.stoppoint (задаёт соответствие между строками исходного кода и генерируемым кодом), %llvm.dbg.declare (задаёт описание локальной переменной) и др., в качестве аргументов которым передаются указатели на специальные структуры.

Аналогичным образом реализована поддержка сборки мусора. LLVM не содержит какого-либо алгоритма сборки мусора, вместо этого предоставляя интерфейс для написания собственного точного GC. Примитивы @llvm.gcroot , @llvm.gcread и @llvm.gc.write позволяют закодировать информацию, необходимую для работы GC, а интерфейс плагина к компилятору LLVM — сгенерировать по этой информации нужные структуры данных и вставить обращения к рантайму.

Что умеет оптимизатор LLVM

• Удаление неиспользуемого кода (dead code elimination).
• Выделение одинаковых подвыражений (common subexpression elimination).
• Распространение констант (constant propagation, condition propagation).
• Инлайн-подстановка функций.
• Разворот хвостовой рекурсии. LLVM также умеет в некоторых случаях разворачивать не хвостовые рекурсивные вызовы за счёт ввода дополнительной переменной-аккумулятора, как это зачастую делают в функциональных языках. Например, в этой функции рекурсивный вызов будет успешно заменён условным переходом.

int factorial(int n)
<
if (n < 2) return 1;
return n * factorial(n — 1);
>

Вместо заключения

Из этого краткого обзора видно, что промежуточное представление LLVM достаточно близко соответствует коду на низкоуровневых процедурных языках вроде Си. Транслятор Си на основе LLVM будет достаточно прост и прямолинеен, но при этом сгенерированный им машинный код по производительности сможет тягаться с последними версиями GCC.

При трансляции высокоуровневых языков — объектно-ориентированных, функциональных, динамических — придётся выполнить гораздо больше промежуточных преобразований, а также написать специализированный рантайм. Но и в этом случае LLVM снимает с разработчика компилятора проблемы кодогенерации для конкретной платформы, берёт на себя большинство независимых от языка оптимизаций — и делает их качественно. Помимо этого, мы получаем готовую инфраструктуру для JIT-компиляции и возможность link-time оптимизации между различными языками, компилируемыми в LLVM.

LLVM пытается достичь баланса между удобством и гибкостью, не навязывая какую-то конкретную парадигму программирования, не ограничивая систему типов.

Полноценный фронтенд на сегодняшний день существуют только для C, C++, Ada и Fortran — это llvm-gcc. Идёт работа по созданию независимого от GCC компилятора C/C++ — clang. Оба проекта поддерживаются основной командой LLVM.

Остальные проекты компиляторов известных языков на базе LLVM пока не достигли уровня практической применимости. Но перспективы заманчивы. Увидим ли мы компилятор современного функционального или динамического (PyPy?) языка на LLVM — покажет время.