Category ITCertification Exams

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());

Firstly, let’s discuss how to set up the JIT engine in our interactive calculator. All of the implementation pertaining to the JIT engine exists within Calc.cpp, and this file has one main() loop for the execution of the program:

1. We must include several header files, aside from the headers including our code generation, semantic analyzer, and parser implementation. The LLJIT.h header defines the LLJIT class and the core classes of the ORC API. Next, the InitLLVM.h header is needed for the basic initialization of the tool, and the TargetSelect.h header is needed for the initialization of the native target. Finally, we also include the C++ header to allow for user input into our calculator application:

include “CodeGen.h”
include “Parser.h”
include “Sema.h”
include “llvm/ExecutionEngine/Orc/LLJIT.h”
include “llvm/Support/InitLLVM.h”
include “llvm/Support/TargetSelect.h”
include

2. Next, we add the llvm and llvm::orc namespaces to the current scope:

using namespace llvm;
using namespace llvm::orc;

3. Many of the calls from our LLJIT instance that we will be creating return an error type, Error. The ExitOnError class allows us to discard Error values that are returned by the calls from the LLJIT instance while logging to stderr and exiting the application. We declare a global ExitOnError variable as follows:

ExitOnError ExitOnErr;

4. Then, we add the main() function, which initializes the tool and the native target:

int main(int argc, const char **argv{
InitLLVM X(argc, argv);
InitializeNativeTarget();
InitializeNativeTargetAsmPrinter();
InitializeNativeTargetAsmParser();

5. We use the LLJITBuilder class to create an LLJIT instance, wrapped in the previously declared ExitOnErr variable in case an error occurs. A possible source of error would be that the platform does not yet support JIT compilation:

auto JIT = ExitOnErr(LLJITBuilder().create());

6. Next, we declare our JITtedFunctions map that keeps track of the function definitions, as we have previously described:

StringMap JITtedFunctions;

7. To facilitate an environment that waits for user input, we add a while() loop and allow the user to type in an expression, saving the line that the user typed within a string called calcExp: while (true) {
   outs() << “JIT calc > “;
   std::string calcExp;
   std::getline(std::cin, calcExp);

8. Afterward, the LLVM context class is initialized, along with a new LLVM module. The module’s data layout is also set accordingly, and we also declare a code generator, which will be used to generate IR for the function that the user has defined on the command line: std::unique_ptr Ctx = std::make_unique();
   std::unique_ptr M = std::make_unique(“JIT calc.expr”, *Ctx);
   M->setDataLayout(JIT->getDataLayout());
   CodeGen CodeGenerator;

9. We must interpret the line that was entered by the user to determine if the user is defining a new function or calling a previous function that they have defined with an argument. A Lexer class is defined while taking in the line of input that the user has given. We will see that there are two main cases that the lexer cares about: Lexer Lex(calcExp);
   Token::TokenKind CalcTok = Lex.peek();

10. The lexer can check the first token of the user input. If the user is defining a new function (represented by the def keyword, or the Token::KW_def token), then we parse it and check its semantics. If the parser or the semantic analyzer detects any issues with the user-defined function, errors will be emitted accordingly, and the calculator program will halt. If no errors are detected from either the parser or the semantic analyzer, this means we have a valid AST data structure, DefDecl: if (CalcTok == Token::KW_def) {
    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;
    }

The lli tool is nothing more than a thin wrapper around LLVM APIs. In the first section, we learned that the ORC engine uses a layered approach. The ExecutionSession class represents a running JIT program. Besides other items, this class holds information such as used JITDylib instances. A JITDylib instance is a symbol table that maps symbol names to addresses. For example, these can be symbols defined in an LLVM IR file or the symbols of a loaded shared library.

For executing LLVM IR, we do not need to create a JIT stack on our own, as the LLJIT class provides this functionality. You can also make use of this class when migrating from the older MCJIT implementation, as this class essentially provides the same functionality.

To illustrate the functions of the LLJIT utility, we will be creating an interactive calculator application while incorporating JIT functionality. The main source code of our JIT calculator will be extended from the calc example from Chapter 2, The Structure of a Compiler.

The primary idea behind our interactive JIT calculator will be as follows:

1. Allow the user to input a function definition, such as def f(x) = x*2.
2. The function inputted by the user is then compiled by the LLJIT utility into a function – in this case, f.
3. Allow the user to call the function they have defined with a numerical value: f(3).
4. Evaluate the function with the provided argument, and print the result to the console: 6.

Before we discuss incorporating JIT functionality into the calculator source code, there are a few main differences to point out with respect to the original calculator example:

• Firstly, we previously only input and parsed functions beginning with the with keyword, rather than the def keyword described previously. For this chapter, we instead only accept function definitions beginning with def, and this is represented as a particular node in our abstract syntax tree (AST) class, known as DefDecl. The DefDecl class is aware of the arguments and their names it is defined with, and the function name is also stored within this class.
• Secondly, we also need our AST to be aware of function calls, to represent the functions that the LLJIT utility has consumed or JIT’ted. Whenever a user inputs the name of a function, followed by arguments enclosed in parentheses, the AST recognizes these as FuncCallFromDef nodes. This class essentially is aware of the same information as the DefDecl class.

Due to the addition of these two AST classes, it is obvious to expect that the semantic analysis, parser, and code generation classes will be adapted accordingly to handle the changes in our AST. One additional thing to note is the addition of a new data structure, called JITtedFunctions, which all these classes are aware of. This data structure is a map with the defined function names as keys, and the number of arguments a function is defined with is stored as values within the map. We will see later how this data structure will be utilized in our JIT calculator.

For more details on the changes we have made to the calc example, the full source containing the changes from calc and this section’s JIT implementation can be found within the lljit source directory.

Using JIT compilation for direct execution
Running LLVM IR directly is the first idea that comes to mind when thinking about a JIT compiler. This is what the lli tool, the LLVM interpreter, and the dynamic compiler do. We will explore the lli tool in the next section.
Exploring the lli tool
Let’s try the lli tool with a very simple example. The following LLVM IR can be stored as a file called hello.ll, which is the equivalent of a C hello world application. This file declares a prototype for the printf() function from the C library. The hellostr constant contains the message to be printed. Inside the main() function, a call to the printf() function is generated, and this function contains a hellostr message that will be printed. The application always returns 0.
The complete source code is as follows:

declare i32 @printf(ptr, …)
@hellostr = private unnamed_addr constant [13 x i8] c”Hello world\0A\00″
define dso_local i32 @main(i32 %argc, ptr %argv) {
%res = call i32 (ptr, …) @printf(ptr @hellostr)
ret i32 0
}

This LLVM IR file is generic enough that it is valid for all platforms. We can directly execute the IR using the lli tool with the following command:

$ lli hello.ll
Hello world

The interesting point here is how the printf() function is found. The IR code is compiled to machine code, and a lookup for the printf symbol is triggered. This symbol is not found in the IR, so the current process is searched for it. The lli tool dynamically links against the C library, and the symbol is found there.
Of course, the lli tool does not link against the libraries you created. To enable the use of such functions, the lli tool supports the loading of shared libraries and objects. The following C source just prints a friendly message:

include
void greetings() {
puts(“Hi!”);
}

Stored in greetings.c, we use this to explore loading objects with lli. The following command will compile this source into a shared library. The –fPIC option instructs clang to generate position-independent code, which is required for shared libraries. Moreover, the compiler creates a greetings.so shared library with –shared:

$ clang greetings.c -fPIC -shared -o greetings.so

We also compile the file into the greetings.o object file:

$ clang greetings.c -c -o greetings.o

We now have two files, the greetings.so shared library and the greetings.o object file, which we will load into the lli tool.
We also need an LLVM IR file that calls the greetings() function. For this, create a main.ll file that contains a single call to the function:

declare void @greetings(…)
define dso_local i32 @main(i32 %argc, i8** %argv) {
call void (…) @greetings()
ret i32 0
}

Notice that on executing, the previous IR crashes, as lli cannot locate the greetings symbol:

$ lli main.ll
JIT session error: Symbols not found: [ _greetings ]
lli: Failed to materialize symbols: { (main, { _main }) }

The greetings() function is defined in an external file, and to fix the crash, we have to tell the lli tool which additional file needs to be loaded. In order to use the shared library, you must use the –load option, which takes the path to the shared library as an argument:

$ lli –load ./greetings.so main.ll
Hi!

It is important to specify the path to the shared library if the directory containing the shared library is not in the search path for the dynamic loader. If omitted, then the library will not be found.
Alternatively, we can instruct lli to load the object file with –extra-object:

$ lli –extra-object greetings.o main.ll
Hi!

Other supported options are –extra-archive, which loads an archive, and –extra-module, which loads another bitcode file. Both options require the path to the file as an argument.
You now know how you can use the lli tool to directly execute LLVM IR. In the next section, we will implement our own JIT tool.

So far, we have only looked at ahead-of-time (AOT) compilers. These compilers compile the whole application. The application can only run after the compilation is finished. If the compilation is performed at the runtime of the application, then the compiler is a JIT compiler. A JIT compiler has interesting use cases:

• Implementation of a virtual machine: A programming language can be translated to byte code with an AOT compiler. At runtime, a JIT compiler is used to compile the byte code to machine code. The advantage of this approach is that the byte code is hardware-independent, and thanks to the JIT compiler, there is no performance penalty compared to an AOT compiler. Java and C use this model today, but this is not a new idea: the USCD Pascal compiler from 1977 already used a similar approach.
• Expression evaluation: A spreadsheet application can compile often-executed expressions with a JIT compiler. For example, this can speed up financial simulations. The lldb LLVM debugger uses this approach to evaluate source expressions at debug time.
• Database queries: A database creates an execution plan from a database query. The execution plan describes operations on tables and columns, which leads to a query answer when executed. A JIT compiler can be used to translate the execution plan into machine code, which speeds up the execution of the query.

The static compilation model of LLVM is not as far away from the JIT model as one may think. The llc LLVM static compiler compiles LLVM IR into machine code and saves the result as an object file on disk. If the object file is not stored on disk but in memory, would the code be executable? Not directly, as references to global functions and global data use relocations instead of absolute addresses. Conceptually, a relocation describes how to calculate the address – for example, as an offset to a known address. If we resolve relocations into addresses, as the linker and the dynamic loader do, then we can execute the object code. Running the static compiler to compile IR code into an object file in memory, performing a link step on the in-memory object file, and running the code gives us a JIT compiler. The JIT implementation in the LLVM core libraries is based on this idea.

During the development history of LLVM, there were several JIT implementations, with different feature sets. The latest JIT API is the On-Request Compilation (ORC) engine. In case you were curious about the acronym, it was the lead developer’s intention to invent yet another acronym based on Tolkien’s universe, after Executable and Linking Format (ELF) and Debugging Standard (DWARF) were already present.

The ORC engine builds on and extends the idea of using the static compiler and a dynamic linker on the in-memory object file. The implementation uses a layered approach. The two basic levels are the compile layer and the link layer. On top of this sits a layer providing support for lazy compilation. A transformation layer can be stacked on top or below the lazy compilation layer, allowing the developer to add arbitrary transformations or simply to be notified of certain events. Moreover, this layered approach has the advantage that the JIT engine is customizable for diverse requirements. For example, a high-performance virtual machine may choose to compile everything upfront and make no use of the lazy compilation layer. On the other hand, other virtual machines will emphasize startup time and responsiveness to the user and will achieve this with the help of the lazy compilation layer.

The older MCJIT engine is still available, and its API is derived from an even older, already-removed JIT engine. Over time, this API gradually became bloated, and it lacks the flexibility of the ORC API. The goal is to remove this implementation, as the ORC engine now provides all the functionality of the MCJIT engine, and new developments should use the ORC API.

In the next section, we look at lli, the LLVM interpreter, and the dynamic compiler, before we dive into implementing a JIT compiler.

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

7. Next, the function declarations are emitted. This is only a constant string, so nothing exciting happens. This finishes emitting the declarations: OS << ” const char *getTokenName(TokenKind Kind) “
   “LLVM_READNONE;\n”
   << ” const char *getPunctuatorSpelling(TokenKind “
   “Kind) LLVM_READNONE;\n”
   << ” const char *getKeywordSpelling(TokenKind “
   “Kind) “
   “LLVM_READNONE;\n”
   << “}\n”
   << “endif\n”;
8. Now, let’s turn to emitting the definitions. Again, this generated code is guarded by a macro called GET_TOKEN_KIND_DEFINITION. First, the token names are emitted into a TokNames array, and the getTokenName() function uses that array to retrieve the name. Please note that the quote symbol must be escaped as \” when used inside a string: OS << “ifdef GET_TOKEN_KIND_DEFINITION\n”; OS << “undef GET_TOKEN_KIND_DEFINITION\n”; OS << “static const char * const TokNames[] = {\n”; for (Record *CC : Records.getAllDerivedDefinitions(“Token”)) { OS << ” \”” << CC->getValueAsString(“Name”)
   << “\”,\n”;
   }
   OS << “};\n\n”;
   OS << “const char *tok::getTokenName(TokenKind Kind) “
   “{\n”
   << ” if (Kind <= tok::NUM_TOKENS)\n”
   << ” return TokNames[Kind];\n”
   << ” llvm_unreachable(\”unknown TokenKind\”);\n”
   << ” return nullptr;\n”
   << “};\n\n”;
9. Next, the getPunctuatorSpelling() function is emitted. The only notable difference to the other parts is that the loop goes over all records derived from the Punctuator class. Also, a switch statement is generated instead of an array: OS << “const char ” “*tok::getPunctuatorSpelling(TokenKind ” “Kind) {\n” << ” switch (Kind) {\n”; for (Record *CC : Records.getAllDerivedDefinitions(“Punctuator”)) { OS << ” ” << CC->getValueAsString(“Name”)
   << “: return \”” << CC->getValueAsString(“Spelling”) << “\”;\n”;
   }
   OS << ” default: break;\n”
   << ” }\n”
   << ” return nullptr;\n”
   << “};\n\n”;
10. And finally, the getKeywordSpelling() function is emitted. The coding is similar to emitting getPunctuatorSpelling(). This time, the loop goes over all records of the Keyword class, and the name is again prefixed with kw_: OS << “const char *tok::getKeywordSpelling(TokenKind ” “Kind) {\n” << ” switch (Kind) {\n”; for (Record *CC : Records.getAllDerivedDefinitions(“Keyword”)) { OS << ” kw_” << CC->getValueAsString(“Name”)
    << “: return \”” << CC->getValueAsString(“Name”)
    << “\”;\n”;
    }
    OS << ” default: break;\n”
    << ” }\n”
    << ” return nullptr;\n”
    << «};\n\n»;
    OS << «endif\n»;
    }
11. The emitKeywordFilter() method is more complex than the previous methods since emitting the filter requires collecting some data from the records. The generated source code uses the std::lower_bound() function, thus implementing a binary search.
    Now, let’s make a shortcut. There can be several records of the TokenFilter class defined in the TableGen file. For demonstration purposes, just emit at most one token filter method: std::vector AllTokenFilter =
    Records.getAllDerivedDefinitionsIfDefined(
    “TokenFilter”);
    if (AllTokenFilter.empty())
    return;