research-article

Register allocation and promotion through combined instruction scheduling and loop unrolling

Authors:

Łukasz Domagała,

Duco van Amstel,

Fabrice Rastello,

P. SadayappanAuthors Info & Claims

CC '16: Proceedings of the 25th International Conference on Compiler Construction

Pages 143 - 151

https://doi.org/10.1145/2892208.2892219

Published: 17 March 2016 Publication History

Abstract

Register allocation is a much studied problem. A particularly important context for optimizing register allocation is within loops, since a significant fraction of the execution time of programs is often inside loop code. A variety of algorithms have been proposed in the past for register allocation, but the complexity of the problem has resulted in a decoupling of several important aspects, including loop unrolling, register promotion, and instruction reordering. In this paper, we develop an approach to register allocation and promotion in a unified optimization framework that simultaneously considers the impact of loop unrolling and instruction scheduling. This is done via a novel instruction tiling approach where instructions within a loop are represented along one dimension and innermost loop iterations along the other dimension. By exploiting the regularity along the loop dimension, and imposing essential dependence based constraints on intra-tile execution order, the problem of optimizing register pressure is cast in a constraint programming formalism. Experimental results are provided from thousands of innermost loops extracted from the SPEC benchmarks, demonstrating improvements over the current state-of-the-art.

References

[1]

A. W. Appel and L. George. Optimal spilling for CISC machines with few registers. In In Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, pages 243–253. ACM Press, 2000.

Digital Library

[2]

M. Bahi and C. Eisenbeis. Rematerialization-based register allocation through reverse computing. In C. Cascaval, P. Trancoso, and V. K. Prasanna, editors, Conf. Computing Frontiers, page 24. ACM, 2011. ISBN 978-1-4503-0698-0.

Digital Library

[3]

N. Beldiceanu and S. Demassey. Global constraint catalog. http: //www.emn.fr/z-info/sdemasse/gccat/, 2013.

[4]

S. Bollapragada, O. Ghattas, and J. N. Hooker. Optimal design of truss structures by logic-based branch and cut. Oper. Res., 49(1):42–51, Jan. 2001. ISSN 0030-364X.

Digital Library

[5]

F. Bouchez, A. Darte, and F. Rastello. On the complexity of spill everywhere under SSA form. In LCTES’07, pages 103–112, 2007.

Digital Library

[6]

P. Briggs, K. D. Cooper, and L. Torczon. Rematerialization. SIGPLAN Not., 27(7):311–321, July 1992. ISSN 0362-1340.

Digital Library

[7]

D. Callahan, S. Carr, and K. Kennedy. Improving register allocation for subscripted variables. In Proceedings of the ACM SIGPLAN 1990 Conference on Programming Language Design and Implementation, PLDI ’90, pages 53–65. ACM, 1990. ISBN 0-89791-364-7. URL http://doi.acm.org/10.1145/93542.93553.

Digital Library

[8]

G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins, and P. W. Markstein. Register allocation via graph coloring. Journal of Computer Languages, 6:45–57, 1981.

Digital Library

[9]

D. R. Chase, M. Wegman, and F. K. Zadeck. Analysis of pointers and structures. In Proceedings of the ACM SIGPLAN 1990 Conference on Programming Language Design and Implementation, PLDI ’90, pages 296–310, New York, NY, USA, 1990. ACM. ISBN 0-89791-364-7. URL http://doi.acm.org/10.1145/93542.93585.

Digital Library

[10]

F. Chow and J. Hennessy. Register allocation by priority-based coloring. SIGPLAN Not., 39(4):91–103, Apr. 2004. ISSN 0362-1340.

Digital Library

[11]

Q. Colombet, F. Brandner, and A. Darte. Studying optimal spilling in the light of SSA. In Proceedings of the 14th International Conference on Compilers, Architectures and Synthesis for Embedded Systems, CASES ’11, pages 25–34, New York, NY, USA, 2011. ACM. ISBN 978-1-4503-0713-0.

