### A Fast and Usually Linear Algorithm for Global Flow AnalysisA Fast and Usually Linear Algorithm for Global Flow Analysis

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

Source: ACM Digital Library