Browse Prior Art Database

Control Dependence Algorithm for Parallel Programming Disclosure Number: IPCOM000036632D
Original Publication Date: 1989-Oct-01
Included in the Prior Art Database: 2005-Jan-29

Publishing Venue


Related People

Cytron, R Ferrante, J [+details]


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.