Pull to refresh

Comments 55

Спасибо за статью. Стало действительно немного понятнее, как это работает.
Хорошо, что все больше статей по LLVM появляется на русском языке, спасибо.

В качестве дополнительных материалов могу предложить послушать мой доклад на прошедшей конференции C++ Siberia.

А еще, буквально в эту пятницу я буду читать доклад на конференции в Санкт-Петербурге об LLVM и проблемах алиасинга. Будет рассказано о технике Alias Analysis, преимуществах, недостатках и о том, как оно применяется в современных компиляторах.
Спасибо, послушаю.
Проблемы алиасинга, даже не слышал, если честно. Буду рад узнать, что это такое.
Ещё пример использования llvm как независимого от входного языка — это LabVIEW. Начиная с версии 2010 они используют именно llvm. Там графическая блок-диаграмма представляется как DFIR (dataflow intermediate representation) граф, который транслируется в llvm IR код. Это даёт возможность иметь компилируемый графический язык, при этом платформонезависимый — это работает не только в windows, но и на линуксе и на маке.
Вот тут можно чуть-чуть почитать: The LabVIEW Compiler — Under the Hood
Ну ещё любопытно обратить внимание на то, где llvm используется: LLVM Users
Вот это интересно, не знал.
UFO just landed and posted this here
Хорошие курсовые, у нас таких не было. Трансляция из блок-схемы в С, это же очень полезная вещь для различных визуальных сред разработки. Программируемые логические контроллеры так и программируются, в целом, например IsaGraf перегоняет разные блоковые диаграммы в С, потом компилирует обычным компилятором, чуть ли не Turbo C.
Маленькое замечание: "Сам GCC написан на языке С."

GCC начали переписывать на C++ в 2012 году, а на текущий момент бОльшая его часть уже на C++.
Спасибо, внёс дополнение в текст.
Отличная статья! Требую продолжения!
Вряд ли возможно реализовать компилятор языка С для 4-хбитной архитектуры
То есть, для Z80 можно?
Да, и даже такие проекты существуют. Не знаю, насколько они закончены и сколько там багов, но на гитхабе я видел.
Как раз хотел разработать свой процессор! :-)
Но возникла проблема — в нем не предусмотренно обращения к памяти по указателю, только по индексу в массиве.
Если я не ошибаюсь, обращения по индексу в LLVM не сделано отдельной операцией, а транслируется в получение указателя и обращение по нему. Можно ли это как-то обойти?
Вы именно ошибаетесь.
Для обращения по индексу в LLVM служит инструкция getelementptr, которая возвращает указатель, получая в качестве аргументов базовый указатель и индексы.
В обычных случаях она преобразуется в сложения и умножения очевидным образом, но при желании её можно обработать как угодно.
Именно. А для моей архитектуры я не могу реализовать getelementptr, там просто нет такого понятия, как указатель. Потучается, что LLVM для нее нельзя реализовать, хотя бы частично (для программ, которые явно не используют указателей).
Ну хорошо, а каким образом в вашей архитектуре происходит доступ к элементу массива?
Не нужно также забывать, что в языке С указатели не просто есть, они составляют основу языка, и с этим придётся смириться.
Примерно как в i*86 к сегментам (точнее, как в i432 к полям объекта) — по индексному регистру и фиксированному смещению или целочисленному регистру.
Я готов смириться, что значитальная чаcть C/C++ программ не ней не пойдут. Но LLVM — это еще и Rust, и еще куча приятных языков, для реализации которых на этой архитектуре особых проблем нет.
То есть индексный регистр + смещение = адрес ячейки, я правильно понял?
Никаких проблем здесь нет. Аргументы инструкции getelementptr можно привести к такому виду без особых проблем. Они как бы к такому виду и приводятся обычно, т. к. в большинстве стандартных архитектур адрес и задаётся как индексный регистр+ смещение.
Я не знаю Rust, увы, может быть, там не указателей с точки зрения пользователя, но на всякий случай попробуйте скомпилировать какую-либо тестовую программу в LLVM IR. Что-то мне подсказывает, что там будут и указатели, и всё вот это.
На уровне системы команд там вообще нет понятия адреса. Индексные регистры получают значение только в результате операций аллокации, вызова подпрограммы (аллокация аналога фрейма стека), получения подобъекта другого объекта или чтения индексной части объекта в памяти.
Можно эмулировать указатель объектом с одним индексным полем и одним целочисленным. Но боюсь это будет сложно в реализации и плохо поддаваться оптимизации.
Я всё равно не понимаю, чем это отличается от стандарной схемы.
Например, код на с:

