Control Dependence Computation

Control dependence is a program dependence relation that is used widely in optimizing and restructuring compilers. Roughly speaking, a statement S is control dependent on a predicate p if p determines whether or not statement S is executed. For example, statements in the body of a conditional are control dependent on the predicate of that conditional.

In the literature, there are at least two different notions of control dependence.

  1. Most optimizing compilers use a notion called strong control dependence which was defined by Ferrante, Ottenstein, and Warren.
  2. The software engineering community uses a different notion called weak control dependence which was defined by Clarke and Podgurski.

Our research in this area, done jointly with Gianfranco Bilardi at the University of Padova in Italy, has led to practical and theoretically optimal algorithms for solving most control dependence problems. In the description below, |E| and |V| are the number of edges and nodes in the control flow graph respectively.

  1. We have designed a data structure called APT which can answer queries for (strong) control dependence successors and predecessors in time proportional to output size. Preprocessing time and space requirements are O(|E|). This is an improvement over previous algorithms which took O(|E||V|) space and time.
  2. We have developed two fast algorithms for computing regions (that is, the (strong) control dependence equivalence relation which determines which nodes in a control flow graph have the same control dependences). One algorithm requires building the postdominator tree of the program, while the other is based on the cycle-equivalence relation. Both algorithms require O(|E|) time. These are improvements over previous algorithms which required O(|E||V|) time.
  3. We have shown that the APT data structure can be used to answer queries for (weak) control dependence predecessors and successors in time proportional to output size. The preprocessing space and time requirements of our algorithm are O(|E|). The best algorithm prior to ours required O(|E|3) time.
  4. We have defined a notion of generalized control dependence that subsumes both strong and weak control dependence, and shown how to compute generalized control dependence predecessors, successors and regions optimally.
  5. We have developed an algorithm that computes interprocedural dominators and interprocedural control dependence in O(|E||V|) time.

Here are some people who use our work.

A sample implementation of the APT data structure for computing control dependence is available for download. It implements cd, conds and cdeq queries.

Related Publications