Abstract
A graph-coloring register allocator that optimally allocates registers for structured programs in polynomial time is presented. It can handle register aliasing. The assignment of registers is optimal with respect to spill and rematerialization costs, register preferences and coalescing. The register allocator is not restricted to programs in SSA form or chordal interference graphs. It assumes the number of registers is to be fixed and requires the input program to be structured, which is automatically true for many programming languages and for others, such as C, is equivalent to a bound on the number of goto labels per function. Non-structured programs can be handled at the cost of either a loss of optimality or an increase in runtime. This is the first optimal approach that has polynomial runtime and works for such a huge class of programs.
An implementation is already the default register allocator in most backends of a mainstream cross-compiler for embedded systems.
Chapter PDF
Similar content being viewed by others
References
Coremark, http://www.coremark.org
Guidelines for the Use of the C Language in Critical Systems (MISRA-C:2004, 2nd Edition). Technical report, MISRA (2008)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal of Computation 25(6), 1305–1317 (1996)
Bodlaender, H.L., Gustedt, J., Telle, J.A.: Linear-Time Register Allocation for a Fixed Number of Registers. In: SODA 1998: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 574–583. Society for Industrial and Applied Mathematics (1998)
Bouchez, F., Darte, A., Rastello, F.: On the Complexity of Register Coalescing. In: Proceedings of the International Symposium on Code Generation and Optimization, CGO 2007, pp. 102–114. IEEE Computer Society (2007)
Burgstaller, B., Blieberger, J., Scholz, B.: On the Tree Width of Ada Programs. In: Llamosí, A., Strohmeier, A. (eds.) Ada-Europe 2004. LNCS, vol. 3063, pp. 78–90. Springer, Heidelberg (2004)
Chaitin, G.J.: Register allocation & spilling via graph coloring. In: SIGPLAN 1982: Proceedings of the 1982 SIGPLAN Symposium on Compiler Construction, pp. 98–105. Association for Computing Machinery (1982)
Chaitin, G.J., Auslander, M.A., Chandra, A.K., Cocke, J., Hopkins, M.E., Markstein, P.W.: Register allocation via coloring. Computer Languages 6, 47–57 (1981)
ChaN. Fatfs, http://elm-chan.org/fsw/ff/00index_e.html
Dendris, N.D., Kirousis, L.M., Thilikos, D.M.: Fugitive-search games on graphs and related parameters. Theoretical Computer Science 172(1-2), 233–254 (1997)
Dunkels, A., Grönvall, B., Voigt, T.: Contiki - a Lightweight and Flexible Operating System for Tiny Networked Sensors. In: Proceedings of the First IEEE Workshop on Embedded Networked Sensors (Emnets-I) (November 2004)
Dutta, S.: Anatomy of a Compiler. Circuit Cellar 121, 30–35 (2000)
Evlogimenos, A.: Improvements to Linear Scan register allocation, Technical report, University of Illinois, Urbana-Champaign (2004)
Farach, M., Liberatore, V.: On local register allocation. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1998, pp. 564–573. Society for Industrial and Applied Mathematics (1998)
Fu, C., Wilken, K.: A Faster Optimal Register Allocator. In: MICRO 35: Proceedings of the 35th Annual ACM/IEEE International Symposium on Microarchitecture, pp. 245–256. IEEE Computer Society Press (2002)
Garey, M.R., Johnson, D.S., Miller, G.L., Papadimitriou, C.H.: The Complexity of Coloring Circular Arcs and Chords. SIAM Journal on Algebraic Discrete Methods 1(2), 216–227 (1980)
Goodwin, D.W., Wilken, K.D.: Optimal and near-optimal global register allocations using 0–1 integer programming. Software Practice & Experience 26(8), 929–965 (1996)
Guruswami, V., Sinop, A.K.: Improved Inapproximability Results for Maximum k-Colorable Subgraph. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol. 5687, pp. 163–176. Springer, Heidelberg (2009)
Gustedt, J., Mæhle, O.A., Telle, J.A.: The Treewidth of Java Programs. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol. 2409, pp. 86–97. Springer, Heidelberg (2002)
Hack, S., Grund, D., Goos, G.: Register Allocation for Programs in SSA-Form. In: Mycroft, A., Zeller, A. (eds.) CC 2006. LNCS, vol. 3923, pp. 247–262. Springer, Heidelberg (2006)
Halin, R.: Zur Klassifikation der endlichen Graphen nach H. Hadwiger und K. Wagner. Mathematische Annalen 172(1), 46–78 (1967)
Hames, L., Scholz, B.: Nearly Optimal Register Allocation with PBQP. In: Lightfoot, D.E., Ren, X.-M. (eds.) JMLC 2006. LNCS, vol. 4228, pp. 346–361. Springer, Heidelberg (2006)
Kannan, S., Proebsting, T.: Register Allocation in Structured Programs. In: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995, pp. 360–368. Society for Industrial and Applied Mathematics (1995)
Karp, R.M.: On the Computational Complexity of Combinatorial Problems. Networks 5, 45–68 (1975)
Krause, P.K.: The Complexity of Register Allocation. To appear in the GROW 2011 special issue of Discrete Applied Mathematics (2011)
Lee, J.K., Palsberg, J., Pereira, F.M.Q.: Aliased register allocation for straight-line programs is NP-complete. Theoretical Computer Science 407(1-3), 258–273 (2008)
Pereira, F.M.Q.: Register Allocation Via Coloring of Chordal Graphs. In: Yi, K. (ed.) APLAS 2005. LNCS, vol. 3780, pp. 315–329. Springer, Heidelberg (2005)
Poletto, M., Sarkar, V.: Linear scan register allocation. ACM Transactions on Programming Languages and Systems (TOPLAS) 21(5), 895–913 (1999)
Robertson, N., Seymour, P.D.: Graph Minors. I. Excluding a Forest. Journal of Combinatorial Theory, Series B 35(1), 39–61 (1983)
Scholz, B., Eckstein, E.: Register Allocation for Irregular Architectures. SIGPLAN Notices 37(7), 139–148 (2002)
Smith, M.D., Ramsey, N., Holloway, G.: A Generalized Algorithm for Graph-Coloring Register Allocation. In: PLDI 2004: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, pp. 277–288. Association for Computing Machinery (2004)
Thorup, M.: All Structured Programs Have Small Tree Width and Good Register Allocation. Information and Computation 142(2), 159–181 (1998)
Weicker, R.P.: Dhrystone: a synthetic systems programming benchmark. Communications of the ACM 27, 1013–1030 (1984)
Weicker, R.P.: Dhrystone Benchmark: Rationale for Version 2 and Measurement Rules. SIGPLAN Notices 23, 49–62 (1988)
Yannakakis, M., Gavril, F.: The maximum k-colorable subgraph problem for chordal graphs. Information Processing Letters 24(2), 133–137 (1987)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Krause, P.K. (2013). Optimal Register Allocation in Polynomial Time. In: Jhala, R., De Bosschere, K. (eds) Compiler Construction. CC 2013. Lecture Notes in Computer Science, vol 7791. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37051-9_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-37051-9_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-37050-2
Online ISBN: 978-3-642-37051-9
eBook Packages: Computer ScienceComputer Science (R0)