Descrição das arquiteturas de processador no LLVM usando o TableGen

No momento, o LLVM já se tornou um sistema muito popular, que muitas pessoas usam ativamente para criar vários compiladores, analisadores, etc. Um grande número de materiais úteis sobre esse tópico já foi escrito, inclusive em russo, o que é uma boa notícia. No entanto, na maioria dos casos, o principal viés nos artigos é feito no LLVM front-end e middle-end. Obviamente, ao descrever o esquema completo da operação do LLVM, a geração do código da máquina não é ignorada, mas basicamente esse tópico é abordado casualmente, especialmente em publicações em russo. Ao mesmo tempo, o LLVM possui um mecanismo bastante flexível e interessante para descrever arquiteturas de processadores. Portanto, esse material será dedicado à utilidade um tanto negligenciada TableGen, que faz parte do LLVM.

A razão pela qual o compilador precisa ter informações sobre a arquitetura de cada uma das plataformas de destino é bastante óbvia. Naturalmente, cada modelo de processador possui seu próprio conjunto de registros, suas próprias instruções de máquina, etc. E o compilador precisa ter todas as informações necessárias sobre eles para poder gerar código de máquina válido e eficiente. O compilador resolve várias tarefas específicas da plataforma: distribui registros, etc. Além disso, os back-ends do LLVM também realizam otimizações no IR da máquina, mais próximo das instruções reais ou nas próprias instruções do montador. Nessas otimizações, as instruções precisam ser substituídas e transformadas; portanto, todas as informações sobre elas devem estar disponíveis.

Para resolver o problema de descrever a arquitetura do processador, o LLVM adotou um único formato para determinar as propriedades do processador necessárias para o compilador. Para cada arquitetura suportada, um .td contém uma descrição em um idioma formal especial. Ele é convertido em arquivos .inc ao criar o compilador usando o utilitário TableGen incluído no LLVM. Os arquivos resultantes, de fato, são de origem C, mas têm uma extensão separada, provavelmente, apenas para que esses arquivos gerados automaticamente possam ser facilmente distinguidos e filtrados. A documentação oficial do TableGen está aqui e fornece todas as informações necessárias, há também uma descrição formal do idioma e uma introdução geral .

Obviamente, esse é um tópico muito extenso, onde há muitos detalhes sobre os quais você pode escrever artigos individuais. Neste artigo, consideramos simplesmente os pontos básicos da descrição dos processadores, mesmo sem uma visão geral de todos os recursos.

Descrição da arquitetura no arquivo .td

Portanto, a linguagem de descrição formal usada no TableGen possui recursos semelhantes às linguagens de programação comuns e permite descrever as características da arquitetura em um estilo declarativo. E pelo que entendi, esse idioma também é chamado de TableGen. I.e. Neste artigo, o TableGen usa o nome da própria linguagem formal e o utilitário que gera os artefatos resultantes.

Os processadores modernos são sistemas muito complexos, portanto, não é de surpreender que sua descrição seja bastante volumosa. Dessa forma, para criar a estrutura e simplificar a manutenção de arquivos .td podemos incluir um ao outro usando a diretiva #include usual para programadores C. Com a ajuda dessa diretiva, o arquivo Target.td é sempre incluído primeiro, contendo interfaces independentes de plataforma que devem ser implementadas para fornecer todas as informações necessárias sobre TableGen. Esse arquivo já inclui um arquivo .td com descrições intrínsecas do LLVM, mas, por si só, contém principalmente classes base, como Register , Instruction , Processor etc., das quais você precisa herdar para criar sua própria arquitetura para o compilador com base em LLVM. A partir da sentença anterior, fica claro que o TableGen possui a noção de classes conhecida por todos os programadores.

Em geral, o TableGen possui apenas duas entidades básicas: classes e definições .

Aulas

As classes TableGen também são abstrações, como em todas as linguagens de programação orientadas a objetos, mas são entidades mais simples.

As classes podem ter parâmetros e campos e também podem herdar outras classes.
Por exemplo, uma das classes base é apresentada abaixo.

 // 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. } 

