.png){kind=icon}
Return
A fast algorithm for finding dominators in a flowgraph
.png){kind=icon}
OA
AI
DOI：10.1145/357062.357071.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A fast algorithm 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 implementation 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
(
m
α(
m
,
n
)) time, where α(
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.
Journal
No journal information available
Organization
No organization information available
Cited Papers
No cited papers available