Nisse

An exact profiler inserts counters in a program to record how many times each edge of that program's control-flow graph has been traversed during an execution of it. It is common practice to instrument only edges in the complement of a minimum spanning tree of the program's control-flow graph, following the algorithm proposed by Knuth and Stevenson in 1973. This repository introduces a technique to reduce the overhead of exact profiling even more. It is possible to use the values of variables incremented by constant steps within loops (henceforth called affine variables) as a replacement for some counters. Such affine variables are common, for they include induction variables of loops. This repository implements this technique in the LLVM compilation infrastructure.

Build

Nisse is implemented on top of LLVM. The code can be built out of the LLVM tree as follows:

LLVM_INSTALL_DIR=<path/to/llvm/build>
cmake -DLLVM_INSTALL_DIR=$LLVM_INSTALL_DIR -G "Unix Makefiles" -B build/ .
cd build
make

Running

We provide a bash script to run our passes, which can be invoked as follows:

bash nisse_profiler.sh <path/to/file.c>

It also requires to configure the file config.sh.

LLVM_INSTALL_DIR is the path to the build directory of llvm. SOURCE_DIR is the path to this folder.

This basic command will create a folder file.c.profiling. In that folder are 5 subfolders:

• compiled contains 3 files:
  • file.ll an IR file modified by the following LLVM passes: mem2reg, and instnamer.
  • file.profiled.ll an IR file instrumented with KS counters.
  • file an executable file compiled from file.profiled.ll.
• profiles contains the complete profile for each function. By default, if a function is called multiple times, the profile will contain the total execution. Adding an an extra argument to the nisse_profiler.sh script generates a separate profile for each execution instead.
• partial_profiles contains the profile data obtained by the instrumentation for each function.
• graphs contains the vertices, edges, spanning tree and instrumented edges of each function's CFG.
• dot contains a dot file with the representation of each function's CFG.

Functions with no branches are not instrumented (since their execution is always linear).