Report Number: CS-TR-76-547
Institution: Stanford University, Department of Computer Science
Title: Iterative algorithms for global flow analysis
Author: Tarjan, Robert Endre
Date: March 1976
Abstract: This paper studies iterative methods for the global flow analsis of computer programs. We define a hierarchy of global flow problem classes, each solvable by an appropriate generalization of the "node listing" method of Kennedy. We show that each of these generalized methods is optimum, among all iterative algorithms, for solving problems within its class. We give lower bounds on the time required by iterative algorithms for each of the problem classes.