A Fast and Usually Linear Algorithm for Global Flow Analysis
Susan L. Graham, Mark N. Wegman · Journal of the ACM · 1976
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.
Cited by 187 works. doi:10.1145/321921.321939 Open-access PDF
Authors
References
- Depth-First Search and Linear Graph Algorithms
- An axiomatic basis for computer programming
- Assigning meanings to programs
- The programming language pascal
- Efficiency of a Good But Not Linear Set Union Algorithm
- A unified approach to global program optimization
- Control flow analysis
- Performance predictions for extended paged memories
- Programming languages and their compilers: Preliminary notes
- Global common subexpression elimination