//сумма эл-тов массива
int foo(int arr[10]) {
  int sum = 0;
  for(int i = 0; i < 10; ++i) {
    sum += arr[i];
  }
  return sum;
}

Код на LLVM IR: (служебная информация опущена)
`
entry:
br label %for.body

for.cond.cleanup:; preds = %for.body
ret i32 %add

for.body:; preds = %for.body, %entry
%indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
%sum.06 = phi i32 [ 0, %entry ], [ %add, %for.body ]
%arrayidx = getelementptr inbounds i32, i32 %arr, i64 %indvars.iv
%0 = load i32, i32
%arrayidx, align 4, !tbaa !1
%add = add nsw i32 %0, %sum.06
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
%exitcond = icmp eq i64 %indvars.iv.next, 10
br i1 %exitcond, label %for.cond.cleanup, label %for.body
}
Видно, что доступ к элементам массива происходит через gelelementptr/load Код на асме ARM:
foo: # foo

BB#0: # %entry
mov r2, 0
mov r3, 0

LBB0_1: # %for.body

=>This Inner Loop Header: Depth=1
mov r4, r1
add r4, r2
ldw r0, 0(r4)
add r0, r3
addi    r2, 4
mov r3, r0
jeqi    r2, 40 goto LBB0_2
jmp LBB0_1

LBB0_2: # %for.cond.cleanup
ret
`

Доступ к элементам массива происходит через индексный регистр r4. Никаких проблем нет.

(парсер хабра что-то чудит с разметкой, но вроде всё понятно)
(1) %arrayidx = getelementptr inbounds i32, i32 %arr, i64 %indvars.iv
(2) %0 = load i32, i32 %arrayidx, align 4, !tbaa !1

Что бы откомпилировать команду (2), мне надо разобрать на части команду (1). Без (1) это сделать невозможно.
Хотя, благодаря SSA, скорее всего команду getelementptr всегда можно найти.
Надо подумать в эту сторону.
Разберите сразу обе команды, например.
Они могут быть разнесены оптимизатором далеко друг от друга. Да и на одну getelementptr может приходится несколько load/store. Так что вся надежда на SSA.
Ну не знаю, я особых сложностей не вижу, если честно.
В конечном итоге, если в вашем процессоре доступ к элементу массива вообще как-то осуществляется, т.е сущ-вует соответствующая последовательность команд, вы можете просто вручную (в смысле, своим кастомным кодом) заменять пару getelementptr/load этой последовательностью.
каждой переменной значение присваивается ровно один раз и только в одной точке программы.
Напомнило Erlang — там переменные присваиваются тоже только один раз.
Посмотреть и сравнить выхлоп ассемблера для gcc, clang-llvm разных версий можно на https://gcc.godbolt.org/
Знакомился с LLVM и не нашёл, как можно изменить содержимое указателя стека. В x86 можно написать так: «xchg esp,other_stack». А как сделать что-то подобное на LLVM? Заранее спасибо.
Не совсем уловил суть вопроса. У вас есть какой-то процессор, в нём есть регистр указателя стека, и есть команды, которые изменяют его содержимое. Вы разрабатываете для этого процессора бэкенд LLVM. В нём вы можете генерировать нужные вам команды, для этого есть множество способов.
А в самом по себе LLVM никакого указателя стека нет.
У меня есть обычный процессор x86. Если я пишу компилятор и желаю переключаться между стеками, то какой код генерировать для этого: машинный код х86 или же LLVM, в котором всё таки есть что-то похожее на «xchg esp,other_stack», но которое я не увидел?
Если я вас правильно понял, то под написанием компилятора вы подразумеваете генерацию машинного кода x86 из промежуточного кода LLVM. В таком случае и генерируйте нужные вам команды для изменения стека, когда сочтете нужным. Я правда не понимаю, зачем вам это, разве то, что уже написано, вас не устраивает? Если бы вы писали под другой процессор, тогда еще понятно, но под древний, как мир, x86???
Промежуточный код LLVM не работает с физическими регистрами. Нужно генерировать машинную инструкцию.
Под компиляцией и генерацией машинного кода я имею в виду варианты:
1) генерация напрямую: программа на языке высокого уровня -> промежуточное представление -> нативный код,
2) генерация через LLVM: программа на языке высокого уровня -> промежуточное представление -> LLVM -> нативный код.

