skip to main content
10.1145/1152154.1152197acmconferencesArticle/Chapter ViewAbstractPublication PagespactConference Proceedingsconference-collections
Article

Prematerialization: reducing register pressure for free

Published: 16 September 2006 Publication History

Abstract

Modern compiler transformations that eliminate redundant computations or reorder instructions, such as partial redundancy elimination and instruction scheduling, are very effective in improving application performance but tend to create longer and potentially more complex live ranges. Typically the task of dealing with the increased register pressure is left to the register allocator. To avoid introduction of spill code which can reduce or completely eliminate the benefit of earlier optimizations, researchers have developed techniques such as live range splitting and rematerializatio.This paper describes prematerialization (PM), a novel method for reducing register pressure for VLIW architectures with nop instructions. PM and rematerialization both select "never killed" live ranges and break them up by introducing one or more definitions close to the uses. However, while rematerialization is applied to live ranges selected for spilling during register allocation, PM relies on the availability of nop instructions and occurs prior to register allocation. PM simplifies register allocation by creating live ranges that are easier to color and less likely to spill. We have implemented prematerialization in HP-UX production compilers for the Intel® Itanium® architecture. Performance evaluation indicates that the proposed technique is effective in reducing register pressure inherent in highly optimized code.

References

[1]
Berson, D., Gupta, R., and Soffa, M. URSA: a unified resource allocator for registers and functional units in VLIW architectures. Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, 1993.]]
[2]
Briggs, P. Register Allocation via Graph Coloring. Ph.D. Thesis, Rice University, Houston, TX, April 1992.]]
[3]
Briggs, P., Cooper, K., and Torczon, L. Rematerialization. Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, 1992.]]
[4]
Briggs, P., Cooper, K., and Torczon, L. Improvements to graph coloring register allocation. ACM Transactions on Programming Languages and Systems, 16(3):428--455, May 1994.]]
[5]
Chaitin, G. Register allocation and spilling via graph coloring. ACM SIGPLAN Notices, 17(6):98--105, June 1982.]]
[6]
Govindarajan, R., Yang, H., Amaral, J., Zhang, C., and Gao, G. Minimum register instruction sequencing to reduce register spills in out-of-order issue superscalar architectures. IEEE Transactions on Computers, 52(1):4--20, January 2003.]]
[7]
Gupta, R. and Bodik, R. Register pressure sensitive redundancy elimination. Proceedings of International Conference on Compiler Construction (CC99), LNCS, vol. 1175, Springer-Verlag, 1999.]]
[8]
Haga, S., Zhang, Y., Webber, A., and Barua, R. Reducing code size in VLIW instruction scheduling. Journal of Embedded Computing, 1(4), 2005.]]
[9]
Hank, R. Region-based Compilation. Ph.D. Thesis, University of Illinois, Urbana, IL, May 1996.]]
[10]
Hoflehner, G., Kirkegaard, K., Skinner, R., Lavery, D., Lee, Y., and Li, W. Compiler optimizations for transaction processing workloads on Itanium Linux systems. Proceedings of 37th Annual International Symposium on Microarchitecture, 2004.]]
[11]
Intel, Intel® Itanium® Architecture Software Developer's Manual Vol. 1-3, January 2006.]]
[12]
Intel, Intel® Itanium® 2 Processor Reference Manual for Software Development and Optimization, 2002.]]
[13]
Intel, Intel® Itanium® Software Conventions & Runtime Architecture Guide, 2002.]]
[14]
Lowney, P., Freudenberger, S., Karzes, T., Lichtenstein, W., Nix, R., O'Donnell, J., and Ruttenberg, J. The Multiflow trace scheduling compiler. The Journal of Supercomputing 7 (1993): 51--142.]]
[15]
Settle, A., Connors, D., Hoflehner, G., and Lavery, D. Optimization for the Intel Itanium architecture register stack. Proceedings of International Symposium on Code Generation and Optimization, 2003.]]
[16]
Simpson, L. Value-driven redundancy elimination. Ph.D. Thesis, Rice University, Houston, TX, May 1996.]]
[17]
Standard Performance Evaluation Corporation, http://www.spec.org.]]
[18]
Touati, S. Register saturation in superscalar and VLIW codes. Proceedings of International Conference on Compiler Construction (CC01), LNCS, vol. 2027, Springer-Verlag, 2001.]]
[19]
Zhao, M., Childers, B., and Soffa, M. Model-based framework: an approach for profit-driven optimization. Proceedings of International Symposium on Code Generation and Optimization, 2005.]]

Cited By

View all
  • (2018)Research of Register Pressure Aware Loop Unrolling Optimizations for CompilerMATEC Web of Conferences10.1051/matecconf/201822803008228(03008)Online publication date: 14-Nov-2018
  • (2014)Register spilling via transformed interference equations for PAC DSP architectureConcurrency and Computation: Practice & Experience10.1002/cpe.305126:3(779-799)Online publication date: 10-Mar-2014
  • (2009)Techniques for Region-Based Register AllocationProceedings of the 7th annual IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO.2009.31(147-156)Online publication date: 22-Mar-2009
  • Show More Cited By

Index Terms

  1. Prematerialization: reducing register pressure for free

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    PACT '06: Proceedings of the 15th international conference on Parallel architectures and compilation techniques
    September 2006
    308 pages
    ISBN:159593264X
    DOI:10.1145/1152154
    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]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 16 September 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Itanium
    2. VLIW
    3. register allocation
    4. register pressure
    5. rematerialization

    Qualifiers

    • Article

    Conference

    PACT06
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 121 of 471 submissions, 26%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)11
    • Downloads (Last 6 weeks)3
    Reflects downloads up to 17 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2018)Research of Register Pressure Aware Loop Unrolling Optimizations for CompilerMATEC Web of Conferences10.1051/matecconf/201822803008228(03008)Online publication date: 14-Nov-2018
    • (2014)Register spilling via transformed interference equations for PAC DSP architectureConcurrency and Computation: Practice & Experience10.1002/cpe.305126:3(779-799)Online publication date: 10-Mar-2014
    • (2009)Techniques for Region-Based Register AllocationProceedings of the 7th annual IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO.2009.31(147-156)Online publication date: 22-Mar-2009
    • (2008)Load schedulingProceedings of the 2008 Asia and South Pacific Design Automation Conference10.5555/1356802.1356888(340-345)Online publication date: 21-Jan-2008

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media