Optimal local register allocation for a multiple-issue machine

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal local register allocation for a multiple-issue machine

Full text

Pdf (987 KB)

Source

International Conference on Supercomputing archive
Proceedings of the 8th international conference on Supercomputing table of contents

Manchester, England

Pages: 107 - 116

Year of Publication: 1994

ISBN:0-89791-665-4

Authors

Waleed M. Meleis	Advanced Computer Architecture Lab, Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI
Edward S. Davidson	Advanced Computer Architecture Lab, Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 12, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/181181.181318 What is a DOI?

ABSTRACT

This paper presents an algorithm that allocates registers optimally for straight-line code running on a generic multi-issue computer. On such a machine, an optimal register allocation is one that minimizes the number of issue slots that the code requires. Optimal spill selection and load/store placement are used to minimize the number of additional issue slots needed, given a schedule for the non-memory reference instructions and a fixed number of available physical registers. The generic multi-issue machine model closely models the operation of vector and VLIW processors, and could be extended to model super-scalar processors. The algorithm uses dynamic programming to search the state space of feasible register allocations; implicit and explicit state pruning are used to make the problem tractable without sacrificing optimality. The optimal allocation produced by the algorithm for a substantial example is presented.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	2	Eric L. Boyd , Edward S. Davidson, Hierarchical performance modeling with MACS: a case study of the convex C-240, Proceedings of the 20th annual international symposium on Computer architecture, p.203-210, May 16-19, 1993, San Diego, California, United States
	3	Fred C. Chow , John L. Hennessy, The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.501-536, Oct. 1990 [doi>10.1145/88616.88621]
	4	CONVEX Computer Corporation. CONVEX Theory of Operation - C200, volume 081-005030-000. 1990.
	5	G. J. ChMtin et al. RegNter aHocation via coloring. Computer Languages, 6:47-57, 1981.
	6	G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
	7	L. P. Horwitz , R. M. Karp , R. E. Miller , S. Winograd, Index Register Allocation, Journal of the ACM (JACM), v.13 n.1, p.43-61, Jan. 1966 [doi>10.1145/321312.321317]
	8	Wei-Chung Hsu , Charles N. Fisher , James R. Goodman, On the Minimization of Loads/Stores in Local Register Allocation, IEEE Transactions on Software Engineering, v.15 n.10, p.1252-1260, October 1989 [doi>10.1109/TSE.1989.559775]