A FRAMEWORK FOR GENERALIZED CONTROL DEPENDENCE

We generalize the notion of dominance by defining a generalized domina nce relation with respect to a set of paths in the control flow graph G = (V, E). This new definition leads to a generalized notion of contr ol dependence, which includes standard control dependence and weak: co ntrol dependence as special cases. If the set of paths underlying a ge neralized dominance relation satisfies some natural closure conditions , that dominance relation is tree-structured. Given this tree, the cor responding control dependence relation can be computed optimally by re duction to the Roman Chariots Problem, which we have developed previou sly for computing standard control dependence. More precisely, given l inear preprocessing time and space, we can answer the (generalized ver sion of the) so called ed, conds, and cdequiv queries in time proporti onal to the output of the query. To illustrate the utility of the fram ework, we show how weak control dependence can be computed optimally i n O(\E\) preprocessing space and time. This improves the O(\V\(3)) tim e required by the best previous algorithm for this problem.