Os colchetes angulares indicam os parâmetros de entrada atribuídos às propriedades da classe. Neste exemplo, você também pode observar que o idioma do TableGen é estaticamente digitado. Os tipos que existem no TableGen: bit (um análogo do tipo Booleano com valores 0 e 1), int , string , code (um pedaço de código, esse é um tipo, simplesmente porque o TableGen não possui métodos e funções no sentido usual, as linhas de código são escritas em [{ ... }] bits <n>, lista <tipo> (os valores são definidos usando colchetes [...] como no Python e em outras linguagens de programação), class type , dag .

A maioria dos tipos deve ser entendida, mas se tiverem perguntas, todas serão descritas em detalhes na especificação do idioma, disponível no link fornecido no início do artigo.

A herança também é descrita por uma sintaxe bastante familiar com :

 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"; } 

Nesse caso, a classe criada, é claro, pode substituir os valores dos campos especificados na classe base usando a palavra-chave let . E pode adicionar seus próprios campos semelhantes à descrição fornecida no exemplo anterior, indicando o tipo de campo.

Definições

As definições já são entidades concretas, você pode compará-las com o familiar para todos os objetos. As definições são definidas usando a palavra-chave def e podem implementar uma classe, redefinir os campos das classes base exatamente da mesma maneira como descrito acima, e também possuem seus próprios campos.

 def i8mem : X86MemOperand<"printbytemem", X86Mem8AsmOperand>; def X86AbsMemAsmOperand : AsmOperandClass { let Name = "AbsMem"; let SuperClasses = [X86MemAsmOperand]; } 

Multiclasses

Naturalmente, um grande número de instruções nos processadores possui semântica semelhante. Por exemplo, pode haver um conjunto de instruções de três endereços que assumem as duas formas “reg = reg op reg” e “reg = reg op imm” . Em um caso, os valores são retirados dos registradores e o resultado também é salvo no registrador; no outro, o segundo operando é um valor constante (operando im-imediato).

Listar todas as combinações manualmente é um tanto tedioso; o risco de cometer um erro aumenta. Obviamente, eles podem ser gerados automaticamente escrevendo um script simples, mas isso não é necessário, porque existe um conceito como multiclasses na linguagem 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)>; } 

Dentro de várias classes, você precisa descrever todas as formas possíveis de instruções usando a palavra-chave def . Mas essa não é uma forma completa de instruções a serem geradas. Ao mesmo tempo, você pode redefinir os campos neles e fazer tudo o que é possível nas definições usuais. Para criar definições reais com base em uma defm , é necessário usar a palavra-chave 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">; 

E, como resultado, para cada definição dada por meio de defm de fato, várias definições serão construídas que são uma combinação da instrução principal e de todas as formas possíveis descritas na multiclasse. Como resultado, as seguintes instruções serão geradas neste exemplo: ADD_rr , ADD_ri , SUB_rr , SUB_ri , MUL_rr , MUL_ri .

Multiclasses podem conter não apenas definições com def , mas também defm aninhado, permitindo assim a geração de formas complexas de instruções. Um exemplo que ilustra a criação de tais cadeias pode ser encontrado na documentação oficial.

Subtargets

Outra coisa básica e útil para processadores que têm diferentes variações do conjunto de instruções é o suporte ao subtarget no LLVM. Um exemplo de uso é a implementação LLVM SPARC, que abrange três versões principais da arquitetura do microprocessador SPARC de uma vez: Versão 8 (V8, arquitetura de 32 bits), Versão 9 (V9, arquitetura de 64 bits) e arquitetura UltraSPARC. A diferença entre as arquiteturas é bastante grande, um número diferente de registros de diferentes tipos, ordem de bytes suportados etc. Nesses casos, se houver várias configurações, vale a pena implementar a classe XXXSubtarget para a arquitetura. O uso dessa classe na descrição resultará em novas opções de linha de comando -mcpu= e -mattr= .

Além da Subtarget classe Subtarget , a classe Subtarget importante.

 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; } 

No arquivo Sparc.td , você pode encontrar exemplos da implementação do SubtargetFeature , que permitem descrever a disponibilidade de um conjunto de instruções para cada subtipo individual da arquitetura.

 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">; 

Nesse caso, de qualquer maneira, Sparc.td ainda define a classe Proc , que é usada para descrever subtipos específicos de processadores SPARC, que podem ter apenas as propriedades descritas acima, incluindo diferentes conjuntos de instruções.

 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]>; 

Relação entre as propriedades das instruções em TableGen e o código de back-end do LLVM

