На данный момент LLVM стала уже очень популярной системой, которую многие активно используют для создания различных компиляторов, анализаторов и т.п. Уже написано большое количество полезных материалов по данной тематике, в том числе и на русском языке, что не может не радовать. Однако в большинстве случаев основной уклон в статьях сделан на frontend и middleend LLVM. Конечно, при описании полной схемы работы LLVM генерация машинного кода не обходится стороной, но в основном данной темы касаются вскользь, особенно в публикациях на русском языке. А при этом у LLVM достаточно гибкий и интересный механизм описания архитектур процессоров. Поэтому данный материал будет посвящен несколько обделенной вниманием утилите TableGen, входящей в состав LLVM.

Причина, по которой компилятору необходимо иметь информацию об архитектуре каждой из целевых платформ вполне очевидна. Естественно, у каждой модели процессора свой набор регистров, свои машинные инструкции и т.д. И компилятору нужно иметь всю необходимую информацию о них, чтобы быть в состоянии генерировать валидный и эффективный машинный код. Компилятор решает различные платформенно-зависимые задачи: производит распределение регистров и т.д. К тому же в бэкендах LLVM также проводятся оптимизации уже на машинном IR, который больше приближен к реальным инструкциям, или же на самих ассемблерных командах. В подобных оптимизациях нужно заменять и преобразовывать инструкции, соответственно вся информация о них должна быть доступна.

Для решения задачи описания архитектуры процессора в LLVM принят единый формат определения необходимых для компилятора свойств процессора. Для каждой поддерживаемой архитектуры в файлах формата .td хранится описание на специальном формальном языке. Оно преобразуется в файлы формата .inc при построении компилятора с помощью утилиты TableGen, входящей в состав LLVM. Результирующие файлы, по сути, являются исходниками на языке C, но имеют отдельное расширение, скорее всего, просто для того, чтобы эти автоматически сгенерированные файлы было легко отличить и отфильтровать. Официальная документация по TableGen находится здесь и дает всю необходимую информацию, также существует формальное описание языка и общее введение.

Конечно, это очень обширная тема, где много деталей, о которых можно писать отдельные статьи. В этом материале мы просто рассмотрим базовые моменты описания процессоров даже без обзора всех возможностей.

Описание архитектуры в .td файле

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

Современные процессоры — это очень сложные системы, поэтому неудивительно, что их описание получается достаточно объемным. Соответственно, для создания структуры и упрощения поддерживаемости .td файлы могут включать друг друга с помощью привычной для C программистов директивы #include. С помощью данной директивы в первую очередь всегда включается файл Target.td, содержащий платформенно независимые интерфейсы, которые должны быть реализованы для предоставления всей необходимой информации TableGen. Данный файл уже в себя включает .td файл с описаниями LLVM интринсиков, сам по себе же он в основном содержит базовые классы, такие как Register, Instruction, Processor и т.д., от которых необходимо наследоваться для создания своей архитектуры для компилятора на базе LLVM. Из предыдущего предложения, понятно, что в языке TableGen присутствует хорошо известное всем программистам понятие классов.

Вообще в TableGen есть всего две базовые сущности: классы и определения (definitions).

Классы

TableGen классы — это тоже абстракции, как во всех объектно-ориентированных языках программирования, но это более простые сущности.

У классов могут быть параметры и поля, а также они могут наследовать другие классы.
Например, один из базовых классов представлен ниже.

// A class representing the register size, spill size and spill alignment
// in bits of a register.
class RegInfo<int RS, int SS, int SA> {
  int RegSize = RS;         // Register size in bits.
  int SpillSize = SS;       // Spill slot size in bits.
  int SpillAlignment = SA;  // Spill slot alignment in bits.
}

В угловых скобках указаны входные параметры, которые присваиваются свойствам класса. Из данного примера, можно также заметить, что язык TableGen является статически типизированным. Типы, существующие в TableGen: bit (аналог булевого типа со значениями 0 и 1), int, string, code (фрагмент кода, это тип, просто потому что в TableGen отсутствуют методы и функции в привычном понимании, строки кода записываются в [{ ... }]), bits<n>, list<type> (значения задаются с помощью квадратных скобок [...] как в Python и некоторых других языках программирования), class type, dag.

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

Наследование описывается тоже достаточно привычным синтаксисом с помощью :.

