Defining a Loop

Headers

Dominators

Natural Loops

Depth-First Order and Depth-First Spanning Trees

Finding Natural Loops Efficiently

There are two main types of loop optimizations: (1) movement of loop-invariant computations outside of the loop and (2) elimination of excess induction variables, the variables which are a linear function of the loop index. Other optimizations often performed within loops are reductions in strength of certain multiplications to additions.

Example 9 shows invariant code movement. The details of how this optimization is found and implemented are given in the next two modules. In this module we focus on the importance of being able to identify a loop.

EXAMPLE 9 Invariant code motion

 	FOR index := 1 TO 10000 DO	t := y * z
 	BEGIN				FOR index := 1 TO 10000 DO
 		x := y * z ;		BEGIN
 		j := index * 3 ; -- >		x := t
 	END					j := index * 3
 	.				END
 	.				.
 					.
 

In Example 9, y * z is computed each time around the loop. If none of y, z, or x changes value in the loop (and this must be checked!), then it is more efficient to compute this product, t, one and to use t every place the computation appears in the loop (x itself may be able to be be eliminated).

Example 9 can also be optimized for strength reduction (turn the multiplication into an addition) and for elimination of induction variables (index and j are tracking one another). We will save these examples for Module 10.

---