Profile guided code positioning

ABSTRACT

This paper presents the results of our investigation of code positioning techniques using execution profile data as input into the compilation process. The primary objective of the positioning is to reduce the overhead of the instruction memory hierarchy. After initial investigation in the literature, we decided to implement two prototypes for the Hewlett-Packard Precision Architecture (PA-RISC). The first, built on top of the linker, positions code based on whole procedures. This prototype has the ability to move procedures into an order that is determined by a “closest is best” strategy. The second prototype, built on top of an existing optimizer package, positions code based on basic blocks within procedures. Groups of basic blocks that would be better as straight-line sequences are identified as chains. These chains are then ordered according to branch heuristics. Code that is never executed during the data collection runs can be physically separated from the primary code of a procedure by a technique we devised called procedure splitting. The algorithms we implemented are described through examples in this paper. The performance improvements from our work are also summarized in various tables and charts.

REFERENCES

• CMR88: D. S. Coutant , S. Meloy , M. Ruscetta, DOC: a practical approach to source-level debugging of globally optimized code, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.125-134, June 20-24, 1988, Atlanta, Georgia, United States
• DV87: Jack W. Davidson , Richard A. Vaughan, The effect of instruction set complexity on program size and memory performance, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.60-64, October 1987, Palo Alto, California, United States
• Fer74: Domenico Ferrari, Improving locality by critical working sets, Communications of the ACM, v.17 n.11, p.614-620, Nov. 1974 [doi>10.1145/361179.361195]
• Fer76: Ferrari, 'The Improvement of Program Behavior," Cotnputer, Vol. 9, No. 11, November 1976, pp. 39-47.
• GKM82: Susan L. Graham , Peter B. Kessler , Marshall K. Mckusick, Gprof: A call graph execution profiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.120-126, June 23-25, 1982, Boston, Massachusetts, United States
• Har88: S. J. Hartley, Compile-Time Program Restructuring in Multiprogrammed Virtual Memory Systems, IEEE Transactions on Software Engineering, v.14 n.11, p.1640-1644, November 1988 [doi>10.1109/32.9051]
• HG71: Hatfield and Gerald, 'Trogram Restructuring for Virtual Memory," IBM Systems Journal, Vol. 10, No. 3, 1971, pp. 168-192.
• HC89: W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, Proceedings of the 16th annual international symposium on Computer architecture, p.242-251, April 1989, Jerusalem, Israel
• McF89: S. McFarling, Program optimization for instruction caches, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.183-191, April 03-06, 1989, Boston, Massachusetts, United States
• Sar89: V. Sarkar, Determining average program execution times and their variance, ACM SIGPLAN Notices, v.24 n.7, p.298-312, July 1989

INDEX TERMS

Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Measurement, Performance