Previous Next |
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_{0} 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_{0} to n must go through d. Every node dominates itself.
Consider a node n with predecessors p_{1},…, 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_{0} to n must go through one of the p_{i}, but every path from s_{0} 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_{0} 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^{0}) 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.
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_{0} 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
idom(n) is not the same node as n,
Every node except s_{0} is dominated by at least one node other than itself (since s_{0} dominates every node), so every node except s_{0} 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.
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.
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:
Compute dominators of G.
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.
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.
JaVa | Previous Next |