article

Open access

Linear scan register allocation

Editor: William Pugh Authors:

Massimiliano Poletto,

Vivek SarkarAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 21, Issue 5

Pages 895 - 913

https://doi.org/10.1145/330249.330250

Published: 01 September 1999 Publication History

Abstract

We describe a new algorithm for fast global register allocation called linear scan. This algorithm is not based on graph coloring, but allocates registers to variables in a single linear-time scan of the variables' live ranges. The linear scan algorithm is considerably faster than algorithms based on graph coloring, is simple to implement, and results in code that is almost as efficient as that obtained using more complex and time-consuming register allocators based on graph coloring. The algorithm is of interest in applications where compile time is a concern, such as dynamic compilation systems, “just-in-time” compilers, and interactive development environments.

Formats available

You can view the full content in the following formats:

References

[1]

Aho, A. V., Sethi, R., and Ullman, J. D. 1986. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, MA.

Digital Library

[2]

Amarasinghe, S. P., Anderson, J. M., Lam, M. S., and Lim, A. W. 1993. An overview of the SUIF compiler for scalable parallel machines. In Proceedings of the 6th Workshop on Languages and Compilers for Parallel Computing. Portland, OR.

Digital Library

[3]

Auslander, M. and Hopkins, M. 1982. An overview of the PL.8 compiler. In Proceedings of the ACM SIGPLAN '82 Symposium on Compiler Construction. 22-31.

Digital Library

[4]

Belady, L. A. 1966. A study of replacement algorithms for a virtual storage computer. IBM Systems Journal 5, 2, 78-101.

Digital Library

[5]

Blickstein, D., Craig, P., Davidson, C., Faiman, R., Glossop, K., Grove, R., Hobbs, S., and Noyce, W. 1992. The GEM optimizing compiler system. Digital Equipment Corporation Technical Journal 4, 4, 121-135.

[6]

Briggs, P., Cooper, K., and Torczon, L. 1994. Improvements to graph coloring register allocation. ACM Transactions on Programming Languages and Systems 16, 3 (May), 428-455.

Digital Library

[7]

Chaitin, G. J., Auslander, M. A., Chandra, A. K., Cocke, J., Hopkins, M. E., and Mark-stein, P. W. 1981. Register allocation via coloring. Computer Languages 6, 47-57.

Digital Library

[8]

Cormen, T. H., Leiserson, C. E., and Rivest, R. L. 1990. Introduction to Algorithms. MIT Press, Cambridge, MA.

Digital Library

[9]

Cytron, R., Ferrante, J., Rosen, B. K., Wegman, M. N., and Zadeck, F. K. 1989. An e cient method of computing static single assignment form. In Conference Record of the 16th Annual ACM Symposium on Principles of Programming Languages. Austin, TX, 25-35.

Digital Library

[10]

Fraser, C. W. and Hanson, D. R. 1995. A Retargetable C Compiler: Design and Implementation. Benjamin/Cummings, Redwood City, CA.

Digital Library

[11]

Freiburghouse, R. A. 1974. Register allocation via usage counts. Communications of the ACM 17, 11 (November), 638-642.

Digital Library

[12]

George, L. and Appel, A. 1996. Iterated register coalescing. ACM Transactions on Programming Languages and Systems 18, 3 (May), 300-324.

Digital Library

[13]

Hsu, W.-C., Fischer, C. N., and Goodman, J. R. 1989. On the minimization of loads and stores in local register allocation. IEEE Transactions on Software Engineering 15, 10 (October), 1252-1260.

Digital Library

[14]

Motwani, R., Palem, K. V., Sarkar, V., and Reyen, S. 1995. Combining Register Allocation and Instruction Scheduling (Technical Summary). Tech. rep., Courant Institute, New York University. July. TR 698.

Digital Library

[15]

Muchnick, S. S. 1997. Advanced compiler design and implementation. Morgan Kaufmann, San Francisco, CA.

Digital Library

[16]

Poletto, M., Engler, D. R., and Kaashoek, M. F. 1997. tcc: A system for fast, exible, and high-level dynamic code generation. In Proceedings of the ACM SIGPLAN '97 {17} Conference on Programming Language Design and Implementation. Las Vegas, NV, 109-121.

Digital Library

[17]

Poletto, M., Hsieh, W. C., Engler, D. R., and Kaashoek, M. F. 1999. `C and tcc: A language and compiler for dynamic code generation. ACM Transactions on Programming Languages and Systems. (To appear).

Digital Library

[18]

Smith, M. 1996. Extending SUIF for machine-dependent optimizations. In Proceedings of the First SUIF Compiler Workshop. Stanford, CA, 14-25. http://www.eecs.harvard.edu/machsuif.

[19]

Traub, O., Holloway, G., and Smith, M. D. 1998. Quality and speed in linear-scan register allocation. In Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation.

Digital Library

Cited By

Reppy JShivers OZhong B(2026)Flow-Analysis-Based Closure OptimizationProceedings of the ACM on Programming Languages10.1145/380826210:PLDI(379-404)Online publication date: 8-Jun-2026
https://dl.acm.org/doi/10.1145/3808262
Yang ZZhang KTian XRen XLiu YLi YDing DChen JXie Y(2026)Unifying Qubit Routing Across Diverse Quantum ISAs via Canonical Representation2026 ACM/IEEE 53rd Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA66397.2026.00162(2302-2317)Online publication date: Jun-2026
https://doi.org/10.1109/ISCA66397.2026.00162
Jin HYang JLyu BGao RBleier N(2026)æSIP: μArch-Aware ASIP-ISA Co-Design via Program Synthesis, Equality Saturation, and External Don't Cares2026 ACM/IEEE 53rd Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA66397.2026.00112(1512-1528)Online publication date: Jun-2026
https://doi.org/10.1109/ISCA66397.2026.00112
Show More Cited By

Index Terms

Recommendations

Comments

View Issue’s Table of Contents