Profile-Driven Compilation
Abstract
As the size and complexity of software continues to grow, it will be necessary for software construction systems to collect, maintain, and utilize much more information about programs than systems do now. This dissertation explores compiler utilization of profile data. Several widely held assumptions about collecting profile data are not true. It is not true that the optimal instrumentation problem has been solved, and it is not true that counting traversals of the arcs of a program flow graph is more expensive and complex than counting executions of basic blocks. There are simple program flow graphs for which finding optimal instrumentations is possibly exponential. An algorithm is presented that computes instrumentations of a program to count arc traversals \201and therefore basic block counts also\202. Such instrumentations impose 10% to 20% overhead on the execution of a program, often less than the overhead required for collecting basic block execution counts. An algorithm called Greedy Sewing improves the behavior of programs on machines with instruction caches. By moving basic blocks physically closer together if they are executed close together in time, miss rates in instruction caches can be reduced up to 50%. Arc-count profile data not only allows the compiler to know which basic blocks to move closer together, it also allows those situations that will have little or no effect on the final performance of the reorganized program to be ignored. Such a low-level compiler optimization would be difficult to do without arc-count profile data. The primary contribution of this work is the development of TYPESETTER, a programming system that utilizes profile data to select implementations of program abstractions. The system integrates the development, evaluation, and selection of alternative implementations of programming abstractions into a package that is transparent to the programmer.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1991
- Accession Number
- ADA604333
Entities
People
- Alan D. Samples
Organizations
- University of California, Berkeley