Первый вариант имеет преимущества:
1) быстрая компиляция
2) полное и эффективное использование возможностей конкретного процессора

Недостаток: необходимость разработки кодогенератора для каждой платформы

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

Мне интересно, насколько сильно обрезаны возможности LLVM в сравнении с традиционными ассемблерами, осталась ли там возможность изменения указатели вершины стека. Почему это интересует – написал в личном сообщении.

Архитектура x86 – живее всех живых, сейчас она существует в своей 64-разрядной инкарнации. Когда-то в ней был регистр SP, потом ESP, теперь RSP. Ну суть осталась та же: он указывает вершину стека. А архитектуре ARM на вершину стека указывает регистр № 13. И ARM, и x86 позволяют загружать эти регистры новым содержимым, т.е. после «xchg esp,other_stack» в 32-разрядной архитектуре x86 он указывает на другое место. А вот в LLVM такой возможности не увиделось. Возможно, плохо искал. Но, может быть, её вообще нет.

Вот в чём суть моих вопросов.
Это не так. Все современные компиляторы, включая LLVM, работают по варианту 1. Более точно это показано на рисунке 1.
Далее я буду писать только про бэкенд, т.е. преобразование из промежуточного кода в код таректа.
По поводу преимуществ:

  1. LLVM имеет возможность быстрой компиляции, в основном для работы в режиме JIT.
  2. Насколько полно и эффективно будут использованы возможности процессора, зависит только от разработчика бэкенда. LLVM не ограничивает его ни в чём.
  3. Разумеется, нужно писать кодогенератор под каждую платформу (если под кодогенератором вы понимаете бэкенд).
  4. В LLVM есть возможность генерации любых машинных инструкций.
Генерация кода из моего собственного промежуточного представления в нативный код быстрее, нежели из собственного промежуточного представления в промежуточное представление LLVM, из которого уже потом получается нативный код. Просто потому, что этапов меньше.

Для полного задействования возможностей x86, в т.ч. загрузки новым значением указателя стека, нужно переписать соответствующий бэкенд? Я правильно понял? Т.е. сейчас в LLVM указатель стека не может быть загружен новым значением по ходу работы? Или я не всё понял в устройстве LLVM?
  1. Зачем нужно собственное промежуточное представление, и генерировать из него LLVM IR? Чем вас не устраивает clang, который просто генерирует LLVM IR?

  2. нужно переписать соответствующий бэкенд?
    Вероятно, да.

  3. Т.е. сейчас в LLVM указатель стека не может быть загружен новым значением по ходу работы?
    Давайте различать LLVM и конкретный бэкенд LLVM. Я не знаю устройство именно бэкенда x86, и не знаю, как он работает со стеком.
Простите, личное сообщение было 32bit_me.

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

