A Study of the Effects of Subprogram Inlining

Abstract

This dissertation examines subprogram inlining, a widely-known code optimization technique whose effects were not well understood prior to this study. For a set of test programs on several computer systems, the sizes and runtimes of executable files produced using a tool that automatically substitutes subprograms inline were compared with those of versions in which call sites were not expanded inline. Issues raised by this experiment's results led to the formulation of equations hypothesized to estimate the execution time performance of noninlined and inlined versions of a program. The accuracy of the equations' description of inlined program execution time behavior was demonstrated on four computer systems. Investigation with the equations provided insights of interest to machine and compiler designers. Using the equations, knowledge about the influence of certain factors on the speed of inlined code was gained. Contrary to a number of published reports in the literature, the increased size of inlined code was not found to affect its execution time performance on a set of demand-paged virtual memory machines. In addition, a modest improvement in the caching and paging behavior of test programs' inlined versions was noted. Situations in which inlining was not beneficial, which were associated with its interactions with register allocation, were characterized. Furthermore, in connection with developing the inlining tool, discoveries were made: an efficient way of organizing an inliner was devised, a new optimization for supplementing inlining's effects was invented, inlining issues related to particular C constructs were identified, and a novel approach to inlining recursive subprograrns was conceived. Note: Abstract extracted from PDF file via OCR