TY - JOUR
T1 - On Local Register Allocation
AU - Farach-Colton, Martin
AU - Liberatore, Vincenzo
N1 - Funding Information:
1Supported by NSF Career Development Award CCR-9501942, NATO Grant CRG 960215, NSF NIH Grant BIR 94-12594-03-CONF, and an Alfred P. Sloan Research Fellowship. Travel support provided by DIMACS. DIMACS is a partnership of Rutgers University, Princeton University, AT & T Labs-Research, Bell Labs, Telcordia Technologies (formerly Bellcore), and NEC Research Institute. DIMACS is an NSF Science and Technology Center, funded under Contract STC 91-19999. DIMACS is also supported by the New Jersey Commission on Science and Technology. A preliminary version of this paper appeared in the Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 564—573. 2 URL: http: www.cs.rutgers.edu farach . 3URL: http: www.umiacs.umd.edu users liberato .
PY - 2000/10
Y1 - 2000/10
N2 - In this paper, we consider the problem of local register allocation (LRA): given a sequence of instructions (basic block) and a number of general purpose registers, find the schedule of variables in registers that minimizes the total traffic between CPU and the memory system. Local register allocation has been studied for more than 30 years in the theory and compiler communities. In this paper, we give a 2-approximation algorithm for LRA. We also show that a variant of the known further-first heuristic achieves a good approximation ratio.
AB - In this paper, we consider the problem of local register allocation (LRA): given a sequence of instructions (basic block) and a number of general purpose registers, find the schedule of variables in registers that minimizes the total traffic between CPU and the memory system. Local register allocation has been studied for more than 30 years in the theory and compiler communities. In this paper, we give a 2-approximation algorithm for LRA. We also show that a variant of the known further-first heuristic achieves a good approximation ratio.
UR - http://www.scopus.com/inward/record.url?scp=0346739888&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0346739888&partnerID=8YFLogxK
U2 - 10.1006/jagm.2000.1095
DO - 10.1006/jagm.2000.1095
M3 - Article
AN - SCOPUS:0346739888
SN - 0196-6774
VL - 37
SP - 37
EP - 65
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 1
ER -