Нет, не так. На уровне IR (промежуточного кода) никакого стека нет, он работает только с виртуальными (не физическими) регистрами.
Дальше генерируются другие промежуточные представления, где действительно есть стек (точнее, Frame Index, индексы в кадре стека). Их обработка и преобразование в конкретные машинные инструкции остаётся целиком за разработчиком бэкенда. При этом процессор может иметь отдельно регистр стека и регистр фрейма, или только регистр стека, например (хотя при этом будет нельзя работать со стеком, динамически изменяющим размер в run-time).
В командах Selection DAG (которое является следующим за IR промежуточным представлением) операнды работы со стеком имеют вид, например FI+1, где FI — текущий кадр стека. Его значение не определено, команды оперируют только относительным смещением.
Указатель стека вы можете изменять, как и любой другой физический регистр, соответствующими командами таргета.
На уровне IR (промежуточного кода) никакого стека нет, он работает только с виртуальными (не физическими) регистрами.

Хотелось бы, чтобы были не только виртуальные регистры, но и виртуальный стек.

Дальше генерируются другие промежуточные представления, где действительно есть стек (точнее, Frame Index, индексы в кадре стека)

«Дальше» – это значит после уровня IR (промежуточного кода)? Если взглянуть на рис. 1. (модульная архитектура компилятора), то в центре стоит оптимизатор. На каком этапе существует IR и на каком появляется стек? Вроде бы выходит, что есть несколько промежуточных представлений. И какое из них всё ещё универсальное, не завязанное на конкретную архитектуру?

В чём притягательная сила LLVM? При написании компилятора нет необходимости делать сотню бэкендов, достаточно сделать единственное преобразование в LLVM IR (это так видится!). О преобразовании в код конкретной архитектуры позаботится инфраструктура LLVM. Главное – написать правильный бит-код для LLVM IR и запустить преобразование с правильными опциями.

Но, оказывается (такой вывод можно сделать из ваших слов), генерацию кода для целевой машины надо допиливать, сто раз для ста платформ. И в чём тогда притягательность LLVM? Для разработчиков новых архитектур она полезна: разработал свой бэкенд, и в твоём распоряжении компиляторы Си, Фортрана, Хаскелла. Но для разработчиков компиляторов новых языков – не вполне.
Хотелось бы, чтобы были не только виртуальные регистры, но и виртуальный стек.

Зачем? IR обходится без этого.

На каком этапе существует IR

Код IR поступает в бэкенд и там преобразуется в SelectionDAG, который уже зависит от таргета. IR не зависит от таргета (если на вдаваться в тонкости).

Притягательная сила LLVM состоит в том, чтобы сделать только то, что вам нужно, а остальное сделает LLVM. Если вы хотите сделать компилятор для нового языка программирования, то вам не нужно писать множество бэкендов, достаточно сгенерировать правильный IR-код. Если вы хотите сделать оптимизации нативного кода для конкретной архитектуры, то вам не нужно заниматься формированием IR-кода, нужно написать только бэкенд (или модифицировать существующий).
Если вам очень хочется изменять регистр стека из IR-кода, можно сделать ассемблерную вставку с нужной командой.
сделать ассемблерную вставку с нужной командой.
Да, такой «костыль» мог бы стать решением, вот только ещё надо знать, как это сделать. На Си я это делал как раз такой вставкой. Конечно, после вставки нативного кода универсальность теряется.
Если вы хотите сделать оптимизации нативного кода для конкретной архитектуры, то вам не нужно заниматься формированием IR-кода, нужно написать только бэкенд (или модифицировать существующий).
Вероятно, надо модифицировать существующий бэкенд, но потом из IR-кода надо ещё как-то воспользоваться этой модификацией. Короче, надо изучать и вникать. Литературы на русском мало, а с английской всё будет дольше.
Спасибо за проявленное терпение!
Конечно, после вставки нативного кода универсальность теряется.

