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 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
Change all the back edges in L from s_i → h to s_i → h′.
Change all the back edges in L′ from s′ _i → h′ to s′ _i → h.

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 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 L₁ else L₂
	L₁ : x ← M[i]
	s ← s + x
	x ← M[i + 4]
	s ← s + x
L₁ : x ← M[i]	i ← i + 8
s ← s + x	if i < n − 8 goto L₁ else L₂
x ← M[i + 4]	L₂ x ← M[i]
s ← s + x	s ← s + x
i ← i + 8	i ← i + 4
if i < n goto L₁ else L₂	if i < n goto L₁ else L₃
L₂	L₂
(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.