adding optimization passes with LLVM PassBuilder

38 Views Asked by At

I am working on a project for which I have to extend the optimizer of a simple compiler in order to improve the quality of the generated LLVM bitcode. The project file I've been given uses LLVM's PassBuilder to implement optimization passes. My task is to add more passes (which I believe I have done correctly as I am referencing the assignment's examples as well as https://github.com/llvm/llvm-project/blob/main/llvm/lib/Passes/PassBuilderPipelines.cpp) but the part I am stuck on is proving that these optimizations actually make a difference in the compiled code. I have to provide a sample program that runs faster with the optimization enabled, yet any program I write seems to run at the same speed with and without the optimization. I have already tried a number of optimizations (including ones I know are supposed to work) and have had the same outcome.

Here is an example provided in the assignment that works correctly for a loop deletion optimization. When run with the optimization, there is a significant decrease in runtime compared to the unoptimized version:

/*
 * Benchmark for loop deletion optimization.
 * 
 * Compile with and without the -del optimization then run:
 *   time ./delete 20000
 * to observe the execution time of the benchmark.
 * You should be able to see a 1000x speedup.
 */
main(n) {
  var i, r, v;
  i = 0;
  v = 42;
  r = 0;
  /* 
   * Need to create a loop that won't be deleted here so that the
   * the benchmark measures speedup in the delete function.
   * To do this we create a loop dependence with the returned value.
   */
  while (n > i) { 
    r = r + delete(n); 
    i = i + 1;
  }
  return r;
}

delete(n) {
  var i;
  i = 0;
  while (n > i) {
    i = i + 1;
  }
  return n;
}

Note that this code is written in TIP (https://github.com/cs-au-dk/TIP/tree/master).

Currently, I am attempting to implement a loop unrolling optimization. This is the program attempting to prove that loop unrolling will speed up the original code:

/*
 * Benchmark for loop unrolling optimization.
 *
 * Compile with and without the -unroll optimization then run:
 *   time ./unroll
 * to observe the execution time of the benchmark.
 */
main() {
  var i, j, r, v, n;
  i = 1;
  r = 0;
  v = 42;
  n = 20000;
  while (n > i) {
    r = r + 101 + 3023 + v;
    i = i + 1;
  }
  return r;
}

This is one of many attempts that does not result in any noticeable time difference between the optimized and unoptimized versions. Does anyone have any suggestions for proving the benefit of this (or other) optimizations? I apologize for the vague question, I just do not know where to go from here as I do not understand why this code would not speed up from a loop unrolling optimization.

0

There are 0 best solutions below