Digital Library

[12]

L. Domagała. Application of CLP to instruction modulo scheduling for VLIW processors. PhD thesis, Silesian University of Technology, Gliwice, Poland, 2012.

[13]

ISBN:9788362652426, available online at http://books.google.com/books?id=e6apNOED26kC.

[14]

E. Duesterwald, R. Gupta, and M. L. Soffa. Register pipelining: An integrated approach to register allocation for scalar and subscripted variables. In Proceedings of the 4th International Conference on Compiler Construction, CC ’92, pages 192–206, New York, NY, USA, 1992. Springer-Verlag. ISBN 3-540-55984-1. URL http://dl.acm. org/citation.cfm?id=647471.727265.

Digital Library

[15]

M. Farach-Colton and V. Liberatore. On local register allocation. J. of Algorithms, 37(1):37–65, 2000.

Digital Library

[16]

P. Feautrier. Compiler optimizations for scalable parallel systems. chapter Array Dataflow Analysis, pages 173–219. Springer-Verlag New York, Inc., New York, NY, USA, 2001. ISBN 3-540-41945-4. URL http://dl.acm.org/citation.cfm?id=380466.380472.

Digital Library

[17]

G12. MiniZinc challenge. http://http://www.minizinc.org/, 2013.

[18]

L. George and A. W. Appel. Iterated register coalescing. ACM Trans. Program. Lang. Syst., 18(3):300–324, 1996.

Digital Library

[19]

S. Hack, D. Grund, and G. Goos. Register Allocation for Programs in SSA Form. In A. Zeller and A. Mycroft, editors, Compiler Construction, volume 3923, pages 247–262. Springer, March 2006.

Digital Library

[20]

V. Jain and I. E. Grossmann. Algorithms for hybrid MILP/CP models for a class of optimization problems. INFORMS J. on Computing, 13 (4):258–276, Sept. 2001. ISSN 1526-5528.

Digital Library

[21]

K. Kuchcinski. Constraints-driven scheduling and resource assignment. ACM Trans. Des. Autom. Electron. Syst., 8(3):355–383, July 2003. ISSN 1084-4309.

Digital Library

[22]

R. Lo, F. Chow, R. Kennedy, S.-M. Liu, and P. Tu. Register promotion by sparse partial redundancy elimination of loads and stores. SIGPLAN Not., 33(5):26–37, May 1998. ISSN 0362-1340.

Digital Library

[23]

Y. Ma. Register Pressure Guided Loop Optimization. PhD thesis, Houghton, MI, USA, 2007. AAI3293043.

Digital Library

[24]

S. A. McKee. Reflections on the memory wall. In Proceedings of the 1st Conference on Computing Frontiers, CF ’04, pages 162–, New York, NY, USA, 2004. ACM. ISBN 1-58113-741-9. URL http://doi.acm.org/10.1145/977091.977115.

Digital Library

[25]

R. Motwani, K. V. Palem, V. Sarkar, and S. Reyen. Combining register allocation and instruction scheduling. Courant Institute, New York University, 1995.

[26]

G. Ottosson and E. S. Thorsteinsson. Linear relaxations and reducedcost based propagation of continuous variable subscripts. In In CP-AIOR’00 Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems, 2000.

[27]

J.-C. Régin. A filtering algorithm for constraints of difference in CSPs. In Proceedings of the Twelfth National Conference on Artificial Intelligence (Vol. 1), AAAI ’94, pages 362–367, Menlo Park, CA, USA, 1994. American Association for Artificial Intelligence. ISBN 0-262-61102-3.

Digital Library

[28]

J.-C. Régin. Generalized arc consistency for global cardinality constraint. In Proceedings of the thirteenth national conference on Artificial intelligence - Volume 1, AAAI’96, pages 209–215. AAAI Press, 1996. ISBN 0-262-51091-X. URL http://portal.acm.org/ citation.cfm?id=1892875.1892906.

Digital Library

[29]

