Thumbnail
Access Restriction
Subscribed

Author Graham, Susan L. ♦ Wegman, Mark
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1976
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract A new algorithm for global flow analysis on reducible graphs is presented. The algorithm is shown to treat a very general class of function spaces. For a graph of $\textit{e}$ edges, the algorithm has a worst-case time bound of $\textit{O}(\textit{e}$ log $\textit{e})$ function operations. It is also shown that in programming terms, the number of operations is proportional to $\textit{e}$ plus the number of exits from program loops. Consequently a restriction to one-entry one-exit control structures guarantees linearity. The algorithm can be extended to yet larger classes of function spaces and graphs by relaxing the time bound. Examples are given of code improvement problems which can be solved using the algorithm.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1976-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 23
Issue Number 1
Page Count 31
Starting Page 172
Ending Page 202


Open content in new tab

   Open content in new tab
Source: ACM Digital Library