Dominators in Linear Time

A linear time algorithm is presented for finding dominators in control flow graphs. 1 Introduction Finding the dominator tree for a control flow graph is one of the most fundamental problems in the area of global flow analysis and program optimization [2, 3, 4, 5, 10, 15]. The problem was first raised in 1969 by Lowry and Medlock [15], where an O(n 4 ) algorithm for the problem was proposed (as usual, n is the number of nodes and m the number of edges in a graph). The result has been improved several times (see e.g. [1, 2, 17, 20]), and in 1979 an O(mff(m; n)) algorithm was found by Lengauer and Tarjan [14]. Finally, at STOC'85, Dov Harel [11] announced a linear time algorithm. Assuming Harel's result, linear time algorithms have been found for many other problems (see e.g. [4, 5, 10]). However, Harel never produced the details of his algorithm and the soundness of his approach has therefore been questioned. Here we first describe some of the concrete problems in Harel's approach, ..