skip to main content
10.1145/1629395.1629408acmconferencesArticle/Chapter ViewAbstractPublication PagesesweekConference Proceedingsconference-collections
research-article

Progressive spill code placement

Published: 11 October 2009 Publication History

Abstract

Register allocation has gained renewed attention in the recent past. Several authors propose a separation of the problem into decoupled sub-tasks including spilling, allocation, assignment, and coalescing. This approach is largely motivated by recent advances in SSA-based register allocation that suggest that a decomposition does not significantly degrade the overall allocation quality.
The algorithmic challenges of intra-procedural spilling have been neglected so far and very crude heuristics were employed. In this work, (1) we introduce the constrained min-cut (CMC) problem for solving the spilling problem, (2) we provide an integer linear program formulation for computing an optimal solution of CMC, and (3) we devise a progressive Lagrangian solver that is viable for production compilers. Our experiments with Spec2k and MiBench show that optimal solutions are feasible, even for very large programs, and that heuristics leave significant potential behind for small register files.

References

[1]
Andrew W Appel and Lal George. Optimal spilling for cisc machines with few registers. In PLDI, pages 243 -- 253. ACM Press, 2001.
[2]
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
[3]
Preston Briggs, Keith D. Cooper, and Linda Torczon. Improvements to graph coloring register allocation. ACM Trans. Program. Lang. Syst., 16(3):428 -- 455, 1994.
[4]
Philip Brisk, Foad Dabiri, Jamie Macbeth, and Majid Sarrafzadeh. Polynomial-time graph coloring register allocation. In International Workshop on Logic and Synthesis. ACM Press, 2005.
[5]
Florent Bouchez, Alain Darte, and Fabrice Rastello. On the complexity of spill everywhere under SSA form. In Santosh Pande and Zhiyuan Li, editors, LCTES, pages 103--112. ACM, 2007.
[6]
Laszlo A. Belady. A study of replacement algorithms for virtual storage computers. IBM Syst. J., 5:78--101, 1966.
[7]
1}CFRW91Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing ssa form and the control dependence graph. TOPLAS, 13(4):451--490, October 1991.
[8]
Fred C. Chow and John L. Hennessy. The priority-based coloring approach to register allocation. ACM Trans. Program. Lang. Syst., 12(4):501--536, 1990.
[9]
G J Chaitin. Register allocation and spilling via graph coloring. Symposium on Compiler Construction, 17(6):98 -- 105, 1982.
[10]
Farach-Colton and Liberatore. On local register allocation. ALGORITHMS: Journal of Algorithms, 37, 2000.
[11]
Lal George and Andrew W Appel. Iterated register coalescing. ACM Trans. Program. Lang. Syst., 18(3):300 -- 324, 1996.
[12]
Jia Guo, Maria Jesus Garzaran, and David A. Padua. The power of belady's algorithm in register allocation for long basic blocks. In LCPC, volume 2958 of LNCS, pages 374--390. Springer, 2004.
[13]
Daniel Grund and Sebastian Hack. A fast cutting-plane algorithm for optimal coalescing. In Compiler Construction, volume 4420 of LNCS, pages 111--125. Springer, 2007.
[14]
Goodwin and Wilken. Optimal and near-optimal global register allocation using 0-1 integer programming. Software-Practice and Experience, 26, 1996.
[15]
Sebastian Hack. Register Allocation for Programs in SSA Form. PhD thesis, Universitat Karlsruhe, October 2007.
[16]
W. Hsu, C. Fischer, and J. Goodman. On the minimization of loads/stores in local register allocation. IEEE Trans. on Softw. Eng., 15(10):1252, October 1989.
[17]
Sebastian Hack and Gerhard Goos. Optimal register allocation for ssa-form programs in polynomial time. Information Processing Letters, 98(4):150--155, May 2006.
[18]
Sebastian Hack, Daniel Grund, and Gerhard Goos. Register Allocation for Programs in SSA-Form. In Compiler Construction, volume 3923, pages 247--262. Springer, March 2006.
[19]
David Ryan Koes and Seth Copen Goldstein. A global progressive register allocator. ACM SIGPLAN Notices, 41(6):204--215, June 2006.
[20]
Chris Lattner and Vikram S. Adve. LLVM: A compilation framework for lifelong program analysis&transformation. In CGO, pages 75--88. IEEE Computer Society, 2004.
[21]
Jinpyo Park and Soo-Mook Moon. Optimistic register coalescing. In PACT, pages 196--204. IEEE Computer Society, October 1998.
[22]
Fernando Magno Quintao Pereira and Jens Palsberg. Register allocation via coloring of chordal graphs. In APLAS, volume 3780 of LNCS, pages 315--329. Springer, 2005.
[23]
Massimiliano Poletto and Vivek Sarkar. Linear scan register allocation. ACM Trans. Program. Lang. Syst., 21(5):895 -- 913, 1999.
[24]
H. S. Stone. Multiprocessor scheduling with the aid of network flow algorithms. IEEE TSE, SE-3(1):85--93, January 1977.
[25]
Mechthild Stoer and Frank Wagner. A simple min-cut algorithm. J. ACM, 44(4):585--591, 1997.

Cited By

View all
  • (2019)Combinatorial Register Allocation and Instruction SchedulingACM Transactions on Programming Languages and Systems10.1145/333237341:3(1-53)Online publication date: 2-Jul-2019
  • (2019)Survey on Combinatorial Register Allocation and Instruction SchedulingACM Computing Surveys10.1145/320092052:3(1-50)Online publication date: 18-Jun-2019
  • (2016)Register allocation and spilling using the expected distance heuristicSoftware—Practice & Experience10.1002/spe.239346:11(1499-1523)Online publication date: 1-Nov-2016
  • Show More Cited By

Index Terms

  1. Progressive spill code placement

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    CASES '09: Proceedings of the 2009 international conference on Compilers, architecture, and synthesis for embedded systems
    October 2009
    298 pages
    ISBN:9781605586267
    DOI:10.1145/1629395
    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: 11 October 2009

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. SSA form
    2. constrained min-cut
    3. register allocation
    4. spilling

    Qualifiers

    • Research-article

    Conference

    ESWeek '09
    ESWeek '09: Fifth Embedded Systems Week
    October 11 - 16, 2009
    Grenoble, France

    Acceptance Rates

    Overall Acceptance Rate 52 of 230 submissions, 23%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 22 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2019)Combinatorial Register Allocation and Instruction SchedulingACM Transactions on Programming Languages and Systems10.1145/333237341:3(1-53)Online publication date: 2-Jul-2019
    • (2019)Survey on Combinatorial Register Allocation and Instruction SchedulingACM Computing Surveys10.1145/320092052:3(1-50)Online publication date: 18-Jun-2019
    • (2016)Register allocation and spilling using the expected distance heuristicSoftware—Practice & Experience10.1002/spe.239346:11(1499-1523)Online publication date: 1-Nov-2016
    • (2015)Studying Optimal Spilling in the Light of SSAACM Transactions on Architecture and Code Optimization10.1145/268539211:4(1-26)Online publication date: 9-Jan-2015
    • (2011)Studying optimal spilling in the light of SSAProceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems10.1145/2038698.2038706(25-34)Online publication date: 9-Oct-2011

    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