LLVM — сложная часть программного обеспечения. Существует несколько способов понять, как это работает, но ни один из них не прост. Недавно мне пришлось копаться в некоторых областях LLVM, с которыми я ранее не был знаком, и эта статья является одним из результатов этого квеста.
Здесь я намерен следовать различным воплощениям, которым «инструкция» пользуется, когда она проходит через несколько этапов компиляции LLVM, начиная с синтаксической конструкции на исходном языке и до кодирования в виде двоичного машинного кода в выходном объектном файле.
Эта статья сама по себе не научит тому, как работает LLVM. Он предполагает некоторое знакомство с дизайном и кодовой базой LLVM и оставляет много «очевидных» деталей. Обратите внимание, что, если не указано иное, приведенная здесь информация относится к LLVM 3.2. LLVM и Clang являются быстро развивающимися проектами, и будущие изменения могут сделать части этой статьи некорректными. Если вы заметили какие-либо несоответствия, пожалуйста, дайте мне знать, и я сделаю все возможное, чтобы исправить их.
Введите код
Я хочу начать этот процесс исследования с самого начала — C источник. Вот простая функция, с которой мы будем работать:
int foo(int aa, int bb, int cc) {
int sum = aa + bb;
return sum / cc;
}
В центре внимания этой статьи будет операция деления.
лязг
Clang служит внешним интерфейсом для LLVM, отвечая за преобразование C, C ++ и ObjC источника в LLVM IR. Основная сложность Clang заключается в способности правильно анализировать и семантически анализировать C ++; последовательность простых операций на уровне C на самом деле довольно проста.
Парсер Clang создает абстрактное синтаксическое дерево (AST) из входных данных. AST является основной «валютой», в которой работают различные части Clang. Для нашей операции деления в AST создается узел BinaryOperator, несущий BO_div «вид оператора» [1] . Генератор кода Clang затем отправляет команду sdiv LLVM IR из узла, поскольку это разделение целочисленных типов со знаком.
LLVM IR
Вот LLVM IR, созданный для функции [2] :
define i32 @foo(i32 %aa, i32 %bb, i32 %cc) nounwind {
entry:
%add = add nsw i32 %aa, %bb
%div = sdiv i32 %add, %cc
ret i32 %div
}
В LLVM IR sdiv является BinaryOperator, который является подклассом инструкции с кодом операции SDiv [3] . Как и любая другая инструкция, она может быть обработана этапами анализа и преобразования LLVM. Для конкретного примера, нацеленного на SDiv, взгляните на SimplifySDivInst. Поскольку на всем «среднем» уровне LLVM инструкция остается в форме IR, я не буду тратить на это много времени. Чтобы засвидетельствовать его следующее воплощение, мы должны смотреть на генератор кода LLVM.
Генератор кода является одной из самых сложных частей LLVM. Его задача — «понизить» относительно высокий уровень, независимый от цели IR LLVM в низкоуровневые, зависящие от цели «машинные инструкции» (MachineInstr). На пути к MachineInstr инструкция IR LLVM проходит через воплощение «узла выбора DAG», о чем я и собираюсь поговорить далее.
Узел SelectionDAG
Узлы Selection DAG [4] создаются классом SelectionDAGBuilder, действующим «на службе» SelectionDAGISel, который является основным базовым классом для выбора инструкций. SelectionDAGIsel просматривает все инструкции IR и вызывает к ним SelectionDAGBuilder :: visit dispatcher. Метод, обрабатывающий инструкцию SDiv, — это SelectionDAGBuilder :: visitSDiv . Он запрашивает новый SDNode у DAG с кодом операции ISD :: SDIV , который становится узлом в DAG.
Исходный DAG, построенный таким образом, все еще только частично зависит от цели. В номенклатуре LLVM это называется «незаконным» — типы, которые он содержит, могут не поддерживаться непосредственно целью; то же самое верно для операций, которые это содержит.
Существует несколько способов визуализации DAG. Один из них — передать флаг -debug в llc , что приведет к созданию текстового дампа DAG на всех этапах выбора. Другой — передать один из параметров -view , который заставляет его создавать дамп и отображать фактическое изображение графика (более подробно в документах генератора кода ). Вот соответствующая часть DAG, показывающая наш узел SDiv, сразу после создания DAG (узел sdiv находится внизу):
Прежде чем механизм SelectionDAG фактически выдает машинные инструкции от узлов DAG, они подвергаются нескольким другим преобразованиям. Наиболее важными являются этапы легализации типа и операций, которые используют специфичные для цели хуки для преобразования всех операций и типов в те, которые фактически поддерживает цель.
«Легализация» разделить на sdivrem на x86
Инструкция деления (idiv для операндов со знаком) x86 вычисляет как частное, так и остаток операции и сохраняет их в двух отдельных регистрах. Поскольку выбор команд LLVM различает такие операции (называемые ISD :: SDIVREM ) и деление, которое вычисляет только частное ( ISD :: SDIV ), наш узел DAG будет «легализован» на этапе легализации DAG, когда целью является x86. Вот как это происходит.
TargetLowering — важный интерфейс, используемый генератором кода для передачи специфичной для цели информации в обычно не зависящие от цели алгоритмы. Цели реализуют этот интерфейс, чтобы описать, как инструкции LLVM IR должны быть понижены до законных операций SelectionDAG. Реализация этого интерфейса в x86 — X86TargetLowering [5] . В своем конструкторе он отмечает, какие операции нужно «расширить» легализацией операции, и ISD :: SDIV является одним из них. Вот интересный комментарий из кода:
// Scalar integer divide and remainder are lowered to use operations that // produce two results, to match the available instructions. This exposes // the two-result form to trivial CSE, which is able to combine x/y and x%y // into a single instruction.
Когда SelectionDAGLegalize :: LegalizeOp видит флаг Expand на узле SDIV [6], он заменяет его на ISD :: SDIVREM . Это интересный пример, демонстрирующий преобразование, которому может подвергаться операция в форме выбора DAG.
Выбор инструкции — от SDNode до MachineSDNode
Следующим шагом в процессе генерации кода [7] является выбор команды . LLVM предоставляет общий механизм выбора команд на основе таблиц, который генерируется автоматически с помощью TableGen. Однако многие целевые серверы предпочитают писать собственный код в своих реализациях SelectionDAGISel :: Select, чтобы обрабатывать некоторые инструкции вручную. Другие инструкции затем отправляются автоматически сгенерированному селектору, вызывая SelectCode.
Бэкэнд X86 обрабатывает ISD :: SDIVREM вручную, чтобы позаботиться о некоторых особых случаях и оптимизации. Узел DAG, созданный на этом шаге, является MachineSDNode, подклассом SDNode, который содержит информацию, необходимую для построения фактической машинной инструкции, но все еще в форме узла DAG. В этот момент выбран действительный код операции инструкции X86 — в нашем случае X86 :: IDIV32r .
Планирование и выдача MachineInstr
Код, который мы имеем на данный момент, все еще представлен как DAG. Но процессоры не выполняют DAG, они выполняют линейную последовательность инструкций. Целью этапа планирования является линеаризация группы доступности базы данных путем назначения порядка ее операциям (узлам). Простейшим подходом было бы просто отсортировать группу DAG топологически, но генератор кода LLVM использует хитрую эвристику (такую как снижение давления в регистре), чтобы попытаться создать расписание, которое приведет к более быстрому коду.
У каждой цели есть несколько хуков, которые она может реализовать, чтобы повлиять на способ планирования. Я не буду останавливаться на этой теме здесь, однако.
Наконец, планировщик выдает список инструкций в MachineBasicBlock, используя InstrEmitter :: EmitMachineNode для перевода из SDNode. Приведенные здесь инструкции принимают форму MachineInstr (далее «форма MI»), и DAG может быть уничтожена.
Мы можем проверить машинные инструкции, генерируемые на этом шаге, вызвав llc с флагом -print-machineinstrs и посмотрев на первый вывод, который говорит «После выбора инструкции»:
# After Instruction Selection:
# Machine code for function foo: SSA
Function Live Ins: %EDI in %vreg0, %ESI in %vreg1, %EDX in %vreg2
Function Live Outs: %EAX
BB#0: derived from LLVM BB %entry
Live Ins: %EDI %ESI %EDX
%vreg2<def> = COPY %EDX; GR32:%vreg2
%vreg1<def> = COPY %ESI; GR32:%vreg1
%vreg0<def> = COPY %EDI; GR32:%vreg0
%vreg3<def,tied1> = ADD32rr %vreg0<tied0>, %vreg1, %EFLAGS<imp-def,dead>; GR32:%vreg3,%vreg0,%vreg1
%EAX<def> = COPY %vreg3; GR32:%vreg3
CDQ %EAX<imp-def>, %EDX<imp-def>, %EAX<imp-use>
IDIV32r %vreg2, %EAX<imp-def>, %EDX<imp-def,dead>, %EFLAGS<imp-def,dead>, %EAX<imp-use>, %EDX<imp-use>; GR32:%vreg2
%vreg4<def> = COPY %EAX; GR32:%vreg4
%EAX<def> = COPY %vreg4; GR32:%vreg4
RET
# End machine code for function foo.
Обратите внимание, что в выходных данных упоминается, что код находится в форме SSA, и мы можем видеть, что некоторые используемые регистры являются «виртуальными» регистрами (например,% vreg1).
Распределение регистра — от SSA до машинных инструкций не-SSA
Помимо некоторых четко определенных исключений, код, сгенерированный из селектора инструкций, находится в форме SSA. В частности, предполагается, что он имеет бесконечный набор «виртуальных» регистров, с которыми можно работать. Это, конечно, не правда. Поэтому следующим шагом генератора кода является вызов «распределителя регистров», задачей которого является замена виртуальных на физические регистры, из целевого банка регистров.
Упомянутые выше исключения также важны и интересны, поэтому давайте поговорим о них немного подробнее.
Некоторые инструкции в некоторых архитектурах требуют фиксированных регистров. Хорошим примером является наша инструкция деления в x86, которая требует, чтобы ее входы были в регистрах EDX и EAX. Селектор команд знает об этих ограничениях, поэтому, как видно из кода выше, входные данные для IDIV32r являются физическими, а не виртуальными регистрами. Это назначение выполняется X86DAGToDAGISel :: Select .
Распределитель регистров заботится обо всех нефиксированных регистрах. Есть еще несколько шагов оптимизации (и расширения псевдоинструкций), которые выполняются в машинных инструкциях в форме SSA, но я собираюсь пропустить их. Точно так же я не буду обсуждать шаги, выполняемые после распределения регистров, поскольку они не меняют основные операции с формами, которые появляются в (MachineInstr, на данный момент). Если вам интересно, взгляните на TargetPassConfig :: addMachinePasses .
Испуская код
Итак, теперь у нас есть исходная функция C, переведенная в форму MI — MachineFunction, заполненная объектами инструкций (MachineInstr). Это тот момент, когда генератор кода завершил свою работу, и мы можем испустить код. В текущем LLVM есть два способа сделать это. Одним из них является (унаследованный) JIT, который испускает исполняемый, готовый к запуску код непосредственно в память. Другой — MC, который является амбициозной структурой объектных файлов и сборок, которая была частью LLVM в течение нескольких лет, заменив предыдущий генератор сборок. MC в настоящее время используется для сборки и передачи объектного файла для всех (или, по крайней мере, важных) целей LLVM. MC также включает «MCJIT», который является структурой JIT-ting на основе уровня MC. Вот почему я имею в виду модуль JIT LLVM как устаревший.
Сначала я скажу несколько слов о прежнем JIT, а затем обратимся к MC, что более интересно для всех.
Последовательность передач в код JIT- emit определяется с помощью LLVMTargetMachine :: addPassesToEmitMachineCode . Он вызывает addPassesToGenerateCode, который определяет все проходы, необходимые для выполнения того, о чем говорилось в большей части этой статьи до сих пор — превращение IR в форму MI. Затем он вызывает addCodeEmitter, который является целевым проходом для преобразования MI в реальный машинный код. Поскольку MI уже очень низкого уровня, довольно просто перевести их в работающий машинный код [8] . Код x86 для этого находится в lib / Target / X86 / X86CodeEmitter.cpp. Для нашей инструкции деления здесь нет особой обработки, потому что MachineInstr, в который он упакован, уже содержит свой код операции и операнды. Он обрабатывается в общем с другими инструкциями в emitInstruction.
MCInst
Когда LLVM используется в качестве статического компилятора (например, как часть clang), MI передаются на уровень MC, который обрабатывает эмиссию объектного файла (он также может генерировать файлы текстовой сборки). Многое можно сказать о MC, но для этого потребуется собственная статья. Хорошая ссылка на этот пост из блога LLVM . Я продолжу сосредотачиваться на пути, взятом единственной инструкцией.
LLVMTargetMachine :: addPassesToEmitFile отвечает за определение последовательности действий, необходимых для создания объектного файла. Фактическая трансляция MI-MCInst выполняется в EmitInstruction интерфейса AsmPrinter. Для x86 этот метод реализован с помощью X86AsmPrinter :: EmitInstruction , который делегирует работу классу X86MCInstLower. Как и в случае с JIT, здесь нет специальной обработки для нашей инструкции деления, и она обычно обрабатывается другими инструкциями.
Пропустив -show-MC-инст в ооо, мы можем увидеть инструкции MC уровня , которые он создает, наряду с фактическим кодом сборки:
foo: # @foo
# BB#0: # %entry
movl %edx, %ecx # <MCInst #1483 MOV32rr
# <MCOperand Reg:46>
# <MCOperand Reg:48>>
leal (%rdi,%rsi), %eax # <MCInst #1096 LEA64_32r
# <MCOperand Reg:43>
# <MCOperand Reg:110>
# <MCOperand Imm:1>
# <MCOperand Reg:114>
# <MCOperand Imm:0>
# <MCOperand Reg:0>>
cltd # <MCInst #352 CDQ>
idivl %ecx # <MCInst #841 IDIV32r
# <MCOperand Reg:46>>
ret # <MCInst #2227 RET>
.Ltmp0:
.size foo, .Ltmp0-foo
Передача объектного файла (или кода сборки) осуществляется посредством реализации интерфейса MCStreamer. Объектные файлы испускаются MCObjectStreamer, который далее разделяется на подклассы в соответствии с фактическим форматом объектного файла. Например, эмиссия ELF реализована в MCELFStreamer. Примерный путь, по которому MCInst проходит через стримеры: MCObjectStreamer :: EmitInstructionсопровождаемый специфичным для формата EmitInstToData. Окончательный вариант инструкции в двоичном виде, конечно же, зависит от цели. Он обрабатывается интерфейсом MCCodeEmitter (например, X86MCCodeEmitter). В то время как в остальной части кода LLVM часто бывает сложно, потому что он должен разделять независимые от цели и специфичные для цели возможности, MC является еще более сложной задачей, поскольку добавляет еще одно измерение — другие форматы объектных файлов. Таким образом, некоторый код является полностью общим, некоторый код зависит от формата, а некоторый код зависит от цели.
Ассемблеры и дизассемблеры
MCInst — намеренно очень простое представление. Он пытается сбросить как можно больше семантической информации, сохраняя только код операции инструкции и список операндов (и местоположение источника для диагностики ассемблера). Как и LLVM IR, это внутреннее представление с несколькими возможными кодировками. Двумя наиболее очевидными являются сборочные (как показано выше) и двоичные объектные файлы.
llvm-mc — это инструмент, использующий инфраструктуру MC для реализации ассемблеров и дизассемблеров. Внутренне MCInst — это представление, используемое для перевода между двоичной и текстовой формами. На данный момент инструменту все равно, какой компилятор создал файл сборки / объект.
| [1] | Чтобы проверить AST, созданный Clang, скомпилируйте исходный файл с опциями -cc1 -ast-dump . |
| [2] | Я запустил этот ИК через opt -mem2reg | llvm-dis для очистки разливов. |
| [3] | Эти вещи немного сложны для понимания из-за некоторого взлома препроцессора C, используемого LLVM для минимизации дублирования кода. Посмотрите файл include / llvm / Instruction.def и его использование в различных местах в источнике LLVM для получения дополнительной информации. |
| [4] | Под DAG здесь подразумевается направленный ациклический граф, представляющий собой структуру данных, которую генератор кода LLVM использует для представления различных операций со значениями, которые они производят и потребляют. |
| [5] | Это, пожалуй, самый страшный кусок кода в LLVM. |
| [6] | Это пример того, как специфичная для цели информация абстрагируется для управления алгоритмом генерации кода, независимого от цели. |
| [7] | Генератор кода выполняет оптимизацию DAG между основными этапами, такими как легализация и выбор. Об этих оптимизациях важно и интересно знать, но, поскольку они действуют и возвращают выбранные узлы DAG, они не рассматриваются в этой статье. |
| [8] | Когда я говорю «машинный код» в этой точке, я имею в виду фактические байты в буфере, представляющие закодированные инструкции, которые может выполнять процессор. JIT направляет ЦП на выполнение кода из этого буфера после завершения эмиссии. |
Похожие сообщения:
- жизнь Юдковского: трансгуманизм, сингулярность
- Рецензия на книгу: «Искусственная жизнь» Стивена Леви
- Рецензия на книгу С. Шнабля «Мужчина и женщина — интимная жизнь»
- Рецензия на книгу: «Жизнь Пи» Яна Мартеля
- SICP раздел 5.2