A Fast Algorithm for Finding Dominators in a Flowgraph THOMAS LENGAUER and ROBERT ENDRE TAR JAN Stanford University A fast algoritbm for finding dominators in a flowgraph is presented. The algorithm uses depth-first search and an efficient method of computing functions defined on paths in trees. A simple implemen- tation of the algorithm runs in O(m log n) time, where m is the number of edges and n is the number of vertices in the problem graph. A more sophisticated implementation runs in O(ma(m, n)) time, where a(m, n) is a functional inverse of Ackermann's function. Both versions of the algorithm were implemented in Algol W, a Stanford University version of Algol, and tested on an IBM 370/168. The programs were compared with an implementation by Purdom and Moore of a straightforward O(mn)-time algorithm, and with ~a bit vector algorithm described by Aho and Ullman. The fast algorithm beat the straightforward algorithm and the bit vector algorithm on all but the smallest graphs tested. Key Words and Phrases: depth-first search, dominators, global flow analysis, graph algorithm, path compression CR Categories: 4.12, 4.34, 5.25, 5.32 1. INTRODUCTION The following graph problem arises in the study of global flow analysis and program optimization [2, 6]. Let G = (V, E, r) be a flowgraph 1 with start vertex r. A vertex v dominates another vertex w ~ v in G if every path from r to w contains v. Vertex v is the immediate dominator of w, denoted v ffi idom(w), if v dominates w and every other dominator of w dominates v. THEOREM 1 [2, 6]. Every vertex of a flowgraph G = (V, E, r) except r has a unique immediate dominator. The edges { (idom(w), w) [ w E V - {r}} form a directed tree rooted at r, called the dominator tree of G, such that v dominates w if and only if v is a proper ancestor of w in the dominator tree. See Figures 1 and 2. We wish to construct the dominator tree of an arbitrary flowgraph G. If G represents the flow of control of a computer program which we are trying to Appendix A contains the graph-theoretic terminology used in this paper. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. The research of the first author was partly supported by the German Academic Exchange Service. The research of the second author was partly supported by the National Science Foundation under Grant MCS75-22870 and by the Office of Naval Research under Contract N00014-76-C-0688. Authors' address: Computer Science Department, Stanford University, Stanford, CA 94305. © 1979 ACM 0164-0925/79/0700-0121 $00.75 ACM Transactions on Programming Languages and Systems, Vol. 1, No. 1, July 1979, Pages 121-141.122 T. Lengauerand R. E. Tadan Fig. 1. A flowgraph I Fig. 2. Dominator tree of flowgraph in Fig. 1 optimize, then the dominator tree provides information about what kinds of code motion are safe. For further details see [2, 6]. Aho and Ullman [2] and Purdom and Moore [17] describe a straightforward algorithm for finding dominators. For each vertex v ~ r, we carry out the following step. General Step. Determine, by means of a search from r, the set S of vertices reachable from r by paths which avoid v. The vertices in V - {v} - S are exactly those which v dominates. Knowing the set of vertices dominated by each vertex, it is an easy matter to construct the dominator tree. ACM Transactions on Programming Languages and Systems, Vol. 1, No. 1, July 1979.A Fast Algorithm for Finding Dominators in a Flowgraph 123 To analyze the running time of this algorithm, let us assume that G has m edges and n vertices. Each execution of the general step requires O (rn) time, and the algorithm performs n - 1 executions of the general step; thus the algorithm requires O (rnn) time total. Aho and Ullman [3] describe another simple algorithm for computing domi- nators. This algorithm manipulates bit vectors of length n. Each vertex v has a bit vector which encodes a superset of the dominators of v. The algorithm makes several passes over the graph, updating the bit vectors during each pass, until no further changes to the bit vectors occur. The bit vector for each vertex v then encodes the dominators of v. This algorithm requires O (m) bit vector operations per pass for O (n) passes, or 0 (nm) bit vector operations total. Since each bit vector operation requires O (n) time, the running time of the algorithm is O(n2m). This bound is pessimistic, however; the constant factor associated with the bit vector operations is very small, and on typical graphs representing real programs the number of passes is small (on reducible flowgraphs [3] only two passes are required [4]). In this paper we shall describe a faster algorithm for solving the dominators problem. The algorithm uses depth-first search [9] in combination with a data structure for evaluating functions defined on paths in trees [14]. We present a simple implementation of the algorithm which runs in O (m log n) time and a more sophisticated implementation which runs in O(rna(m, n)) time, where a(rn, n) is a functional inverse of Ackermann's function [1], defined as follows. For integers i,j >_ 0, let A(i, 0) ffi 0 if i _> 0, A(0,j) = 2 y ifj _> 1, A(i, 1) = A(i - 1, 2) if i _> 1, and A(i,j) ffi A(i - 1, A(i,j- 1)) if i __ 1, j_> 2. Then a(m, n) = min{i _> 1 [A(i, I 2rn/n J) > log2n}. The algorithm is a refinement of earlier versions appearing in [10-12]. Although proving its correctness and verifying its running time require rather complicated analysis, the algorithm is quite simple to program and is very fast in practice. We programmed both versions of the algorithm in Algol W, a Stanford University version of Algol, and tested the programs on an IBM 370/168. We compared the programs with a transcription into Algol W of the Purdom-Moore algorithm and with an implementation of the bit vector algorithm. On all but the smallest graphs tested our algorithm beat the other methods. This paper consists of five