Loops in Flow Graphs
Introduction: In our discussion so far, loops have not been handled differently; they have been treated just like any other kind of control flow. However, loops are important because programs spend most of their time executing them, and optimizations that improve the performance of loops can have a significant impact. Thus, it is essential that we identify loops and treat them specially. Loops also affect the running time of program analyses. If a program does not contain any loops, we can obtain the answers to data-flow problems by making just one pass through the program. For example, a forward data-flow problem can be solved by visiting all the nodes once, in topological order.
In this section, we introduce the following concepts: dominators, depth-first ordering, back edges, graph depth, and reducibility. Each of these is needed for our subsequent discussions on finding loops and the speed of convergence of iterative data-flow analysis.
Dominators: We say node d of a flow graph dominates node n, written d dom n, if every pathfrom the entry node of the flow graph to n goes through d. Note that underthis definition, every node dominates itself.
Example: Consider the flow graph of Fig. 9.38, with entry node 1. The entry node dominates every node (this statement is true for every flow graph). Node 2 dominates only itself, since control can reach any other node along a path that begins with 1 -> 3. Node 3 dominates all but 1 and 2. Node 4 dominates all but 1, 2 and 3, since all paths from 1 must begin with l - > - 2 - > - 3 - > - 4 or 1 3 4. Nodes 5 and 6 dominate only themselves, since flow of control can skip around either by going through the other. Finally, 7 dominates 7, 8, 9, and 10; 8 dominates 8, 9, and 10; 9 and 10 dominate only themselves.
A useful way of presenting dominator information is in a tree, called the dominator tree, in which the entry node is the root, and each node d dominates only its descendants in the tree. For example, Fig. 9.39 shows the dominator tree for the flow graph of Fig. 9.38
The existence of dominator trees follows from a property of dominators: each node n has a unique immediate dominator m that is the last dominator of n on any path from the entry node to n. In terms of the dom relation, the immediate dominator m has that property that if d ^ n and d dom n, then d dom m.
We shall give a simple algorithm for computing the dominators of every node n in a flow graph, based on the principle that if pi,p2, . . . ,Pk are all the predecessors of n, and d ^ n, then d dom n if and only if d dom pi for each i. This problem can be formulated as a forward data-flow analysis. The data-flow values are sets of basic blocks. A node's set of dominators, other than itself, is the intersection of the dominators of all its predecessors; thus the meet operator is set intersection. The transfer function for block B simply adds B itself to the set of input nodes. The boundary condition is that the ENTRY node dominates itself. Finally, the initialization of the interior nodes is the universal set, that is, the set of all nodes.
Algorithm: Finding dominators.
INPUT: A flow graph G with set of nodes N, set of edges E and entry node ENTRY.
OUTPUT: D(n), the set of nodes that dominate node n, for all nodes n in N.
METHOD: Find the solution to the data-flow problem whose parameters are shown in Fig. 9.40. The basic blocks are the nodes. D(n) = OUT[n] for all n in N.
Finding dominators using this data-flow algorithm is efficient. Nodes in the graph need to be visited only a few times, as we shall see in Section 9.6.7.