Description of processor architectures in LLVM using TableGen

At the moment, LLVM has already become a very popular system, which many people actively use to create various compilers, analyzers, etc. A large number of useful materials on this topic have already been written, including in Russian, which is good news. However, in most cases, the main bias in the articles is made on the frontend and middleend LLVM. Of course, when describing the full scheme of LLVM operation, machine code generation is not bypassed, but basically this topic is touched on casually, especially in publications in Russian. At the same time, LLVM has a rather flexible and interesting mechanism for describing processor architectures. Therefore, this material will be devoted to the somewhat neglected utility TableGen, which is part of LLVM.



The reason the compiler needs to have information about the architecture of each of the target platforms is quite obvious. Naturally, each processor model has its own set of registers, its own machine instructions, etc. And the compiler needs to have all the necessary information about them in order to be able to generate valid and efficient machine code. The compiler solves various platform-specific tasks: distributes registers, etc. In addition, LLVM backends also carry out optimizations on machine IR, which is closer to the actual instructions, or on the assembler instructions themselves. In such optimizations, instructions need to be replaced and transformed; accordingly, all information about them should be available.



To solve the problem of describing the processor architecture, LLVM adopted a single format for determining the processor properties necessary for the compiler. For each supported architecture, a .td



contains a description in a special formal language. It is converted to .inc



files when building the compiler using the TableGen utility included with LLVM. The resulting files, in fact, are C source, but have a separate extension, most likely, just so that these automatically generated files can be easily distinguished and filtered. The official documentation for TableGen is here and gives all the necessary information, there is also a formal description of the language and a general introduction .



Of course, this is a very extensive topic, where there are many details about which you can write individual articles. In this article, we will simply consider the basic points of describing processors even without an overview of all the features.

Description of architecture in .td file

So, the formal description language used in TableGen has similar features to ordinary programming languages ​​and allows you to describe the characteristics of architecture in a declarative style. And as I understand it, this language is also commonly called TableGen. Those. in this article TableGen uses both the name of the formal language itself and the utility that generates the resulting artifacts from it.



Modern processors are very complex systems, so it is not surprising that their description is quite voluminous. Accordingly, to create structure and simplify supportability .td



files can include each other using the usual #include



directive for C programmers. With the help of this directive, the Target.td



file is always first included, containing platform independent interfaces that must be implemented to provide all the necessary TableGen information. This file already includes a .td



file with intrinsic LLVM descriptions, but by itself it mainly contains base classes, such as Register



, Instruction



, Processor



, etc., from which you must inherit to create your own architecture for a compiler based on LLVM. From the previous sentence, it is clear that in the TableGen language there is a well-known concept of classes for all programmers.



In general, TableGen has only two basic entities: classes and definitions .

Classes

TableGen classes are also abstractions, as in all object-oriented programming languages, but they are simpler entities.



Classes can have parameters and fields, and they can also inherit other classes.

For example, one of the base classes is presented below.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

The angle brackets indicate the input parameters that are assigned to the class properties. From this example, you can also notice that the TableGen language is statically typed. The types that exist in TableGen: bit



(an analog of the Boolean type with values ​​0 and 1), int



, string



, code



(a piece of code, this is a type, simply because there are no methods and functions in TableGen in the usual sense, lines of code are written in [{ ... }]



), bits <n>, list <type> (values ​​are set using square brackets [...] as in Python and some other programming languages), class type



, dag



.



Most types should be understood, but if they have questions, they are all described in detail in the language specification, available at the link given at the beginning of the article.



Inheritance is also described by a fairly familiar syntax with :

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

In this case, the created class, of course, can override the values ​​of the fields specified in the base class using the let



keyword. And it can add its own fields similarly to the description provided in the previous example, indicating the type of field.

Definitions

Definitions are already concrete entities, you can compare them with the familiar to all objects. Definitions are defined using the def



keyword and can implement a class, redefine fields of base classes in exactly the same way as described above, and also have their own fields.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Multiclasses

Naturally, a large number of instructions in processors have similar semantics. For example, there may be a set of three-address instructions that take the two forms “reg = reg op reg”



