next up previous
Next: Experiments Up: Optimization Previous: Loop Unrolling


To eliminate complicated distributed index subscript expressions and to hoist control variables in the inner loops, we adopted the following algorithm;

Step 1:
(Optional) Apply Loop Unrolling.
Step 2:
Hoist control variables to the outermost loop by using compiler information if loop invariant.
Step 3:
Apply Partial Redundancy Elimination and Strength Reduction.
Step 4:
Apply Dead Code Elimination.
We call this algorithm HPJOPT2 (HPJava OPTimization Level 2)4. Applying Loop Unrolling is optional since it is only useful when a nested overall loop involves the pattern, (i` + expr) % 2 such as in Figure 3. We don't treat Step 3 of HPJOPT2 as a part of PRE. It is feasible for control variables and control subscripts to be hoisted by applying PRE. But using information available to the compiler, we often know in advance they are loop invariant without applying PRE. Thus, without requiring PRE, the compiler hoists them if they are loop invariant.

In the section 5, we will see the performance of HPJava adopting HPJOPT2 optimization strategies.

Bryan Carpenter 2004-04-24