A Fast and Usually Linear Algorithm for Global Flow Analysis
- 1 January 1976
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 23 (1) , 172-202
- https://doi.org/10.1145/321921.321939
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 e edges, the algorithm has a worst-case time bound of O ( e log e ) function operations. It is also shown that in programming terms, the number of operations is proportional to 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.Keywords
This publication has 20 references indexed in Scilit:
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975
- Characterizations of Reducible Flow GraphsJournal of the ACM, 1974
- On the capabilities of while, repeat, and exit statementsCommunications of the ACM, 1973
- A case against the GOTOACM SIGPLAN Notices, 1972
- Flow Graph ReducibilitySIAM Journal on Computing, 1972
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972
- Control flow analysisACM SIGPLAN Notices, 1970
- Global common subexpression eliminationACM SIGPLAN Notices, 1970
- An axiomatic basis for computer programmingCommunications of the ACM, 1969
- Assigning meanings to programsPublished by American Mathematical Society (AMS) ,1967