Search

This article presents an algorithm related to an immediate predominators in a directed graph prepared by Paul W. Purdom and Edward F. Moore. The authors assume a directed graph whose nodes are labeled by integers between 1 and n. The arcs of this graph correspond to the flow of control between blocks of a computer program. The initial node of this graph is labeled by the integer 1. For optimizing the object code generated by a compiler, the relationship of immediate predominator has been used by scholars Edward S. Lowry and C.W. Medlock. It is said that the node/predominates node k if every path from node 1 to node k passes through node i. Node j is an immediate predominator of node k if node j predominates node k and if every other node i which predominates node k also predominates node j. The precise details of the list representation can be expressed in a more brief and unambiguous manner by a few lines of Algol than by an English description. The predominators of any given node can be computed as in an equation from the immediate predominators, and the articulation points of a graph are the predominators of the exit node.