Previous    Next

LOOP UNROLLING

Some loops have such a small body that most of the time is spent incrementing the loop-counter variable and testing 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. Given a loop L with header node h and back edges sih, we can unroll the loop as follows:

  1. Copy the nodes to make a loop L′ with header h′ and back edges si

  2. Change all the back edges in L from sih to sih′.
  3. Change all the back edges in L′ from sih′ to sih.

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 ii + Δ 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 loop-exit 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 L1 else L2

 

L1 : xM[i]

 

ss + x

 

xM[i + 4]

 

ss + x

L1 : xM[i]

ii + 8

ss + x

if i < n − 8 goto L1 else L2

xM[i + 4]

L2 xM[i]

ss + x

ss + x

ii + 8

ii + 4

if i < n goto L1 else L2

if i < n goto L1 else L3

L2

L2

(a) Fragile

(b) Robust

Java End example

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.


JaVaScreenshot Previous    Next
Comments