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:Java ScreenShot

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 r → s to the start node s of G (indicating that the surrounding program might enter G) and an edge r → exit 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 y → x whenever G has an edge x → y;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 x → y whenever x∉ DFG′[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. shows the CDG for the program of .
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 A → B composed of SSA use-def edges and CDG edges, then there is a Tutorial of data- and control-dependence requiring A to be performed before B.

AGGRESSIVE DEAD-CODE ELIMINATION

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

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). shows the amusing result of running this algorithm on the program of : The entire loop is deleted, leaving a very efficient program!
Image 19.16: Aggressive dead-code elimination

Caveat. The aggressive dead-code elimination algorithm will remove output-free infinite loops, which does change the meaning of the program. Instead of producing nothing, the program will execute the statements after the loop, which may produce output. In many environments this is regarded as unacceptable.

But on the other hand, the control-dependence graph is often used in parallelizing compilers: Any two statements that are not control-dependent or data-dependent can be executed in parallel. Even if such a compiler did not delete a useless infinite loop, it might choose to execute the loop in parallel with successor statements (that are not control-dependent on it); this would have approximately the same effect as deleting the infinite loop.