Category Drawbacks of TableGen

Now, let’s take a brief look at some of the changes we have made within CodeGen.cpp to support our JIT-based calculator:

1. As previously mentioned, the code generation class has two important methods: one to compile the user-defined function into LLVM IR and print the IR to the console, and another to prepare the calculation evaluation function, calc_expr_func, which contains a call to the original user-defined function for evaluation. This second function also prints the resulting IR to the user:
   void CodeGen::compileToIR(AST *Tree, Module *M,
   StringMap &JITtedFunctions) {
   ToIRVisitor ToIR(M, JITtedFunctions);
   ToIR.run(Tree);
   M->print(outs(), nullptr);
   }
   void CodeGen::prepareCalculationCallFunc(AST *FuncCall,
   Module *M, llvm::StringRef FnName,
   StringMap &JITtedFunctions) {
   ToIRVisitor ToIR(M, JITtedFunctions);
   ToIR.genFuncEvaluationCall(FuncCall);
   M->print(outs(), nullptr);
   }

2. As noted in the preceding source, these code generation functions define a ToIRVisitor instance that takes in our module and a JITtedFunctions map to be used in its constructor upon initialization:
   class ToIRVisitor : public ASTVisitor {
   Module *M;
   IRBuilder<> Builder;
   StringMap &JITtedFunctionsMap;
   . . .
   public:
   ToIRVisitor(Module *M,
   StringMap &JITtedFunctions)
   : M(M), Builder(M->getContext()), JITtedFunctionsMap(JITtedFunctions) {

3. Ultimately, this information is used to either generate IR or evaluate the function that the IR was previously generated for. When generating the IR, the code generator expects to see a DefDecl node, which represents defining a new function. The function name, along with the number of arguments it is defined with, is stored within the function definitions map:
   virtual void visit(DefDecl &Node) override {
   llvm::StringRef FnName = Node.getFnName();
   llvm::SmallVector FunctionVars = Node.getVars();
   (JITtedFunctionsMap)[FnName] = FunctionVars.size();

4. Afterward, the actual function definition is created by the genUserDefinedFunction() call:
   Function *DefFunc = genUserDefinedFunction(FnName);

5. Within genUserDefinedFunction(), the first step is to check if the function exists within the module. If it does not, we ensure that the function prototype exists within our map data structure. Then, we use the name and the number of arguments to construct a function that has the number of arguments that were defined by the user, and make the function return a single integer value:
   Function *genUserDefinedFunction(llvm::StringRef Name) {
   if (Function *F = M->getFunction(Name))
   return F;
   Function *UserDefinedFunction = nullptr;
   auto FnNameToArgCount = JITtedFunctionsMap.find(Name);
   if (FnNameToArgCount != JITtedFunctionsMap.end()) {
   std::vector IntArgs(FnNameToArgCount->second, Int32Ty);
   FunctionType *FuncType = FunctionType::get(Int32Ty, IntArgs, false);
   UserDefinedFunction =
   Function::Create(FuncType, GlobalValue::ExternalLinkage, Name, M);
   }
   return UserDefinedFunction;
   }

6. After generating the user-defined function, a new basic block is created, and we insert our function into the basic block. Each function argument is also associated with a name that is defined by the user, so we also set the names for all function arguments accordingly, as well as generate mathematical operations that operate on the arguments within the function:
   BasicBlock BB = BasicBlock::Create(M->getContext(), “entry”, DefFunc); Builder.SetInsertPoint(BB); unsigned FIdx = 0; for (auto &FArg : DefFunc->args()) { nameMap[FunctionVars[FIdx]] = &FArg; FArg.setName(FunctionVars[FIdx++]); } Node.getExpr()->accept(this);
   };

7. When evaluating the user-defined function, the AST that is expected in our example is called a FuncCallFromDef node. First, we define the evaluation function and name it calc_expr_func (taking in zero arguments and returning one result):
   virtual void visit(FuncCallFromDef &Node) override {
   llvm::StringRef CalcExprFunName = “calc_expr_func”;
   FunctionType *CalcExprFunTy = FunctionType::get(Int32Ty, {}, false);
   Function *CalcExprFun = Function::Create(
   CalcExprFunTy, GlobalValue::ExternalLinkage, CalcExprFunName, M);

8. Next, we create a new basic block to insert calc_expr_func into:
   BasicBlock *BB = BasicBlock::Create(M->getContext(), “entry”, CalcExprFun);
   Builder.SetInsertPoint(BB);

9. Similar to before, the user-defined function is retrieved by genUserDefinedFunction(), and we pass the numerical parameters of the function call into the original function that we have just regenerated:
   llvm::StringRef CalleeFnName = Node.getFnName();
   Function *CalleeFn = genUserDefinedFunction(CalleeFnName);

10. Once we have the actual llvm::Function instance available, we utilize IRBuilder to create a call to the defined function and also return the result so that it is accessible when the result is printed to the user in the end:
    auto CalleeFnVars = Node.getArgs();
    llvm::SmallVector IntParams;
    for (unsigned i = 0, end = CalleeFnVars.size(); i != end; ++i) {
    int ArgsToIntType;
    CalleeFnVars[i].getAsInteger(10, ArgsToIntType);
    Value *IntParam = ConstantInt::get(Int32Ty, ArgsToIntType, true);
    IntParams.push_back(IntParam);
    }
    Builder.CreateRet(Builder.CreateCall(CalleeFn, IntParams, “calc_expr_res”));
    };

11. We then can pass our newly constructed AST into our code generator to compile the IR for the function that the user has defined. The specifics of IR generation will be discussed afterward, but this function that compiles to the IR needs to be aware of the module and our JITtedFunctions map. After generating the IR, we can add this information to our LLJIT instance by calling addIRModule() and wrapping our module and context in a ThreadSafeModule class, to prevent these from being accessed by other concurrent threads: CodeGenerator.compileToIR(Tree, M.get(), JITtedFunctions);
    ExitOnErr(
    JIT->addIRModule(ThreadSafeModule(std::move(M), std::move(Ctx))));

12. Instead, if the user is calling a function with parameters, which is represented by the Token::ident token, we also need to parse and semantically check if the user input is valid prior to converting the input into a valid AST. The parsing and checking here are slightly different compared to before, as it can include checks such as ensuring the number of parameters that the user has supplied to the function call matches the number of parameters that the function was originally defined with: } else if (CalcTok == Token::ident) {
    outs() << “Attempting to evaluate expression:\n”;
    Parser Parser(Lex);
    AST *Tree = Parser.parse();
    if (!Tree || Parser.hasError()) {
    llvm::errs() << “Syntax errors occured\n”;
    return 1;
    }
    Sema Semantic;
    if (Semantic.semantic(Tree, JITtedFunctions)) {
    llvm::errs() << “Semantic errors occured\n”;
    return 1;
    }

13. Once a valid AST is constructed for a function call, FuncCallFromDef, we get the name of the function from the AST, and then the code generator prepares to generate the call to the function that was previously added to the LLJIT instance. What occurs under the cover is that the user-defined function is regenerated as an LLVM call within a separate function that will be created that does the actual evaluation of the original function. This step requires the AST, the module, the function call name, and our map of function definitions: llvm::StringRef FuncCallName = Tree->getFnName();
    CodeGenerator.prepareCalculationCallFunc(Tree, M.get(), FuncCallName, JITtedFunctions);

14. After the code generator has completed its work to regenerate the original function and to create a separate evaluation function, we must add this information to the LLJIT instance. We create a ResourceTracker instance to track the memory that is allocated to the functions that have been added to LLJIT, as well as another ThreadSafeModule instance of the module and context. These two instances are then added to the JIT as an IR module: auto RT = JIT->getMainJITDylib().createResourceTracker();
    auto TSM = ThreadSafeModule(std::move(M), std::move(Ctx));
    ExitOnErr(JIT->addIRModule(RT, std::move(TSM)));

15. The separate evaluation function is then queried for within our LLJIT instance through the lookup() method, by supplying the name of our evaluation function, calc_expr_func, into the function. If the query is successful, the address for the calc_expr_func function is cast to the appropriate type, which is a function that takes no arguments and returns a single integer. Once the function’s address is acquired, we call the function to generate the result of the user-defined function with the parameters they have supplied and then print the result to the console: auto CalcExprCall = ExitOnErr(JIT->lookup(“calc_expr_func”));
    int (*UserFnCall)() = CalcExprCall.toPtr();
    outs() << “User defined function evaluated to: ” << UserFnCall() << “\n”;

16. After the function call is completed, the memory that was previously associated with our functions is then freed by ResourceTracker:

ExitOnErr(RT->remove());

Performance of the token filter

Using a plain binary search for the keyword filter does not give a better performance than the implementation based on the llvm::StringMap type. To beat the performance of the current implementation, you need to generate a perfect hash function.

The classic algorithm from Czech, Havas, and Majewski can be easily implemented, and it gives you a very good performance. It is described in An optimal algorithm for generating minimal perfect hash functions, Information Processing Letters, Volume 43, Issue 5, 1992. See https://www.sciencedirect.com/science/article/abs/pii/002001909290220P.

A state-of-the-art algorithm is PTHash from Pibiri and Trani, described in PTHash: Revisiting FCH Minimal Perfect Hashing, SIGIR ’21. See https://arxiv.org/pdf/2104.10402.pdf.

Both algorithms are good candidates for generating a token filter that is actually faster than llvm::StringMap.

Drawbacks of TableGen

Here are a few drawbacks of TableGen:

• The TableGen language is built on a simple concept. As a consequence, it does not have the same computing capabilities as other DSLs. Obviously, some programmers would like to replace TableGen with a different, more powerful language, and this topic comes up from time to time in the LLVM discussion forum.
• With the possibility of implementing your own backends, the TableGen language is very flexible. However, it also means that the semantics of a given definition are hidden inside the backend. Thus, you can create TableGen files that are basically not understandable by other developers.
• And last, the backend implementation can be very complex if you try to solve a non-trivial task. It is reasonable to expect that this effort would be lower if the TableGen language were more powerful.

Even if not all developers are happy with the capabilities of TableGen, the tool is used widely in LLVM, and for a developer, it is important to understand it.

Summary

In this chapter, you first learned the main idea behind TableGen. Then, you defined your first classes and records in the TableGen language, and you acquired knowledge of the syntax of TableGen. Finally, you developed a TableGen backend emitting fragments of C++ source code, based on the TableGen classes you defined.

In the next chapter, we examine another unique feature of LLVM: generating and executing code in one step, also known as Just-In-Time (JIT) compilation.

17. The only missing part now is a way to call this implementation, for which you define a global function, EmitTokensAndKeywordFilter(). The emitSourceFileHeader() function declared in the llvm/TableGen/TableGenBackend.h header emits a comment at the top of the generated file:

void EmitTokensAndKeywordFilter(RecordKeeper &RK,
raw_ostream &OS) {
emitSourceFileHeader(“Token Kind and Keyword Filter “
“Implementation Fragment”,
OS);
TokenAndKeywordFilterEmitter(RK).run(OS);
}

With that, you finished the implementation of the source emitter in the TokenEmitter.cpp file. Overall, the coding is not too complicated.
The TableGenBackends.h header file only contains the declaration of the EmitTokensAndKeywordFilter() function. To avoid including other files, you use forward declarations for the raw_ostream and RecordKeeper classes:

ifndef TABLEGENBACKENDS_H
define TABLEGENBACKENDS_H
namespace llvm {
class raw_ostream;
class RecordKeeper;
} // namespace llvm
void EmitTokensAndKeywordFilter(llvm::RecordKeeper &RK,
llvm::raw_ostream &OS);
endif

The missing part is the implementation of the driver. Its task is to parse the TableGen file and emit the records according to the command-line options. The implementation is in the TableGen.cpp file:

1. As usual, the implementation begins with including the required headers. The most important one is llvm/TableGen/Main.h because this header declares the frontend of TableGen:

include “TableGenBackends.h”
include “llvm/Support/CommandLine.h”
include “llvm/Support/PrettyStackTrace.h”
include “llvm/Support/Signals.h”
include “llvm/TableGen/Main.h”
include “llvm/TableGen/Record.h”

2. To simplify coding, the llvm namespace is imported:

using namespace llvm;

3. The user can choose one action. The ActionType enumeration contains all possible actions:

enum ActionType {
PrintRecords,
DumpJSON,
GenTokens,
};

4. A single command-line option object called Action is used. The user needs to specify the –gen-tokens option to emit the token filter you implemented. The other two options, –print-records and –dump-json, are standard options to dump read records. Note that the object is in an anonymous namespace:

namespace {
cl::opt Action(
cl::desc(“Action to perform:”),
cl::values(
clEnumValN(
PrintRecords, “print-records”,
“Print all records to stdout (default)”),
clEnumValN(DumpJSON, “dump-json”,
“Dump all records as “
“machine-readable JSON”),
clEnumValN(GenTokens, “gen-tokens”,
“Generate token kinds and keyword “
“filter”)));

5. The Main() function performs the requested action based on the value of Action. Most importantly, your EmitTokensAndKeywordFilter() function is called if –gen-tokens was specified on the command line. After the end of the function, the anonymous namespace is closed:

bool Main(raw_ostream &OS, RecordKeeper &Records) {
switch (Action) {
case PrintRecords:
OS << Records; // No argument, dump all contents
break;
case DumpJSON:
EmitJSON(Records, OS);
break;
case GenTokens:
EmitTokensAndKeywordFilter(Records, OS);
break;
}
return false;
}
} // namespace

6. And lastly, you define a main() function. After setting up the stack trace handler and parsing the command-line options, the TableGenMain() function is called to parse the TableGen file and create records. That function also calls your Main() function if there are no errors:

int main(int argc, char **argv) {
sys::PrintStackTraceOnErrorSignal(argv[0]);
PrettyStackTraceProgram X(argc, argv);
cl::ParseCommandLineOptions(argc, argv);
llvm_shutdown_obj Y;
return TableGenMain(argv[0], &Main);
}

Your own TableGen tool is now implemented. After compiling, you can run it with the KeywordC.td sample input file as follows:

$ tinylang-tblgen –gen-tokens –o TokenFilter.inc KeywordC.td

The generated C++ source code is written to the TokenFilter.inc file.

12. The keywords used for the filter are in the list named Tokens. To get access to that list, you first need to look up the Tokens field in the record. This returns a pointer to an instance of the RecordVal class, from which you can retrieve the Initializer instance via the calling method, getValue(). The Tokens field is defined as a list, so you cast the initializer instance to ListInit. If this fails, then exit the function: ListInit *TokenFilter = dyn_cast_or_null(
    AllTokenFilter[0]
    ->getValue(“Tokens”)
    ->getValue());
    if (!TokenFilter)
    return;
13. Now, you are ready to construct a filter table. For each keyword stored in the TokenFilter, list, you need the name and the value of the Flag field. That field is again defined as a list, so you need to loop over those elements to calculate the final value. The resulting name/flag value pair is stored in a Table vector: using KeyFlag = std::pair;
    std::vector Table;
    for (size_t I = 0, E = TokenFilter->size(); I < E; ++I) { Record *CC = TokenFilter->getElementAsRecord(I);
    StringRef Name = CC->getValueAsString(“Name”);
    uint64_t Val = 0;
    ListInit *Flags = nullptr;
    if (RecordVal *F = CC->getValue(“Flags”))
    Flags = dyn_cast_or_null(F->getValue());
    if (Flags) {
    for (size_t I = 0, E = Flags->size(); I < E; ++I) { Val |= Flags->getElementAsRecord(I)->getValueAsInt(
    “Val”);
    }
    }
    Table.emplace_back(Name, Val);
    }
14. To be able to perform a binary search, the table needs to be sorted. The comparison function is provided by a lambda function: llvm::sort(Table.begin(), Table.end(),
    [](const KeyFlag A, const KeyFlag B) {
    return A.first < B.first;
    });
15. Now, you can emit the C++ source code. First, you emit the sorted table containing the name of the keyword and the associated flag value: OS << “ifdef GET_KEYWORD_FILTER\n”
    << “undef GET_KEYWORD_FILTER\n”;
    OS << “bool lookupKeyword(llvm::StringRef Keyword, “
    “unsigned &Value) {\n”;
    OS << ” struct Entry {\n”
    << ” unsigned Value;\n”
    << ” llvm::StringRef Keyword;\n”
    << ” };\n”
    << “static const Entry Table” << Table.size() << “ = {\n”;
    for (const auto &[Keyword, Value] : Table) {
    OS << ” { ” << Value << “, llvm::StringRef(\””
    << Keyword << “\”, ” << Keyword.size()
    << “) },\n”;
    }
    OS << ” };\n\n”;
16. Next, you look up the keyword in the sorted table, using the std::lower_bound() standard C++ function. If the keyword is in the table, then the Value parameter receives the value of the flags associated with the keyword, and the function returns true. Otherwise, the function simply returns false: OS << ” const Entry *E = ” “std::lower_bound(&Table[0], ” “&Table” << Table.size() << “, Keyword, [](const Entry &A, const ” “StringRef ” “&B) {\n”; OS << ” return A.Keyword < B;\n”; OS << ” });\n”; OS << ” if (E != &Table” << Table.size() << “) {\n”; OS << ” Value = E->Value;\n”;
    OS << ” return true;\n”;
    OS << ” }\n”;
    OS << ” return false;\n”;
    OS << “}\n”;
    OS << “endif\n”;
    }

Since parsing and creation of records are done through an LLVM library, you only need to care about the backend implementation, which consists mostly of generating C++ source code fragments based on the information in the records. First, you need to be clear about what source code to generate before you can put it into the backend.
Sketching the source code to be generated
The output of the TableGen tool is a single file containing C++ fragments. The fragments are guarded by macros. The goal is to replace the TokenKinds.def database file. Based on the information in the TableGen file, you can generate the following:

1. The enumeration members used to define flags. The developer is free to name the type; however, it should be based on the unsigned type. If the generated file is named TokenKinds.inc, then the intended use is this:

enum Flags : unsigned {
define GET_TOKEN_FLAGS
include “TokenKinds.inc”
}

2. The TokenKind enumeration, and the prototypes and definitions of the getTokenName(), getPunctuatorSpelling(), and getKeywordSpelling() functions. This code replaces the TokenKinds.def database file, most of the TokenKinds.h include file and the TokenKinds.cpp. source file.
3. A new lookupKeyword() function that can be used instead of the current implementation using the llvm::StringMap. type. This is the function you want to optimize.
   Knowing what you want to generate, you can now turn to implementing the backend.
   Creating a new TableGen tool
   A simple structure for your new tool is to have a driver that evaluates the command-line options and calls the generation functions and the actual generator functions in a different file. Let’s call the driver file TableGen.cpp and the file containing the generator TokenEmitter.cpp. You also need a TableGenBackends.h header file. Let’s begin the implementation with the generation of the C++ code in the TokenEmitter.cpp file:
4. As usual, the file begins with including the required headers. The most important one is llvm/TableGen/Record.h, which defines a Record class, used to hold records generated by parsing the .td file:

include “TableGenBackends.h”
include “llvm/Support/Format.h”
include “llvm/TableGen/Record.h”
include “llvm/TableGen/TableGenBackend.h”
include

2. To simplify coding, the llvm namespace is imported:

using namespace llvm;

3. The TokenAndKeywordFilterEmitter class is responsible for generating the C++ source code. The emitFlagsFragment(), emitTokenKind(), and emitKeywordFilter() methods emit the source code, as described in the previous section, Sketching the source code to be generated. The only public method, run(), calls all the code-emitting methods. The records are held in an instance of RecordKeeper, which is passed as a parameter to the constructor. The class is inside an anonymous namespace:

namespace {
class TokenAndKeywordFilterEmitter {
RecordKeeper &Records;
public:
explicit TokenAndKeywordFilterEmitter(RecordKeeper &R)
: Records(R) {}
void run(raw_ostream &OS);
private:
void emitFlagsFragment(raw_ostream &OS);
void emitTokenKind(raw_ostream &OS);
void emitKeywordFilter(raw_ostream &OS);
};
} // End anonymous namespace

The TokenKinds.def database file defines three different macros. The TOK macro is used for tokens that do not have a fixed spelling – for example, for integer literals. The PUNCTUATOR macro is used for all kinds of punctuation marks and includes a preferred spelling. Lastly, the KEYWORD macro defines a keyword that is made up of a literal and a flag, which is used to indicate at which language level this literal is a keyword. For example, the thread_local keyword was added to C++11.
One way to express this in the TableGen language is to create a Token class that holds all the data. You can then add subclasses of that class to make the usage more comfortable. You also need a Flag class for flags defined together with a keyword. And last, you need a class to define a keyword filter. These classes define the basic data structure and can be potentially reused in other projects. Therefore, you create a Keyword.td file for it. Here are the steps:

1. A flag is modeled as a name and an associated value. This makes it easy to generate an enumeration from this data:

class Flag {
string Name = name;
int Val = val;
}

2. The Token class is used as the base class. It just carries a name. Please note that this class has no parameters:

class Token {
string Name;
}

3. The Tok class has the same function as the corresponding TOK macro from the database file. it represents a token without fixed spellings. It derives from the base class, Token, and just adds initialization for the name:

class Tok : Token {
let Name = name;
}

4. In the same way, the Punctuator class resembles the PUNCTUATOR macro. It adds a field for the spelling of the token:

class Punctuator : Token {
let Name = name;
string Spelling = spelling;
}

5. And last, the Keyword class needs a list of flags:

class Keyword flags> : Token {
let Name = name;
list Flags = flags;
}

6. With these definitions in place, you can now define a class for the keyword filter, called TokenFilter. It takes a list of tokens as a parameter:

class TokenFilter tokens> {
string FunctionName;
list Tokens = tokens;
}

With these class definitions, you are certainly able to capture all the data from the TokenKinds.def database file. The TinyLang language does not utilize the flags, since there is only this version of the language. Real-world languages such as C and C++ have undergone a couple of revisions, and they usually require flags. Therefore, we use keywords from C and C++ as an example. Let’s create a KeywordC.td file, as follows:

1. First, you include the class definitions created earlier:

Include “Keyword.td”

2. Next, you define flags. The value is the binary value of the flag. Note how the !or operator is used to create a value for the KEYALL flag:

def KEYC99 : Flag<“KEYC99”, 0x1>;
def KEYCXX : Flag<“KEYCXX”, 0x2>;
def KEYCXX11: Flag<“KEYCXX11”, 0x4>;
def KEYGNU : Flag<“KEYGNU”, 0x8>;
def KEYALL : Flag<“KEYALL”, !or(KEYC99.Val, KEYCXX.Val, KEYCXX11.Val , KEYGNU.Val)>;

3. There are tokens without a fixed spelling – for example, a comment:

def : Tok<“comment”>;

4. Operators are defined using the Punctuator class, as in this example:

def : Punctuator<“plus”, “+”>;
def : Punctuator<“minus”, “-“>;

5. Keywords need to use different flags:

def kw_auto: Keyword<“auto”, [KEYALL]>;
def kw_inline: Keyword<“inline”, [KEYC99,KEYCXX,KEYGNU]>;
def kw_restrict: Keyword<“restrict”, [KEYC99]>;

6. And last, here’s the definition of the keyword filter:

def : TokenFilter<[kw_auto, kw_inline, kw_restrict]>;

Of course, this file does not include all tokens from C and C++. However, it demonstrates all possible usages of the defined TableGen classes.
Based on these TableGen files, you’ll implement a TableGen backend in the next section.

Let’s define a simple record for an instruction:

def ADD {
string Mnemonic = “add”;
int Opcode = 0xA0;
}

The def keyword signals that you define a record. It is followed by the name of the record. The record body is surrounded by curly braces, and the body consists of field definitions, similar to a structure in C++.
You can use the llvm-tblgen tool to see the generated records. Save the preceding source code in an inst.td file and run the following:

$ llvm-tblgen –print-records inst.td
————- Classes —————–
————- Defs —————–
def ADD {
string Mnemonic = “add”;
int Opcode = 160;
}

This is not yet exciting; it only shows the defined record was parsed correctly.
Defining instructions using single records is not very comfortable. A modern CPU has hundreds of instructions, and with this amount of records, it is very easy to introduce typing errors in the field names. And if you decide to rename a field or add a new field, then the number of records to change becomes a challenge. Therefore, a blueprint is needed. In C++, classes have a similar purpose, and in TableGen, it is also called a class. Here is the definition of an Inst class and two records based on that class:

class Inst {
string Mnemonic = mnemonic;
int Opcode = opcode;
}
def ADD : Inst<“add”, 0xA0>;
def SUB : Inst<“sub”, 0xB0>;

The syntax for classes is similar to that of records. The class keyword signals that a class is defined, followed by the name of the class. A class can have a parameter list. Here, the Inst class has two parameters, mnemonic and opcode, which are used to initialize the records’ fields. The values for those fields are given when the class is instantiated. The ADD and SUB records show two instantiations of the class. Again, let’s use llvm-tblgen to look at the records:

$ llvm-tblgen –print-records inst.td
————- Classes —————–
class Inst {
string Mnemonic = Inst:mnemonic;
int Opcode = Inst:opcode;
}
————- Defs —————–
def ADD { // Inst
string Mnemonic = “add”;
int Opcode = 160;
}
def SUB { // Inst
string Mnemonic = “sub”;
int Opcode = 176;
}

Now, you have one class definition and two records. The name of the class used to define the records is shown as a comment. Please note that the arguments of the class have the default value ?, which indicates int is uninitialized.

LLVM comes with its own domain-specific language (DSL) called TableGen. It is used to generate C++ code for a wide range of use cases, thus reducing the amount of code a developer has to produce. The TableGen language is not a full-fledged programming language. It is only used to define records, which is a fancy word for a collection of names and values. To understand why such a restricted language is useful, let’s examine two examples.

Typical data you need to define one machine instruction of a CPU is:

• The mnemonic of the instruction
• The bit pattern
• The number and types of operands
• Possible restrictions or side effects

It is easy to see that this data can be represented as a record. For example, a field named asmstring could hold the value of the mnemonic; say, “add”. Also, a field named opcode could hold the binary representation of the instruction. Together, the record would describe an additional instruction. Each LLVM backend describes the instruction set in this way.

Records are such a general concept that you can describe a wide variety of data with them. Another example is the definition of command-line options. A command-line option:

• Has a name
• May have an optional argument
• Has a help text
• May belong to a group of options

Again, this data can be easily seen as a record. Clang uses this approach for the command-line options of the Clang driver.

The TableGen language

In LLVM, the TableGen language is used for a variety of tasks. Large parts of a backend are written in the TableGen language; for example, the definition of a register file, all instructions with mnemonic and binary encoding, calling conventions, patterns for instruction selection, and scheduling models for instruction scheduling. Other uses of LLVM are the definition of intrinsic functions, the definition of attributes, and the definition of command-line options.

You’ll find the Programmer’s Reference at https://llvm.org/docs/TableGen/ProgRef.html and the Backend Developer’s Guide at https://llvm.org/docs/TableGen/BackGuide.html.

To achieve this flexibility, the parsing and the semantics of the TableGen language are implemented in a library. To generate C++ code from the records, you need to create a tool that takes the parsed records and generates C++ code from it. In LLVM, that tool is called llvm-tblgen, and in Clang, it is called clang-tblgen. Those tools contain the code generators required by the project. But they can also be used to learn more about the TableGen language, which is what we’ll do in the next section.

Experimenting with the TableGen language

Very often, beginners feel overwhelmed by the TableGen language. But as soon as you start experimenting with the language, it becomes much easier.

To allow the user to add passes at every extension point, you need to add the preceding code snippet for each extension point.

3. Now is a good time to try out the different pass manager options. With the –debug-pass-manager option, you can follow which passes are executed in which order. You can also print the IR before or after each pass, which is invoked with the –print-before-all and –print-after-all options. If you created your own pass pipeline, then you can insert the print pass in points of interest. For example, try the –passes=”print,inline,print” option. Furthermore, to identify which pass changes the IR code, you can use the –print-changed option, which will only print the IR code if it has changed compared to the result from the pass before. The greatly reduced output makes it much easier to follow IR transformations.
   

The PassBuilder class has a nested OptimizationLevel class to represent the six different optimization levels. Instead of using the “default<O?>” pipeline description as an argument to the parsePassPipeline() method, we can also call the buildPerModuleDefaultPipeline() method, which builds the default optimization pipeline for the request level – except for level O0. This optimization level means that no optimization is performed.

Consequently, no passes are added to the pass manager. If we still want to run a certain pass, then we can add it to the pass manager manually. A simple pass to run at this level is the AlwaysInliner pass, which inlines a function marked with the always_inline attribute into the caller. After translating the command-line option value for the optimization level into the corresponding member of the OptimizationLevel class, we can implement this as follows:
    PassBuilder::OptimizationLevel Olevel = …;
    if (OLevel == PassBuilder::OptimizationLevel::O0)
      MPM.addPass(AlwaysInlinerPass());
    else
      MPM = PB.buildPerModuleDefaultPipeline(OLevel, DebugPM);

Of course, it is possible to add more than one pass to the pass manager in this fashion. PassBuilder also uses the addPass() method when constructing the pass pipeline.

Running extension point callbacks

Because the pass pipeline is not populated for optimization level O0, the registered extension points are not called. If you use the extension points to register passes that should also run at O0 level, this is problematic. You can call the runRegisteredEPCallbacks() method to run the registered extension point callbacks, resulting in a pass manager populated only with the passes that were registered through the extension points.

By adding the optimization pipeline to tinylang, you created an optimizing compiler similar to clang. The LLVM community works on improving the optimizations and the optimization pipeline with each release. Due to this, it is very seldom that the default pipeline is not used. Most often, new passes are added to implement certain semantics of the programming language.

Summary

In this chapter, you learned how to create a new pass for LLVM. You ran the pass using a pass pipeline description and an extension point. You extended your compiler with the construction and execution of a pass pipeline similar to clang, turning tinylang into an optimizing compiler. The pass pipeline allows the addition of passes at extension points, and you learned how you can register passes at these points. This allows you to extend the optimization pipeline with your developed passes or existing passes.

In the next chapter, you will learn the basics of the TableGen language, which is used extensively in LLVM and clang to significantly reduce manual programming.