The LLVM passes implement code transformations and optimizations and generate analysis results for other passes. A custom pass can be implemented inside the LLVM source tree or outside of it, as a dynamic library to be loaded at runtime. You can find here more information about writing an LLVM pass.

Each LLVM pass is a subclass of the Pass class, whose virtual methods should be overridden in order to implement a custom analysis or transformation pass. In order to implement a specific type of pass, we can inherit from one of the existing subclasses of Pass: BasicBlockPass, CallGraphSCCPass, FunctionPass, LoopPass, ModulePass and RegionPass.

A FunctionPass is invoked on each function in the module at a time, without modifying the other functions. The classes derived from FunctionPass are not allowed to modify other functions, add or remove functions or global variables from the current module, or maintain state between different invocations of the pass.

The FunctionPass class has three virtual methods that can be overridden in order to implement a custom pass:

virtual bool doInitialization(Module &M);
virtual bool runOnFunction(Function &F) = 0;
virtual bool doFinalization(Module &M); 

The methods return true if they modified the program and false, otherwise.

The doInitialization method is used to do initializations that are independent of the functions on which the pass is invoked and is allowed to add or remove functions to/from the module. The runOnFunction method deals with the processing of a function and it's called for each of the module’s functions. The doFinalization method is called after processing all of the module’s functions.

We will try to implement an LLVM pass that searches for calls with constant arguments and replaces them with their actual result. The pass will be developed as a dynamic library to be loaded at runtime by opt.

In order to load and run the pass you can use:

opt -S file.ll -o file.opt.ll -load <path_to_library> <option-name>

Iterate over the basic blocks and dump the instructions to the error output.

To iterate over the basic blocks of a function you can use:

for (auto &BB : F) { }

To iterate over the instructions of a basic block you can use:

for (auto &I : BB) { }

To dump an instruction, you can use:

I.dump();

Compute the number of call instructions in a function and print it to the error output.

To check if an instruction has a specific type you can use:

if (InstType *CI = dyn_cast<InstType>(&I)) { }

To print something to the error output you can use:

errs() << message;

Identify the call instructions that have only one argument and whose value is a constant integer and print the name of the called function and the value of the argument to the error output.

For each call with constant arguments to prim, fact and fib compute the result of the function. Use the return type of the function and the result to generate a ConstantInt value. Save the value into a map indexed by the instruction's pointer.

To declare a map you can use:

DenseMap<K, V> Map;

To store a (Key, Value) pair into a map you can use:

Map[Key] = Value;

Replace each instruction from the map with the value associated with it.

To iterate over a map you can use:

for (auto &E : Map) {  }

To replace an instruction with a value you can use:

I->replaceAllUsesWith(V);
I->eraseFromParent();