Node listings applied to data flow analysis

ABSTRACT

A new approach to global program data flow analysis which constructs a "node listing" 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.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 2: {AU2} Aho, A. V. and Ullman, J. D., Private Communication.
• 3: Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
• 4: P. E. Allen, A method for determining program data relationships, Proceedings of the International Sympoisum on Theoretical Programming, p.299-308, August 07-11, 1972
• 5: {AC} Allen, F. E., and Cocke, J., "Graph Theoretic Constructs for Program Control Flow Analysis," IBM Research Report RC4633, T. J. Watson Research Center, Yorktown Heights, New York, Nov., 1973.
• 6: Corrado Böhm , Giuseppe Jacopini, Flow diagrams, turing machines and languages with only two formation rules, Communications of the ACM, v.9 n.5, p.366-371, May 1966 [doi>10.1145/355592.365646]
• 7: Ole Johan Dahl, Structured Programming, Academic Press, Inc., Orlando, FL, 1972
• 8: Matthew S. Hecht , Jeffrey D. Ullman, Analysis of a simple algorithm global data flow problems, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.207-217, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512946]
• 9: {HU2} Hecht, M. S. and Ullman, J. D., "Flow Graph Reducibility," SIAM J. Computing, Vol. 1, No. 2, pp. 188-202, June 1972.
• 10: M. S. Hecht , J. D. Ullman, Characterizations of Reducible Flow Graphs, Journal of the ACM (JACM), v.21 n.3, p.367-375, July 1974 [doi>10.1145/321832.321835]
• 11: {Ke1} Kennedy, K., "Safety of Code Motion", International J. Computer Math, Vol. 3, pp. 5-15, Dec. 1971.
• 12: {Ke2} Kennedy, K., "A Comparison of Algorithms for Global Flow Analysis," Technical Report 476-093-1, Dept. of Mathematical Sciences, Rice Univ., Houston, Texas, February 1974.
• 13: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 14: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 15: {Kn2} Knuth, D. E., "Structured Programming with goto Statements," draft, Jan. 1974.
• 16: Marvin Schaefer, A mathematical theory of global program optimization (Prentice-Hall series in automatic computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1973
• 17: {U} Ullman, J. D., "Fast Algorithms for the Elimination of Common Subexpressions", Acta Informatica, Vol. 2, No. 3, pp. 191-213, 1973.
• 18: Charles T. Zahn, Jr., A control statement for natural top-down structured programming, Programming Symposium, Proceedings Colloque sur la Programmation, p.170-180, April 09-11, 1974