Abstract
We present a simple algorithm for register allocation which is competitive with the iterated register coalescing algorithm of George and Appel. We base our algorithm on the observation that 95% of the methods in the Java 1.5 library have chordal interference graphs when compiled with the JoeQ compiler. A greedy algorithm can optimally color a chordal graph in time linear in the number of edges, and we can easily add powerful heuristics for spilling and coalescing. Our experiments show that the new algorithm produces better results than iterated register coalescing for settings with few registers and comparable results for settings with many registers.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Andersson, C.: Register allocation by optimal graph coloring. In: 12th Conference on Compiler Construction, pp. 34–45. Springer, Heidelberg (2003)
Appel, A.W., George, L.: Optimal spilling for cisc machines with few registers. In: International Conference on Programming Languages Design and Implementation, pp. 243–253. ACM Press, New York (2001)
Appel, A.W., George, L.: 27,921 actual register-interference graphs generated by standard ML of New Jersey, version 1.09 (2005), http://www.cs.princeton.edu/~appel/graphdata/
Berry, A., Blair, J., Heggernes, P., Peyton, B.: Maximum cardinality search for computing minimal triangulations of graphs. Algorithmica 39(4), 287–298 (2004)
Briggs, P., Cooper, K.D., Torczon, L.: Improvements to graph coloring register allocation. Transactions on Programming Languages and Systems (TOPLAS) 16(3), 428–455 (1994)
Brisk, P., Dabiri, F., Macbeth, J., Sarrafzadeh, M.: Polynomial-time graph coloring register allocation. In: 14th International Workshop on Logic and Synthesis. ACM Press, New York (2005)
Budimlic, Z., Cooper, K.D., Harvey, T.J., Kennedy, K., Oberg, T.S., Reeves, S.W.: Fast copy coalescing and live-range identification. In: International Conference on Programming Languages Design and Implementation, pp. 25–32. ACM Press, New York (2002)
Chaitin, G.J.: Register allocation and spilling via graph coloring. In: Symposium on Compiler Construction, vol. 17(6), pp. 98–105 (1982)
Chudnovsky, M., Cornuejols, G., Liu, X., Seymour, P., Vuskovic, K.: Recognizing berge graphs. Combinatorica 25, 143–186 (2005)
Dirac, G.A.: On rigid circuit graphs. In: Abhandlungen aus dem Mathematischen Seminar der Universiat Hamburg, vol. 25, pp. 71–75. University of Hamburg (1961)
Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SICOMP 1(2), 180–187 (1972)
George, L., Appel, A.W.: Iterated register coalescing. Transactions on Programming Languages and Systems (TOPLAS) 18(3), 300–324 (1996)
Grotschel, M., Lovasz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169–197 (1981)
Hack, S.: Interference graphs of programs in SSA-form. Technical report, Universitat Karlsruhe (2005)
Pereira, F.M.Q., Palsberg, J.: Register allocation after SSA elimination is NP-complete (2005) (Manuscript)
Poletto, M., Sarkar, V.: Linear scan register allocation. ACM Transactions on Programming Languages and Systems 21(5), 895–913 (1999)
Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13(3), 566–579 (1984)
West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice-Hall, Englewood Cliffs (2001)
Whaley, J.: Joeq: a virtual machine and compiler infrastructure. In: Workshop on Interpreters, virtual machines and emulators, pp. 58–66. ACM Press, New York (2003)
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
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pereira, F.M.Q., Palsberg, J. (2005). Register Allocation Via Coloring of Chordal Graphs. In: Yi, K. (eds) Programming Languages and Systems. APLAS 2005. Lecture Notes in Computer Science, vol 3780. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11575467_21
Download citation
DOI: https://doi.org/10.1007/11575467_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29735-2
Online ISBN: 978-3-540-32247-4
eBook Packages: Computer ScienceComputer Science (R0)