SPO600 Compiler Optimizations

As we start our projects for SPO600, the professor introduced the class to optimizations the compiler does automatically for code, so we don't try to do similar ones manually. I'll explain a few ones as it was interesting (at least to me) what types of things are done behind the scenes make code more efficient.

Hoisting
Some times code written in a loop is the same no matter the iteration. For example

//Increments i by k
int k;
for (int i = 0; i < 10; i++){
  k = 5 + 9;
  i += k;
}

Since the value of k is 14 no matter how many times the loop is run. The compiler figures it can move the line k = 5+9; outside of the loop so we get something like the the below

//Increments i by k
int k;
k = 5 + 9;
for (int i = 0; i < 10; i++){
  i += k;
}

This shaves off a bit of computing time because now k doesn't have to compute the value of k for
i < 10 times.

Dead Store
This sometimes happens in code, a variable assigned a value, is assigned another one before it is used. For example

//Increments i by k
int k;
k = 0;
k = 5 + 9;
for (int i = 0; i < 10; i++){
  i += k;
}

As you noticed, k = 0; is never used and is reassigned to 5 + 9; The compiler notices this when it does an internal representation of the code and will remove k = 0 so the code becomes

//Increments i by k
int k;
k = 5 + 9;
for (int i = 0; i < 10; i++){
  i += k;
}

Strength Reduction
Multiplication and division in code is more expensive than adding or subtracting. Take the following for example

//Multiplies i by k
int k = 5;
for (int i = 0; i < 10; i++){
  int c = k * i;
  printf(c);
}

The compiler will do something like the below:

//Multiplies i by k
int k = 5;
for (int i = 0; i < 50; i+=5){
  int c = k + i;
  printf(c);
}

Both programs will output 0, 5, 10... up until 50. However the multiplication operation has now been swapped out for an addition operation.