8.6.2 Headers

A node n is the header of a set of nodes S if every path from the start node to a node in S first goes through n.

A cycle must have a header to be considered a loop. Optimizations such as code motion cannot be done safely if there is more than one entry to the loop. Also, the header concept makes the algorithms for loop-invariant code motion, etc. conceptually simplier.

Example 10 shows a flow graph with two cycles, one of which is a loop and one of which is not a loop.

Finding Loops

Although the preceding definition is helpful for us humans to find a loop, we will need some more definitions in order to write an algorithm to find a loop.

An efficient algorithm for finding a loop involves finding dominators, depth-first search, and depth-first ordering.