Previous    Next

## THE CONTROL-DEPENDENCE GRAPH

Can node x directly control whether node y is executed? The answer to this question can help us with program transformations and optimizations. Any flowgraph must have an exit node. If a control-flow graph represents a single function, then this is the return statement of the function; if there are several return statements, we assume that each one of them is really a control-flow edge to some unique canonical exit node of the CFG. We say that a node y is control-dependent on x if from x we can branch to u or v; from u there is a path to exit that avoids y, and from v every path to exit hits y:

The control-dependence graph (CDG) has an edge from x to y whenever y is control-dependent on x. We say that y postdominates v when y is on every path from v to exit - that is, y dominates v in the reverse control-flow graph. Construction of the control-dependence graph To construct the CDG of a control-flow graph G,

1. Add a new entry-node r to G, with an edge rs to the start node s of G (indicating that the surrounding program might enter G) and an edge rexit to the exit node of G (indicating that the surrounding program might not execute G at all).

2. Let G′ be the reverse control-flow graph that has an edge yx whenever G has an edge xy;the start node of G′ corresponds to the exit node of G.
3. Construct the dominator tree of G′ (its root corresponds to the exit node of G).
4. Calculate the dominance frontiers DFG′ of the nodes of G′.
5. The CDG has edge xy whenever xDFG′[y].

That is, x directly controls whether y executes, if and only if x is in the dominance frontier of y in the reverse control-flow graph. Image 19.15 shows the CDG for the program of Image 19.4.

Image 19.15: Construction of the control-dependence graph.

With the SSA graph and the control-dependence graph, we can now answer questions of the form, "must A be executed before B?" If there is any path AB composed of SSA use-def edges and CDG edges, then there is a trail of data- and control-dependence requiring A to be performed before B.

One interesting use of the control-dependence graph is in dead-code elimination. Suppose we have a situation such as the one in Image 19.13d, where conventional dead-code analysis (as described in or Algorithm 19.12) determines:

• k2 is live because it's used in the definition of k3,

• k3 is live because it's used in the definition of k2,

but neither variable contributes anything toward the eventual result of the calculation. Just as conditional constant propagation assumes a block is unreachable unless there is evidence that execution can reach it, aggressive dead-code elimination assumes a statement is dead unless it has evidence that it contributes to the eventual result of the program. Algorithm Mark live any statement that:

1. Performs input/output, stores into memory, returns from the function, or calls another function that might have side effects;

2. Defines some variable v that is used by another live statement; or
3. Is a conditional branch, upon which some other live statement is control dependent.

Then delete all unmarked statements. This can be solved by iteration (or by a work-list algorithm). Image 19.16 shows the amusing result of running this algorithm on the program of Image 19.13d: The entire loop is deleted, leaving a very efficient program!