class X86MemOperand<string printMethod,
          AsmOperandClass parserMatchClass = X86MemAsmOperand> : Operand<iPTR> {
    let PrintMethod = printMethod;
    let MIOperandInfo = (ops ptr_rc, i8imm, ptr_rc_nosp, i32imm, SEGMENT_REG);
    let ParserMatchClass = parserMatchClass;
    let OperandType = "OPERAND_MEMORY";
}

При этом создаваемый класс, естественно, может переопределить значения полей, заданных в базовом классе с использованием ключевого слова let. И может добавить собственные поля аналогично представленному в предыдущем примере описанию, указав тип поля.

Определения (definitions)

Определения — это уже конкретные сущности, можно сравнить их с привычными всем объектами. Определения задаются при помощи ключевого слова def и могут реализовывать класс, переопределять поля базовых классов абсолютно тем же способом, что был описан выше, а также и иметь свои собственные поля.

def i8mem   : X86MemOperand<"printbytemem",   X86Mem8AsmOperand>;

def X86AbsMemAsmOperand : AsmOperandClass {
    let Name = "AbsMem";
    let SuperClasses = [X86MemAsmOperand];
}

Мультиклассы (multiclasses)

Естественно, большое количество инструкций в процессорах имеет схожую семантику. Например, может быть набор трехадресных инструкций, которые имеют две формы “reg = reg op reg” и “reg = reg op imm”. В одном случае берутся значения из регистров и результат сохраняется также в регистр, а в другом случае второй операнд — это константное значение (imm — immediate operand).

Перечислять все комбинации вручную достаточно утомительно, повышается риск совершить ошибку. Их, конечно, можно сгенерировать автоматически, написав простенький скрипт, но это не нужно, потому что существует в языке TableGen такое понятие как мультиклассы.

multiclass ri_inst<int opc, string asmstr> {
     def _rr : inst<opc, !strconcat(asmstr, " $dst, $src1, $src2"),
                 (ops GPR:$dst, GPR:$src1, GPR:$src2)>;
     def _ri : inst<opc, !strconcat(asmstr, " $dst, $src1, $src2"),
                 (ops GPR:$dst, GPR:$src1, Imm:$src2)>;
}

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

// Instantiations of the ri_inst multiclass.
defm ADD : ri_inst<0b111, "add">;
defm SUB : ri_inst<0b101, "sub">;
defm MUL : ri_inst<0b100, "mul">;

И в результате для каждого такого определения, заданного через defm будет сконструировано на самом деле несколько определений, являющихся комбинацией основной инструкции и всех возможных форм, описанных в мультиклассе. В результате в данном примере будут сгенерированы следующие инструкции: ADD_rr, ADD_ri, SUB_rr, SUB_ri, MUL_rr, MUL_ri.

Мультиклассы могут содержать в себе не только определения с def, но и вложенные defm, тем самым, позволяя генерировать сложные формы инструкций. Пример, иллюстрирующий создание таких цепочек, можно найти в официальной документации.

Subtargets

Еще одной базовой и полезной вещью для процессоров, у которых существуют различные вариации набора инструкций, является поддержка subtargetов в LLVM. В качестве примера использования можно привести реализацию LLVM SPARC, которая покрывает сразу три основных версии архитектуры микропроцессоров SPARC: Version 8 (V8, 32-бит архитектура), Version 9 (V9, 64-бит архитектура) и архитектура UltraSPARC. Разница у архитектур достаточно большая, разное количество регистров разного типа, поддерживаемый порядок байт и т.д. В подобных случаях при наличии нескольких конфигураций, стоит реализовать XXXSubtarget класс для архитектуры. Использование данного класса при описании приведет к появление новых опций командной строки -mcpu= и -mattr=.

Помимо самого класса Subtarget важным является класс SubtargetFeature.

class SubtargetFeature<string n, string a, string v, string d,
                       list<SubtargetFeature> i = []> {
    string Name = n;
    string Attribute = a;
    string Value = v;
    string Desc = d;
    list<SubtargetFeature> Implies = i;
}

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

def FeatureV9 : SubtargetFeature<"v9", "IsV9", "true",
                     "Enable SPARC-V9 instructions">;
def FeatureV8Deprecated : SubtargetFeature<"deprecated-v8",
                     "V8DeprecatedInsts", "true",
                     "Enable deprecated V8 instructions in V9 mode">;
def FeatureVIS : SubtargetFeature<"vis", "IsVIS", "true",
                     "Enable UltraSPARC Visual Instruction Set extensions">;

