8.6.4 Natural Loops

We use dominators to find loops. Since loops contain a cycle, and a header dominates all the nodes in a loop,

For this reason, we search for an arc whose head dominates its tail. This is called a back edge. Loops must have a back edge.

The natural loop of the back edge is defined to be the smallest set of nodes that includes the back edge and has no predecessors outside the set except for the predecessor of the header. Natural loops are the loops for which we find optimizations.

Send questions and comments to: Karen Lemone