В данной статье рассмотрена стратегия и этапы проектирования бэкенд части компилятора с использованием инфраструктуры LLVM для целевой архитектуры ShuraCore. В статье показаны все этапы прохождения LLVM IR кода в SSA представлении к моменту получения исполняемого файла для целевой архитектуры.
This article discusses a strategy and design stages of a backend part of a compiler using LLVM infrastructure for the ShuraCore target architecture. The article shows all stages of passing LLVM IR code in SSA representation by the time the executable file is received for the target architecture.
Введение. Инфраструктуры компиляторов часто представляют собой большую сферу академических и практических исследований, сферу, к которой проявляется большой интерес. По мере развития цифровой информатизации и информационных технологий растет потребность в увеличении производительности цифрового оборудования. Основным компонентом в большинстве сложных цифровых систем является центральный процессор или центральное процессорное устройство. Компиляторы отвечают за создание кода для целевой архитектуры или кода сборки, который можно преобразовать в объектный код и выполнить на реальном оборудовании. Конечная цель компилятора — создать исполняемый код для целевой архитектуры, который можно выполнить на реальном оборудовании. Чтобы сгенерировать ассемблерный код компилятору необходимо знать различные аспекты целевой архитектуры — регистры, набор команд, соглашение о вызовах, конвейер и т. д. На этом этапе также можно выполнить множество оптимизаций. Сегодня для создания компилятора целевой архитектуры все чаще используется LLVM [1]. LLVM имеет свой собственный способ определения целевой архитектуры. Он использует tablegen для указания целевых регистров, инструкций, соглашения о вызовах и так далее. Функции tablegen облегчают механизм, которым описывается большой набор свойств архитектуры. LLVM имеет структуру конвейера для бэкенда, где инструкции проходят через следующие фазы: из IR LLVM в SelectionDAG, затем в MachineDAG, затем в MachineInstr и, наконец, в MCInst. IR преобразуется в SelectionDAG (DAG означает направленный ациклический граф). Затем происходит легализация (оформление) SelectionDAG, где на разрешенных операциях, разрешенных целевой архитектуре, отображаются недопустимые инструкции. После этого этапа SelectionDAG преобразуется в MachineDAG, который в основном является набором инструкций, поддерживаемых бэкендом. Процессоры выполняют линейную последовательность инструкций. Генератор кода LLVM использует умную эвристику (такую как снижение нагрузки на регистры), чтобы попытаться создать планирование, которое приведет к более быстрому коду. Политика распределения регистров также играет важную роль в создании лучшего кода LLVM. Современные компиляторы обычно работают в трех основных фазах: фронтенд, оптимизатор и бэкенд. Существует два основных подхода, как компиляторы должны выполнить эту задачу: подход Ахо-Ульмана [2] и подход Дэвидсона-Фрейзера. Модель Ахо-Ульмана уделяет большое внимание использованию целевого языка промежуточного представления (intermediate representation — IR) для основной части оптимизации перед бэкенд частью, что позволяет процессу выбора инструкций использовать подход, основанный на затратах. Модель Дэвидсона-Фрейзера направлена на преобразование IR в целевой независимый тип «регистр языка перевода» (язык перевода (RTL) не следует путать с абстракцией дизайна уровня передачи регистров (RTL), используемой для проектирования цифровой логики). RTL затем проходит процесс расширения с последующим распознавателем, который выбирает инструкции на основе расширенного представления. Наибольший интерес при разработке компилятора для целевой архитектуры представляет собой LLVM бэкенд.
Основная часть.
Проектирование LLVM бэкенда начинается с определения наборов регистров, а также с описания специализированных регистров и иной информации о целевой архитектуре. Данная процедура выполняется с помощью tablegen. Tablegen необходим для написания абстракции целевой архитектуры. Этот инструмент преобразует целевой файл описания (.td) в C++ код, который используется затем при генерации кода. Его основная цель состоит в том, чтобы свести большие, утомительные описания к более мелким и гибким определениям, которыми легче управлять и легче структурировать. Функция tablegen обрабатывает файлы .td для генерации файлов .inc, которые, как правило, имеют перечисления, сгенерированные для регистров. Эти перечисления могут использоваться в файлах .cpp, в которых можно ссылаться на регистры целевой архитектуры. Файлы .inc будут сгенерированы, когда будет собираться проект LLVM для целевой архитектуры.
ShuraCoreRegisterInfo.td
//===----------------------------------------------------------------------===//
// Declarations that describe the ShuraCore register file
//===----------------------------------------------------------------------===//
class ShuraCoreReg<bits<16> Enc, string n> : Register<n> {
let HWEncoding = Enc;
let Namespace = "ShuraCore";
}
// CPU registers
def R0 : ShuraCoreReg< 0, "R0">;
def R1 : ShuraCoreReg< 1, "R1">;
def R2 : ShuraCoreReg< 2, "R2">;
def R3 : ShuraCoreReg< 3, "R3">;
def R4 : ShuraCoreReg< 4, "R4">;
def R5 : ShuraCoreReg< 5, "R5">;
def R6 : ShuraCoreReg< 6, "R6">;
def R7 : ShuraCoreReg< 7, "R7">;
def R8 : ShuraCoreReg< 8, "R8">;
def R9 : ShuraCoreReg< 9, "R9">;
def R10 : ShuraCoreReg< 10, "R10">;
def R11 : ShuraCoreReg< 11, "R11">;
def STACK_POINTER : ShuraCoreReg<12, "STACK_POINTER">;
def PROGRAMM_COUNTER : ShuraCoreReg<13, "PROGRAMM_COUNTER">;
def RETURN_ADDRESS : ShuraCoreReg<14, "RETURN_ADDRESS">;
def EXCEPTION : ShuraCoreReg<15, "EXCEPTION">;
....
Следующим важным моментом LLVM бэкенда является определение соглашения о вызовах. Определение соглашения о вызовах описывает часть ABI, которая управляет перемещением данных между вызовами функций и определяет, как значения передаются в/из функции при вызове самой функции. Этот этап показывает, как определить соглашение о вызовах, которое будет использоваться в ISelLowering (фаза понижения выбора команд) с помощью указателей функций. В tablegen будет указано, что возвращаемые значения целочисленного типа 32 бита хранятся в неком регистре или в некоторых регистрах. Всякий раз, когда аргументы передаются в функцию, первые 6 аргументов сохраняются в регистрах. Также указывается, что всякий раз, когда будет встречаться любой тип данных, такой как целое число 8 бит или 16 бит, он будет повышен до 32-битного целого типа. Функция tablegen генерирует файл ShuraCoreCallingConv.inc, который будет указан в файле ShuraCoreISelLowering.cpp.
После описания соглашения о вызове, необходимо определить набор команд целевой архитектуры и описать их. Набор команд архитектуры варьируется в зависимости от различных функций, присутствующих в архитектуре. В файле описания целевого объекта архитектуры для инструкции определены три вещи: операнд, строка сборки и шаблон инструкции. Спецификация содержит список определений или выходов, а также список применений или входов. Могут существовать различные классы операндов, такие как класс Register, а также непосредственные и более сложные операнды.
Закончив с описанием набора команд целевой архитектуры, необходимо реализовать понижение кадра. Когда функция понижения кадра выполняется, она получает некоторое количество пространства в стеке для хранения переменных стека и регистры, а также сохраненные вызываемым пользователем объекты. Понижение кадра стека — это процесс вычисления объема пространства и макета, необходимого для сохранения, а затем выполнения необходимых машинных инструкций в прологе и эпилоге (начале и конце) функции. Когда на переменные в стеке ссылаются перед шагом вставки пролога-эпилога (PEI), они адресуются с помощью «индексов фреймов», произвольного имени для местоположения, которое в конечном итоге разрешит относительное смещение указателя стека. При этом необходимо учитывать, что PEI происходит довольно поздно (после выделения регистра). Для понижения кадра необходимо определить две функции, а именно ShuraCoreFrameLowering::emitPrologue() и ShuraCoreFrameLowering::emitEpilogue(). Функция emitPrologue сначала вычисляет размер стека, чтобы определить, требуется ли пролог вообще. Затем корректируется указатель стека, вычисляя смещение. Для эпилога сначала проверяется, требуется ли эпилог или нет. После чего восстанавливается указатель стека до того, что было в начале функции.
После данного этапа необходимо описать механизм формирования вывода инструкций.
Следующим шагом этого процесса является создание SelectionDAG из входных данных. SelectionDAG считается недопустимым, если он содержит инструкции или операнды, которые не могут быть представлены в целевой архитектуре. Преобразование из LLVM IR в начальный SelectionDAG является жестко закодированным и законченным фреймворком генератора кода. IR-инструкция в DAG должна быть понижена до целевой инструкции. Узел SelectionDAG содержит IR, который необходимо сопоставить с узлами DAG, специфичными для архитектуры. Результат этапа выбора готов к планированию. Для выбора аппаратно-зависимой инструкции необходимо определить отдельный класс ShuraCoreDAGToDAGISel. Самая важный метод для определения в этом классе — функция Select(), которая будет возвращать объект SDNode, специфичный для аппаратной инструкции. Функция ShuraCoreDAGToDAGISel::Select() файла ShuraCoreISelDAGToDAG.cpp используется для выбора узла DAG OP кода, а ShuraCoreDAGToDAGISel::SelectAddr() используется для выбора узла DAG DATA с типом addr. Если тип и вид инструкции определяется конкретными битовыми полями в 32 битном слове, то можно использовать битовое поле в файле .td при определении инструкции. Целевая архитектура может иметь подзадачу — как правило, вариант с инструкциями — способ обработки операндов, среди прочих инструкций. Функция подзадачи может поддерживаться в бэкенде LLVM. Подзадача может содержать некоторые дополнительные инструкции, регистры, модели планирования и т.д. У ARM есть подзадачи, такие как NEON и THUMB, в то время как у x86 есть функции подзадач, такие как SSE, AVX и так далее. Набор команд отличается для функции подзадачи, например, NEON для ARM и SSE/AVX для функций подзадачи, которые поддерживают векторные инструкции. SSE и AVX также поддерживают набор векторных команд, но их инструкции отличаются друг от друга.
Следующая фаза – фаза планирования. Планирование отвечает за преобразование DAG инструкций для платформы в список машинных инструкций (представленных экземплярами класса MachineInstr). Планировщик может упорядочить инструкции в зависимости от ограничений, таких как минимизация использования регистров или уменьшение общей задержки исполняемой программы. Как только список машинных инструкций финализирован, DAG завершается.
Заключительный этап – это этап создания кода. Задача заключительного этапа бэкенда – сформировать список машинных инструкций с помощью ассемблера (получить объектный файл для платформы). Ассемблер сборки кода требует реализации нескольких пользовательских классов. Класс ShuraCoreAsmPrinter представляет подход, который позволяет формировать ассемблерный код. Класс ShuraCoreMCAsmInfo определяет некоторую базовую статическую информацию для ассемблера. Пользовательский машинный код создается в виде объектного файла ELF. Как и в случае с ассемблером, для создания машинного кода необходимо реализовать несколько пользовательских классов. Класс ShuraCoreELFObjectWriter в основном служит оболочкой для своего базового класса, а MCELFObjectTargetWriter отвечает за правильное форматирование файла ELF. Класс ShruaCoreMCCodeEmitter содержит большинство важных функций для выдачи машинного кода. Он импортирует код C++, который автоматически генерируется из эмиттера кода TableGen бэкенда. Этот бэкенд обрабатывает большую часть битового сдвига и форматирования, необходимого для кодирования инструкций. Класс ShruaCoreMCCodeEmitter также отвечает за кодирование пользовательских операндов.
Заключение.
Инфраструктура LLVM позволяет с большой легкостью реализовать бэкенд компилятора для целевой архитектуры. LLVM является той инфраструктурой, которая необходима как базовая вещь для стратегии проектирования и создания компиляторов для целевых архитектур. При этом не будет необходимости написания и реализации фронтенд части компиляторов.
Литература.
-
The LLVM Compiler Infrastructure. https://LLVM.org/
-
Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии, инструменты. 2-е изд. Издательство: Вильямс, 2018. 1184 с.