A Fast and Usually Linear Algorithm for Global
Flow Analysis (Abstract only--Complete paper JACM 
23,1 January, 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
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.

CACM December, 1975

Graham, S. L.
Wegman, M.

global flow analysis, data flow, code optimization,
common subexpression elimination, live-dead 
analysis, information propagation, flow graph, reducibility,
go-to-less programming, depth-first search, 
path compression

4.12 5.24 5.25 5.32

CA751206 JB January 5, 1978  4:08 PM

2701	5	2701
2701	5	2701
2701	5	2701