[Sprint 2] Add GVN Pass

[sharaelong]

Overview

The GVN (Global Value Numbering) pass in LLVM is an optimization pass that performs a technique called global value numbering. GVN is designed to eliminate redundant computations by identifying expressions that compute the same value and replacing them with a single computation. This optimization can improve both the execution speed and code size of the program.

The GVN pass performs the following key steps:

1. Expression numbering: GVN assigns a unique value number to each expression in the program. Expressions that compute the same value are assigned the same value number.
2. Value propagation: GVN propagates known values through the program by tracking the relationships between variables and expressions. This allows it to replace uses of variables with their known values.
3. Value numbering: GVN performs value numbering on expressions and instructions, identifying expressions that have already been computed and assigning them the same value number.
4. Redundant expression elimination: GVN eliminates redundant computations by replacing expressions with their value numbers. If an expression with the same value number has already been computed, GVN replaces subsequent occurrences of the expression with the value number, effectively eliminating redundant computations.

Implementation

It's just including appropriate headers and passes. Read opt.cpp!

Test cases

I tested this pass for 2 aspects especially: redundant expression elimination and value propagation. In test01, int a, b has same declaration with combinations of previously declared variables. Its return value is return a+b, so GVN pass will change it to return 2*a. Test02 is the one which is not trivial.

int sumArray(int *arr, int n) {
  int sum = 0;
  for (int i = 0; i < n; i++) {
    sum += arr[i];
  }
  return sum;
}

is pretty simple code which maybe thought as no optimization can be possible. However, pointer addition is redundant here. GVN pass will change it like:

int sumArray(int *arr, int n) {
  int sum = 0;
  int *end = arr + n;
  while (arr != end) {
    sum += *arr++;
  }
  return sum;
}

Lastly, test03 is about constant propagation. You can see it directly in my commits.

[germanium32]

Adding pass and test cases looks good to me. Handle the opt.cpp where you've commented all other passes.

Also, a caveat to your test case; your second test case clashes with the loop2sum pass, which should be prioritized? I'm considering putting loop2sum directly after the first pass: SimplifyCFG. Which pass will reduce more instruction costs?