As propriedades de classes e definições permitem gerar e configurar corretamente os recursos de arquitetura, mas não há acesso direto a eles a partir do código-fonte de back-end do LLVM. No entanto, às vezes você deseja obter algumas propriedades de instruções específicas da plataforma diretamente no código do compilador.

TSFlags

Para fazer isso, a classe base Instruction possui um campo TSFlags especial, tamanho de 64 bits, que é convertido por TableGen em um campo de objetos C ++ da classe MCInstrDesc , gerados com base nos dados recebidos da descrição TableGen. Você pode especificar qualquer número de bits necessário para armazenar informações. Pode ser algum valor booleano, por exemplo, para indicar que estamos usando uma ALU escalar.

 let TSFlags{0} = SALU; 

Ou podemos armazenar o tipo de instrução. Então precisamos, é claro, de mais de um pouco.

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

Como resultado, torna-se possível obter essas propriedades da instrução no código de back-end.

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

Se a propriedade for mais complexa, você poderá compará-la com o valor descrito em TableGen, que será adicionado à enumeração gerada automaticamente.

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

Predicados de função

Além disso, os predicados de função podem ser usados ​​para obter as informações necessárias sobre as instruções. Com a ajuda deles, você pode mostrar ao TableGen que você precisa gerar uma função que estará disponível no código de back-end. A classe base com a qual você pode criar essa definição de função é apresentada abaixo.

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

Você pode encontrar facilmente exemplos de uso no back-end para X86. Portanto, há sua própria classe intermediária, com a ajuda da qual as definições necessárias de funções já foram criadas.

 // 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>>; 

Como resultado, você pode usar o método isThreeOperandsLEA no código C ++.

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

Aqui, TII é a informação da instrução de destino, que pode ser obtida usando o método getInstrInfo() do MCSubtargetInfo para a arquitetura desejada.

Transformação de instruções durante otimizações. Mapeamento de instruções

Durante um grande número de otimizações realizadas nos estágios posteriores da compilação, geralmente surge a tarefa de converter todas ou apenas parte das instruções de um formulário em instruções de outro formulário. Dada a aplicação das multiclasses descritas no início, podemos ter um grande número de instruções com propriedades e semânticas semelhantes. No código, essas transformações, é claro, poderiam ser escritas na forma de grandes construções de switch-case , que para cada instrução esmagavam a transformação correspondente. Parcialmente, essas enormes construções podem ser reduzidas com a ajuda de macros, que formariam o nome necessário da instrução de acordo com regras conhecidas. Mas, ainda assim, essa abordagem é muito inconveniente, é difícil de manter devido ao fato de todos os nomes de instruções serem listados explicitamente. Adicionar uma nova instrução pode facilmente levar a um erro, porque lembre-se de adicioná-lo a todas as conversões relevantes. Tendo sido atormentado com essa abordagem, o LLVM criou um mecanismo especial para converter eficientemente uma forma de instrução em outro Instruction Mapping .

A ideia é muito simples, é necessário descrever possíveis modelos para transformar instruções diretamente no TableGen. Portanto, no LLVM TableGen, há uma classe base para descrever esses modelos.

 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 = []; } 

Vejamos um exemplo que é dado na documentação. Os exemplos que podem ser encontrados no código fonte são agora ainda mais simples, pois apenas duas colunas são obtidas na tabela final. No código de back-end, você pode encontrar a conversão de formulários antigos para novas formas de instruções, instruções dsp em mmdsp, etc., descritas usando o Mapeamento de Instruções. De fato, esse mecanismo não é tão amplamente usado até agora, simplesmente porque a maioria dos back-end começou a ser criada antes de aparecer e, para que funcione, você ainda precisa definir as propriedades corretas para as instruções, portanto, mudar para ele nem sempre é fácil, talvez seja necessário refatoração.

Então, por exemplo. Suponha que tenhamos formas de instruções sem predicados e instruções em que o predicado é respectivamente verdadeiro e falso. Nós os descrevemos com a ajuda de uma classe múltipla e uma classe especial, que usaremos apenas como filtro. Uma descrição simplificada sem parâmetros e muitas propriedades pode ser algo assim.

 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”>; … 

