More Web Proxy on the site http://driver.im/

Article

Free access

Register allocation over the program dependence graph

Authors:

Lori L. PollockAuthors Info & Claims

PLDI '94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation

Pages 266 - 277

https://doi.org/10.1145/178243.178427

Published: 01 June 1994 Publication History

Abstract

This paper describes RAP, a Register Allocator that allocates registers over the Program Dependence Graph (PDG) representation of a program in a hierarchical manner. The PDG program representation has been used successfully for scalar optimizations, the detection and improvement of parallelism for vector machines, multiple processor machines, and machines that exhibit instruction level parallelism, as well as debugging, the integration of different versions of a program, and translation of imperative programs for data flow machines. By basing register allocation on the PDG, the register allocation phase may be more easily integrated and intertwined with other optimization analyses and transformations. In addition, the advantages of a hierarchical approach to global register allocation can be attained without constructing an additional structure used solely for register allocation. Our experimental results have shown that on average, code allocated registers via RAP executed 2.7% faster than code allocated registers via a standard global register allocator.

References

[1]

H. Agrawal and j. R. Horgan. Dynamic program slicing. In Proceedings of the $IGPLAN '90 Conference on Programming Language Design and Implementation, pages 246-256, White Plains, NY, June 1990.

Digital Library

[2]

V. H. Allan, J. Janardhan, R. M. Lee, and M. Srinivas. Enhanced region scheduling on a program dependence graph. In Proceedings of the twenty-fifth International Symposium on Microarchitecture, pages 72-80, Portland, OR, 1992.

Digital Library

[3]

F. E. Allen, M. Burke, P. Charles, R. Cytron, and J. Ferrante. An overview of the PTRAN analysis system for multiprocessing. Journal of Parallel and Distributed Computing, 5:617-640, 1988.

Digital Library

[4]

R. A. Ballance, A. B. Maccabe, and K. J. Ottenstein. The program dependence web: a representation supporting control-, data-, and demand~ driven interpretation of imperative languages. In Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementation, pages 257-271, White Plains, NY, june 1990.

Digital Library

[5]

W. Baxter and H. R. Bauer, III. The program dependence graph and vectorization. In Proceedings of the Sizteenth Annual A CM $IGACT/SIGPLAN Symposium on Principles of Programming Languages, Austin, TX, 1989.

Digital Library

[6]

D. Bernstein and M. Rodeh. Global instruction scheduling for superscalar machines. In Proceedings of the A CM SIGPLAN '91 Conference on Programming Language Design and Implementation, Toronto, June 1991.

Digital Library

[7]

David Bernstein and Michael Rodeh. Global instruction scheduling for superscalar machines. In Proceedings of the $IGPLAN '91 Conference on Programming Language Design and Implementatzon, Toronto, CANADA, June 1991.

Digital Library

[8]

Preston Briggs. Register allocation wa graph coloring. PhD thesis, Rice University, April 1992.

Digital Library

[9]

Preston Briggs, Keith D. Cooper, Ken Kennedy, and Linda Torczon. Coloring heuristics for register allocation. In Proceedings of the A CM SIGPLAN '89 Conference on Programming Language Design and Implementation, July 1989.

Digital Library

[10]

Preston Briggs, Keith D. Cooper, and Linda Torczon. R'~ programming environment newsletter ~44. Department of Computer Science, Rice University, September 1987.

[11]

Preston Briggs, Keith D. Cooper, and Linda Torczon. Rematerialization. in Proceedings of the SIG- PLAN '92 Conference on Programming Language Design and Implementation, June 1992.

Digital Library

[12]

David Callahan and Brian Koblenz. Register allocation via hierarchical graph coloring. In Proceedings of the SIGPLAN '91 Conference on Programming Language Design and Implementation, pages 192-203, Toronto, CANADA, June 1991.

Digital Library

[13]

G. J. Chaitin. Register allocation and spilling via graph coloring. In SIGPLAN Symposium on Compiler Construction, Boston, June 1982.

Digital Library

[14]

Gregory Chaitin, Marc Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. M arkstein. Register allocation via coloring. Computer Languages, 6:47-57, January 1981.

Digital Library

[15]

