DOMINATORS

Before we optimize the loops, we must find them in the flow graph. The notion of dominators is useful for that purpose. Each control-flow graph must have a start node s₀ with no predecessors, where program (or procedure) execution is assumed to begin. A node d dominates a node n if every path of directed edges from s₀ to n must go through d. Every node dominates itself.

ALGORITHM FOR FINDING DOMINATORS

Consider a node n with predecessors p₁,…, p_k, and a node d (with d ≠ n). If d dominates each one of the p_i, then it must dominate n, because every path from s₀ to n must go through one of the p_i, but every path from s₀ to a p_i must go through d. Conversely, if d dominates n, it must dominate all the p_i ; otherwise there would be a path from s₀ to n going through the predecessor not dominated by d. Let D[n] be the set of nodes that dominate n. Then

The simultaneous equations can be solved, as usual, by iteration, treating each equation as an assignment statement. However, in this case each set D[n] (for n ≠ s⁰) must be initialized to hold all the nodes in the graph, because each assignment D[n]← {n}∪… makes D[n] smaller (or unchanged), not larger. This algorithm can be made more efficient by ordering the set assignments in quasi-topological order, that is, according to a depth-first search of the graph (Algorithm 17.5). describes a faster algorithm for computing dominators.

Technically, an unreachable node is dominated by every node in the graph; we will avoid the pathologies this can cause by deleting unreachable nodes from the graph before calculating dominators and doing loop optimizations. See also Exercise 18.4.

IMMEDIATE DOMINATORS

Theorem: In a connected graph, suppose d dominates n, and e dominates n. Then it must be that either d dominates e, or e dominates d. Proof: (By contradiction.) Suppose neither d nor e dominates the other. Then there is some path from s₀ to e that does not go through d. Therefore any path from e to n must go through d;otherwise d would not dominate n. Conversely, any path from d to n must go through e. But this means that to get from e to n the path must infinitely loop from d to e to d …and never get to n. This theorem tells us that every node n has no more than one immediate dominator, idom.n), such that

1. idom(n) is not the same node as n,
2. idom(n) dominates n, and
3. idom(n) does not dominate any other dominator of n.

Every node except s₀ is dominated by at least one node other than itself (since s₀ dominates every node), so every node except s₀ has exactly one immediate dominator. Dominator tree Let us draw a graph containing every node of the flow graph, and for every node n an edge from idom(n) to n. The resulting graph will be a tree, because each node has exactly one immediate dominator. This is called the dominator tree. Image 18.3 shows a flow graph and its dominator tree. Some edges in the dominator tree correspond to single flow-graph edges (such as 4 → 6), but others do not (such as 4 → 7). That is, the immediate dominator of a node is not necessarily its predecessor in the flow graph.
Image 18.3: (a) A flow graph; (b) its dominator tree.

A flow-graph edge from a node n to a node h that dominates n is called a back edge. For every back edge there is a corresponding subgraph of the flow graph that is a loop. The back edges in Image 18.3a are 3 → 2, 4 → 2, 10 → 5, 9 → 8.

LOOPS

The natural loop of a back edge n → h, where h dominates n, isthesetof nodes x such that h dominates x and there is a path from x to n not containing h. The header of this loop will be h. The natural loop of the back edge 10 → 5 from Image 18.3a includes nodes 5, 8, 9, 10 and has the loop 8, 9 nested within it. A node h can be the header of more than one natural loop, if there is more than one back edge into h. In Image 18.3a, the natural loop of 3 → 2 consists of the nodes 3, 2 and the natural loop of 4 → 2 consists of 4, 2. The loop optimizations described in this chapter can cope with any loop, whether it is a natural loop or not, and whether or not that loop shares its header with some other loop. However, we usually want to optimize an inner loop first, because most of the program's execution time is expected to be in the inner loop. If two loops share a header, then it is hard to determine which should be considered the inner loop. A common way of solving this problem is to merge all the natural loops with the same header. The result will not necessarily be a natural loop. If we merge all the loops with header 2 in Image 18.3a, we obtain the loop 2, 3, 4 - which is not a natural loop. Nested loops If A and B are loops with headers a and b, respectively, such that a ≠ b and b is in A, then the nodes of B are a proper subset of the nodes of A. We say that loop B is nested within A, orthat B is the inner loop. We can construct a loop-nest tree of loops in a program. The procedure is, for a flow graph G:

1. Compute dominators of G.
2. Construct the dominator tree.
3. Find all the natural loops, and thus all the loop-header nodes.
4. For each loop header h, merge all the natural loops of h into a single loop, loop[h].
5. Construct the tree of loop headers (and implicitly loops), such that h₁ is above h₂ in the tree if h₂ is in loop[h₁].

The leaves of the loop-nest tree are the innermost loops. Just to have a place to put nodes not in any loop, we could say that the entire procedure body is a pseudo-loop that sits at the root of the loop-nest tree. The loop-nest tree of Image 18.3 is shown in Image 18.4.
Image 18.4: The loop-nest tree for Image 18.3a. Each loop header is shown in the top half of each oval (nodes 1, 2, 5, 8); a loop comprises a header node (e.g., node 5), all the other nodes shown in the same oval (e.g., node 10), and all the nodes shown in subtrees of the loop-nest-tree node (e.g., 8, 9).

LOOP PREHEADER

Many loop optimizations will insert statements immediately before the loop executes. For example, loop-invariant hoisting moves a statement from inside the loop to immediately before the loop. Where should such statements be put? Image 18.5a illustrates a problem: If we want to insert statement s into a basic block immediately before the loop, we need to put s at the end of blocks 2 and 3. In order to have one place to put such statements, we insert a new, initially empty, preheader node p outside the loop, with an edge p → h. All edges x → h from nodes x inside the loop are left unchanged, but all existing edges y → h from nodes y outside the loop are redirected to point to p.
Image 18.5: (a) A loop; (b) the same loop with a preheader.