Lab 3: Optimization

Overview

In this lab, you will design and implement several classical control flow graph optimization algorithms based on the program analysis algorithm completed in lab 2.

This lab consists of three parts. In part A, you will design and implement a dead code elimination optimization. In part B, you will design and implement a constant propagation optimization, and a copy propagation optimization (if you are interested in it). Finally, in part C, your will design and implement a common sub-expression elimination optimization.

Getting Started

First check out the source we offered you for lab 3: 

    $ git commit -am 'my solution to lab2'
    $ git fetch
    $ git checkout -b lab3 origin/lab3

which will commit your changes to 'lab2' branch to your local Git repository, and create and check out a new lab3 branch from the remote lab2 branch.

Again, you will need to merge your code from lab2 into the new lab3 branch: 

    $ git merge lab2

Do not forget to resolve any conflicts before commiting to the local lab3 branch: 

    $ git commit -am 'lab3 init'

Lab 3 contains the following new source files, which you should browse through: 

    cfg/lab2/AvailExp.java              available expression analysis framework
    cfg/lab3/ConstPropagation.java      const propagation optimization framework
    cfg/lab3/CopyProp.java              copy propagation optimization framework
    cfg/lab3/DeadCode.java              dead code elimination framework
    cfg/lab3/UnreachableBlock.java      unreachable block elimination framework

Hand-in Procedure

When you finished this lab, zip you code and submit to the online teaching system.

Part A: Dead Code Elimination

Dead code elimination is an optimization that removes code which does not affect the program’s observable behavior. This includes both useless code (assignments to variables that are never used), and unreachable code (blocks of code that are never executed).

Exercise 1. An assignment statement x = v is useless, if the variable x does not live out this statement. Hence, this statement can be safely removed. Finish the useless code elimination in cfg/lab3/DeadCode.java by implementing the aforementioned algorithm. You may assume that side-effecting operations (e.g., method calls, I/O) must be preserved. Also note that removing one useless code may have cascading effects to make other code dead, so make sure that your useless code elimination optimization can eliminate all useless code.
Exercise 2. Unreachable code elimination removes basic blocks that cannot be reached from the function’s entry block. Finish the unreachable code elimination in cfg/lab3/UnreachableBlock.java.

Part B: Constant Propagation

Constant propagation propagates a constant definition to it uses. For example, for any statement s of the form x = y op z, where the variable y is defined in by a statement t like y = c where c is a constant. And suppose the definition t is the unique definition that reaches the statement s. Then we can replace, in the statement s, the variable y by the constant c.

Exercise 3. Finish the constant propagation code in the file cfg/lab3/ConstPropagation.java. To be noted, this exercise relies on Exercise 2, therefore, make sure Exercise 2 has been completed before proceeding with it.

Copy propagation is like constant propagation. Suppose, for any statement s of the form x = y or x = y op z, where y is defined in some statement t like y = m with a variable m. And suppose the definition t is the unique definition that reaches the statement s. Then you can replace the variable y, in the statement s, with the variable m from the statement t.

Challenge. Since copy propagation is far more complex than constant propagation, this experiment is presented as a challenge. If you are interested in it, you can try to finish the constant propagation code in the file cfg/lab3/CopyProp.java.

Part C: Common Sub-Expression Elimination

In this part, you'll complete the common sub-expression elimination (CSE) algorithm. You first need to compute the available expression at the entry point for each statement in the CFG, and use the result to do common sub-expression elimination.

Available Expressions

Consider the statement x = y op z, if the expression y op z has been computed before this statement, then the expression y op z can reuse the computed result. Hence, you can compute whether the expression y op z is available here.

Exercise 4. Finish the available expression analysis in the file cfg/lab2/AvailExp.java if you haven't done it yet.

Common Sub-Expression Elimination (CSE)

For the statement x = y op z, if the expression y op z is available. We can substitute the expression y op z with the most recent definition using y op z.

Exercise 5. Implement common sub-expression elimination in cfg/lab3/Cse.java.

Hand-in

This completes the lab. Remember to hand in your solution to the online teaching system.