Category Exploring the lli tool

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.

5. Now, we must replace the existing emit() function with a new version. Additionally, we must declare the required PassBuilder instance at the top of the function:

bool emit(StringRef Argv0, llvm::Module *M,
llvm::TargetMachine *TM,
StringRef InputFilename) {
PassBuilder PB(TM);

6. To implement the support for pass plugins given on the command line, we must loop through the list of plugin libraries given by the user and try to load the plugin. We’ll emit an error message if this fails; otherwise, we’ll register the passes: for (auto &PluginFN : PassPlugins) {
   auto PassPlugin = PassPlugin::Load(PluginFN);
   if (!PassPlugin) {
   WithColor::error(errs(), Argv0)
   << “Failed to load passes from ‘” << PluginFN << “‘. Request ignored.\n”; continue; } PassPlugin->registerPassBuilderCallbacks(PB);
   }
7. The information from the static plugin registry is used in a similar way to register those plugins with our PassBuilder instance:

define HANDLE_EXTENSION(Ext) \
getExtPluginInfo().RegisterPassBuilderCallbacks( \
PB);
include “llvm/Support/Extension.def”

8. Now, we need to declare variables for the different analysis managers. The only parameter is the debug flag: LoopAnalysisManager LAM(DebugPM);
   FunctionAnalysisManager FAM(DebugPM);
   CGSCCAnalysisManager CGAM(DebugPM);
   ModuleAnalysisManager MAM(DebugPM);
9. Next, we must populate the analysis managers with calls to the respective register method on the PassBuilder instance. Through this call, the analysis manager is populated with the default analysis passes and also runs registration callbacks. We must also make sure that the function analysis manager uses the default alias-analysis pipeline and that all analysis managers know about each other: FAM.registerPass(
   [&] { return PB.buildDefaultAAPipeline(); });
   PB.registerModuleAnalyses(MAM);
   PB.registerCGSCCAnalyses(CGAM);
   PB.registerFunctionAnalyses(FAM);
   PB.registerLoopAnalyses(LAM);
   PB.crossRegisterProxies(LAM, FAM, CGAM, MAM);
10. The MPM module pass manager holds the pass pipeline that we constructed. The instance is initialized with the debug flag: ModulePassManager MPM(DebugPM);
11. Now, we need to implement two different ways to populate the module pass manager with the pass pipeline. If the user provided a pass pipeline on the command line – that is, they have used the –passes option – then we use this as the pass pipeline: if (!PassPipeline.empty()) {
    if (auto Err = PB.parsePassPipeline(
    MPM, PassPipeline)) {
    WithColor::error(errs(), Argv0)
    << toString(std::move(Err)) << “\n”;
    return false;
    }
    }
12. Otherwise, we use the chosen optimization level to determine the pass pipeline to construct. The name of the default pass pipeline is default, and it takes the optimization level as a parameter: else {
    StringRef DefaultPass;
    switch (OptLevel) {
    case 0: DefaultPass = “default”; break;
    case 1: DefaultPass = “default”; break;
    case 2: DefaultPass = “default”; break;
    case 3: DefaultPass = “default”; break;
    case -1: DefaultPass = “default”; break;
    case -2: DefaultPass = “default”; break;
    }
    if (auto Err = PB.parsePassPipeline(
    MPM, DefaultPass)) {
    WithColor::error(errs(), Argv0)
    << toString(std::move(Err)) << “\n”;
    return false;
    }
    }
13. With that, the pass pipeline to run transformations on the IR code has been set up. After this step, we need an open file to write the result to. The system assembler and LLVM IR output are text-based, so we should set the OF_Text flag for them: std::error_code EC;
    sys::fs::OpenFlags OpenFlags = sys::fs::OF_None;
    CodeGenFileType FileType = codegen::getFileType();
    if (FileType == CGFT_AssemblyFile)
    OpenFlags |= sys::fs::OF_Text;
    auto Out = std::make_unique(
    outputFilename(InputFilename), EC, OpenFlags);
    if (EC) {
    WithColor::error(errs(), Argv0)
    << EC.message() << ‘\n’;
    return false;
    }

The runtime.c file is not instrumented because the pass checks that the special functions are not yet declared in a module.
This already looks better, but does it scale to larger programs? Let’s assume you want to build an instrumented binary of the tinylang compiler for Chapter 5. How would you do this?
You can pass compiler and linker flags on the CMake command line, which is exactly what we need. The flags for the C++ compiler are given in the CMAKE_CXX_FLAGS variable. Thus, specifying the following on the CMake command line adds the new pass to all compiler runs:

-DCMAKE_CXX_FLAGS=”-fpass-plugin=/PPProfiler.so”

Please replace with the absolute path to the shared library.
Similarly, specifying the following adds the runtime.o file to each linker invocation. Again, please replace with the absolute path to a compiled version of runtime.c:

-DCMAKE_EXE_LINKER_FLAGS=”/runtime.o”

Of course, this requires clang as the build compiler. The fastest way to make sure clang is used as the build compiler is to set the CC and CXX environment variables accordingly:

export CC=clang
export CXX=clang++

With these additional options, the CMake configuration from Chapter 5 should run as usual.
After building the tinylang executable, you can run it with the example Gcd.mod file. The ppprofile.csv file will also be written, this time with more than 44,000 lines!
Of course, having such a dataset raises the question of if you can get something useful out of it. For example, getting a list of the 10 most often called functions, together with the call count and the time spent in the function, would be useful information. Luckily, on a Unix system, you have a couple of tools that can help. Let’s build a short pipeline that matches enter events with exit events, counts the functions, and displays the top 10 functions. The awk Unix tool helps with most of these steps.
To match an enter event with an exit event, the enter event must be stored in the record associative map. When an exit event is matched, the stored enter event is looked up, and the new record is written. The emitted line contains the timestamp from the enter event, the timestamp from the exit event, and the difference between both. We must put this into the join.awk file:

BEGIN { FS = “|”; OFS = “|” }
/enter/ { record[$2] = $0 }
/exit/ { split(record[$2],val,”|”)
print val[2], val[3], $3, $3-val[3], val[4] }

To count the function calls and the execution, two associative maps, count and sum, are used. In count, the function calls are counted, while in sum, the execution time is added. In the end, the maps are dumped. You can put this into the avg.awk file:

BEGIN { FS = “|”; count[“”] = 0; sum[“”] = 0 }
{ count[$1]++; sum[$1] += $4 }
END { for (i in count) {
if (i != “”) {
print count[i], sum[i], sum[i]/count[i], I }
} }

After running these two scripts, the result can be sorted in descending order, and then the top 10 lines can be taken from the file. However, we can still improve the function names, __ppp_enter() and __ppp_exit(), which are mangled and are therefore difficult to read. Using the llvm-cxxfilt tool, the names can be demangled. The demangle.awk script is as follows:

{ cmd = “llvm-cxxfilt ” $4
(cmd) | getline name
close(cmd); $4 = name; print }

To get the top 10 function calls, you can run the following:

$ cat ppprofile.csv | awk -f join.awk | awk -f avg.awk |\
sort -nr | head -15 | awk -f demangle.awk

Here are some sample lines from the output:

446 1545581 3465.43 charinfo::isASCII(char)
409 826261 2020.2 llvm::StringRef::StringRef()
382 899471 2354.64
tinylang::Token::is(tinylang::tok::TokenKind) const
171 1561532 9131.77 charinfo::isIdentifierHead(char)

The first number is the call count of the function, the second is the cumulated execution time, and the third number is the average execution time. As explained previously, do not trust the time values, though the call counts should be accurate.
So far, we’ve implemented a new instrumentation pass, either as a plugin or as an addition to LLVM, and we used it in some real-world scenarios. In the next section, we’ll explore how to set up an optimization pipeline in our compiler.

Often, the runtime support for a feature is more complicated than adding that feature to the compiler itself. This is also true in this case. When the __ppp_enter() and __ppp_exit() functions are called, you can view this as an event. To analyze the data later, it is necessary to save the events. The basic data you would like to get is the event of the type, the name of the function and its address, and a timestamp. Without tricks, this is not as easy as it seems. Let’s give it a try.
Create a file called runtime.c with the following content:

1. You need the file I/O, standard functions, and time support. This is provided by the following includes:

include
include
include

2. For the file, a file descriptor is needed. Moreover, when the program finishes, that file descriptor should be closed properly:

static FILE *FileFD = NULL;
static void cleanup() {
if (FileFD == NULL) {
fclose(FileFD);
FileFD = NULL;
}
}

3. To simplify the runtime, only a fixed name for the output is used. If the file is not open, then open the file and register the cleanup function:

static void init() {
if (FileFD == NULL) {
FileFD = fopen(“ppprofile.csv”, “w”);
atexit(&cleanup);
}
}

4. You can call the clock_gettime() function to get a timestamp. The CLOCK_PROCESS_CPUTIME_ID parameter returns the time consumed by this process. Please note that not all systems support this parameter. You can use one of the other clocks, such as CLOCK_REALTIME, if necessary:

typedef unsigned long long Time;
static Time get_time() {
struct timespec ts;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts);
return 1000000000L * ts.tv_sec + ts.tv_nsec;
}