При этом все равно в Sparc.td еще определен класс Proc, который используется для описания конкретных подтипов процессоров SPARC, которые как раз могут иметь описанные выше свойства, включающие разные наборы инструкций.

class Proc<string Name, list<SubtargetFeature> Features>
  : Processor<Name, NoItineraries, Features>;

def : Proc<"generic",         []>;
def : Proc<"v8",              []>;
def : Proc<"supersparc",      []>;
def : Proc<"sparclite",       []>;
def : Proc<"f934",            []>;
def : Proc<"hypersparc",      []>;
def : Proc<"sparclite86x",    []>;
def : Proc<"sparclet",        []>;
def : Proc<"tsc701",          []>;
def : Proc<"v9",              [FeatureV9]>;
def : Proc<"ultrasparc",      [FeatureV9, FeatureV8Deprecated]>;
def : Proc<"ultrasparc3",     [FeatureV9, FeatureV8Deprecated]>;
def : Proc<"ultrasparc3-vis", [FeatureV9, FeatureV8Deprecated, FeatureVIS]>;

Связь между свойствами инструкций в TableGen и коде бэкенда LLVM

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

TSFlags

Для этого в базовом классе Instruction есть специальное поле TSFlags, размером в 64 бита, которое преобразуется TableGenом в поле объектов C++ класса MCInstrDesc, генерируемых на основе данных полученных из TableGen описания. Можно указывать любое количество битов, которое нужно для сохранения информации. Это может быть некоторое булевое значение, например для указания, что пользуемся скалярным ALU.

let TSFlags{0} = SALU;

Или мы можем хранить тип инструкции. Тогда нам нужно, естественно, больше одного бита.

// Instruction type according to the ISA.
IType Type = type;
let TSFlags{7-1} = Type.Value;

В результате в коде бэкенда появляется возможность получить эти свойства у инструкции.

bool isSALU = MI.getDesc().TSFlags & SIInstrFlags::SALU;

Если свойство более сложное, то можно сравнить со значением, описанным в TableGen, которое будет добавлено в автосгенерированное перечисление.

(Desc.TSFlags & X86II::FormMask) == X86II::MRMSrcMem

Предикаты функций

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

// Base class for function predicates.
class FunctionPredicateBase<string name, MCStatement body> {
    string FunctionName = name;
    MCStatement Body = body;
}

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

// Check that a call to method `Name` in class "XXXInstrInfo" (where XXX is
// the name of a target) returns true.
//
// TIIPredicate definitions are used to model calls to the target-specific
// InstrInfo. A TIIPredicate is treated specially by the InstrInfoEmitter
// tablegen backend, which will use it to automatically generate a definition in
// the target specific `InstrInfo` class.
//
// There cannot be multiple TIIPredicate definitions with the same name for the
// same target
class TIIPredicate<string Name, MCStatement body>
    : FunctionPredicateBase<Name, body>, MCInstPredicate;

// This predicate evaluates to true only if the input machine instruction is a
// 3-operands LEA.  Tablegen automatically generates a new method for it in
// X86GenInstrInfo.
def IsThreeOperandsLEAFn :
    TIIPredicate<"isThreeOperandsLEA", IsThreeOperandsLEABody>; // первый операнд - имя результирующей сгенерированной функции, второй - тело функции, в качестве которого передается следующее определение 
// Used to generate the body of a TII member function.
def IsThreeOperandsLEABody :
    MCOpcodeSwitchStatement<[LEACases], MCReturnStatement<FalsePred>>;

В итоге можно использовать метод isThreeOperandsLEA в C++ коде.

if (!(TII->isThreeOperandsLEA(MI) || hasInefficientLEABaseReg(Base, Index)) ||
      !TII->isSafeToClobberEFLAGS(MBB, MI) ||
      Segment.getReg() != X86::NoRegister)
    return;

Здесь TII — это target instruction info, которое может быть получено с помощью метода getInstrInfo() у наследника MCSubtargetInfo для нужной архитектуры.

Преобразования инструкций во время оптимизаций. Instruction Mapping