L. Renganarayanan, U. Ramakrishna, and S. V. Rajopadhye. Combined ilp and register tiling: Analytical model and optimization framework. In LCPC, pages 244–258, 2005.

Digital Library

[30]

F. Rossi, P. v. Beek, and T. Walsh. Handbook of Constraint Programming (Foundations of Artificial Intelligence). Elsevier Science Inc., New York, NY, USA, 2006. ISBN 0444527265.

Digital Library

[31]

P. Shaw. Using constraint programming and local search methods to solve vehicle routing problems. In Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming, CP ’98, pages 417–431, London, UK, UK, 1998. Springer-Verlag. ISBN 3-540-65224-8.

Digital Library

[32]

P. Stanley-Marbell, V. Caparros Cabezas, and R. Luijten. Pinned to the walls: Impact of packaging and application properties on the memory and power walls. In Proceedings of the 17th IEEE/ACM International Symposium on Low-power Electronics and Design, ISLPED ’11, pages 51–56, Piscataway, NJ, USA, 2011. IEEE Press. ISBN 978-1-61284-660-6. URL http://dl.acm.org/citation.cfm?id= 2016802.2016815.

Digital Library

[33]

R. Surendran, R. Barik, J. Zhao, and V. Sarkar. Inter-iteration scalar replacement using array SSA form. In Compiler Construction - 23rd International Conference, CC 2014, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2014, Grenoble, France, April 5-13, 2014. Proceedings, pages 40–60, 2014.

[34]

S. A. A. Touati and C. Eisenbeis. Early control of register pressure for software pipelined loops. In Compiler Construction, 12th International Conference, CC 2003, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2003, Warsaw, Poland, April 7-11, 2003, Proceedings, pages 17–32, 2003.

Digital Library

[35]

P. van Beek and X. Chen. CPlan: A constraint programming approach to planning. In Proceedings of the Sixteenth National Conference on Artificial Intelligence and the Eleventh Innovative Applications of Artificial Intelligence Conference Innovative Applications of Artificial Intelligence, AAAI ’99/IAAI ’99, pages 585–590, Menlo Park, CA, USA, 1999. American Association for Artificial Intelligence. ISBN 0-262-51106-1.

Digital Library

[36]

W. A. Wulf and S. A. McKee. Hitting the memory wall: Implications of the obvious. SIGARCH Comput. Archit. News, 23(1):20–24, Mar. 1995. ISSN 0163-5964. URL http://doi.acm.org/10.1145/ 216585.216588.

Digital Library

Cited By

Ye ZJiao J(2024)Loop Unrolling Based on SLP and Register Pressure Awareness2024 20th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD)10.1109/ICNC-FSKD64080.2024.10702289(1-6)Online publication date: 27-Jul-2024
https://doi.org/10.1109/ICNC-FSKD64080.2024.10702289
Shobaki GMuyan-Özçelik PHutton JLinck BMalyshenko VKerbow ARamirez-Ortega RGordon VGrosser TDubach CSteuwer MXue JOttoni GQuintão Pereira F(2024)Instruction Scheduling for the GPU on the GPUProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444869(435-447)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1109/CGO57630.2024.10444869
Shobaki GGordon VMcHugh PDubois TKerbow A(2022)Register-Pressure-Aware Instruction Scheduling Using Ant Colony OptimizationACM Transactions on Architecture and Code Optimization10.1145/350555819:2(1-23)Online publication date: 31-Jan-2022
https://dl.acm.org/doi/10.1145/3505558
Show More Cited By

Index Terms

Register allocation and promotion through combined instruction scheduling and loop unrolling
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Modulo Scheduling with Reduced Register Pressure

Software pipelining is a scheduling technique that is used by some product compilers in order to expose more instruction level parallelism out of innermost loops. Modulo scheduling refers to a class of algorithms for software pipelining. Most previous ...
Register Constrained Modulo Scheduling