Frederick Chow and John Hennessy. Register allocation by priority-based coloring, in Proceedings of the SIGPLAN '8,~ Symposium on Compiler Construction, June 1984.

Digital Library

[16]

Jeanne Ferrante, Karl J. Ottenstein, and Joe D. Warren. The program dependence graph and its use in optimization. A CM Transactions on Programming Languages and Systems, 9(3):319-349, 1987.

Digital Library

[17]

Claude-Nicolas Fiechter. PDG C Compiler. University of Pittsburgh, 1992.

[18]

J. H. Griffin and K. J. Ottenstein. PROBE: a dependence-based program browser. Technical Report LA-UR-89-1823, Los Alamos National Laboratory, Los Alamos, NM, November 1989.

[19]

Rajiv Gupta and Mary Lou Sofia. Region scheduling: An approach for detecting and redistributing parallelism. IEEE Transactions on Software Engineering, 16(4):421-431, 1990.

Digital Library

[20]

Rajiv Gupta, Mary Lou Sofia, and Tim Steele. Register allocation via clique separators. In Proceedings of the SIGPLAN '89 Conference on Programming Language Design and Implementation, Portland, Oregon, June 1989.

Digital Library

[21]

S. Horwitz. Identifying the semantic and textual differences between two versions of a program. In Proceedings of the $IGPLAN '90 Conference on Programming Language Design and Implementation, pages 234-245, White Plains, NY, June 1990.

Digital Library

[22]

E. I-Iorwi~z, J. Prlns, and T. Reps. In~egrating noninterfering versions of programs. In Proceedings of the Fifteenth Annual A CM SiGA CT/SIGPLAN Symposium on Principles of Programming Languages, pages 133-145, San Diego, CA, 1988.

Digital Library

[23]

D. J. Kuck, R. H. Kuhn, B. Leasure, D. A. Padua, and M. Wolfe. Dependence graphs and compiler optimizations. In Proceedings of the Eighth Annual A CM Symposium on Principles of Programming Languages, pages 207-218, 1981.

Digital Library

[24]

Cindy Norris and Lori L. Pollock. A schedulersensitive global register allocator. In $upercomputing '93 Proceedings, Portland, OR, November 1993.

Digital Library

[25]

K. J. Ottenstein. An intermediate program form based on a cyclic data-dependence graph. Technical Report 81-1, Department of Computer Science, Michigan Tech. University, 1981.

[26]

K. J. Ottenstein and L. M. Ottenstein. The program dependence graph in a software development environment. In Proceedings of A CM SIG- PLAN/SIGSOFT Symposium on Practical Software Development Environments, pages 177-184, Pittsburgh, PA, April 1984.

Digital Library

[27]

Todd A. Proebsting and Charles N. Fischer. Probabilistic register allocation. In Proceedings of the SIGPLAN '92 Conference on Programming Language Design and implementation, pages 300-310, San Francisco, CA, June 1992.

Digital Library

[28]

J. Warren. A hierarchical basis for reordering transformations. In Proceedings of the Eleventh Annual A CM Symposium on Principles of Programming Languages, pages 272-282, 1984.

Digital Library

[29]

M. Weiser. Program slicing. IEEE Transactions on Software Engineering, SE-10(4):352-357, 1984.

Digital Library

[30]

M. J. Wolfe. Research Monographs in Parallel and Distributed Computing. The MIT Press, 1989.

Cited By

Kiran DGurunarayanan SMisra JBhatia M(2017)Register allocation for fine grain threads on multicore processorJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2015.04.00129:1(85-92)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1016/j.jksuci.2015.04.001
Brisk PSarrafzadeh M(2007)Interference graphs for procedures in static single information form are interval graphsProceedingsof the 10th international workshop on Software & compilers for embedded systems10.1145/1269843.1269858(101-110)Online publication date: 20-Apr-2007
https://dl.acm.org/doi/10.1145/1269843.1269858
Jain MBalakrishnan MKumar A(2006)An efficient technique for exploring register file size in ASIP designIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2004.83771723:12(1693-1699)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TCAD.2004.837717
Show More Cited By

Index Terms

Register allocation over the program dependence graph

Recommendations

Register allocation over the program dependence graph

