Example LLVM passes - based on LLVM 9
llvm-tutor is a collection of self-contained reference LLVM passes. It's a tutorial that targets novice and aspiring LLVM developers. Key features:
- Complete - includes
CMakebuild scripts, LIT tests and CI set-up
- Out of source - builds against a binary LLVM installation (no need to build LLVM from sources)
- Modern - based on the latest version of LLVM (and updated with every release)
The source files contain comments that will guide you through the implementation and the LIT tests verify that each pass works as expected. This document explains how to get started.
Table of Contents
- Development Environment
- Building & Testing
- Overview Of The Passes
- About Pass Managers in LLVM
- Credits & References
For each function in a module, HelloWord prints its name and the number of arguments that it takes. You can build it like this:
export LLVM_DIR=<installation/dir/of/llvm/9> mkdir build cd build cmake -DLT_LLVM_INSTALL_DIR=$LLVM_DIR <source/dir/llvm/tutor>/HelloWorld/ make
Before you can test it, you need to prepare an input file:
# Generate an llvm test file $LLVM_DIR/bin/clang -S -emit-llvm <source/dir/llvm/tutor/>inputs/input_for_hello.c -o input_for_hello.ll
Finally, run HelloWorld with opt:
# Run the pass on the llvm file $LLVM_DIR/bin/opt -load-pass-plugin libHelloWorld.dylib -passes=hello-world -disable-output input_for_hello.ll # The expected output Visiting: foo (takes 1 args) Visiting: bar (takes 2 args) Visiting: fez (takes 3 args) Visiting: main (takes 2 args)
The HelloWorld pass doesn't modify the input module. The
flag is used to prevent opt from printing the output bitcode file.
Platform Support And Requirements
This project has been tested on Linux 18.04 and Mac OS X 10.14.4. In order to build llvm-tutor you will need:
- LLVM 9
- C++ compiler that supports C++14
- CMake 3.4.3 or higher
In order to run the passes, you will need:
- clang-9 (to generate input LLVM files)
- opt (to run the passes)
There are additional requirements for tests (these will be satisfied by installing LLVM-9):
- lit (aka llvm-lit, LLVM tool for executing the tests)
- FileCheck (LIT requirement, it's used to check whether tests generate the expected output)
Installing LLVM-9 on Mac OS X
On Darwin you can install LLVM 9 with Homebrew:
brew install llvm@9
This will install all the required header files, libraries and tools in
Installing LLVM-9 on Ubuntu
wget -O - https://apt.llvm.org/llvm-snapshot.gpg.key | sudo apt-key add - sudo apt-add-repository "deb http://apt.llvm.org/bionic/ llvm-toolchain-bionic-9 main" sudo apt-get update sudo apt-get install -y llvm-9 llvm-9-dev clang-9 llvm-9-tools
This will install all the required header files, libraries and tools in
Building LLVM-9 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-9. The following steps will work on Linux and Mac OS X:
git clone https://github.com/llvm/llvm-project.git cd llvm-project git checkout release/9.x mkdir build cd build cmake -DCMAKE_BUILD_TYPE=Release -DLLVM_TARGETS_TO_BUILD=X86 <llvm-project/root/dir>/llvm/ cmake --build .
For more details read the official documentation.
Building & Testing
You can build llvm-tutor (and all the provided passes) as follows:
cd <build/dir> cmake -DLT_LLVM_INSTALL_DIR=<installation/dir/of/llvm/9> <source/dir/llvm/tutor> make
LT_LLVM_INSTALL_DIR variable should be set to the root of either the
installation or build directory of LLVM 9. It is used to locate the
LLVMConfig.cmake script that is used to set the include and
In order to run the tests, you need to install llvm-lit (aka lit). It's not bundled with LLVM 9 packages, but you can install it with pip:
# Install lit - note that this installs lit globally pip install lit
Running the tests is as simple as:
$ lit <build_dir>/test
Voilà! You should see all tests passing.
Overview of The Passes
- HelloWorld - prints the functions in the input module and prints the number of arguments for each
- InjectFuncCall - instruments
the input module by inserting calls to
- StaticCallCounter - counts direct function calls at compile time (only static calls, pure analysis pass)
- DynamicCallCounter - counts direct function calls at run-time ( analysis through instrumentation)
- MBASub - code transformation for integer
subinstructions (transformation pass, parametrisable)
- MBAAdd - code transformation for 8-bit integer
addinstructions (transformation pass, parametrisable)
- RIV - finds reachable integer values for each basic block (analysis pass)
- DuplicateBB - duplicates basic blocks, requires RIV analysis results (transformation pass, parametrisable)
Once you've built this project, you can experiment with
every pass separately. It is assumed that you have
PATH. All passes work with LLVM files. You can generate one like
export LLVM_DIR=<installation/dir/of/llvm/9> # Textual form $LLVM_DIR/bin/clang -emit-llvm input.c -S -o out.ll # Binary/bit-code form $LLVM_DIR/bin/clang -emit-llvm input.c -o out.bc
It doesn't matter whether you choose the binary (without
-S) or textual
-S), but obviously the latter is more human-friendly. All passes,
except for HelloWorld, are described below.
Inject Calls To Printf (InjectFuncCall)
For every function defined in the input module,
InjectFuncCall will add
(inject) the following call to
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
FuncName is the name of the function and
FuncNumArgs is the
number of arguments that the function takes.
This pass is a HelloWorld example for code instrumentation. You can test it as follows:
export LLVM_DIR=<installation/dir/of/llvm/9> # Generate an LLVM file to analyze $LLVM_DIR/bin/clang -emit-llvm -c <source_dir>/inputs/input_for_inject.c -o input_for_inject.bc # Run the pass through opt $LLVM_DIR/bin/opt -load <build_dir>/lib/libInjectFuncCall.dylib -legacy-inject-func-call input_for_inject.bc -o instrumented.bin $LLVM_DIR/bin/lli instrumented.bin 123
instrumented.bin will print the following output:
(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
As you can see the output is similar to what HelloWorld generates, but the implementation is completely different.
Count Compile Time Function Calls (StaticCallCounter)
StaticCallCounter will count the number of function calls in the input
LLVM file that are visible during the compilation (i.e. if a function is
called within a loop, that counts as one call). Only direct function calls are
considered (TODO: Expand).
export LLVM_DIR=<installation/dir/of/llvm/9> # Generate an LLVM file to analyze $LLVM_DIR/bin/clang -emit-llvm -c <source_dir>/inputs/input_for_cc.c -o input_for_cc.bc # Run the pass through opt $LLVM_DIR/bin/opt -load <build_dir>/lib/libStaticCallCounter.dylib -legacy-static-cc -analyze input_for_cc.bc
static executable is a command line wrapper that allows you to run
StaticCallCounter without the need for
Count Run-Time Function Calls (DynamicCallCounter)
DynamicCallCounter will count the number of run-time function calls. It does
so by instrumenting the input LLVM file - it inserts call-counting instructions
that are executed every time a function is called. This pass will only count
calls to functions that are defined in the input module are counted.
Although the primary goal of this pass is to analyse function calls, it also modifies the input file. Therefore it is a transformation/instrumentation pass. You can test it with one of the provided examples, e.g.:
export LLVM_DIR=<installation/dir/of/llvm/9> # Generate an LLVM file to analyze $LLVM_DIR/bin/clang -emit-llvm -c <source_dir>/inputs/input_for_cc.c -o input_for_cc.bc # Instrument the input file $LLVM_DIR/bin/opt -load <build_dir>/lib/libDynamicCallCounter.dylib -legacy-dynamic-cc input_for_cc.bc -o instrumented_bin # Run the instrumented binary ./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
If you are interested in a more introductory example for code instrumentation, you may want experiment with InjectFuncCall first.
Mixed Boolean Arithmetic Transformations
These passes implement mixed boolean arithmetic transformations. Similar transformation are often used in code obfuscation (you may also know them from Hacker's Delight) and are a great illustration of what and how LLVM passes can be used for.
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. You can run this pass as follows:
export LLVM_DIR=<installation/dir/of/llvm/9> $LLVM_DIR/bin/clang -emit-llvm -S inputs/input_for_mba_sub.c -o input_for_sub.ll $LLVM_DIR/bin/opt -load <build_dir>/lib/libMBASub.so -legacy-mba-sub input_for_sub.ll -o out.ll
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
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. You can run MBAAdd like this:
export LLVM_DIR=<installation/dir/of/llvm/9> $LLVM_DIR/bin/clang -O1 -emit-llvm -S inputs/input_for_mba.c -o input_for_mba.ll $LLVM_DIR/bin/opt -load <build_dir>/lib/libMBAAdd.so -legacy-mba-add input_for_mba.ll -o out.ll
You can also specify the level of obfuscation on a scale of
0 corresponding to no obfuscation and
1 meaning that all
are to be replaced with
(((a ^ b) + 2 * (a & b)) * 39 + 23) * 151 + 111, e.g.:
$LLVM_DIR/bin/opt -load <build_dir>/lib/libMBAAdd.so -legacy-mba-add -mba-ratio=0.3 inputs/input_for_mba.c -o out.ll
Reachable Integer Values (RIV)
For each basic block in a module, RIV calculates the reachable integer values (i.e. values that can be used in the particular basic block). There are a few LIT tests that verify that indeed this is correct. You can run this pass as follows:
export LLVM_DIR=<installation/dir/of/llvm/9> $LLVM_DIR/bin/opt -load <build_dir>/lib/libRIV.so -riv inputs/input_for_riv.c
Note that this pass, unlike previous passes, will produce information only about the IR representation of the original module. It won't be very useful if trying to understand the original C or C++ input file.
Duplicate Basic Blocks (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.
This pass depends on the RIV pass, hence you need to load it too in order for DuplicateBB to work:
export LLVM_DIR=<installation/dir/of/llvm/9> $LLVM_DIR/bin/opt -load <build_dir>/lib/libRIV.so -load <build_dir>/lib/libDuplicateBB.so -riv inputs/input_for_duplicate_bb.c
Basic blocks are duplicated by inserting an
if-then-else construct and
cloning all the instructions (with the exception of PHI
nodes) into the
export LLVM_DIR=<installation/dir/of/llvm/9> $LLVM_DIR/bin/clang -emit-llvm -S -O1 inputs/input_for_mba.c -o input_for_mba.ll $LLVM_DIR/bin/opt -load-pass-plugin <build_dir>/lib/libMBAAdd.dylib -passes=mba-add input_for_mba.ll -debug-only=mba-add -stats -o out.ll
-stats flags in the command line - that's
what enables the following output:
%12 = add i8 %1, %0 -> <badref> = add i8 111, %11 %20 = add i8 %12, %2 -> <badref> = add i8 111, %19 %28 = add i8 %20, %3 -> <badref> = add i8 111, %27 ===-------------------------------------------------------------------------=== ... Statistics Collected ... ===-------------------------------------------------------------------------=== 3 mba-add - The # of substituted instructions
As you can see, you get a nice summary from MBAAdd. In many cases this will be sufficient to understand what might be going wrong.
For tricker issues just use a debugger. Below I demonstrate how to debug
MBAAdd. More specifically, how to set up a breakpoint on entry
MBAAdd::run. Hopefully that will be sufficient for you to start.
Mac OS X
The default debugger on OS X is LLDB. You will normally use it like this:
export LLVM_DIR=<installation/dir/of/llvm/9> $LLVM_DIR/bin/clang -emit-llvm -S -O1 inputs/input_for_mba.c -o input_for_mba.ll lldb -- $LLVM_DIR/bin/opt -load-pass-plugin <build_dir>/lib/libMBAAdd.dylib -passes=mba-add input_for_mba.ll -o out.ll (lldb) breakpoint set --name MBAAdd::run (lldb) process launch
or, equivalently, by using LLDBs aliases:
export LLVM_DIR=<installation/dir/of/llvm/9> $LLVM_DIR/bin/clang -emit-llvm -S -O1 inputs/input_for_mba.c -o input_for_mba.ll lldb -- $LLVM_DIR/bin/opt -load-pass-plugin <build_dir>/lib/libMBAAdd.dylib -passes=mba-add input_for_mba.ll -o out.ll (lldb) b MBAAdd::run (lldb) r
At this point, LLDB should break at the entry to
On most Linux systems, GDB is the most popular debugger. A typical session will look like this:
export LLVM_DIR=<installation/dir/of/llvm/9> $LLVM_DIR/bin/clang -emit-llvm -S -O1 inputs/input_for_mba.c -o input_for_mba.ll gdb --args $LLVM_DIR/bin/opt -load-pass-plugin <build_dir>/lib/libMBAAdd.so -passes=mba-add input_for_mba.ll -o out.ll (gdb) b MBAAdd.cpp:MBAAdd::run (gdb) r
At this point, GDB should break at the entry to
About Pass Managers in LLVM
LLVM is a quite complex project (to put it mildly) and passes lay at its center - this is true for any multi-pass compiler. In order to manage the passes, a compiler needs a pass manager. LLVM currently enjoys not one, but two pass manager. This is important, because depending on which pass manager you decide to use, the implementation (and in particular pass registration) will look slightly differently. I have tried my best to make the distinction in the source code very clear.
Overview of Pass Managers in LLVM
As mentioned earlier, there are two pass managers in LLVM:
- Legacy Pass Manager which currently is the default pass manager
- It is implemented in the legacy namespace
- It is very well documented (more specifically, writing and registering a pass withing the Legacy PM is very well documented)
- New Pass Manager aka Pass Manager (that's how it's referred to in the code base)
The best approach is to implement your passes for both pass managers. Fortunately, once you have an implementation that works for one of them, it's relatively straightforward to extend it so that it works for the other one as well. All passes in LLVM provide an interface for both and that's what I've been trying to achieve here as well.
New vs Legacy PM When Running Opt
MBAAdd implements interface for both pass managers. This is how you will use it via the legacy pass manager:
$LLVM_DIR/bin/opt -load <build_dir>/lib/libMBAAdd.so -legacy-mba-add input_for_mba.ll -o out.ll
And this is how you run it with the new pass manager:
$LLVM_DIR/bin/opt -load-pass-plugin <build_dir>/lib/libMBAAdd.so -passes=mba-add input_for_mba.ll -o out.ll
There are two differences:
- the way you load your plugins:
- the way you specify which pass/plugin to run:
The command line option is different because with the legacy pass manager you
register a new command line option with opt and with the new pass manager
you just define the pass pipeline (via
This is first and foremost a community effort. This project wouldn't be possible without the amazing LLVM online documentation, the plethora of great comments in the source code, and the llvm-dev mailing list. Thank you!
It goes without saying that there's plenty of great presentations on YouTube, blog posts and GitHub projects that cover similar subjects. I've learnt a great deal from them - thank you all for sharing! There's one presentation/tutorial that has been particularly important in my journey as an aspiring LLVM developer and that helped to democratise out-of-source pass development:
- "Building, Testing and Debugging a Simple out-of-tree LLVM Pass" Serge Guelton, Adrien Guinet (slides, video)
Adrien and Serge came up with some great, illustrative and self-contained examples that are great for learning and tutoring LLVM pass development. You'll notice that there are similar transformation and analysis passes available in this project. The implementations available here reflect what I (aka banach-space) found most challenging while studying them.
I also want to thank Min-Yih Hsu for his blog series "Writing LLVM Pass in 2018". It was invaluable in understanding how the new pass manager works and how to use it. Last, but not least I am very grateful to Nick Sunmer (e.g. llvm-demo) and Mike Shah (see Mike's Fosdem 2018 talk) for sharing their knowledge online. I have learnt a great deal from it, thank you! I always look-up to those of us brave and bright enough to work in academia - thank you for driving the education and research forward!
Below is a list of LLVM resources available outside the official online documentation that I have found very helpful. Where possible, the items are sorted by date.
- LLVM IR
- Legacy vs New Pass Manager
- Examples in LLVM
- Examples in LLVM source tree in llvm/examples/IRTransforms/. This was recently added in the following commit:
commit 7d0b1d77b3d4d47df477519fd1bf099b3df6f899 Author: Florian Hahn <email@example.com> Date: Tue Nov 12 14:06:12 2019 +0000 [Examples] Add IRTransformations directory to examples.
- LLVM Pass Development
- "Getting Started With LLVM: Basics ", J. Paquette, F. Hahn, LLVM Dev Meeting 2019 (not yet uploaded)
- "Writing an LLVM Pass: 101", A. Warzyński, LLVM Dev Meeting 2019 (not yet uploaded)
- "Writing LLVM Pass in 2018", Min-Yih Hsu, blog series
- "Building, Testing and Debugging a Simple out-of-tree LLVM Pass" Serge Guelton, Adrien Guinet, LLVM Dev Meeting 2015 (slides, video)
- LLVM Based Tools Development
The MIT License (MIT)
Copyright (c) 2019 Andrzej Warzyński
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.