A program form based on data dependency in predicate regions

ABSTRACT

A new program representation is presented which permits certain optimizations to be performed at less expense than with other forms. This paper describes code motion, common subexpression elimination and induction variable detection. Scalar propagation and constant folding are sketched here, but detailed elsewhere. The powerful code motion strategy allows entire regions of the program to be moved. The representation described may be used as a compiler intermediate form or simply as a model for program analysis. It has great potential for use in translation for parallel machines.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: Allen, Frances E. and Cocke, John. Graph theoretic constructs for program control flow analysis. IBM Research Report RC-3923 (July 1972) 65 pages.
• 3: Allen, Frances E. and Cocke, John. A catalogue of optimizing transformations in Design and Optimization of Compilers (Randall Rustin, Ed.) Prentice-Hall (1972) 1-30.
• 4: Allen, Frances E., Cocke, John., and Kennedy, K. Reduction of operator strength Program Flow Analysis (Muchnik, S., and Jones, N., Eds.) Prentice-Hall (1981) 79-101.
• 5: Allen, John R. and Kennedy, Ken. PFC: a program to convert Fortran to parallel form. Rice MASC TR82-6 (March 1982) 63 pages.
• 6: Banerjee,U. Data dependence in ordinary programs. University of Illinois Department of Computer Science Report 76-837 (November 1976).
• 7: J. Lawrence Carter, A case study of a new code generation technique for compilers, Communications of the ACM, v.20 n.12, p.914-920, Dec. 1977 [doi>10.1145/359897.359902]
• 8: Chaitin, Gregory J.; Auslander, Marc A.; Chandra, Ashok K.; Cocke, John; Hopkins, Martin E.; and Markstein, Peter W. Register allocation via coloring. Computer Languages 6 (1981) 47-57.
• 9: John Cocke , Ken Kennedy, An algorithm for reduction of operator strength, Communications of the ACM, v.20 n.11, p.850-856, Nov. 1977 [doi>10.1145/359863.359888]
• 10: John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
• 11: Dennis, Jack B. Data flow supercomputers. IEEE Computer 13, 11 (Nov. 1980) 48-56.
• 12: Dennis J. Frailey, Expression optimization using unary complement operators, Proceedings of a symposium on Compiler optimization, p.67-85, July 27-28, 1970, Urbana-Champaign, Illinois
• 13: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 14: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• 15: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 16: L. B. Montz, SAFETY AND OPTIMIZATION TRANSFORMATIONS FOR DATA FLOW PROGRAMS, Massachusetts Institute of Technology, Cambridge, MA, 1980
• 17: Ottenstein, Karl J. A fast algorithm for scalar propagation and constant folding. Dept. of Math. and Computer Sciences, Mich. Tech. Univ. (August 1982). Submitted for publication.
• 18: Ottenstein, Karl J. An intermediate program form based on a cyclic data-dependency graph. CS-TR 81-1, Dept. of Math. and Computer Sciences, Mich. Tech. Univ. (Oct. 1981) Submitted for publication.
• 19: Karl Joseph Ottenstein, Data-flow graphs as an intermediate program form., 1978
• 20: Pottosin, I. V. Economy of expressions in the alpha-translator, appearing in The ALPHA automatic programming system (A. P. Yershov, ed.; J. McWilliams, trans.) Academic Press (1971) 149-159.
• 21: Standish, T. A., Harriman, D. C., Kibler, D. F. and Neighbors, J. M. The Irvine Program Transformation Catalogue. Dept. of Info. and Computer Science, Univ. of Calif, Irvine (Jan 7, 1976) 82 pages.
• 22: Treleaven, Philip C.; Hopkins, Richard P. and Rautenbach, Paul W. Combining data flow and control flow computing. The Computer Journal 25, 2 (1982) 207-217.
• 23: Urschler,G. Complete redundant expression elimination in flow diagrams. IBM Research Report RC 4965 T.J. Watson Research Center, Yorktown Heights, N.Y. (August 1974).
• 24: Wegbright, B. Property extraction in well founded property sets. Software Engineering (September 1975) 270-285.
• 25: Mark N. Wegman, General and efficient methods for global code improvement, 1981
• 26: William Allan Wulf , Richard K. Johnsson , Charles B. Weinstock , Steven O. Hobbs , Charles M. Geschke, The Design of an Optimizing Compiler, Elsevier Science Inc., New York, NY, 1975