Во время большого количества оптимизаций, выполняемых на поздних этапах компиляции, очень часто возникает задача преобразовывать все или только часть инструкций одной формы в инструкции другой формы. С учетом применения описанных в начале мультиклассов у нас может быть большое количество инструкций со схожей семантикой и свойствами. В коде эти преобразования, конечно, можно было бы писать в виде больших switch-case конструкций, которые для каждой инструкции задавили соответствующую ей в преобразовании. Частично эти огромные конструкции можно сокращать с помощью макросов, которые бы по известным правилам формировали нужное имя инструкции. Но все равно такой подход очень неудобен, его сложно поддерживать из-за того, что все имена инструкций перечислены в явном виде. Добавление новой инструкции очень легко может привести к ошибке, т.к. нужно не забыть ее добавить во все релевантные преобразования. Намучившись с таким подходом, в LLVM создали специальный механизм для произведения эффективного преобразования одной формы инструкции в другую Instruction Mapping.

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

class InstrMapping {
  // Used to reduce search space only to the instructions using this
  // relation model.
  string FilterClass;

  // List of fields/attributes that should be same for all the instructions in
  // a row of the relation table. Think of this as a set of properties shared
  // by all the instructions related by this relationship.
  list<string> RowFields = [];

  // List of fields/attributes that are same for all the instructions
  // in a column of the relation table.
  list<string> ColFields = [];

  // Values for the fields/attributes listed in 'ColFields' corresponding to
  // the key instruction. This is the instruction that will be transformed
  // using this relation model.
  list<string> KeyCol = [];

  // List of values for the fields/attributes listed in 'ColFields', one for
  // each column in the relation table. These are the instructions a key
  // instruction will be transformed into.
  list<list<string> > ValueCols = [];
}

Давайте рассмотрим пример, который приведен в документации. Примеры, которые можно найти в исходном коде сейчас еще проще, так как в итоговой таблице получается лишь две колонки. В коде бэкендов можно найти преобразование старых форм в новые формы инструкций, dsp инструкций в mmdsp и т.д., описанных с помощью Instruction Mapping. На самом деле пока этот механизм не так широко применяется, просто потому что большинство бэкендов начали создаваться раньше, чем он появился, а для того, чтобы он работал нужно еще задать инструкциям правильные свойства, так что перейти на него не всегда просто, может понадобиться некоторый рефакторинг.

Итак, к самому примеру. Допустим, у нас есть формы инструкций без предикатов и инструкции, где предикат соответственно истенен и ложен. Описываем, мы их с помощью мультикласса и специального класса, который как раз будем использовать в качестве фильтра. Упрощенное описание без параметров и множества свойств у нас может быть примерно таким.

class PredRel;
multiclass MyInstruction<string name> {
    let BaseOpcode = name in {
        def : PredRel {
            let PredSense = "";
        }
        def _pt: PredRel {
            let PredSense = "true";
        }
        def _pf: PredRel {
             let PredSense = "false";
        }
    }
} 
defm ADD: MyInstruction<”ADD”>;
defm SUB: MyIntruction<”SUB”>;
defm MUL: MyInstruction<”MUL”>;
…

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

def getPredOpcode : InstrMapping {
  // Показываем, что в преобразовании могут участвовать только инструкции-наследники PredRel класса
  let FilterClass = "PredRel";

  // В каждой строке таблицы преобразований у нас будут инструкции, у которых одинаковое базовое имя   
  let RowFields = ["BaseOpcode"];

  // А колонки у нас будут сформированы по значению свойства PredSense.
  let ColFields = ["PredSense"];

  // Первой колонкой, содержащей инструкции, которые мы можем преобразовать в другую форму, будут инструкции у которых PredSense=””
  let KeyCol = [""];

  // Задаем значение PredSense для других колонок таблицы преобразования
  let ValueCols = [["true"], ["false"]];
}

В результате, по такому описанию будет сформирована следующая таблица.


А в .inc файле будет сгенерирована функция

int getPredOpcode(uint16_t Opcode, enum PredSense inPredSense)

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

И в коде бэкенда вместо написания switch-case достаточно просто вызвать сгенерированную функцию, которая вернет код преобразованной инструкции. Простое решение, где добавление новых инструкций, не приведет к необходимости дополнительных действий.

Автогенерируемые артефакты (.inc файлы)

Все взаимодействие между TableGen описанием и кодом бэкенда LLVM обеспечивается благодаря генерируемым .inc файлам, которые содержат C код. Для получения целостной картины немного посмотрим, что именно они из себя представляют.

