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,

there must be a least one arc entering the header from a node in the 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.

Algorithm

Finding the nodes in a natural loop

FOR every node n, find all m such that n DOM m
FOR every back edge th, i.e., for every arc such that h DOM t, construct the natural loop:

Send questions and comments to: Karen Lemone