Managing Interprocedural Optimization

This work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/16446This dissertation addresses a number of important issues related to interprocedural optimization. Interprocedural optimization is an integral component in a compilation system for high-performance computing. The importance of interprocedural optimization stems from two sources: it increases the context available to the optimizing compiler, and it enables programmers to use procedure calls without the concern of hurting execution time. While important, interprocedural optimization can introduce some significant compile-time costs. When interprocedural information is used to optimize a procedure, the procedure is then dependent on those interprocedural facts.Thus, even if the procedure is not edited, it may require recompilation due to changes in the interprocedural facts. In addition to these effects on recompilation, interprocedural information can also be expensive to compute.Furthermore, interprocedural optimizations can increase program size which can in turn increase compile time. To make interprocedural optimization feasible in a compilation system, it must be possible to manage the compile-time costs.This dissertation explores some open questions in interprocedural optimization. An efficient algorithm is developed for constructing the call multigraph, the underlying program representation for interprocedural optimization. A procedure cloning algorithm is also described. This algorithm avoids the significant code growth and increased compilation time possible with cloning, while focusing optimization on the most profitable opportunities. We present results of an in-depth study of inline substitution. These results led to a new approach for interprocedural optimization, focusing on enabling only high-payoff optimizations. All of these ideas are brought together in a compilation system supporting interprocedural optimization, which significantly reduces the costs of interprocedural optimization. The compilation system is further adapted to support optimizations for enhancing parallelism