CS4130/5130 Project 2: Value Numbering
Due: Wednesday, Oct. 16 @ 5:00 PM
We will continue basing our project on the Low Level Virtual Machine (LLVM) compiler infrastructure. Please make sure you are working on LLVM 8.0.1 as we did in Project 1. In this project you will implement and compare three value numbering techniques, local value numbering (LVN), super local value numbering (SVN) and dominator-tree-based global value numbering (GVN).
1 Project Summary
GVN has already been implemented in LLVM (see $(llvm)/lib/Transforms/Scalar/GVN.cpp). Note that GVN subsumes SVN, which, in turn, subsumes LVN. You need to update the GVN code so that it can be downgraded to perform LVN or SVN only. To implement super local value numbering, CS5130 students need to implement an analysis pass that identifies extended basic blocks. CS4130 students are NOT required to implement this pass. However, you will need an algorithm to determine if basic block A is an ancestor of basic block B in an EBB. Below is the pseudo code of a simple algorithm. You can design an algorithm of your own.
/* return true if A is an ancestor of B in an EBB,
otherwise, return false */
bool is_ancestor(BasicBlock A, BasicBlock B}
{
if (A == B)
return true;
if (B has more than one predecessor or B has no predecessor)
return false;
C = predcessor of B;
return is_ancessor(A, C);
}
2
Implementation
You will need to introduce two new command line options for opt which suggest the optimizer to perform LVN or SVN instead of GVN. I will use command line option -gvn to trigger global value numbering. You
1
should add the following two options to opt:
1. -lvn: perform local value numbering only.
2. -svn: perform super local value numbering only. CS5130 students need to output EBBs for each function if this option is enabled.
I will use ¡°opt -gvn -lvn¡± to test your implementation of local value numbering. Similarly, ¡°opt -gvn -svn¡± is for super local value numbering. Most of your work is to understand GVN.cpp and make changes to integrate local and super local value numbering into it. The command line option ¡°-stats¡± can be used to check the statistics of ¡°opt¡± including the number of instructions deleted by ¡°gvn¡±.
2.1 Testing
To focus on testing the effects of GVN, SVN and LVN, you are recommended to disable partial redundancy elimination in GVN.cpp.
We will use test-suite/SingleSource/Benchmarks/Stanford as the testing benchmark suite. Your optimization should pass all the benchmarks in this suite. You need to collect the number of instructions deleted by value numbering. Note that the LLVM command llc can convert bitcode to assembly code. You can use gcc to compile the generated assembly to executable. You should use gcc to compile the original source code and compare the output with the one by your optimized code to ensure your optimization is correct.
I have attached a hand-coded test case, vn.ll, for your convenience. You should expect different numbers of instructions deleted for this test case.
2.2 Extended Basic Block (CS5130 students only)
Dump all the extended basic blocks in each function led by the function name followed by a colon. Each EBB should be output as a pre-order sequence of the basic blocks in it enclosed by a pair of curly brackets and each basic block can be represented by its name. The sample output of EBBs for the bitcode in Project 1 would be as following:
erk:
{entry}
{for.cond, for.body, for.inc, for.end}
3 Submission
Tar all the source files you have changed including their directories into a tar ball, project2.tar, and submit it through Canvas. Write a report that summarizes your implementation and analyzes your experimental results for the Stanford benchmark suite.
CS5130 students should also attach your EBB outputs and name them after the original input file names with .ebb extension. For example, the EBB output for Bubblesort.c should be stored in file Bubblesort.ebb.
2