Symbolic evaluation and the global value graph

ABSTRACT

This paper is concerned with difficult global flow problems which require the symbolic evaluation of programs. We use, as is common in global flow analysis, a model in which the expressions computed are specified, but the flow of control is indicated only by a directed graph whose nodes are blocks of assignment statements. We show that if such a program model is interpreted in the domain of integer arithmetic then many natural global flow problems are unsolvable. We then develop a direct (non-iterative) method for finding general symbolic values for program expressions. Our method gives results similar to an iterative method due to Kildall and a direct method due to Fong, Kam, and Ullman. By means of a structure called the global value graph which compactly represents both symbolic values and the flow of these values through the program, we are able to obtain results that are as strong as either of these algorithms at a lower time cost, while retaining applicability to all flow graphs.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 2: Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
• 3: John Cocke, Global common subexpression elimination, ACM SIGPLAN Notices, v.5 n.7, p.20-24, July 1970
• 4: {CA} Cocke, J. and Allen, F. E., "A catalogue of Optimization Transformations," Design and Optimization of Computers, R. Rustin, ed.), Printice-Hall, (1971), pp 1-30.
• 5: Amelia Fong , John Kam , Jeffrey Ullman, Application of lattice algebra to loop optimization, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-9, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512977]
• 6: Amelia C. Fong , Jeffrey D. Ullman, Induction variables in very high level languages, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.104-112, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811544]
• 7: Charles Matthew Geschke, Global program optimizations., 1973
• 8: Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
• 9: 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]
• 10: John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
• 11: {KU2} Kam, J. B. and Ullman, J. D., "Monotone data flow analysis frameworks," Technical Report 167, Computer Science Department, Princeton University, (Jan. 1976).
• 12: {K} Karr, M, "P-graphs," Massachusetts Computer Associates, CAID-7501-1511, (Jan. 1975).
• 13: {Ke1} Kennedy, K., "Safety of code motion," International J. Computer Math., vol. 3, (Dec. 1971), pp. 5-15.
• 14: {Ke2} Kennedy, K., "A comparison of algorithms for global glow analysis," TR 476-093-1, Dept of Mathematical Sciences, Rice Univ., Houston, Texas, (Feb. 1974).
• 15: K. W. Kennedy, Node listings applied to data flow analysis, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.10-21, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512978]
• 16: 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]
• 17: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 18: Donald E. Knuth, Big Omicron and big Omega and big Theta, ACM SIGACT News, v.8 n.2, p.18-24, April-June 1976 [doi>10.1145/1008328.1008329]
• 19: David B. Loveman , Ross A. Faneuf, Program optimization - theory and practice, Proceedings of the conference on Programming languages and compilers for parallel and vector machines, p.97-102, March 18-19, 1975, New York, New York
• 20: {M} Matijasevic, Y., "Enumerable sets are diophantine," (Russian), Dodl. Akad. Nauk SSSR 191 (1970), pp. 279-282.
• 21: {R} Reif, J. H., Ph.D. Dissertation, in progress.
• 22: {S} Schaefer, M., A Mathematical Theory of Global Analysis, Prentice-Hall, Englewood Cliffs, N.J., (1973).
• 23: {Sc} Schwartz, J. T., "Optimization of very high level languages -- value transmission and its corollaries," Computer Languages, V. 1, (1975), pp. 161-194.
• 24: {SS} Shapiro, R. and Saint, H., "The representation of algorithms R?DC, Technical Report 313, Vol., June (1972).
• 25: {T1} Tarjan, R. E., "Depth-first search and linear graph algorithms," SIAM J. Computing, Vol. 1, No. 2, (June 1972), pp. 146-160.
• 26: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 27: Robert E Tarjan, Applications of path compression on balanced trees., Stanford University, Stanford, CA, 1975
• 28: Robert E Tarjan, Solving path problems on directed graphs., Stanford University, Stanford, CA, 1975
• 29: {T5} Tarjan, R., Personal communication to M. Karr, (1976).
• 30: {U} Ullman, J. D., "Fast algorithms for elimination of common subexpressions," Acta Informatica, Vol. 2, N. 3, (Dec. 1973), pp 191-213.
• 31: Ben Wegbreit, The synthesis of loop predicates, Communications of the ACM, v.17 n.2, p.102-113, Feb. 1974 [doi>10.1145/360827.360850]