Abstract
Decisions made during register allocation greatly influence the overall quality of compiled code. Standard graph-coloring allocators often make spilling decisions which are not guided by program structure or path-sensitive control flow information. This can result in generation and placement of load and store instructions which is inefficient from a global perspective. Quite often, allocation decisions get heavily influ- enced by the choice of candidates for register residency. We propose a framework which selectively demotes variables in a contained manner to maintain balanced register pressure. The decisions for selective demotion are made through a flow-analytic approach and the loads and stores are inserted in strategic points such that degrading effect of spill code on overall code quality is sufficiently reduced. Our approach tries to keep variables as candidates for register allocation only along the paths where it is profitable to do so. We attempt to identify good local candidates for demotion, however, decisions are taken only after their global demo- tion costs are captured. We have implemented the framework inside the SGI MIPSPRO compiler and have obtained very encouraging results in improving the allocation of a Briggs-style allocator.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers Priciples, Techniques, and Tools. Addison-Wesley Publishing Company, 1986.
P. Bergner, P. Dahl, D. Engebretsen, and M. O’Keefe. Spill Code Minimization via Interference Region Spilling. In Proceedings of the 1997 ACM SIGPLAN Con-ference on Programming Languages Design and Implementation, pages 287–295, June 1997.
P. Briggs, K. Cooper, and L. Torczon. Improvements to Graph Coloring Reg-ister Allocation. ACM Transactions on Programming Languages and Systems, 16(3):428–455, May 1994.
D. Callahan and B. Koblenz. Register Allocation via Hierarchical Graph Coloring. In Proceedings of the 1991 ACM SIGPLAN Conference on Programming Languages Design and Implementation, pages 192–203, June 1991.
G. Chaitin, M. Auslander, A. Chandra, J. Cocke, M. Hopkins, and P. Markstein. Register Allocation via Coloring. Computer Languages, 6:47–57, January 1981.
F. Chow and J. Hennessy. The Priority-based Coloring Approach to Register Al-location. ACM Transactions on Programming Languages and Systems, 12(4):501–536, October 1990.
P. Kolte and M. J. Harrold. Load/store Range Analysis for Global Register Allocation. In Proceedings of the 1993 ACM SIGPLAN Conference on Programming Languages Design and Implementation, pages 268–277, June 1993.
R. Lo, F. Chow, R. Kennedy, S. Liu, and P. Tu. Register Promotion by Sparse Partial Redundancy Elimination of Loads and Stores. In Proceedings of the 1998 ACM SIGPLAN Conference on Programming Languages Design and Implementa-tion, pages 26–37, May 1998.
Guei-Yuan Lueh. Fusion-based register allocation. PhD Thesis CMU-CS-97-135, Carnegie Mellon University, 1997.
S. Mantripragada, S. Jain, and J. Dehnert. A New Framework for Integrated Global Local Scheduling. In Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, pages 167–175, October 1998.
C. Norris and L. L. Pollock. RAP: A PDG-based Register Allocator. Software-Practice and Experience, 28(4):401–424, April 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bairagi, D., Pande, S., Agrawal, D.P. (2000). A Framework for Efficient Register Allocation through Selective Register Demotion. In: Dwarkadas, S. (eds) Languages, Compilers, and Run-Time Systems for Scalable Computers. LCR 2000. Lecture Notes in Computer Science, vol 1915. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-40889-4_5
Download citation
DOI: https://doi.org/10.1007/3-540-40889-4_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41185-7
Online ISBN: 978-3-540-40889-5
eBook Packages: Springer Book Archive