and “reg = reg op imm”



. In one case, values ​​are taken from the registers and the result is also stored in the register, and in the other case, the second operand is a constant value (imm - immediate operand).



Listing all combinations manually is rather tedious; the risk of making a mistake increases. Of course, they can be generated automatically by writing a simple script, but this is not necessary because there is such a thing as multiclasses in 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)>; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Inside multiclasses, you need to describe all possible forms of instructions using the def



keyword. But this is not a complete form of instructions to be generated. At the same time, you can redefine the fields in them and do everything that is possible in ordinary definitions. To create real definitions based on a multiclass, you need to use the defm



keyword.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

As a result, for each such definition given through defm



in fact, several definitions will be constructed that are a combination of the main instruction and all possible forms described in the multiclass. As a result, the following instructions will be generated in this example: ADD_rr



, ADD_ri



, SUB_rr



, SUB_ri



, MUL_rr



, MUL_ri



.



Multiclasses can contain not only definitions with def



, but also nested defm



, thereby allowing the generation of complex forms of instructions. An example illustrating the creation of such chains can be found in the official documentation.

Subtargets

Another basic and useful thing for processors that have different variations of the instruction set is the support of subtarget in LLVM. An example of use is the LLVM SPARC implementation, which covers three main versions of the SPARC microprocessor architecture at once: Version 8 (V8, 32-bit architecture), Version 9 (V9, 64-bit architecture) and UltraSPARC architecture. The difference between the architectures is quite large, a different number of registers of different types, supported byte order, etc. In such cases, if there are several configurations, it is worth implementing the XXXSubtarget



class for the architecture. Using this class in the description will result in new command line options -mcpu=



and -mattr=



.



In addition to the Subtarget



class itself, the Subtarget



class Subtarget



important.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

In the Sparc.td



file, you can find examples of the implementation of SubtargetFeature



, which allow you to describe the availability of a set of instructions for each individual subtype of the architecture.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

In this case, anyway, Sparc.td



still defines the Proc



class, which is used to describe specific subtypes of SPARC processors, which just may have the properties described above, including different sets of instructions.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Relationship between the properties of instructions in TableGen and the LLVM backend code

The properties of classes and definitions allow you to correctly generate and set architectural features, but there is no direct access to them from the LLVM backend source code. However, sometimes you want to be able to get some platform-specific properties of instructions directly in the compiler code.

TSFlags

To do this, the Instruction



base class has a special TSFlags



field of 64 bits, which is converted by TableGen to a field of C ++ objects of class MCInstrDesc



, generated on the basis of data received from the TableGen description. You can specify any number of bits that you need to store information. This may be some Boolean value, for example, to indicate that we are using a scalar ALU.

 let TSFlags{0} = SALU;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Or we can store the type of instruction. Then we need, of course, more than one bit.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

As a result, it becomes possible to get these properties from the instruction in the backend code.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

If the property is more complex, then you can compare it with the value described in TableGen, which will be added to the auto-generated enumeration.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Function predicates

Also, function predicates can be used to obtain necessary information about instructions. With their help, you can show TableGen that you need to generate a function that will accordingly be available in the backend code. The base class with which you can create such a function definition is presented below.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

You can easily find usage examples in the backend for X86. So there is its own intermediate class, with the help of which the necessary function definitions are already created.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

As a result, you can use the isThreeOperandsLEA



method in C ++ code.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Here TII is the target instruction info, which can be obtained using the getInstrInfo()



method from the MCSubtargetInfo



for the desired architecture.

Transformation of instructions during optimizations. Instruction mapping

During a large number of optimizations performed in the later stages of compilation, the task often arises of converting all or only part of the instructions of one form into instructions of another form. Given the application of the multiclasses described at the beginning, we can have a large number of instructions with similar semantics and properties. In the code, these transformations, of course, could be written in the form of large switch-case



constructions, which for each instruction crushed the corresponding transformation. Partially, these huge constructions can be reduced with the help of macros, which would, according to well-known rules, form the desired instruction name. But still, this approach is very inconvenient, it is difficult to maintain due to the fact that all instruction names are listed explicitly. Adding a new instruction can very easily lead to an error, because you must remember to add it to all relevant conversions. Having been tormented with this approach, LLVM created a special mechanism for efficiently converting one form of instruction into another Instruction Mapping



.



The idea is very simple, it is necessary to describe possible models for transforming instructions directly in TableGen. Therefore, in LLVM TableGen there is a base class for describing such models.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Let's look at an example that is given in the documentation. The examples that can be found in the source code are now even simpler, since only two columns are obtained in the final table. In the backend code you can find the conversion of old forms into new forms of instructions, dsp instructions in mmdsp, etc., described using Instruction Mapping. In fact, this mechanism is not so widely used so far, simply because most backends started to be created before it appeared, and in order for it to work, you still need to set the correct properties for the instructions, so switching to it is not always easy, you may need some refactoring.



So, for example. Suppose we have forms of instructions without predicates and instructions where the predicate is respectively true and false. We describe them with the help of a multiclass and a special class, which we will just use as a filter. A simplified description without parameters and many properties may be something like this.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

In this example, by the way, it is also shown how to override a property for several definitions at once using the let … in



construct. As a result, we have many instructions that store their base name and property, which uniquely describes their form. Then you can create a transformation model.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

As a result, the following table will be generated from this description.





A function will be generated in the .inc



file

 int getPredOpcode(uint16_t Opcode, enum PredSense inPredSense)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Which, accordingly, accepts the instruction code for the conversion and the value of the PredSense auto-generated enumeration, which contains all possible values ​​in the columns. The implementation of this function is very simple, because it returns the desired array element for the instruction of interest to us.



And in the backend code, instead of writing switch-case



enough to simply call the generated function, which will return the code of the converted instruction. A simple solution, where adding new instructions, will not lead to the need for additional action.

Auto-generated artifacts ( .inc



files)

All the interaction between the TableGen description and the LLVM backend code is ensured by the generated .inc



files that contain the C code. To get a complete picture, let's see a little what exactly they are.



After each build, for each architecture, there will be several .inc



files in the build directory, each of which stores separate pieces of information about the architecture.So there is a file <TargetName>GenInstrInfo.inc



containing information about the instructions <TargetName>GenRegisterInfo.inc



, respectively, which contains information about the registers, there are files to work directly with the assembler and its output <TargetName>GenAsmMatcher.inc



and <TargetName>GenAsmWriter.inc



etc.



So what do these files consist of? In general, they contain enumerations, arrays, structures, and simple functions. For an example, you can look at the converted information on instructions in <TargetName>GenInstrInfo.inc



.



In the first part of the namespace with the name of the target is an enumeration containing all the instructions that have been described.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Next is an array describing the properties of the instructions const MCInstrDesc X86Insts[]



. The following arrays contain information about instruction names, etc. Basically, all information is stored in transfers and arrays.



There are also functions that have been described using predicates. Based on the function predicate definition discussed in the previous section, the following function will be generated.

 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 }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

But there are data in the generated files and structures. In X86GenSubtargetInfo.inc



you can find an example of the structure that should be used in the backend code to obtain information about the architecture, through it in the previous section it turned out 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); } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

If used Subtarget



to describe various configurations XXXGenSubtarget.inc



, an enumeration will be created with the properties described using SubtargetFeature



arrays with constant values ​​to indicate the characteristics and subtypes of the CPU, and a function will be generated ParseSubtargetFeatures



that processes the string with the option set Subtarget



. In this case, the implementation of the method XXXSubtarget



in the backend code should correspond to the following pseudocode, in which it is just necessary to use this function:

 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 }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Despite the fact that the .inc



files are very voluminous and contain huge arrays, this allows us to optimize the access time to information, since accessing an array element has a constant time. The generated search functions by instructions are implemented using a binary search algorithm to minimize operating time. So storage in this form is quite justified.

Conclusion

As a result, thanks to TableGen in LLVM, we have readable and easily supported architecture descriptions in a single format with various mechanisms for interacting and accessing information from LLVM backend source code for optimizations and code generation. At the same time, such a description does not affect the performance of the compiler due to self-generated code that uses efficient solutions and data structures.