In the LLVM framework, optimizations are implemented as a series of passes which transform the
LLVM bitcode. Each optimization pass can have set dependencies, which ensures that passes are
executed in the intended order. There are several different types of optimization passes, but in this
programming assignment, you will implement two function passes (constant branch folding and
dead block removal) and one loop pass (loop invariant code motion).
A function pass is a local optimization pass that is executed once per each function in the code
module. Since it is limited to a single function, it will not be able to optimize interactions between
several different functions. Rather, it can only iterate through the basic blocks of a single function
and apply whichever optimizations are desired.
A loop pass is a local optimization pass that is executed once per loop inside of a function. This is
handy because it will automatically identify back edges and loops for you. While it certainly would
be possible to manually determine this in a function pass, it’s much simpler to apply loop- focused
optimizations in a loop pass.
In USCC, optimization passes can be invoked with the -O (that is, an uppercase letter O) command
line switch. For example, assuming you are in the tests directory, the following would compile
opt01.usc, run the optimization passes, and print the resulting bitcode to stdout:
$ ../bin/uscc -p -O opt01.usc
The provided starting code has one function pass already implemented – constant propagation –
which is implemented in opt/ConstantOps.cpp. Constant propagation is a peephole optimization
that looks for certain instructions, such as arithmetic, that are operating on constant values. These
instructions are then replaced with the resultant constant value. For example, an add instruction
between the constants 5 and 10 would have its uses replaced with the constant value of 15.
In practice, a great deal of constant propagation in LLVM occurs when you construct the bitcode
– the factory methods used to create the instructions check for constant values and propagates them
automatically. However, it is still possible in some cases to end up with unpropagated constants,
which is what this optimization pass aims to eliminate.
You should study the code in ConstantOps.cpp before continuing. Notice how there are two
functions implemented – this is the minimum required for any pass. The getAnalysisUsage
function is used to inform the LLVM Pass Manager how a particular optimization pass behaves.
For ConstantOps, the only behavior noted is that it preserves the CFG. This is because the pass
will not alter any of the edges between blocks. The getAnalysisUsage function can also be used
to specify dependencies – in this case, ConstantOps does not depend on any other passes.
The other function in ConstantOps.cpp is runOnFunction. This represents the actual optimization
pass code, and is called once per function. Since this is called once per function, you are not
allowed to have any data persist between multiple function calls (such as any static data). All data
must be local to a single invocation.
The overall structure of ConstantOps::runOnFunction is similar to many function passes – it
iterates through every basic block in the function, and then every instruction in the basic block. It
uses isa or dyn_cast to identify instructions of interest, and then uses the replaceAllUsesWith
member function to replace these instructions. One thing that’s very important to note is that
eraseFromParent is not called during the initial iteration, because this will invalidate the iterator.
Instead, instructions to be erased are added to a set, and then erased once all instructions have been
visited. Finally, runOnFunction should return true if the function was changed in any way.