An Incremental Algorithm for Maintaining the Dominator Tree of a Reducible Flowgraph

G. Ramalingam and Thomas Reps

We present a new incremental algorithm for the problem of maintaining the dominator tree of a reducible flowgraph as the flowgraph undergoes changes such as the insertion and deletion of edges. Such an algorithm has applications in incremental dataflow analysis and incremental compilation.

(Click here to access the paper: PostScript, PDF.)