Control Dependence Algorithm for Parallel Programming
Original Publication Date: 1989-Oct-01
Included in the Prior Art Database: 2005-Jan-29
A technique is described for efficiently constructing control dependences. It is an improvement over previous concepts which required quadratic space for intermediate computations and multiple passes over the post-dominator tree. The improved algorithm propagates dependences in a single pass through the post-dominator tree. The technique is provably linear for structured programs.