Program Optimization

Implementation of the program optimization algorithms discussed in the lecture "Program Optimization" at the Technical University of Munich.

See the Course Slides for more information.

Features

The project contains tools for arbitrary program optimization given in C-like code. The following optimizations are implemented:

• Available Expressions Analysis
• (True) Liveness Analysis
• Superflous Assignments Analysis
• Constant Propagation
• Interval Analysis
• Memory Aliasing Analysis (Basic)
• Very Busy Expressions Analysis
• Loop Rotation
• Function Inlining
• Transformation to Static Single Assignment (SSA)
• Register Allocation (Graph Coloring)

Example

The following code contains unnecessary bounds checks. The interval analysis can be used to remove them.

int M[];
int A;

void main(int A0) {
  int i = 0;
  while (i < 5) {
    if (0 <= i) {
      if (i < 5) {
        int A1 = A + i;
        M[A1] = i;
        i = i + 1;
      }
    }
  }
}

Initial CFG

Resulting CFG

This corresponds to the following code:

int M[];
int A;

void main(int A0) {
  int i = 0;
  while (i < 5) {
    int A1 = A + i;
    M[A1] = i;
    i = i + 1;
  }
}