An Analysis of Inline Substitution for a Structured Programming Language 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 constrain ts 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. CACM September, 1977 Scheifler, R. W. inline substitution, open coding, open compilation, program optimization, compilers, structured programming languages, run-time statistics 4.12 CA770905 JB December 27, 1977 1:23 PM 1086 4 2929 1132 4 2929 1234 4 2929 1263 4 2929 1265 4 2929 1270 4 2929 1323 4 2929 1358 4 2929 1379 4 2929 1380 4 2929 1453 4 2929 1464 4 2929 1484 4 2929 1491 4 2929 1498 4 2929 1613 4 2929 1614 4 2929 1781 4 2929 1825 4 2929 1860 4 2929 2083 4 2929 2178 4 2929 2179 4 2929 2252 4 2929 2325 4 2929 2341 4 2929 2546 4 2929 2645 4 2929 2652 4 2929 2684 4 2929 2842 4 2929 2929 4 2929 2934 4 2929 3069 4 2929 669 4 2929 679 4 2929 691 4 2929 761 4 2929 949 4 2929 989 4 2929 2929 5 2929 2929 5 2929 2929 5 2929 3184 5 2929