Incremental Computation of Dominator Trees

Abstract

In this article, we present a new algorithm for incrementally maintaining the dominator tree of an arbitrary flowgraph.Previous work most relevant to this article includes only the Carroll-Ryder algorithm and the Ramalingam-Reps algorithm.Both these methods are restricted to reducible flowgraphs.By contrast, our approach can handle irreducible as well as reducible flowgraphs.For the case where an edge is inserted, our incremental algorithm is also faster than previous incremental algorithms in the worst case.For the deletion case, our algorithm has a quadratic time complexity in the worst case.