# llvm-tutor **Repository Path**: sheenisme/llvm-tutor ## Basic Information - **Project Name**: llvm-tutor - **Description**: A collection of out-of-tree LLVM passes for teaching and learning - **Primary Language**: Unknown - **License**: MIT - **Default Branch**: main - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2022-07-12 - **Last Updated**: 2023-02-25 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README llvm-tutor ========= [![Build Status](https://github.com/banach-space/llvm-tutor/workflows/x86-Ubuntu/badge.svg?branch=main)](https://github.com/banach-space/llvm-tutor/actions?query=workflow%3Ax86-Ubuntu+branch%3Amain) [![Build Status](https://github.com/banach-space/llvm-tutor/workflows/x86-Darwin/badge.svg?branch=main)](https://github.com/banach-space/llvm-tutor/actions?query=workflow%3Ax86-Darwin+branch%3Amain) Example LLVM passes - based on **LLVM 15** **llvm-tutor** is a collection of self-contained reference LLVM passes. It's a tutorial that targets novice and aspiring LLVM developers. Key features: * **Out-of-tree** - builds against a binary LLVM installation (no need to build LLVM from sources) * **Complete** - includes `CMake` build scripts, LIT tests, CI set-up and documentation * **Modern** - based on the latest version of LLVM (and updated with every release) ### Overview LLVM implements a very rich, powerful and popular API. However, like many complex technologies, it can be quite daunting and overwhelming to learn and master. The goal of this LLVM tutorial is to showcase that LLVM can in fact be easy and fun to work with. This is demonstrated through a range self-contained, testable LLVM passes, which are implemented using idiomatic LLVM. This document explains how to set-up your environment, build and run the examples, and go about debugging. It contains a high-level overview of the implemented examples and contains some background information on writing LLVM passes. The source files, apart from the code itself, contain comments that will guide you through the implementation. All examples are complemented with [LIT](https://llvm.org/docs/TestingGuide.html) tests and reference [input files](https://github.com/banach-space/llvm-tutor/blob/main/inputs). Visit [**clang-tutor**](https://github.com/banach-space/clang-tutor/) if you are internested in similar tutorial for Clang. ### Table of Contents * [HelloWorld: Your First Pass](#helloworld-your-first-pass) * Part 1: **llvm-tutor** in more detail * [Development Environment](#development-environment) * [Building & Testing](#building--testing) * [Overview of the Passes](#overview-of-the-passes) * [Debugging](#debugging) * Part 2: Passes In LLVM * [About Pass Managers in LLVM](#about-pass-managers-in-llvm) * [Analysis vs Transformation Pass](#analysis-vs-transformation-pass) * [Dynamic vs Static Plugins](#dynamic-vs-static-plugins) * [Optimisation Passes Inside LLVM](#optimisation-passes-inside-llvm) * [References](#references) HelloWorld: Your First Pass =========================== The **HelloWorld** pass from [HelloWorld.cpp](https://github.com/banach-space/llvm-tutor/blob/main/HelloWorld/HelloWorld.cpp) is a self-contained *reference example*. The corresponding [CMakeLists.txt](https://github.com/banach-space/llvm-tutor/blob/main/HelloWorld/CMakeLists.txt) implements the minimum set-up for an out-of-source pass. For every function defined in the input module, **HelloWorld** prints its name and the number of arguments that it takes. You can build it like this: ```bash export LLVM_DIR= mkdir build cd build cmake -DLT_LLVM_INSTALL_DIR=$LLVM_DIR /HelloWorld/ make ``` Before you can test it, you need to prepare an input file: ```bash # Generate an LLVM test file $LLVM_DIR/bin/clang -O1 -S -emit-llvm /inputs/input_for_hello.c -o input_for_hello.ll ``` Finally, run **HelloWorld** with [**opt**](http://llvm.org/docs/CommandGuide/opt.html) (use `libHelloWorld.so` on Linux and `libHelloWorld.dylib` on Mac OS): ```bash # Run the pass $LLVM_DIR/bin/opt -load-pass-plugin ./libHelloWorld.{so|dylib} -passes=hello-world -disable-output input_for_hello.ll # Expected output (llvm-tutor) Hello from: foo (llvm-tutor) number of arguments: 1 (llvm-tutor) Hello from: bar (llvm-tutor) number of arguments: 2 (llvm-tutor) Hello from: fez (llvm-tutor) number of arguments: 3 (llvm-tutor) Hello from: main (llvm-tutor) number of arguments: 2 ``` The **HelloWorld** pass doesn't modify the input module. The `-disable-output` flag is used to prevent **opt** from printing the output bitcode file. Development Environment ======================= ## Platform Support And Requirements This project has been tested on **Ubuntu 22.04** and **Mac OS X 11.7**. In order to build **llvm-tutor** you will need: * LLVM 15 * C++ compiler that supports C++17 * CMake 3.13.4 or higher In order to run the passes, you will need: * **clang-15** (to generate input LLVM files) * [**opt**](http://llvm.org/docs/CommandGuide/opt.html) (to run the passes) There are additional requirements for tests (these will be satisfied by installing LLVM 15): * [**lit**](https://llvm.org/docs/CommandGuide/lit.html) (aka **llvm-lit**, LLVM tool for executing the tests) * [**FileCheck**](https://llvm.org/docs/CommandGuide/FileCheck.html) (LIT requirement, it's used to check whether tests generate the expected output) ## Installing LLVM 15 on Mac OS X On Darwin you can install LLVM 15 with [Homebrew](https://brew.sh/): ```bash brew install llvm@15 ``` If you already have an older version of LLVM installed, you can upgrade it to LLVM 15 like this: ```bash brew upgrade llvm ``` Once the installation (or upgrade) is complete, all the required header files, libraries and tools will be located in `/usr/local/opt/llvm/`. ## Installing LLVM 15 on Ubuntu On Ubuntu Jammy Jellyfish, you can [install modern LLVM](https://blog.kowalczyk.info/article/k/how-to-install-latest-clang-6.0-on-ubuntu-16.04-xenial-wsl.html) from the official [repository](http://apt.llvm.org/): ```bash wget -O - https://apt.llvm.org/llvm-snapshot.gpg.key | sudo apt-key add - sudo apt-add-repository "deb http://apt.llvm.org/jammy/ llvm-toolchain-jammy-15 main" sudo apt-get update sudo apt-get install -y llvm-15 llvm-15-dev llvm-15-tools clang-15 ``` This will install all the required header files, libraries and tools in `/usr/lib/llvm-15/`. ## Building LLVM 15 From Sources Building from sources can be slow and tricky to debug. It is not necessary, but might be your preferred way of obtaining LLVM 15. The following steps will work on Linux and Mac OS X: ```bash git clone https://github.com/llvm/llvm-project.git cd llvm-project git checkout release/15.x mkdir build cd build cmake -DCMAKE_BUILD_TYPE=Release -DLLVM_TARGETS_TO_BUILD=host -DLLVM_ENABLE_PROJECTS=clang /llvm/ cmake --build . ``` For more details read the [official documentation](https://llvm.org/docs/CMake.html). Building & Testing =================== ## Building You can build **llvm-tutor** (and all the provided pass plugins) as follows: ```bash cd cmake -DLT_LLVM_INSTALL_DIR= make ``` The `LT_LLVM_INSTALL_DIR` variable should be set to the root of either the installation or build directory of LLVM 15. It is used to locate the corresponding `LLVMConfig.cmake` script that is used to set the include and library paths. ## Testing In order to run **llvm-tutor** tests, you need to install **llvm-lit** (aka **lit**). It's not bundled with LLVM 15 packages, but you can install it with **pip**: ```bash # Install lit - note that this installs lit globally pip install lit ``` Running the tests is as simple as: ```bash $ lit /test ``` Voilà! You should see all tests passing. ## LLVM Plugins as shared objecs In **llvm-tutor** every LLVM pass is implemented in a separate shared object (you can learn more about shared objects [here](http://www.yolinux.com/TUTORIALS/LibraryArchives-StaticAndDynamic.html)). These shared objects are essentially dynamically loadable plugins for **opt**. All plugins are built in the `/lib` directory. Note that the extension of dynamically loaded shared objects differs between Linux and Mac OS. For example, for the **HelloWorld** pass you will get: * `libHelloWorld.so` on Linux * `libHelloWorld.dylib` on MacOS. For the sake of consistency, in this README.md file all examples use the `*.so` extension. When working on Mac OS, use `*.dylib` instead. Overview of The Passes ====================== The available passes are categorised as either Analysis, Transformation or CFG. The difference between Analysis and Transformation passes is rather self-explanatory ([here](#analysis-vs-transformation-pass) is a more technical breakdown). A CFG pass is simply a Transformation pass that modifies the Control Flow Graph. This is frequently a bit more complex and requires some extra bookkeeping, hence a dedicated category. In the following table the passes are grouped thematically and ordered by the level of complexity. | Name | Description | Category | |-----------|-----------------|------| |[**HelloWorld**](#helloworld-your-first-pass) | visits all functions and prints their names | Analysis | |[**OpcodeCounter**](#opcodecounter) | prints a summary of LLVM IR opcodes in the input module | Analysis | |[**InjectFuncCall**](#injectfunccall) | instruments the input module by inserting calls to `printf` | Transformation | |[**StaticCallCounter**](#staticcallcounter) | counts direct function calls at compile-time (static analysis) | Analysis | |[**DynamicCallCounter**](#dynamiccallcounter) | counts direct function calls at run-time (dynamic analysis) | Transformation | |[**MBASub**](#mbasub) | obfuscate integer `sub` instructions | Transformation | |[**MBAAdd**](#mbaadd) | obfuscate 8-bit integer `add` instructions | Transformation | |[**FindFCmpEq**](#findfcmpeq) | finds floating-point equality comparisons | Analysis | |[**ConvertFCmpEq**](#convertfcmpeq) | converts direct floating-point equality comparisons to difference comparisons | Transformation | |[**RIV**](#riv) | finds reachable integer values for each basic block | Analysis | |[**DuplicateBB**](#duplicatebb) | duplicates basic blocks, requires **RIV** analysis results | CFG | |[**MergeBB**](#mergebb) | merges duplicated basic blocks | CFG | Once you've [built](#building--testing) this project, you can experiment with every pass separately. All passes, except for [**HelloWorld**](#helloworld-your-first-pass), are described in more details below. LLVM passes work with LLVM IR files. You can generate one like this: ```bash export LLVM_DIR= # Textual form $LLVM_DIR/bin/clang -O1 -emit-llvm input.c -S -o out.ll # Binary/bit-code form $LLVM_DIR/bin/clang -O1 -emit-llvm input.c -c -o out.bc ``` It doesn't matter whether you choose the binary, `*.bc` (default), or textual/LLVM assembly form (`.ll`, requires the `-S` flag). Obviously, the latter is more human-readable. Similar logic applies to **opt** - by default it generates `*.bc` files. You can use `-S` to have the output written as `*.ll` files instead. Note that `clang` adds the `optnone` [function attribute](https://llvm.org/docs/LangRef.html#function-attributes) if either * no optimization level is specified, or * `-O0` is specified. If you want to compile at `-O0`, you need to specify `-O0 -Xclang -disable-O0-optnone` or define a static [isRequired](https://llvm.org/docs/WritingAnLLVMNewPMPass.html#required-passes) method in your pass. Alternatively, you can specify `-O1` or higher. Otherwise the new pass manager will register the pass but your pass will not be executed. As noted [earlier](#llvm-plugins-as-shared-objecs), all examples in this file use the `*.so` extension for pass plugins. When working on Mac OS, use `*.dylib` instead. ## OpcodeCounter **OpcodeCounter** is an Analysis pass that prints a summary of the [LLVM IR opcodes](https://github.com/llvm/llvm-project/blob/release/15.x/llvm/lib/IR/Instruction.cpp#L347-L426) encountered in every function in the input module. This pass can be [run automatically](#auto-registration-with-optimisation-pipelines) with one of the pre-defined optimisation pipelines. However, let's use our tried and tested method first. ### Run the pass We will use [input_for_cc.c](https://github.com/banach-space/llvm-tutor/blob/main/inputs/input_for_cc.c) to test **OpcodeCounter**. Since **OpcodeCounter** is an Analysis pass, we want **opt** to _print_ its results. To this end, we will use a [printing pass](#printing-passes-for-the-new-pass-manager) that corresponds to **OpcodeCounter**. This pass is called `print`. No extra arguments are needed, but it's a good idea to add `-disable-output` to prevent **opt** from printing the output LLVM IR module - we are only interested in the results of the analysis rather than the module itself. In fact, as this pass does not modify the input IR, the output module would be identical to the input anyway. ```bash export LLVM_DIR= # Generate an LLVM file to analyze $LLVM_DIR/bin/clang -emit-llvm -c /inputs/input_for_cc.c -o input_for_cc.bc # Run the pass through opt $LLVM_DIR/bin/opt -load-pass-plugin /lib/libOpcodeCounter.so --passes="print" -disable-output input_for_cc.bc ``` For `main`, **OpcodeCounter** prints the following summary (note that when running the pass, a summary for other functions defined in `input_for_cc.bc` is also printed): ``` ================================================= LLVM-TUTOR: OpcodeCounter results for `main` ================================================= OPCODE #N TIMES USED ------------------------------------------------- load 2 br 4 icmp 1 add 1 ret 1 alloca 2 store 4 call 4 ------------------------------------------------- ``` ### Auto-registration with optimisation pipelines You can run **OpcodeCounter** by simply specifying an optimisation level (e.g. `-O{1|2|3|s}`). This is achieved through auto-registration with the existing optimisation pass pipelines. Note that you still have to specify the plugin file to be loaded: ```bash $LLVM_DIR/bin/opt -load-pass-plugin /lib/libOpcodeCounter.so --passes='default' input_for_cc.bc ``` In this example I used the New Pass Manager (the plugin file was specified with `-load-pass-plugin` rather than `-load`). The auto-registration also works with the Legacy Pass Manager: ```bash $LLVM_DIR/bin/opt -load /lib/libOpcodeCounter.so -O1 input_for_cc.bc ``` This is implemented in [OpcodeCounter.cpp](https://github.com/banach-space/llvm-tutor/blob/main/lib/OpcodeCounter.cpp), on [line 122](https://github.com/banach-space/llvm-tutor/blob/main/lib/OpcodeCounter.cpp#L122-L126) for the New PM, and on [line 159](https://github.com/banach-space/llvm-tutor/blob/main/lib/OpcodeCounter.cpp#L159-L164) for the Legacy PM. This [section](#about-pass-managers-in-llvm) contains more information about the pass managers in LLVM. ## InjectFuncCall This pass is a _HelloWorld_ example for _code instrumentation_. For every function defined in the input module, **InjectFuncCall** will add (_inject_) the following call to [`printf`](https://en.cppreference.com/w/cpp/io/c/fprintf): ```C printf("(llvm-tutor) Hello from: %s\n(llvm-tutor) number of arguments: %d\n", FuncName, FuncNumArgs) ``` This call is added at the beginning of each function (i.e. before any other instruction). `FuncName` is the name of the function and `FuncNumArgs` is the number of arguments that the function takes. ### Run the pass We will use [input_for_hello.c](https://github.com/banach-space/llvm-tutor/blob/main/inputs/input_for_hello.c) to test **InjectFuncCall**: ```bash export LLVM_DIR= # Generate an LLVM file to analyze $LLVM_DIR/bin/clang -O0 -emit-llvm -c /inputs/input_for_hello.c -o input_for_hello.bc # Run the pass through opt - New PM $LLVM_DIR/bin/opt -load-pass-plugin /lib/libInjectFuncCall.so --passes="inject-func-call" input_for_hello.bc -o instrumented.bin # Run the pass through opt - Legacy PM $LLVM_DIR/bin/opt -enable-new-pm=0 -load /lib/libInjectFuncCall.so -legacy-inject-func-call input_for_hello.bc -o instrumented.bin ``` This generates `instrumented.bin`, which is the instrumented version of `input_for_hello.bc`. In order to verify that **InjectFuncCall** worked as expected, you can either check the output file (and verify that it contains extra calls to `printf`) or run it: ``` $LLVM_DIR/bin/lli instrumented.bin (llvm-tutor) Hello from: main (llvm-tutor) number of arguments: 2 (llvm-tutor) Hello from: foo (llvm-tutor) number of arguments: 1 (llvm-tutor) Hello from: bar (llvm-tutor) number of arguments: 2 (llvm-tutor) Hello from: foo (llvm-tutor) number of arguments: 1 (llvm-tutor) Hello from: fez (llvm-tutor) number of arguments: 3 (llvm-tutor) Hello from: bar (llvm-tutor) number of arguments: 2 (llvm-tutor) Hello from: foo (llvm-tutor) number of arguments: 1 ``` ### InjectFuncCall vs HelloWorld You might have noticed that **InjectFuncCall** is somewhat similar to [**HelloWorld**](#helloworld-your-first-pass). In both cases the pass visits all functions, prints their names and the number of arguments. The difference between the two passes becomes quite apparent when you compare the output generated for the same input file, e.g. `input_for_hello.c`. The number of times `Hello from` is printed is either: * once per every function call in the case of **InjectFuncCall**, or * once per function definition in the case of **HelloWorld**. This makes perfect sense and hints how different the two passes are. Whether to print `Hello from` is determined at either: * run-time for **InjectFuncCall**, or * compile-time for **HelloWorld**. Also, note that in the case of **InjectFuncCall** we had to first run the pass with **opt** and then execute the instrumented IR module in order to see the output. For **HelloWorld** it was sufficient to run the pass with **opt**. ## StaticCallCounter The **StaticCallCounter** pass counts the number of _static_ function calls in the input LLVM module. _Static_ refers to the fact that these function calls are compile-time calls (i.e. visible during the compilation). This is in contrast to _dynamic_ function calls, i.e. function calls encountered at run-time (when the compiled module is run). The distinction becomes apparent when analysing functions calls within loops, e.g.: ```c for (i = 0; i < 10; i++) foo(); ``` Although at run-time `foo` will be executed 10 times, **StaticCallCounter** will report only 1 function call. This pass will only consider direct functions calls. Functions calls via function pointers are not taken into account. ### Run the pass through **opt** We will use [input_for_cc.c](https://github.com/banach-space/llvm-tutor/blob/main/inputs/input_for_cc.c) to test **StaticCallCounter**: ```bash export LLVM_DIR= # Generate an LLVM file to analyze $LLVM_DIR/bin/clang -emit-llvm -c /inputs/input_for_cc.c -o input_for_cc.bc # Run the pass through opt - Legacy PM $LLVM_DIR/bin/opt -enable-new-pm=0 -load /lib/libStaticCallCounter.so -legacy-static-cc -analyze input_for_cc.bc ``` You should see the following output: ``` ================================================= LLVM-TUTOR: static analysis results ================================================= NAME #N DIRECT CALLS ------------------------------------------------- foo 3 bar 2 fez 1 ------------------------------------------------- ``` Note the extra command line option above: `-analyze`. It's required to inform **opt** to print the results of the analysis to `stdout`. We discussed this option in more detail [here](#run-the-pass). ### Run the pass through `static` You can run **StaticCallCounter** through a standalone tool called `static`. `static` is an LLVM based tool implemented in [StaticMain.cpp](https://github.com/banach-space/llvm-tutor/blob/main/tools/StaticMain.cpp). It is a command line wrapper that allows you to run **StaticCallCounter** without the need for **opt**: ```bash /bin/static input_for_cc.bc ``` It is an example of a relatively basic static analysis tool. Its implementation demonstrates how basic pass management in LLVM works (i.e. it handles that for itself instead of relying on **opt**). ## DynamicCallCounter The **DynamicCallCounter** pass counts the number of _run-time_ (i.e. encountered during the execution) function calls. It does so by inserting call-counting instructions that are executed every time a function is called. Only calls to functions that are _defined_ in the input module are counted. This pass builds on top of ideas presented in [**InjectFuncCall**](#injectfunccall). You may want to experiment with that example first. ### Run the pass We will use [input_for_cc.c](https://github.com/banach-space/llvm-tutor/blob/main/inputs/input_for_cc.c) to test **DynamicCallCounter**: ```bash export LLVM_DIR= # Generate an LLVM file to analyze $LLVM_DIR/bin/clang -emit-llvm -c /inputs/input_for_cc.c -o input_for_cc.bc # Instrument the input file $LLVM_DIR/bin/opt -load-pass-plugin=/lib/libDynamicCallCounter.so -passes="dynamic-cc" input_for_cc.bc -o instrumented_bin ``` This generates `instrumented.bin`, which is the instrumented version of `input_for_cc.bc`. In order to verify that **DynamicCallCounter** worked as expected, you can either check the output file (and verify that it contains new call-counting instructions) or run it: ```bash # Run the instrumented binary $LLVM_DIR/bin/lli ./instrumented_bin ``` You will see the following output: ``` ================================================= LLVM-TUTOR: dynamic analysis results ================================================= NAME #N DIRECT CALLS ------------------------------------------------- foo 13 bar 2 fez 1 main 1 ``` ### DynamicCallCounter vs StaticCallCounter The number of function calls reported by **DynamicCallCounter** and **StaticCallCounter** are different, but both results are correct. They correspond to _run-time_ and _compile-time_ function calls respectively. Note also that for **StaticCallCounter** it was sufficient to run the pass through **opt** to have the summary printed. For **DynamicCallCounter** we had to _run the instrumented binary_ to see the output. This is similar to what we observed when comparing [HelloWorld and InjectFuncCall](#injectfunccall-vs-helloworld). ## Mixed Boolean Arithmetic Transformations These passes implement [mixed boolean arithmetic](https://tel.archives-ouvertes.fr/tel-01623849/document) transformations. Similar transformation are often used in code obfuscation (you may also know them from [Hacker's Delight](https://www.amazon.co.uk/Hackers-Delight-Henry-S-Warren/dp/0201914654)) and are a great illustration of what and how LLVM passes can be used for. Similar transformations are possible at the source-code level. The relevant Clang plugins are available in [**clang-tutor**](https://github.com/banach-space/clang-tutor#obfuscator). ### MBASub The **MBASub** pass implements this rather basic expression: ``` a - b == (a + ~b) + 1 ``` Basically, it replaces all instances of integer `sub` according to the above formula. The corresponding LIT tests verify that both the formula and that the implementation are correct. #### Run the pass We will use [input_for_mba_sub.c](https://github.com/banach-space/llvm-tutor/blob/main/inputs/input_for_mba_sub.c) to test **MBASub**: ```bash export LLVM_DIR= $LLVM_DIR/bin/clang -emit-llvm -S /inputs/input_for_mba_sub.c -o input_for_sub.ll $LLVM_DIR/bin/opt -load-pass-plugin=/lib/libMBASub.so -passes="mba-add" -S input_for_sub.ll -o out.ll ``` ### MBAAdd The **MBAAdd** pass implements a slightly more involved formula that is only valid for 8 bit integers: ``` a + b == (((a ^ b) + 2 * (a & b)) * 39 + 23) * 151 + 111 ``` Similarly to `MBASub`, it replaces all instances of integer `add` according to the above identity, but only for 8-bit integers. The LIT tests verify that both the formula and the implementation are correct. #### Run the pass We will use [input_for_add.c](https://github.com/banach-space/llvm-tutor/blob/main/inputs/input_for_mba.c) to test **MBAAdd**: ```bash export LLVM_DIR= $LLVM_DIR/bin/clang -O1 -emit-llvm -S /inputs/input_for_mba.c -o input_for_mba.ll $LLVM_DIR/bin/opt -load-pass-plugin=/lib/libMBAAdd.so -passes="mba-add" -S input_for_mba.ll -o out.ll ``` You can also specify the level of _obfuscation_ on a scale from `0.0` to `1.0`, with `0.0` corresponding to no obfuscation and `1.0` meaning that all `add` instructions are to be replaced with the formula above. However, for this extra functionality to work you will have to use the Legacy Pass Manager: ```bash $LLVM_DIR/bin/opt -load /lib/libMBAAdd.so -legacy-mba-add -mba-ratio=0.3 /inputs/input_for_mba.c -o out.ll ``` ## RIV **RIV** is an analysis pass that for each [basic block](http://llvm.org/docs/ProgrammersManual.html#the-basicblock-class) BB in the input function computes the set reachable integer values, i.e. the integer values that are visible (i.e. can be used) in BB. Since the pass operates on the LLVM IR representation of the input file, it takes into account all values that have [integer type](https://llvm.org/docs/LangRef.html#integer-type) in the [LLVM IR](https://llvm.org/docs/LangRef.html) sense. In particular, since at the LLVM IR level booleans are represented as 1-bit wide integers (i.e. `i1`), you will notice that booleans are also included in the result. This pass demonstrates how to request results from other analysis passes in LLVM. In particular, it relies on the [Dominator Tree](https://en.wikipedia.org/wiki/Dominator_(graph_theory)) analysis pass from LLVM, which is used to obtain the dominance tree for the basic blocks in the input function. ### Run the pass We will use [input_for_riv.c](https://github.com/banach-space/llvm-tutor/blob/main/inputs/input_for_riv.c) to test **RIV**: ```bash export LLVM_DIR= # Generate an LLVM file to analyze $LLVM_DIR/bin/clang -emit-llvm -S -O1 /inputs/input_for_riv.c -o input_for_riv.ll # Run the pass through opt - Legacy PM $LLVM_DIR/bin/opt -load-pass-plugin /lib/libRIV.so -passes="print" -disable-output input_for_riv.ll ``` You will see the following output: ``` ================================================= LLVM-TUTOR: RIV analysis results ================================================= BB id Reachable Ineger Values ------------------------------------------------- BB %entry i32 %a i32 %b i32 %c BB %if.then %add = add nsw i32 %a, 123 %cmp = icmp sgt i32 %a, 0 i32 %a i32 %b i32 %c BB %if.end8 %add = add nsw i32 %a, 123 %cmp = icmp sgt i32 %a, 0 i32 %a i32 %b i32 %c BB %if.then2 %mul = mul nsw i32 %b, %a %div = sdiv i32 %b, %c %cmp1 = icmp eq i32 %mul, %div %add = add nsw i32 %a, 123 %cmp = icmp sgt i32 %a, 0 i32 %a i32 %b i32 %c BB %if.else %mul = mul nsw i32 %b, %a %div = sdiv i32 %b, %c %cmp1 = icmp eq i32 %mul, %div %add = add nsw i32 %a, 123 %cmp = icmp sgt i32 %a, 0 i32 %a i32 %b i32 %c ``` Note the extra command line option above: `-analyze`. It's required to inform **opt** to print the results of the analysis to `stdout`. We discussed this option in more detail [here](#run-the-pass). ## DuplicateBB This pass will duplicate all basic blocks in a module, with the exception of basic blocks for which there are no reachable integer values (identified through the **RIV** pass). An example of such a basic block is the entry block in a function that: * takes no arguments and * is embedded in a module that defines no global values. Basic blocks are duplicated by first inserting an `if-then-else` construct and then cloning all the instructions from the original basic block (with the exception of [PHI nodes](https://en.wikipedia.org/wiki/Static_single_assignment_form)) into two new basic blocks (clones of the original basic block). The `if-then-else` construct is introduced as a non-trivial mechanism that decides which of the cloned basic blocks to branch to. This condition is equivalent to: ```cpp if (var == 0) goto clone 1 else goto clone 2 ``` in which: * `var` is a randomly picked variable from the `RIV` set for the current basic block * `clone 1` and `clone 2` are labels for the cloned basic blocks. The complete transformation looks like this: ```c BEFORE: AFTER: ------- ------ [ if-then-else ] DuplicateBB / \ [ BB ] ------------> [clone 1] [clone 2] \ / [ tail ] LEGEND: ------- [BB] - the original basic block [if-then-else] - a new basic block that contains the if-then-else statement (inserted by DuplicateBB) [clone 1|2] - two new basic blocks that are clones of BB (inserted by DuplicateBB) [tail] - the new basic block that merges [clone 1] and [clone 2] (inserted by DuplicateBB) ``` As depicted above, **DuplicateBB** replaces qualifying basic blocks with 4 new basic blocks. This is implemented through LLVM's [SplitBlockAndInsertIfThenElse](https://github.com/llvm/llvm-project/blob/release/15.x/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h#L467). **DuplicateBB** does all the necessary preparation and clean-up. In other words, it's an elaborate wrapper for LLVM's `SplitBlockAndInsertIfThenElse`. ### Run the pass This pass depends on the **RIV** pass, which also needs be loaded in order for **DuplicateBB** to work. Let's use [input_for_duplicate_bb.c](https://github.com/banach-space/llvm-tutor/blob/main/inputs/input_for_duplicate_bb.c) as our sample input. First, generate the LLVM file: ```bash export LLVM_DIR= $LLVM_DIR/bin/clang -emit-llvm -S -O1 /inputs/input_for_duplicate_bb.c -o input_for_duplicate_bb.ll ``` Function `foo` in `input_for_duplicate_bb.ll` should look like this (all metadata has been stripped): ```llvm define i32 @foo(i32) { ret i32 1 } ``` Note that there's only one basic block (the _entry_ block) and that `foo` takes one argument (this means that the result from **RIV** will be a non-empty set). We will now apply **DuplicateBB** to `foo`: ```bash $LLVM_DIR/bin/opt -load-pass-plugin /lib/libRIV.so -load-pass-plugin /lib/libDuplicateBB.so -passes=duplicate-bb -S input_for_duplicate_bb.ll -o duplicate.ll ``` After the instrumentation `foo` will look like this (all metadata has been stripped): ```llvm define i32 @foo(i32) { lt-if-then-else-0: %2 = icmp eq i32 %0, 0 br i1 %2, label %lt-if-then-0, label %lt-else-0 clone-1-0: br label %lt-tail-0 clone-2-0: br label %lt-tail-0 lt-tail-0: ret i32 1 } ``` There are four basic blocks instead of one. All new basic blocks end with a numeric id of the original basic block (`0` in this case). `lt-if-then-else-0` contains the new `if-then-else` condition. `clone-1-0` and `clone-2-0` are clones of the original basic block in `foo`. `lt-tail-0` is the extra basic block that's required to merge `clone-1-0` and `clone-2-0`. ## MergeBB **MergeBB** will merge qualifying basic blocks that are identical. To some extent, this pass reverts the transformations introduced by **DuplicateBB**. This is illustrated below: ```c BEFORE: AFTER DuplicateBB: AFTER MergeBB: ------- ------------------ -------------- [ if-then-else ] [ if-then-else* ] DuplicateBB / \ MergeBB | [ BB ] ------------> [clone 1] [clone 2] --------> [ clone ] \ / | [ tail ] [ tail* ] LEGEND: ------- [BB] - the original basic block [if-then-else] - a new basic block that contains the if-then-else statement (**DuplicateBB**) [clone 1|2] - two new basic blocks that are clones of BB (**DuplicateBB**) [tail] - the new basic block that merges [clone 1] and [clone 2] (**DuplicateBB**) [clone] - [clone 1] and [clone 2] after merging, this block should be very similar to [BB] (**MergeBB**) [label*] - [label] after being updated by **MergeBB** ``` Recall that **DuplicateBB** replaces all qualifying basic block with four new basic blocks, two of which are clones of the original block. **MergeBB** will merge those two clones back together, but it will not remove the remaining two blocks added by **DuplicateBB** (it will update them though). ### Run the pass Let's use the following IR implementation of `foo` as input. Note that basic blocks 3 and 5 are identical and can safely be merged: ```llvm define i32 @foo(i32) { %2 = icmp eq i32 %0, 19 br i1 %2, label %3, label %5 ;