Abstract--Software pipelining is an instruction scheduling technique that exploits the instruction level parallelism (ILP) available in loops by overlapping operations from various successive loop iterations. The main drawback of aggressive software ...
Fast, frequency-based, integrated register allocation and instruction scheduling

Instruction scheduling and register allocation are two of the most important optimization phases in modern compilers as they have a significant impact on the quality of the generated code. Unfortunately, the objectives of these two optimizations are in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CC '16: Proceedings of the 25th International Conference on Compiler Construction

March 2016

270 pages

ISBN:9781450342414

DOI:10.1145/2892208

General Chair:
Ayal Zaks
Intel, Israel / Technion, Israel
,
Program Chair:
Manuel Hermenegildo
IMDEA SW Institute, Spain / T.U. Madrid-UPM, Spain

Copyright © 2016 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 the author(s) 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

In-Cooperation

IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 March 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CGO '16

Sponsor:

CGO '16: 14th Annual IEEE/ACM International Symposium on Code Generation and Optimization

March 17 - 18, 2016

Barcelona, Spain

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
381
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)3

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ye ZJiao J(2024)Loop Unrolling Based on SLP and Register Pressure Awareness2024 20th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD)10.1109/ICNC-FSKD64080.2024.10702289(1-6)Online publication date: 27-Jul-2024
https://doi.org/10.1109/ICNC-FSKD64080.2024.10702289
Shobaki GMuyan-Özçelik PHutton JLinck BMalyshenko VKerbow ARamirez-Ortega RGordon VGrosser TDubach CSteuwer MXue JOttoni GQuintão Pereira F(2024)Instruction Scheduling for the GPU on the GPUProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444869(435-447)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1109/CGO57630.2024.10444869
Shobaki GGordon VMcHugh PDubois TKerbow A(2022)Register-Pressure-Aware Instruction Scheduling Using Ant Colony OptimizationACM Transactions on Architecture and Code Optimization10.1145/350555819:2(1-23)Online publication date: 31-Jan-2022
https://dl.acm.org/doi/10.1145/3505558
Shobaki GBassett JHeffernan MKerbow AEgger BSmith A(2022)Graph transformations for register-pressure-aware instruction schedulingProceedings of the 31st ACM SIGPLAN International Conference on Compiler Construction10.1145/3497776.3517771(41-53)Online publication date: 19-Mar-2022
https://dl.acm.org/doi/10.1145/3497776.3517771
Kim MPark JMoon S(2020)Irregular Register Allocation for Translation of Test-pattern ProgramsACM Transactions on Architecture and Code Optimization10.1145/342737818:1(1-23)Online publication date: 30-Dec-2020
https://dl.acm.org/doi/10.1145/3427378
Shobaki GKerbow APulido CDobson W(2019)Exploring an Alternative Cost Function for Combinatorial Register-Pressure-Aware Instruction SchedulingACM Transactions on Architecture and Code Optimization10.1145/330148916:1(1-30)Online publication date: 27-Feb-2019
https://dl.acm.org/doi/10.1145/3301489
Lozano RSchulte C(2019)Survey on Combinatorial Register Allocation and Instruction SchedulingACM Computing Surveys10.1145/320092052:3(1-50)Online publication date: 18-Jun-2019
https://dl.acm.org/doi/10.1145/3200920
Kuchcinski K(2019)Constraint programming in embedded systems designMicroprocessors & Microsystems10.1016/j.micpro.2019.05.01269:C(24-34)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1016/j.micpro.2019.05.012
Rawat PSukumaran-Rajam ARountev ARastello FPouchet LSadayappan P(2018)Associative instruction reordering to alleviate register pressureProceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis10.5555/3291656.3291718(1-13)Online publication date: 11-Nov-2018
https://dl.acm.org/doi/10.5555/3291656.3291718
Liu HGuo Z(2018)A loop unrolling method based on machine learningVibroengineering Procedia10.21595/vp.2018.1992818(215-221)Online publication date: 22-May-2018
https://doi.org/10.21595/vp.2018.19928
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