An analysis of inline substitution for a structured programming language

ABSTRACT

An optimization technique known as inline substitution is analyzed. The optimization consists of replacing a procedure invocation by a modified copy of the procedure body. The general problem of using inline substitution to minimize execution time subject to size constraints is formulated, and an approximate algorithmic solution is proposed. The algorithm depends on run-time statistics about the program to be optimized. Preliminary results for the CLU structured programming language indicate that, in programs with a low degree of recursion, over 90 percent of all procedure calls can be eliminated, with little increase in the size of compiled code and a small savings in execution time. Other conclusions based on these results are also presented.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Atkinson, R.R. Optimization techniques for a structured programming language. S .M. Th., M.I .T., Cambridge, Mass., 1976.
• 3: John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
• 4: Hoare, C.A.R., Quicksort. Comput. J. 5, 1 (April 1962), 10- 15.
• 5: Galley, S.W., and Pfister, G. The MDL Primer and Manual. SYS.11.01, Lab. Comptr. Sci. M.I.T., Cambridge, Mass., 1975.
• 6: Knuth, D.E. An empirical study of FORTRAN programs. Software - Practice and Experience 1,2 (April-June 1971), 105-133.
• 7: Liskov, B.H., et al. Abstraction mechanisms in CLU. Computation Structures Group Memo 144-1. Lab. Comptr. Sci., M.I.T., Cambridge, Mass., Jan. 1977.
• 8: Barbara Liskov , Stephen Zilles, Programming with abstract data types, Proceedings of the ACM SIGPLAN symposium on Very high level languages, p.50-59, March 28-29, 1974, Santa Monica, California, United States
• 9: J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger , P. Naur, Revised report on the algorithm language ALGOL 60, Communications of the ACM, v.6 n.1, p.1-17, Jan. 1963 [doi>10.1145/366193.366201]
• 10: Palm, R.C. A portable optimizer for the language C. S.M. Th., M.I.T., Cambridge, Mass., 1975.
• 11: T. W. Pratt, Programming languages: design and implementation (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1983
• 12: Rivest, R.L. Private communication.
• 13: Sartaj Sahni, Approximate Algorithms for the 0/1 Knapsack Problem, Journal of the ACM (JACM), v.22 n.1, p.115-124, Jan. 1975 [doi>10.1145/321864.321873]
• 14: Marvin Schaefer, A mathematical theory of global program optimization (Prentice-Hall series in automatic computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1973
• 15: Schneck, P.B., and Angel, E. A FORTRAN to FORTRAN optimizing compiler. Comput. J. 16, 4 (Nov. 1973), 322-330.
• 16: Zelkowitz, M.V., and Bail, W.G. Optimization of structured programs. Software- Practice and Experience 4, 1 (Jan.-March 1974), 51-57.

INDEX TERMS

Keywords:
compilers, inline substitution, open coding, open compilation, program optimization, run-time statistics, structured programming languages