Article

Optimal spilling for CISC machines with few registers

Authors:

Andrew W. Appel,

Lal GeorgeAuthors Info & Claims

PLDI '01: Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation

Pages 243 - 253

https://doi.org/10.1145/378795.378854

Published: 01 May 2001 Publication History

Abstract

Many graph-coloring register-allocation algorithms don't work well for machines with few registers. Heuristics for live-range splitting are complex or suboptimal; heuristics for register assignment rarely factor the presence of fancy addressing modes; these problems are more severe the fewer registers there are to work with. We show how to optimally split live ranges and optimally use addressing modes, where the optimality condition measures dynamically weighted loads and stores but not register-register moves. Our algorithm uses integer linear programming but is much more efficient than previous ILP-based approaches to register allocation. We then show a variant of Park and Moon's optimistic coalescing algorithm that does a very good (though not provably optimal) job of removing the register-register moves. The result is Pentium code that is 9.5% faster than code generated by SSA-based splitting with iterated register coalescing.

References

[1]

A. W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, Cambridge, England, 1998.

Digital Library

[2]

A. W. Appel and D. B. MacQueen. Standard ML of New Jersey. In M. Wirsing, editor, 3rd International Symp. on Prog. Lang. Implementation and Logic Programming, pages 1-13, New York, Aug. 1991. Springer-Verlag.

[3]

P. Briggs. Register Allocation via Graph Coloring. PhD thesis, Rice University, April 1992.

Digital Library

[4]

P. Briggs, K. D. Cooper, and L. Torczon. Improvements to graph coloring register allocation. ACM Trans. on Programming Languages and Systems, 16(3):428-455, May 1994.

Digital Library

[5]

G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins, and P. W. Markstein. Register allocation via coloring. Computer Languages, 6:47-57, January 1981.

Digital Library

[6]

F. C. Chow and J. L. Hennessy. The priority-based coloring approach to register allocation. ACM Trans. on Programming Languages and Systems, 12(4):501-536, October 1990.

Digital Library

[7]

CPLEX mixed integer solver. www.cplex.com, 2000.

[8]

R. Fourer, D. M. Gay, and B. W. Kernighan. AMPL: A Modeling Language for Mathematical Programming. Scientific Press, South San Francisco, CA, 1993. www.ampl.com.

Digital Library

[9]

L. George and A. W. Appel. Iterated register coalescing. In 23rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 208-218, New York, Jan 1996. ACM Press.

Digital Library

[10]

L. George, F. Guillame, and J. Reppy. A portable and optimizing back end for the SML/NJ compiler, volume 786 of LNCS, pages 83-97. Springer-Verlag, 1994.

Digital Library

[11]

D. W. Goodwin. Optimal and Near-Optimal Global Register Allocation. PhD thesis, University of California at Davis, 1996.

[12]

D. W. Goodwin and K. D. Wilken. Optimal and near-optimal global register allocation using 0-1 integer programming. Software-Practice and Experience, 26(8):929-965, 1996.

Digital Library

[13]

M. S. Hung. Optimization with IBM-OSL. Scientific Press, South San Francisco, CA, 1993.

[14]

A. B. Kempe. On the geographical problem of the four colors. American Journal of Mathematics, 2:193-200, 1879.

[15]

T. Kong and K. D. Wilken. Precise register allocation for irregular architectures. In 31st International Microarchitecture Conference. ACM, December 1998.

Digital Library

[16]

G. Lueh, T. Gross, and A. Adl-Tabatabai. Global register allocation based on graph fusion. In Languages and Compilers for Parallel Computing, pages 246-265. Springer Verlag, LNCS 1239, August 1997.

Digital Library

[17]

J. Park and S.-M. Moon. Optimistic register coalescing. In Proceedings of the 1998 International Conference on Parallel Architecture and Compilation Techniques, pages 196-204, 1998.

Digital Library

[18]

Y. Wu and J. R. Larus. Static branch frequency and program profile analysis. In 27th IEEE/ACM International Symposium on Microarchitecture (MICRO-27), Nov. 1994.

Digital Library

Cited By

VenkataKeerthy SJain SKundu AAggarwal RCohen AUpadrasta RVerbrugge CLhoták OShen X(2023)RL4ReAl: Reinforcement Learning for Register AllocationProceedings of the 32nd ACM SIGPLAN International Conference on Compiler Construction10.1145/3578360.3580273(133-144)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3578360.3580273
Farvardin KReppy J(2020)A New Backend for Standard ML of New JerseyProceedings of the 32nd Symposium on Implementation and Application of Functional Languages10.1145/3462172.3462191(55-66)Online publication date: 2-Sep-2020
https://dl.acm.org/doi/10.1145/3462172.3462191
MacQueen DHarper RReppy J(2020)The history of Standard MLProceedings of the ACM on Programming Languages10.1145/33863364:HOPL(1-100)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3386336
Show More Cited By

