The purpose of this project is to get you acquainted with LLVM. In particular, it will give you familiarity with the data structures, types, and code organization you will need to understand to implement program analyses. All code will be written in C++, as that is the language in which LLVM is written.
Your task is to write a function pass that counts the number of each unique instruction in a function statically. After processing a function, the pass should output the counts to stderr in the following format:
[instruction name]\t[count]\n
For example, if the pass processes a function that consists of 2 load
and 3 add
instructions, the output should be:
load 2
add 3
Directions
/LLVM_ROOT/llvm/lib/Transforms/CSE231_Project/Passes/part1/CountStaticInstructions.cpp
as a function pass. opt -load /LLVM_ROOT/build/lib/CSE231.so -cse231-csi < input.bc > /dev/null
where CSE231.so
is the name of the shared object containing your pass (we assume this for the following two sections. You may name it whatever you want.) and input.bc
is the bitcode file to be analyzed.Instruction::getOpcodeName
.STATISTIC
convenience macro provided by LLVM.Hints
std::map
or LLVM’s DenseMap
to store instruction counts.The analysis you wrote in Section 1 was a static analysis because it did not actually execute the program to analyze it. In this section, we are going to write a dynamic analysis that executes the program and collects runtime information. In particular, you will write a pass that instruments the original program by inserting code to count the number times each instruction executes. Each instrumented function should output the analysis results before function termination.
The general strategy you should follow:
/lib231/lib231.cpp
that contains helper functions and global data structures. You are free to implement your own runtime library but you need to name it as lib231.cpp
.Directions
/LLVM_ROOT/llvm/lib/Transforms/CSE231_Project/Passes/part1/CountDynamicInstructions.cpp
as a function pass. opt -load /LLVM_ROOT/build/lib/CSE231.so -cse231-cdi < input.bc -o input-instrumented.bc
where input.bc
is the original bitcode file and input-instrumented.bc
is the instrumented version.input-instrumented.bc
is the instrumented code and lib231.bc
is the library, then you should link them by running clang++ lib231.bc input-instrumented.bc -o mytest
(Why do we need this?)Hints
IRBuilder
class, which is a convenience class for adding instructions. IRBuilder::SetInsertPoint
sets the insertion point, and various create...
methods on the IRBuilder
instance insert instructions at the specified point.FunctionType::get
Module::getOrInsertFunction
IRBuilder::CreateCall
Now, write a dynamic analysis that computes the branch bias on a per-function basis: count the number of times conditional branch instructions are executed and the number of times conditional branch instructions are taken. Note that we only consider conditional branches. A conditional branch is considered taken if its condition evaluates to true. Each instrumented function should output these two counts before function termination. The output should be in the following format:
taken\t[count of taken]\n
total\t[count of total]\n
The general strategy you should follow:
/lib231/lib231.cpp
that contains helper functions and global data structures. You are free to implement your own runtime library but you need to name it as lib231.cpp
and put it in /lib231/
.Directions
/LLVM_ROOT/llvm/lib/Transforms/CSE231_Project/Passes/part1/BranchBias.cpp
as a function pass. opt -load /LLVM_ROOT/build/lib/CSE231.so -cse231-bb < input.bc -o input-instrumented.bc
where input.bc
is the original bitcode file and input-instrumented.bc
is the instrumented version.input-instrumented.bc
is the instrumented code and lib231.bc
is the library, then you should link them by running clang++ lib231.bc input-instrumented.bc -o mytest
(Why do we need this?)To help you test your code, we provide our solution in binary. If you use the docker image, you can find it at /solution/opt
. Otherwise, you can download it here. All the three passes have been statically linked to opt
, which means that you do not need to load any shared object to run one of the three passes. For example, to run the cse231-csi
pass from Section 1, type
/solution/opt -cse231-csi < input.bc > /dev/null
Note that the cse231-cdi
and cse231-bb
passes assume the use of our runtime library. That is, you have to link the bitcode that is instrumented by the solution opt
with the runtime library we provide.
In addition, we provide you a test case in /tests/test-example
. This directory has test code in C/C++, and a bash script, /tests/test-example/run.sh
, that builds and runs the tests.
Directions
/tests/test-example/run.sh
are correct;
/tests/test-example/run.sh
runs all three passes. If you have not implemented them all, you need to comment out the lines for the pass(es) you have not implemented;cse231-csi
, cse231-cdi
, and cse231-bb
are saved in /tmp/csi.result
, /tmp/csi.result
, and /tmp/bb.result
, respectively.The turnin script for part 1 is here.
Directions
CountStaticInstructions.cpp
CountDynamicInstructions.cpp
BranchBias.cpp
lib231.cpp