5. Now, it is easy to define the __ppp_enter() function. Just make sure the file is open, get the timestamp, and write the event:

void __ppp_enter(const char *FnName) {
init();
Time T = get_time();
void *Frame = __builtin_frame_address(1);
fprintf(FileFD,
// “enter|name|clock|frame”
„enter|%s|%llu|%p\n”, FnName, T, Frame);
}

6. The __ppp_exit() function only differs in terms of the event type:

void __ppp_exit(const char *FnName) {
init();
Time T = get_time();
void *Frame = __builtin_frame_address(1);
fprintf(FileFD,
// “exit|name|clock|frame”
„exit|%s|%llu|%p\n”, FnName, T, Frame);
}

That concludes a very simple implementation for runtime support. Before we try it, some remarks should be made about the implementation as it should be obvious that there are several problematic parts.
First of all, the implementation is not thread-safe since there is only one file descriptor, and access to it is not protected. Trying to use this runtime implementation with a multithreaded program will most likely lead to disturbed data in the output file.
In addition, we omitted checking the return value of the I/O-related functions, which can result in data loss.
But most importantly, the timestamp of the event is not precise. Calling a function already adds overhead, but performing I/O operations in that function makes it even worse. In principle, you can match the enter and exit events for a function and calculate the runtime of the function. However, this value is inherently flawed because it may include the time required for I/O. In summary, do not trust the times recorded here.
Despite all the flaws, this small runtime file allows us to produce some output. Compile the bitcode of the instrumented file together with the file containing the runtime code and run the resulting executable:

$ clang hello_inst.bc runtime.c
$ ./a.out

This results in a new file called ppprofile.csv in the directory that contains the following content:

$ cat ppprofile.csv
enter|main|3300868|0x1
exit|main|3760638|0x1

Cool – the new pass and the runtime seem to work!

To fully integrate the new pass into LLVM, the source of the plugin needs to be structured slightly differently. The main reason for this is that the constructor of the pass class is called from the pass registry, which requires the class interface to be put into a header file.
Like before, you must put the new pass into the Transforms component of LLVM. Begin the implementation by creating the llvm-project/llvm/include/llvm/Transforms/PPProfiler/PPProfiler.h header file. The content of that file is the class definition; put it into the llvm namespace. No other changes are required:

ifndef LLVM_TRANSFORMS_PPPROFILER_PPPROFILER_H
define LLVM_TRANSFORMS_PPPROFILER_PPPROFILER_H
include “llvm/IR/PassManager.h”
namespace llvm {
class PPProfilerIRPass
: public llvm::PassInfoMixin {
public:
llvm::PreservedAnalyses
run(llvm::Module &M, llvm::ModuleAnalysisManager &AM);
private:
void instrument(llvm::Function &F,
llvm::Function *EnterFn,
llvm::Function *ExitFn);
};
} // namespace llvm
endif

Next, copy the source file of the pass plugin, PPProfiler.cpp, into the new directory, llvm-project/llvm/lib/Transforms/PPProfiler. This file needs to be updated in the following way:

1. Since the class definition is now in a header file, you must remove the class definition from this file. At the top, add the include directive for the header file:

include “llvm/Transforms/PPProfiler/PPProfiler.h”

2. The llvmGetPassPluginInfo() function must be removed because the pass wasn’t built into a shared library of its own.
   As before, you also need to provide a CMakeLists.txt file for the build. You must declare the new pass as a new component:

add_llvm_component_library(LLVMPPProfiler
PPProfiler.cpp
LINK_COMPONENTS
Core
Support
)

After, like in the previous section, you need to include the new source directory by adding the following line to the CMakeLists.txt file in the parent directory:

add_subdirectory(PPProfiler)

Inside LLVM, the available passes are kept in the llvm/lib/Passes/ PassRegistry.def database file. You need to update this file. The new pass is a module pass, so we need to search inside the file for the section in which module passes are defined, for example, by searching for the MODULE_PASS macro. Inside this section, add the following line:

MODULE_PASS(“ppprofiler”, PPProfilerIRPass())

This database file is used in the llvm/lib/Passes/PassBuilder.cpp class. This file needs to include your new header file:

include “llvm/Transforms/PPProfiler/PPProfiler.h”

These are all required source changes based on the plugin version of the new pass.
Since you created a new LLVM component, it is also necessary to add a link dependency in the llvm/lib/Passes/CMakeLists.txt file. Under the LINK_COMPONENTS keyword, you need to add a line with the name of the new component:

PPProfiler

Et voilà – you are ready to build and install LLVM. The new pass, ppprofiler, is now available to all LLVM tools. It has been compiled into the libLLVMPPProfiler.a library and available in the build system as the PPProfiler component.
So far, we have talked about how to create a new pass. In the next section, we will examine how to use the ppprofiler pass.