A1 (4 marks, due Jan 18, 2015 23:55)
Install LLVM 3.5 + Clang on Linux, compile.
Run existing analyses on the LLVM IR and gather statistics.

1. Counts of various types of instructions (number of Add, Alloca, ... instructions)
2. Dead code elimination (number of instructions DCE removes)
3. Alias analysis (various statistics such as NoAlias responses, MayAlias responses, ...)

• typescript generated by program script.
  • shellprompt# script
  • shellprompt# execute llvm commands to get counts of various types of instructions
  • shellprompt# execute llvm commands to run dce
  • shellprompt# execute llvm commands to run alias analysis
  • shellprompt# exit
• Your testcases (.c programs) for each analysis.
• A script (preferably shell-script) to run your testcases.
• A report (in .txt) which describes the statistics you obtained. You can explain any relevant observations that you made.

A2 (8 marks, due Feb 3, 2015 23:55)
Write an LLVM pass to perform intra-procedural static slicing (backward) in LLVM.
Assume that there is a single function main() with only integer types, conditionals, loops. There are no other functions, types, constructs. The slicing criteria is provided as a single printf() statement which appears somewhere in main(). You need to print slice corresponding to that printf() -- which means corresponding to the use of the variables in that printf() statement. The output should print all the LLVM IR instructions in program order that are part of the slice. Get started!

A3 (13 marks, due Feb 15 or 22, 2015 23:55)
Write an LLVM pass to find parallel iterations for each loop.
Assume that there is a single function main() with only integer types (scalars + arrays), for loops (could be nested). There are no other functions, types, constructs. We want to run each iteration of this loop in parallel, but there exist dependencies across iterations. Therefore, we need to insert appropriate synchronization. Your job is not to insert synchronization, but to identify when is it required to do so -- that is, identifying dependent loop iterations.

For each loop, analyze the loop body to find expressions arrname[f(index1, index2, ...)] where arrname is an integer array, f() is a linear combination function of loop indices index1, index2, ... with +-*/ operators, such as a[2*ii - 3*jj + kk]. Each loop index is normalized, that is it starts with 0, is always incremented by 1, but it may end at any value (known or unknown), such as for (ii = 0; ii < n; ++ii). Given such a program, your analysis should figure out what pairs of instructions have dependence and of what type (RW, WR, WW). For instance, the following array accesses do not have any dependence.

for (ii = 0; ii < n; ++ii) {
    a[2 * ii] = 100 + 2 * a[2 * ii + 1] - 200;
}