Для каждой архитектуры после построения в build директории будут находится несколько .inc файлов, каждый из которых хранит отдельные части информации об архитектуре. Так есть файл <TargetName>GenInstrInfo.inc, содержащий информацию об инструкциях, <TargetName>GenRegisterInfo.inc, соответственно хранящий информацию о регистрах, есть файлы для непосредственной работы с ассемблером и его вывода <TargetName>GenAsmMatcher.inc и <TargetName>GenAsmWriter.inc и т.д.

Так из чего состоят эти файлы? В общем случае они содержат перечисления, массивы, структуры и простые функции. Для примера можно посмотреть на преобразованную информацию об инструкциях в <TargetName>GenInstrInfo.inc.

В первой части в namespace с именем таргета находится перечисление, содержащее все инструкции, которые были описаны.

namespace X86 {
  enum {
    PHI	= 0,
…
ADD16i16	= 287,
    ADD16mi	= 288,
    ADD16mi8	= 289,
    ADD16mr	= 290,
    ADD16ri	= 291,
    ADD16ri8	= 292,
    ADD16rm	= 293,
    ADD16rr	= 294,
    ADD16rr_REV	= 295,
…
}

Дальше располагается массив с описанием свойств инструкций const MCInstrDesc X86Insts[]. Следующие массивы содержат информацию об именах инструкций и т.д. В основном, вся информация хранится в перечислениях и массивах.

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

bool X86InstrInfo::isThreeOperandsLEA(const MachineInstr &MI) {
  switch(MI.getOpcode()) {
  case X86::LEA32r:
  case X86::LEA64r:
  case X86::LEA64_32r:
  case X86::LEA16r:
    return (
      MI.getOperand(1).isReg() 
      && MI.getOperand(1).getReg() != 0
      && MI.getOperand(3).isReg() 
      && MI.getOperand(3).getReg() != 0
      && (
        (
          MI.getOperand(4).isImm() 
          && MI.getOperand(4).getImm() != 0
        )
        || (MI.getOperand(4).isGlobal())
      )
    );
  default:
    return false;
  } // end of switch-stmt
}

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

struct X86GenMCSubtargetInfo : public MCSubtargetInfo {
  X86GenMCSubtargetInfo(const Triple &TT, 
    StringRef CPU, StringRef FS, ArrayRef<SubtargetFeatureKV> PF,
    ArrayRef<SubtargetSubTypeKV> PD,
    const MCWriteProcResEntry *WPR,
    const MCWriteLatencyEntry *WL,
    const MCReadAdvanceEntry *RA, const InstrStage *IS,
    const unsigned *OC, const unsigned *FP) :
      MCSubtargetInfo(TT, CPU, FS, PF, PD,
                      WPR, WL, RA, IS, OC, FP) { }

  unsigned resolveVariantSchedClass(unsigned SchedClass,
      const MCInst *MI, unsigned CPUID) const override {
    return X86_MC::resolveVariantSchedClassImpl(SchedClass, MI, CPUID); 
  }
};

В случае использования Subtarget для описания различных конфигураций в XXXGenSubtarget.inc будет создано перечисление со свойствами, описанными с помощью SubtargetFeature, массивы с константными значениями для указания характеристик и подтипов CPU, а также будет сгенерирована функция ParseSubtargetFeatures, которая обрабатывает строку с установленной опцией Subtarget. При этом реализация метода XXXSubtarget в коде бэкенда должна соответствовать следующему псевдокоду, в котором как раз необходимо использовать данную функцию:

XXXSubtarget::XXXSubtarget(const Module &M, const std::string &FS) {
  // Set the default features
  // Determine default and user specified characteristics of the CPU
  // Call ParseSubtargetFeatures(FS, CPU) to parse the features string
  // Perform any additional operations
}

Несмотря на то, что .inc файлы очень объемные и содержат огромные массивы, это позволяет оптимизировать время доступа к информации, так как обращение к элементу массива имеет константное время. Генерируемые функции поиска по инструкциям реализованы с применением алгоритма бинарного поиска, чтобы минимизировать время работы. Так что хранение в подобном виде вполне оправдано.

Заключение

В итоге благодаря TableGen в LLVM мы имеем читабельные и легко поддерживаемые описания архитектур в едином формате с различными механизмами для взаимодействия и доступа к информации из исходного кода LLVM бэкендов для выполнения оптимизаций и кодогенерации. При этом подобное описание не наносит урон производительности компилятора благодаря автогенерируемому коду, который использует эффективные решения и структуры данных.