Access Restriction

Author Purdom, Paul W. ♦ Moore, Edward F.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Articulation ♦ Program optimization ♦ Predominator ♦ Shortest path ♦ Connectivity ♦ Graph theory ♦ Immediate predominator ♦ Optimizing compiler ♦ Directed graph
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.
Description Affiliation: Univ. of Wisconsin, Madison (Purdom, Paul W.; Moore, Edward F.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 15
Issue Number 8
Page Count 2
Starting Page 777
Ending Page 778

Open content in new tab

   Open content in new tab
Source: ACM Digital Library