• Section 1: Collecting Static Instruction Counts
  • Section 2: Collecting Dynamic Instruction Counts
  • Section 3: Profiling Branch Bias
  • Testing
  • Turnin Instructions
  • Tutorial

  • 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.

    Section 1: Collecting Static Instruction Counts

    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

    Hints

    Section 2: Collecting Dynamic 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:

    1. You need a C++ runtime library to keep track of the runtime information (In this section, it is how many times each instruction is executed.). We provide you a reference implementation in /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.
    2. From your LLVM pass, instrument the program with calls to the runtime library at the correct locations.
    3. When it’s time to run the analysis, run your LLVM pass on the original bitcode file, link the runtime library to the instrumented bitcode, then execute the linked program.

    Directions

    Hints

    Section 3: Profiling Branch Bias

    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:

    1. You need a C++ runtime library to keep track of the runtime information (In this section, it is how many times a branch is executed or taken.). We provide you a reference implementation in /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/.
    2. From your LLVM pass, instrument the program with calls to the runtime library at the correct locations.
    3. When it’s time to run the analysis, run your LLVM pass on the original bitcode file, link the runtime library to the instrumented bitcode, then execute the linked program.

    Directions

    Testing

    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

    Turnin Instructions

    The turnin script for part 1 is here.

    Directions

    Tutorial

    You can find a tutorial on the relevant parts of the LLVM API here and here.