Index Terms

Recommendations

Optimal spilling for CISC machines with few registers

Many graph-coloring register-allocation algorithms don't work well for machines with few registers. Heuristics for live-range splitting are complex or suboptimal; heuristics for register assignment rarely factor the presence of fancy addressing modes; ...
Studying optimal spilling in the light of SSA
CASES '11: Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems

Recent developments in register allocation, mostly linked to static single assignment (SSA) form, have shown that it is possible to decouple the problem in two successive phases: a first spilling phase places load and store instructions so that the ...
Exploiting virtual registers to reduce pressure on real registers

It is well known that a large fraction of variables are short-lived. This paper proposes a novel approach to exploiting this fact to reduce the register pressure for pipelined processors with data-forwarding network. The idea is that the compiler can ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '01: Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation

June 2001

331 pages

ISBN:1581134142

DOI:10.1145/378795

Chairmen:
Michael Burke
IBM T.J. Watson Research Center
,
Mary Lou Soffa
Univ. of Pittsburgh

ACM SIGPLAN Notices Volume 36, Issue 5
May 2001
330 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/381694
Editors:
Cindy Norris,
James B. Bergin
Issue’s Table of Contents

Copyright © 2001 ACM.

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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI01

Sponsor:

SIGPLAN

PLDI01: ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation

Utah, Snowbird, USA

Acceptance Rates

PLDI '01 Paper Acceptance Rate 30 of 144 submissions, 21%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

128
Total Citations
View Citations
1,270
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)4

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

VenkataKeerthy SJain SKundu AAggarwal RCohen AUpadrasta RVerbrugge CLhoták OShen X(2023)RL4ReAl: Reinforcement Learning for Register AllocationProceedings of the 32nd ACM SIGPLAN International Conference on Compiler Construction10.1145/3578360.3580273(133-144)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3578360.3580273
Farvardin KReppy J(2020)A New Backend for Standard ML of New JerseyProceedings of the 32nd Symposium on Implementation and Application of Functional Languages10.1145/3462172.3462191(55-66)Online publication date: 2-Sep-2020
https://dl.acm.org/doi/10.1145/3462172.3462191
MacQueen DHarper RReppy J(2020)The history of Standard MLProceedings of the ACM on Programming Languages10.1145/33863364:HOPL(1-100)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3386336
Lozano RCarlsson MBlindell GSchulte C(2019)Combinatorial Register Allocation and Instruction SchedulingACM Transactions on Programming Languages and Systems10.1145/333237341:3(1-53)Online publication date: 2-Jul-2019
https://dl.acm.org/doi/10.1145/3332373
Mendis CAmarasinghe S(2018)goSLP: globally optimized superword level parallelism frameworkProceedings of the ACM on Programming Languages10.1145/32764802:OOPSLA(1-28)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276480
ÖZCAN G(2016)P53 KONSENSÜS SEKANSININ YAKALANMASI: SINIF ÖZELLİKLİ YENİ BİR SEKANS EŞLEŞTİRME ALGORİTMASIUludağ University Journal of The Faculty of Engineering10.17482/uumfd.27397021:2(269-269)Online publication date: 7-Dec-2016
https://doi.org/10.17482/uumfd.273970
Hayes ALi LChavarría-Miranda DSong SZhang E(2016)OrionProceedings of the 17th International Middleware Conference10.1145/2988336.2988355(1-13)Online publication date: 28-Nov-2016
https://dl.acm.org/doi/10.1145/2988336.2988355
Domagała Łvan Amstel DRastello FSadayappan PZaks AHermenegildo M(2016)Register allocation and promotion through combined instruction scheduling and loop unrollingProceedings of the 25th International Conference on Compiler Construction10.1145/2892208.2892219(143-151)Online publication date: 17-Mar-2016
https://dl.acm.org/doi/10.1145/2892208.2892219
Burroughs N(2016)Register allocation and spilling using the expected distance heuristicSoftware—Practice & Experience10.1002/spe.239346:11(1499-1523)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1002/spe.2393
Krause PCorporaal HStuijk S(2015)Bytewise Register AllocationProceedings of the 18th International Workshop on Software and Compilers for Embedded Systems10.1145/2764967.2764971(22-27)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1145/2764967.2764971
Show More Cited By

View Options

Get Access

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents