% Efficient Computation of Interprocedural Control Dependence


Control dependence information is useful for a wide range of software
maintenance and testing tasks.  For example, program slicers use it to
determine statements and predicates that might affect the value of a
particular variable at a particular program location. In the
intraprocedural context an optimal algorithm is known for computing
control dependence which unfortunately relies critically on the underlying 
intraprocedural postdominance relation being tree-structured.
Hence, this algorithm is not directly applicable to the interprocedural case
where the transitive reduction of the postdominance relation can be a
directed acyclic graph (DAG), with nodes having multiple immediate dominators.

In this paper we present two efficient, conceptually simple algorithms
for computing the interprocedural postdominance relation that can be used to
compute interprocedural control dependence. For an interprocedural
control flow graph $G=(V,E)$, our reachability based algorithm takes time
and space $O(|V|^2 + |V||E|)$.  Unlike other algorithms, it does not perform
confluence operations on whole bit-vectors and can be tuned to concentrate
on the interprocedural rather than intraprocedural relations in a
program thus allowing it to scale better to larger programs.
