article

Free access

Profile guided code positioning

Authors:

Karl Pettis,

Robert C. HansenAuthors Info & Claims

ACM SIGPLAN Notices, Volume 25, Issue 6

Pages 16 - 27

https://doi.org/10.1145/93548.93550

Published: 01 June 1990 Publication History

PDF eReader

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

[1]

Coutant, Meloy and Ruscetta, 'T)OC: A Practical Approach to Source-Level Debugging of Globally Optim/zecl Code," Proceedings of SiGPLAN '88 Conference on Programming Language Design and Implementation, SiGPLAN Notices, Vol. 23, No. 7, July 1988, pp. 125-134.

Digital Library

Google Scholar

[2]

Davidson and Vaughan, 'The Effect of Instruction Set Complexity on Program Size and Memory Performance," Second International Conference on Architectural Support for Programmb,g Lal2guages and Operating Systems, October 1987, pp. 60-63.

Digital Library

Google Scholar

[3]

Ferrari, "Improving Locality by Critical Working Sets," CACM, Vol. 17, No. 11, November 1974, pp. 614-620.

Digital Library

Google Scholar

[4]

Ferrari, 'The Improvement of Program Behavior," Cotnputer, Vol. 9, No. 11, November 1976, pp. 39-47.

Digital Library

Google Scholar

[5]

Graham, Kessler and McKusick, "gprof: a Call Graph Execution Profiler," Ptvceedings of the SIGPIAN '82 Symposium on Compiler Construction, SIGPLAN Notices, Vol. 17, No. 6, June 1982, pp. 120-126.

Digital Library

Google Scholar

[6]

Hartley, "Compile-T/me Program Restructuring in Multiprogrammed Virtual Memory Systems," IEEE Transactions on Software Engineering Vol. 14, No. 11, November, 1988, pp. 1640-1644.

Digital Library

Google Scholar

[7]

Hatfield and Gerald, 'Trogram Restructuring for Virtual Memory," IBM Systems Journal, Vol. 10, No. 3, 1971, pp. 168-192.

Digital Library

Google Scholar

[8]

Hwu and Chang, "Achieving High Instruction Cache Performance with an Optimizing Compiler," Proc. 16th Sym. on Computer Amhitectum, Jerusalem, Israel, May 1989, pp. 242-250.

Digital Library

Google Scholar

[9]

McFafiing, 'Program Optimization for Instruction Caches," Third International Conference on Amhiteetural Support for Programming Languages and Operating Systems, April 1989, pp. 183-191.

Digital Library

Google Scholar

[10]

Sarkar, "Determining Average Program Execution Times and their Variance," Proceedings of SIGPLAN '89 Conference on Programming Language Design and Implementation, SIGPIA2q Notices, Vol. 24, No. 7, July 1989, pp. 298-312.

Digital Library

Google Scholar

Cited By

View all

Wang WWang Y(2024)Research on Link Optimization Technology Based on Function Reordering2024 5th International Symposium on Computer Engineering and Intelligent Communications (ISCEIC)10.1109/ISCEIC63613.2024.10810229(475-480)Online publication date: 8-Nov-2024
https://doi.org/10.1109/ISCEIC63613.2024.10810229
Wang WWang Y(2024)A Method for Implementing Function Reordering in GNU ld2024 4th International Conference on Electronic Information Engineering and Computer (EIECT)10.1109/EIECT64462.2024.10866982(1002-1005)Online publication date: 15-Nov-2024
https://doi.org/10.1109/EIECT64462.2024.10866982
Čugurović MVujošević Janičić MJovanović VWürthinger T(2024)GraalSPJournal of Systems and Software10.1016/j.jss.2024.112058213:COnline publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.jss.2024.112058
Show More Cited By

Recommendations

Profile guided code positioning
PLDI '90: Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation

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 ...
Profile guided code positioning
20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979-1999: A Selection

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 ...
Profile guided selection of ARM and thumb instructions
LCTES/SCOPES '02: Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems

The ARM processor core is a leading processor design for the embedded domain. In the embedded domain, both memory and energy are important concerns. For this reason the 32 bit ARM processor also supports the 16 bit Thumb instruction set. For a given ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGPLAN Notices Volume 25, Issue 6

Jun. 1990

343 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/93548

Editor:
Marina Chen

Issue’s Table of Contents

PLDI '90: Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation
June 1990
351 pages
ISBN:0897913647
DOI:10.1145/93542
Chairman:
Bernard N. Fischer

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1990

Published in SIGPLAN Volume 25, Issue 6

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

464
Total Citations
View Citations
3,010
Total Downloads

Downloads (Last 12 months)458
Downloads (Last 6 weeks)66

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wang WWang Y(2024)Research on Link Optimization Technology Based on Function Reordering2024 5th International Symposium on Computer Engineering and Intelligent Communications (ISCEIC)10.1109/ISCEIC63613.2024.10810229(475-480)Online publication date: 8-Nov-2024
https://doi.org/10.1109/ISCEIC63613.2024.10810229
Wang WWang Y(2024)A Method for Implementing Function Reordering in GNU ld2024 4th International Conference on Electronic Information Engineering and Computer (EIECT)10.1109/EIECT64462.2024.10866982(1002-1005)Online publication date: 15-Nov-2024
https://doi.org/10.1109/EIECT64462.2024.10866982
Čugurović MVujošević Janičić MJovanović VWürthinger T(2024)GraalSPJournal of Systems and Software10.1016/j.jss.2024.112058213:COnline publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.jss.2024.112058
Huang WMarr SUgawa THong JLanperne MPark JCerny TShahriar H(2023)Optimizing the Order of Bytecode Handlers in Interpreters using a Genetic AlgorithmProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing10.1145/3555776.3577712(1384-1393)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3555776.3577712
(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Cooper KTorczon L(2023)Introduction to OptimizationEngineering a Compiler10.1016/B978-0-12-815412-0.00014-0(379-447)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00014-0
Ottoni GLiu BLee J(2021)HHVM jump-startProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370314(340-350)Online publication date: 27-Feb-2021
https://dl.acm.org/doi/10.1109/CGO51591.2021.9370314
Luan FZhao SBala KGkioulekas I(2020)Langevin monte carlo rendering with gradient-based adaptationACM Transactions on Graphics10.1145/3386569.339238239:4(140:1-140:16)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392382
Newell APupyrev S(2020)Improved Basic Block ReorderingIEEE Transactions on Computers10.1109/TC.2020.298288869:12(1784-1794)Online publication date: 1-Dec-2020
https://doi.org/10.1109/TC.2020.2982888
Lee YKim YYeom H(2020)Lightweight memory tracing for hot data identificationCluster Computing10.1007/s10586-020-03130-1Online publication date: 4-Jun-2020
https://doi.org/10.1007/s10586-020-03130-1
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Profile guided code positioning

Profile guided code positioning

Profile guided selection of ARM and thumb instructions