A unified approach to global program optimization

ABSTRACT

A technique is presented for global analysis of program structure in order to perform compile time optimization of object code generated for expressions. The global expression optimization presented includes constant propagation, common subexpression elimination, elimination of redundant register load operations, and live expression analysis. A general purpose program flow analysis algorithm is developed which depends upon the existence of an "optimizing function." The algorithm is defined formally using a directed graph model of program flow structure, and is shown to be correct. Several optimizing functions are defined which, when used in conjunction with the flow analysis algorithm, provide the various forms of code optimization. The flow analysis algorithm is sufficiently general that additional functions can easily be defined for other forms of global code optimization.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , J. D. Ullman, A formal approach to code optimization, Proceedings of a symposium on Compiler optimization, p.86-100, July 27-28, 1970, Urbana-Champaign, Illinois
• 2: Allen, F. Program optimization. In Annual Review in Automatic Programming, Pergamon Press, 5(1969), 239-307.
• 3: ____ A basis for program optimization. IFIP Congress 71, Ljubljana, August, 1971, 64-68.
• 4: Frances E. Allen, Control flow analysis, Proceedings of a symposium on Compiler optimization, p.1-19, July 27-28, 1970, Urbana-Champaign, Illinois
• 5: James P. Anderson, A note on some compiling algorithms, Communications of the ACM, v.7 n.3, p.149-150, March 1964 [doi>10.1145/363958.363976]
• 6: Bruce W. Arden , Bernard A. Galler , Robert M. Graham, An Algorithm for Translating Boolean Expressions, Journal of the ACM (JACM), v.9 n.2, p.222-239, April 1962 [doi>10.1145/321119.321121]
• 7: Bachmann, P. A contribution to the problem of the optimization of programs. IFIP Congress 71, Ljubljana, August, 1971, 74-78.
• 8: Ballard, A., and Tsichritzis, D. Transformations of programs. IFIP Congress 71, Ljubljana, August, 1971, 89-93.
• 9: Melvin A. Breuer, Generation of optimal code for expressions via factorization, Communications of the ACM, v.12 n.6, p.333-340, June 1969 [doi>10.1145/363011.363153]
• 10: Vincent A. Busam , Donald E. Englund, Optimization of expressions in Fortran, Communications of the ACM, v.12 n.12, p.666-674, Dec. 1969 [doi>10.1145/363626.363635]
• 11: John Cocke, Global common subexpression elimination, Proceedings of a symposium on Compiler optimization, p.20-24, July 27-28, 1970, Urbana-Champaign, Illinois
• 12: ____, and Miller, R. Some analysis techniques for optimizing computer programs. Proc. Second International Conference of System Sciences, Hawaii, January, 1969, 143-146.
• 13: John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
• 14: Day, W. Compiler assignment of data items to registers. IBM Systems Journal, 8, 4(1970), 281-317.
• 15: C. P. Earnest , K. G. Balke , J. Anderson, Analysis of Graphs by Ordering of Nodes, Journal of the ACM (JACM), v.19 n.1, p.23-42, Jan. 1972 [doi>10.1145/321679.321683]
• 16: Elson, M., and Rake, S. Code generation technique for large language compilers. IBM Systems Journal 3(1970), 166-188.
• 17: Richard J. Fateman, Optimal code for serial and parallel computation, Communications of the ACM, v.12 n.12, p.694-695, Dec. 1969 [doi>10.1145/363626.363661]
• 18: Finkelstein, M. A compiler optimization technique. The Computer Review (Feb. 1968), 22-25.
• 19: Robert W. Floyd, An algorithm for coding efficient arithmetic operations, Communications of the ACM, v.4 n.1, p.42-51, Jan. 1961 [doi>10.1145/366062.366082]
• 20: 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
• 21: Dennis John Frailey, A study of code optimization using a general purpose optimizer, 1971
• 22: Freiburghouse, R. The MULTICS PL/I compiler. AFIPS Conf. Proc. FJCC (1969), 187-199.
• 23: C. W. Gear, High speed compilation of efficient object code, Communications of the ACM, v.8 n.8, p.483-488, Aug. 1965 [doi>10.1145/365474.365489]
• 24: David Gries, Compiler Construction for Digital Computers, John Wiley & Sons, Inc., New York, NY, 1971
• 25: Hill, V., Langmaack, H., Schwartz, H., and Seegumuller, G. Efficient handling of subscripted variables in ALGOL-60 compilers. Proc. Symbolic Languages in Data Processing, Gordon and Breach, New York, 1962, 331-340.
• 26: Hopkins, M. An optimizing compiler design. IFIP Congress 71, Ljubljana, August, 1971, 69-73.
• 27: L. P. Horwitz , R. M. Karp , R. E. Miller , S. Winograd, Index Register Allocation, Journal of the ACM (JACM), v.13 n.1, p.43-61, Jan. 1966 [doi>10.1145/321312.321317]
• 28: H. D. Huskey , W. H. Wattenburg, Compiling techniques for Boolean expressions and conditional statements in ALGOL 60, Communications of the ACM, v.4 n.1, p.70-75, Jan. 1961 [doi>10.1145/366062.366098]
• 29: Huskey, H. Compiling techniques for algebraic expressions. Computer Journal 4, 4(April 1961), 10-19.
• 30: Huxtable, D. On writing an optimizing translator for ALGOL-60. In Introduction to System Programming, Academic Press, Inc., New York, 1964.
• 31: IBM System/360 Operating System, FORTRAN IV (G and H) Programmer's Guide. c28-6817-1, International Business Machines, 1967, 174-179.
• 32: Kennedy, K. A global flow analysis algorithm. Intern. J. of Computer Mathematics, Section A, Vol. 3, 1971, 5-15.
• 33: Kildall, G. Global expression optimization during compilation. Technical Report No. TR# 72-06-02, University of Washington Computer Science Group, University of Washington, Seattle, Washington, June, 1972.
• 34: ____ A code synthesis filter for basic block optimization. Technical Report No. TR# 72-01-01, University of Washington Computer Science Group, University of Washington, Seattle, Washington, January, 1972.
• 35: Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
• 36: F. Luccio, A comment on index register allocation, Communications of the ACM, v.10 n.9, p.572-574, Sept. 1967 [doi>10.1145/363566.363694]
• 37: Maurer, W. Programming-An Introduction to Computer Language Technique. Holden-Day, San Francisco, 1968, 202-203.
• 38: W. M. McKeeman, Peephole optimization, Communications of the ACM, v.8 n.7, p.443-444, July 1965 [doi>10.1145/364995.365000]
• 39: Ikuo Nakata, On compiling algorithms for arithmetic expressions, Communications of the ACM, v.10 n.8, p.492-494, Aug. 1967 [doi>10.1145/363534.363549]
• 40: J. Nievergelt, On the automatic simplification of computer programs, Communications of the ACM, v.8 n.6, p.366-370, June 1965 [doi>10.1145/364955.364963]
• 41: Painter, J. Compiler effectiveness. Proceedings of a Symposium on Compiler Optimization, University of Illinois at Urbana-Champaign, July, 1970.
• 42: Brian Randall , Lawford J. Russell, Algol-60 Implementation, Academic Press, Inc., Orlando, FL, 1964
• 43: R. R. Redziejowski, On arithmetic expressions and trees, Communications of the ACM, v.12 n.2, p.81-84, Feb. 1969 [doi>10.1145/362848.362859]
• 44: Ryan, J. A direction-independent algorithm for determining the forward and backward compute points for a term or subscript during compilation. Computer Journal 9, 2(Aug. 1966), 157-160.
• 45: Schnieder, V. On the number of registers needed to evaluate arithmetic expressions. BIT 11(1971), 84-93.
• 46: Ravi Sethi , J. D. Ullman, The Generation of Optimal Code for Arithmetic Expressions, Journal of the ACM (JACM), v.17 n.4, p.715-728, Oct. 1970 [doi>10.1145/321607.321620]
• 47: Robert Alan Wagner, Some techniques for algorithm optimization with application to matrix arithmetic expressions, 1968
• 48: A. P. Ershov, On programming of arithmetic operations, Communications of the ACM, v.1 n.8, p.3-6, Aug. 1958 [doi>10.1145/368892.368907]
• 49: A. P. Yershov, ALPHA—An Automatic Programming System of High Efficiency, Journal of the ACM (JACM), v.13 n.1, p.17-24, Jan. 1966 [doi>10.1145/321312.321314]