Managing interprocedural optimization

This 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.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Engineering

Grantor

Rice University

Year dc:date.issued

1991

Author dc:creator

• Hall, Mary Wolcott

Advisor dc:contributor.advisor

• Kennedy, Ken

• Computer science

Statement dc:rights

• Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder.

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1911/16446

OAI identifier oai:identifier

oai:repository.rice.edu:1911/16446