Neste exemplo, a propósito, também é mostrado como substituir uma propriedade por várias definições de uma só vez usando a construção let … in . Como resultado, temos muitas instruções que armazenam seu nome base e propriedade que descrevem exclusivamente seu formulário. Então você pode criar um modelo de transformação.

 def getPredOpcode : InstrMapping { // ,       - PredRel  let FilterClass = "PredRel"; //         ,      let RowFields = ["BaseOpcode"]; //          PredSense. let ColFields = ["PredSense"]; //  ,  ,       ,     PredSense=”” let KeyCol = [""]; //   PredSense      let ValueCols = [["true"], ["false"]]; } 

Como resultado, a tabela a seguir será gerada a partir dessa descrição.


Uma função será gerada no arquivo .inc

 int getPredOpcode(uint16_t Opcode, enum PredSense inPredSense) 

Que, consequentemente, aceita um código de instrução para conversão e o valor da enumeração gerada automaticamente do PredSense, que contém todos os valores possíveis nas colunas. A implementação desta função é muito simples, porque retorna o elemento de matriz desejado para a instrução de seu interesse.

E no código de back-end, em vez de escrever uma switch-case basta chamar a função gerada, que retornará o código da instrução convertida. Uma solução simples, onde adicionar novas instruções, não levará à necessidade de ação adicional.

Artefatos gerados .inc (arquivos .inc )

Toda a interação entre a descrição do TableGen e o código de back-end do LLVM é garantida pelos arquivos .inc gerados que contêm o código C. Para obter uma imagem completa, vamos ver um pouco o que exatamente eles são.

Após cada construção, para cada arquitetura, haverá vários arquivos .inc no diretório de construção, cada um dos quais armazena informações separadas sobre a arquitetura.Portanto, há um arquivo <TargetName>GenInstrInfo.incque contém informações sobre as instruções <TargetName>GenRegisterInfo.inc, respectivamente, que contém informações sobre os registros, existem arquivos para trabalhar diretamente com a montadora e sua saída <TargetName>GenAsmMatcher.ince <TargetName>GenAsmWriter.incetc.

Então, no que esses arquivos consistem? Em geral, eles contêm enumerações, matrizes, estruturas e funções simples. Por exemplo, você pode ver as informações convertidas nas instruções em <TargetName>GenInstrInfo.inc.

Na primeira parte, no espaço de nomes com o nome do destino, há uma enumeração contendo todas as instruções que foram descritas.

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

A seguir, é apresentada uma matriz que descreve as propriedades das instruções const MCInstrDesc X86Insts[]. As seguintes matrizes contêm informações sobre nomes de instruções, etc. Basicamente, todas as informações são armazenadas em transferências e matrizes.

Também há funções que foram descritas usando predicados. Com base na definição de predicado de função discutida na seção anterior, a seguinte função será gerada.

 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 } 

Mas existem dados nos arquivos e estruturas gerados. Em X86GenSubtargetInfo.incvocê pode encontrar um exemplo da estrutura que deve ser usada no código de back-end para obter informações sobre a arquitetura, por meio dela, na seção anterior, descobriu-se 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); } }; 

Se usado Subtargetpara descrever várias configurações XXXGenSubtarget.inc, uma enumeração será criada com as propriedades descritas usando SubtargetFeaturematrizes com valores constantes para indicar as características e subtipos da CPU, e será gerada uma função ParseSubtargetFeaturesque processa a sequência com o conjunto de opções Subtarget. Além disso, a implementação do método XXXSubtargetno código de back-end deve corresponder ao seguinte pseudo-código, no qual é necessário usar esta função:

 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 } 

Apesar de os .incarquivos serem muito volumosos e conterem grandes matrizes, isso permite otimizar o tempo de acesso às informações, pois o acesso a um elemento da matriz tem um tempo constante. As funções de pesquisa geradas por instruções são implementadas usando um algoritmo de pesquisa binária para minimizar o tempo de operação. Portanto, o armazenamento nesta forma é bastante justificado.

Conclusão

Como resultado, graças ao TableGen no LLVM, temos descrições de arquitetura legíveis e facilmente suportadas em um único formato com vários mecanismos para interagir e acessar informações do código-fonte de back-end do LLVM para otimizações e geração de código. Ao mesmo tempo, essa descrição não afeta o desempenho do compilador devido ao código gerado automaticamente que usa soluções e estruturas de dados eficientes.