Most programs spend the majority of their time in loops. The payoff in optimizing loops is, on the average, greater than any other optimization.
In Chapter 8, we discussed how to identify a loop. We use that here when performing loop optimizations.
In particular, there is a useful property of loops: two natural loops are either disjoint (except for the header) or one is nested within the other.
Two loops with the same header should probably be merged into one:
We will use the property that two natural loops are either nested or disjoint for some loop optimizations. The two most common optimizations are detection and movement of invariant code and induction variable elimination. Other optimizations optimize special loop forms such as loops which make changes to array elements one by one or pairs of loops with the same execution conditions.
Loop-Invariant Computations and Code Motion
Induction Variable Detection and Elimination
