Immediate predominators in a directed graph [H]

ABSTRACT

We 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 (corresponding to the entry point of the program) is labeled by the integer 1. For optimizing the object code generated by a compiler, the relationship of immediate predominator has been used by Lowry and Medlock [3]. We say that node i predominates node k if every path from node 1 to node k passes through (i.e. both into and out of) 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. It can easily be proved that if k ≠ 1 and node k is reachable from node 1t hen node k has exactly one immediate predominator. In case k = 1, or node k is not reachable from node 1, the immediate predominator of node k is undefined, and the value 0 will be given by the procedure PREDOMINATOR.

REFERENCES

• 1: Allen, F.E. Program optimization. Annual Rev. in Automatic Programming 5 (1969), 239-307.
• 2: Dijkstra, E.W. A note on two problems in connexion with graphs, Numerische Mathematik 1, 5 (Oct. 1959), 269-271.
• 3: Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
• 4: Munro, Jan. Efficient determination of the transitive closure of a directed graph. To be published.
• 5: Purdom, Paul Jr. A transitive closure algorithm, BIT 10, 1 (1970), 76-95.
• 6: Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]

INDEX TERMS

Keywords:
articulation, connectivity, directed graph, graph theory, immediate predominator, optimizing compiler, predominator, program optimization, shortest path