Вы говорили, что вам нужно только под платформу x86.
Если нужно всё-таки для разных, можно вставлять разный код для разных архитектур.

из IR-кода надо ещё как-то воспользоваться этой модификацией.

Так часто практикуется. Clang может генерировать разный IR-код для разных аппаратных платформ, в расчёте на то, что конкретный бэкенд умеет оптимизировать определённые структуры в IR-коде.
Вы говорили, что вам нужно только под платформу x86.
Да, нет, я начал с этого:
Знакомился с LLVM и не нашёл, как можно изменить содержимое указателя стека. В x86 можно написать так: «xchg esp,other_stack». А как сделать что-то подобное на LLVM?
Если есть какой-то универсальный механизм, то кто ж тогда откажется, чтобы его компилятор работал сразу на многих платформах? Честно говоря, написать бэкенд для x86 для меня проще, чем для LLVM, потому что всё знакомо. Но если LLVM позволит сделать многоплатформенный компилятор, то стоит задуматься об изучении LLVM – игра будет стоить свеч.
написать бэкенд для x86 для меня проще, чем для LLVM

Бэкенд для x86 уже написан, и он входит в состав LLVM. Я не знаю точно, что вы хотите сделать, но вам нужно внести изменения в Clang, наверное.
Вы хотите реализовать какой-то свой язык программирования?
Бэкенд для x86 уже написан, и он входит в состав LLVM. Я не знаю точно, что вы хотите сделать, но вам нужно внести изменения в Clang, наверное.
Вы хотите реализовать какой-то свой язык программирования?
Имею в виду преобразование (бэкенд) «своё промежуточное представление -> код x86» (которое для меня проще), нежели «своё промежуточное представление -> код LLVM IR»
Вы хотите реализовать какой-то свой язык программирования?
Мы, по-видимому, смотрим на LLVM под разным углом зрения: я – как состыковать свой язык программирования с LLVM, а Вы – как состыковать с ним своё железо :)
своё промежуточное представление

Если вы удалите из этой схемы своё промежуточное представление, вы существенно упростите себе жизнь.
Свой язык программирования можно реализовать в Clang-е, есть хорошие примеры, описания и т.д.
Промежуточное представление – это очень общее понятие, это может быть и ориентированный граф, и трёхадресный код, и обратная польская запись и т.д. Лексический, синтаксический, семантический анализ должны каким-то образом хранить анализируемую программу, для этого ПП и служит. Разным по стилю языкам можно подобрать наиболее удобную форму. Если я удалю своё ПП – то как я проанализирую? Воспользоваться ПП от LLVM? Но это опять проблемы. Где взять его описание, какие он оно вообще работает? Много вопросов. Больше, чем если бы просто делал по обычным учебникам.
Да, разумеется, пользоваться библиотекой LLVM и Clang.
Описание взять здесь: llvm.org.
Кстати, если вспомнить, что LLVM – это виртуальная машина низкого уровня, то можно ли запустить её в режиме интерпретации? Т.е. подаёшь на вход какой-то код, а LLVM его выполняет? Не с целью генерации кода, а чтобы "поиграться", попробовать. В LLVM Projects нет намёков на это.
Из Википедии:
«В основе LLVM лежит промежуточное представление кода (Intermediate Representation, IR)… Из этого представления генерируется оптимизированный машинный код для целого ряда платформ, как статически, так и динамически (JIT-компиляция)».

Мне хотелось узнать, какими средствами LLVM IR нужно пользоваться, чтобы генератор кода (уже написанный для x86) делал переключение стеков. Меня не интересует конкретный бэкенд LLVM. Мне хочется узнать, как это сделать на уровне LLVM IR. Если LLVM IR это имеет, то и конкретный бэкенд сделает то, что я хочу. Может, он придумает что-то более оптимальное, нежели «xchg esp,other_stack».
На уровне LLVM IR стека нет (см. ответ выше).
Sign up to leave a comment.

Articles