Previous Next 
Some loops have such a small body that most of the time is spent incrementing the loopcounter variable and testing the loopexit condition. We can make these loops more efficient by unrolling them, putting two or more copies of the loop body in a row. Given a loop L with header node h and back edges s_{i} → h, we can unroll the loop as follows:
Copy the nodes to make a loop L′ with header h′ and back edges s′ _{i}
For example, Program 18.10a unrolls into Program 18.10b. But nothing useful has been accomplished; each "original" iteration still has an increment and a conditional branch. By using information about induction variables, we can do better. We need an induction variable i such that every increment i ← i + Δ dominates every back edge of the loop. Then we know that each iteration increments i by exactly the sum of all the Δ's, so we can agglomerate the increments and loopexit tests to get Program 18.11a. But this unrolled loop works correctly only if the original loop iterated an even number of times. We execute "odd" iterations in an epilogue, as shown in Program 18.11b.
Useful loop unrolling; (a) works correctly only for an even number of iterations of the original loop; (b) works for any number of iterations of the original loop.
if i < n − 8 goto L_{1} else L_{2} 

L_{1} : x ← M[i] 

s ← s + x 

x ← M[i + 4] 

s ← s + x 

L_{1} : x ← M[i] 
i ← i + 8 
s ← s + x 
if i < n − 8 goto L_{1} else L_{2} 
x ← M[i + 4] 
L_{2} x ← M[i] 
s ← s + x 
s ← s + x 
i ← i + 8 
i ← i + 4 
if i < n goto L_{1} else L_{2} 
if i < n goto L_{1} else L_{3} 
L_{2} 
L_{2} 
(a) Fragile 
(b) Robust 
Here we have shown only the case of unrolling by a factor of two. When a loop is unrolled by a factor of K, then the epilogue is a loop (much like the original one) that iterates up to K − 1 times.
JaVa  Previous Next 