Node listings applied to data flow analysis

Abstract

A new approach to global program data flow analysis which constructs a for the control flow graph is discussed and a simple algorithm which uses a node listing to determine the live variables in a program is presented. This algorithm combined with a fast node listing constructor due to Aho and Ullman has produced an 0(n log n) algorithm for live analysis. The utility of the node-listing method is demonstrated by an examination of the class of graphs for which short listings exist. This class is quite similar to the class of graphs for understandable programs.