next up previous
Next: HPJOPT2 Up: Optimization Previous: Dead Code Elimination


Loop Unrolling

In conventional programming languages some loops have such a small body that most of the time is spent to increment the loop-counter variables and to test the loop-exit condition. We can make these loops more efficient by unrolling them, putting two or more copies of the loop body in a row. This technique is called Loop Unrolling (LU) [2].

Our experiments [20] did not suggest that this is a very useful source-level optimization for HPJava, except in one special but important case. LU will be applied for overall constructs in an HPJava Program of Laplace equation using red-black relaxation. For example,

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}overa...
...(i\lq  + iter) % 2 : N-2 : 2) { ... }
\end{verbatim}\end{minipage}\end{displaymath}

The overall is repeated in every iteration of the loop associated with the outer overall. Because red-black iteration is a common pattern, HPJava compiler should probably try to recognize this idiom. If a nested overall includes expressions of the form


where expr is invariant with respect to the outer loop, this should be taken as an indication to unroll the outer loop by 2. The modulo expressions then become loop invariant and arguments of the call to localBlock(), the whole invocation is a candidate to be lifted out of the outer loop.


next up previous
Next: HPJOPT2 Up: Optimization Previous: Dead Code Elimination
Bryan Carpenter 2004-04-24