Next: Strength Reduction
Up: Optimization
Previous: Optimization
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 wellknown 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
dataflow analysis.

Step 2:
 Solve a dataflow 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.
Next: Strength Reduction
Up: Optimization
Previous: Optimization
Bryan Carpenter
20040424