Register allocation via usage counts

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Register allocation via usage counts

Full text

Pdf (478 KB)

Source

Communications of the ACM archive
Volume 17 , Issue 11 (November 1974) table of contents

Pages: 638 - 642

Year of Publication: 1974

ISSN:0001-0782

Author

R. A. Freiburghouse

Honeywell Information Systems Inc., Cambridge, MA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 36, Citation Count: 22

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/361179.361201 What is a DOI?

ABSTRACT

This paper introduces the notion of usage counts, shows how usage counts can be developed by algorithms that eliminate redundant computations, and describes how usage counts can provide the basis for register allocation. The paper compares register allocation based on usage counts to other commonly used register allocation techniques, and presents evidence which shows that the usage count technique is significantly better than these other techniques.

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	Allen, F. Program optimization. In Annual Review of Automatic Programming, Vol. 5. Pergamon Press, New York 1968, pp. 239-307.
	2	Beatty, J.C. A register assignment algorithm for generation of highly optimized object code. IBM J. Res. Dev. 18, 1 (Jan. 1974), 20-39.
	3	Belady, L.A. A study of replacement algorithms for a virtualstorage computer. IBM Syst. J. 5, 2 (Apr. 1966), 78-101.
	4	Vincent A. Busam , Donald E. Englund, Optimization of expressions in Fortran, Communications of the ACM, v.12 n.12, p.666-674, Dec. 1969 [doi>10.1145/363626.363635]
	5	John Cocke, Global common subexpression elimination, Proceedings of a symposium on Compiler optimization, p.20-24, July 27-28, 1970, Urbana-Champaign, Illinois
	6	Freiburghouse, R. The Multics PL/I compiler. Proc. AFIPS 1969 FJCC, AFIPS Press, Montvale, N.J., pp. 187-199.
	7	Green, P. An implementation of SEAL on Multics. Bachelor's Th. Dep. Elec. Eng., MIT, Cambridge, May 1973.
	8	David Gries, Compiler Construction for Digital Computers, John Wiley & Sons, Inc., New York, NY, 1971
	9	The Multics PL/I Language. AG94, Honeywell Information Systems Inc., 1972.
	10	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]
	11	Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
	12	F. Luccio, A comment on index register allocation, Communications of the ACM, v.10 n.9, p.572-574, Sept. 1967 [doi>10.1145/363566.363694]

CITED BY 22

	J. R. Goodman , W. C. Hsu, On the use of registers vs. cache to minimize memory traffic, ACM SIGARCH Computer Architecture News, v.14 n.2, p.375-383, June 1986
	C.-H. Chi , H. Dietz, Unified management of registers and cache using liveness and cache bypass, ACM SIGPLAN Notices, v.24 n.7, p.344-353, July 1989
	Jack W. Davidson , Christopher W. Fraser, Code selection through object code optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.505-526, Oct. 1984
	A. V. Aho , S. C. Johnson , J. D. Ullman, Code generation for expressions with common subexpressions (Extended Abstract), Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.19-31, January 19-21, 1976, Atlanta, Georgia
	Changqing Fu , Kent Wilken, A faster optimal register allocator, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
	Massimiliano Poletto , Dawson R. Engler , M. Frans Kaashoek, tcc: a system for fast, flexible, and high-level dynamic code generation, ACM SIGPLAN Notices, v.32 n.5, p.109-121, May 1997
	H. Dietz , C. H. Chi, CRegs: a new kind of memory for referencing arrays and pointers, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.360-367, November 12-17, 1988, Orlando, Florida, United States
	Christoph Kessler , Andrzej Bednarski, Optimal integrated code generation for clustered VLIW architectures, ACM SIGPLAN Notices, v.37 n.7, July 2002
	D. A. Taffs , M. W. Taffs , J. C. Rienzo , T. R. Hampson, The ALS Ada compiler global optimizer, ACM SIGAda Ada Letters, v.V n.2, p.355-366, Sep., Oct. 1985
	A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977
	Massimiliano Poletto , Vivek Sarkar, Linear scan register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.895-913, Sept. 1999
	Todd A. Proebsting , Charles N. Fischer, Demand-driven register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.6, p.683-710, Nov. 1996
	Richard L. Sites, Machine-independent register allocation, ACM SIGPLAN Notices, v.14 n.8, p.221-225, August 1979
	Todd A. Proebsting , Charles N. Fischer, Probabilistic register allocation, ACM SIGPLAN Notices, v.27 n.7, p.300-310, July 1992
	Frederick Chow , John Hennessy, Register allocation by priority-based coloring, ACM SIGPLAN Notices, v.19 n.6, p.222-232, June 1984
	Christoph Keßler , Andrzej Bednarski, A Dynamic Programming Approach to Optimal Integrated Code Generation, ACM SIGPLAN Notices, v.36 n.8, p.165-174, Aug. 2001
	Jack W. Davidson , Christopher W. Fraser, Eliminating redundant object code, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.128-132, January 25-27, 1982, Albuquerque, Mexico
	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
	Fred Chow , John Hennessy, Register allocation by priority-based coloring, ACM SIGPLAN Notices, v.39 n.4, April 2004
	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
	Jack W. Davidson , Anne M. Holler, Subprogram Inlining: A Study of its Effects on Program Execution Time, IEEE Transactions on Software Engineering, v.18 n.2, p.89-102, February 1992
	Manfred Weber , Susan L. Bernstein, Global register allocation for non-equivalent register sets, ACM SIGPLAN Notices, v.15 n.2, p.74-81, February 1980