Program improvement by the selective integration of procedure calls
John Ball · 1983
This thesis investigates the application of program transformations which are characterized by a true trade-off between code execution speed and code space. The transformations considered involve modifications of procedure calls, ranging from the complete inline expansion of a procedure body at the point of call, to the creation of specialized procedure bodies optimized for particular calling sequences. Because these transformations involve duplicating code sequences, they can not be considered optimizations in the traditional sense. That is, they can not be applied at every point at which the transformation is legal without running the risk of actually increasing the program's use of valuable resources. The thesis argues that the performance improvements to be gained from procedure call transformations can be quite significant, yet with current language systems, a programmer can only achieve them by sacrificing program modularity and clarity. It then demonstrates the feasibility of automatically selecting an appropriate set of transformations, based on information about program structure gained from data flow analysis and execution frequency statistics. The value of one of these procedure call transformations depends on several factors: first, the relative frequency of execution of the procedure call; secondly, the amount of traditional optimization which will become possible after the transformation is performed; and finally, the cost in additional code space added by the transformation. The system analyzes each procedure body, and estimates its sensitivity to information about its parameters: how much optimization could be performed on the procedure if the value of any of its parameters were known? It then uses these estimates to evaluate individual calling points to the procedure, and predict the value of integrating or specializing that call. Finally, it selects a set of procedure call transformations which are most likely to result in further savings by traditional optimizations on the expanded procedure bodies. The methods described have been implemented in a demonstration system for a small Algol-based language calld PLZ: the thesis describes the analysis algorithms used, and discusses the effectiveness of several strategies for selecting an appropriate set of transformations for a particular program.