Loop Optimizations

OVERVIEW

loop: a series of instructions that is repeated until a terminating condition is reached

Webster's Dictionary

Loops are pervasive in computer programs, and a great proportion of the execution time of a typical program is spent in one loop or another. Hence it is worthwhile devising optimizations to make loops go faster. Intuitively, a loop is a sequence of instructions that ends by jumping back to the beginning. But to be able to optimize loops effectively we will use a more precise definition. A loop in a control-flow graph is a set of nodes S including a header node h with the following properties:

• From any node in S there is a path of directed edges leading to h.
• There is a path of directed edges from h to any node in S.
• There is no edge from any node outside S to any node in S other than h.

Thus, the dictionary definition (from Webster's) is not the same as the technical definition. Image 18.1 shows some loops. A loop entry node is one with some predecessor outside the loop; a loop exit node is one with a successor outside the loop. Images 18.1c, 18.1d, and 18.1f illustrate that a loop may have multiple exits, but may have only one entry. Images 18.1e and 18.1f contain nested loops.
Image 18.1: Some loops; in each case, 1 is the header node.