Partial Redundancy Elimination

Partial Redundancy Elimination (PRE) [18] is a very important optimization technique to remove partial redundancies in the program by solving a data flow problem that yields code replacements. PRE is a powerful and proper algorithm for HPJava compiler optimization, since loop invariants, which are naturally partially redundant, often occur in the subscript expression of distributed arrays.

PRE should be applied to a general or Static Single Assignment (SSA) [10] formed data flow graph after adding landing pads [24], representing entry to the loop from outside.

PRE is a complicated algorithm to understand and to implement, compared with other well-known optimization algorithms. However, the basic idea of PRE is simple. Basically, PRE converts partially redundant expressions into redundant expressions. The key steps of PRE are:

Step 1:

Discover where expressions are partially redundant using data-flow analysis.

Step 2:

Solve a data-flow problem that shows where inserting copies of a computation would convert a partial redundancy into a full redundancy.

Step 3:

Insert the appropriate code and delete the redundant copy of the expression.