This paper describes RAP, a Register Allocator that allocates registers over the Program Dependence Graph (PDG) representation of a program in a hierarchical manner. The PDG program representation has been used successfully for scalar optimizations, the ...
Differential register allocation
PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation

Micro-architecture designers are very cautious about expanding the number of architected registers (also the register field), because increasing the register field adds to the code size, raises I-cache and memory pressure, complicates processor ...
Bytewise Register Allocation
SCOPES '15: Proceedings of the 18th International Workshop on Software and Compilers for Embedded Systems

Traditionally, variables have been considered as atoms by register allocation: Each variable was to be placed in one register, or spilt (placed in main memory) or rematerialized (recalculated as needed). Some flexibility arose from what would be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation

August 1994

360 pages

ISBN:089791662X

DOI:10.1145/178243

Chairmen:
Vivek Sarkar
IBM Santa Teresa Lab.
,
Barbara Ryder
Rutgers Univ., New Brunswick, NJ
,
Mary Lou Soffa
Univ. of Pittsburgh, Pittsburgh, PA

ACM SIGPLAN Notices Volume 29, Issue 6
June 1994
360 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/773473
Guest Editor:
Brent T. Hailpern
Issue’s Table of Contents

Copyright © 1994 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 June 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI94

Sponsor:

SIGPLAN

PLDI94: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 20 - 24, 1994

Florida, Orlando, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
645
Total Downloads

Downloads (Last 12 months)47
Downloads (Last 6 weeks)8

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kiran DGurunarayanan SMisra JBhatia M(2017)Register allocation for fine grain threads on multicore processorJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2015.04.00129:1(85-92)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1016/j.jksuci.2015.04.001
Brisk PSarrafzadeh M(2007)Interference graphs for procedures in static single information form are interval graphsProceedingsof the 10th international workshop on Software & compilers for embedded systems10.1145/1269843.1269858(101-110)Online publication date: 20-Apr-2007
https://dl.acm.org/doi/10.1145/1269843.1269858
Jain MBalakrishnan MKumar A(2006)An efficient technique for exploring register file size in ASIP designIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2004.83771723:12(1693-1699)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TCAD.2004.837717
Thorup M(2005)Structured programs have small tree-width and good register allocationGraph-Theoretic Concepts in Computer Science10.1007/BFb0024507(318-332)Online publication date: 17-Jun-2005
https://doi.org/10.1007/BFb0024507
Lueh GGross TAdl-Tabatabai A(2005)Global register allocation based on graph fusionLanguages and Compilers for Parallel Computing10.1007/BFb0017257(246-265)Online publication date: 10-Jun-2005
https://doi.org/10.1007/BFb0017257
Cooper KDasgupta AEckhardt J(2005)Revisiting graph coloring register allocationProceedings of the 18th international conference on Languages and Compilers for Parallel Computing10.1007/978-3-540-69330-7_1(1-16)Online publication date: 20-Oct-2005
https://dl.acm.org/doi/10.1007/978-3-540-69330-7_1
Govindarajan RYang HAmaral JZhang CGao G(2003)Minimum Register Instruction Sequencing to Reduce Register Spills in Out-of-Order Issue Superscalar ArchitecturesIEEE Transactions on Computers10.1109/TC.2003.115975052:1(4-20)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.1109/TC.2003.1159750
Fu CWilken KAltman EEbcioǧlu KMahlke SRau BPatel S(2002)A faster optimal register allocatorProceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture10.5555/774861.774888(245-256)Online publication date: 18-Nov-2002
https://dl.acm.org/doi/10.5555/774861.774888
Jain MBalakrishnan MKumar ABhattacharyya SMudge TWolf WJerraya A(2002)An efficient technique for exploring register file size in ASIP synthesisProceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems10.1145/581630.581671(252-261)Online publication date: 8-Oct-2002
https://dl.acm.org/doi/10.1145/581630.581671
Govindarajan RYang HAmaral JZhang CGao G(2001)Minimum register instruction sequence problem: revisiting optimal code generation for DAGsProceedings 15th International Parallel and Distributed Processing Symposium. IPDPS 200110.1109/IPDPS.2001.924962(8)Online publication date: 2001
https://doi.org/10.1109/IPDPS.2001.924962
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents