An optimistic and conservative register assignment heuristic for chordal graphs

ABSTRACT

This paper presents a new register assignment heuristic for procedures in SSA Form, whose interference graphs are chordal; the heuristic is called optimistic chordal coloring (OCC). Previous register assignment heuristics eliminate copy instructions via coalescing, in other words, merging nodes in the interference graph. Node merging, however, can not preserve the chordal graph property, making it unappealing for SSA-based register allocation. OCC is based on graph coloring, but does not employ coalescing, and, consequently, preserves graph chordality, and does not increase its chromatic number; in this sense, OCC is conservative as well as optimistic. OCC is observed to eliminate at least as many dynamically executed copy instructions as iterated register coalescing (IRC) for a set of chordal interference graphs generated from several Mediabench and MiBench applications. In many cases, OCC and IRC were able to find optimal or near-optimal solutions for these graphs. OCC ran 1.89x faster than IRC, on average.

REFERENCES

• 1: Bouchez, F., Darte, A., Guillon, C., and Rastello, F. Register Allocation and Spill Complexity Under SSA, Technical Report 2005-33, ENS-Lyon, Lyon France, 2005.
• 2: Bouchez, F., Darte, A., Guillon, C., and Rastello, F. Register allocation : what does the NP-Completeness proof of Chaitin et al. really prove? Or revisting register allocation: why and how. In Proc. of the 19th International Workshop on Languages and Compilers for Parallel Computing (LCPC '06), (New Orleans, LA, USA, November 2-4, 2006).
• 3: Florent Bouchez , Alain Darte , Fabrice Rastello, On the Complexity of Register Coalescing, Proceedings of the International Symposium on Code Generation and Optimization, p.102-114, March 11-14, 2007 [doi>10.1109/CGO.2007.26]
• 4: Preston Briggs , Keith D. Cooper , Timothy J. Harvey , L. Taylor Simpson, Practical improvements to the construction and destruction of static single assignment form, Software—Practice & Experience, v.28 n.8, p.859-881, July 10, 1998 [doi>10.1002/(SICI)1097-024X(19980710)28:8<859::AID-SPE188>3.0.CO;2-8]
• 5: Preston Briggs , Keith D. Cooper , Linda Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.428-455, May 1994 [doi>10.1145/177492.177575]
• 6: Brisk, P., Dabiri, F., Jafari, R., and Sarrafzadeh, M. Optimal register sharing for high-level synthesis of SSA form programs. IEEE Trans. Computer Aided Design, vol. 25, no. 25, May, 2006, 772--779.
• 7: Zoran Budimlic , Keith D. Cooper , Timothy J. Harvey , Ken Kennedy , Timothy S. Oberg , Steven W. Reeves, Fast copy coalescing and live-range identification, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 8: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 9: Jong-Deok Choi , Ron Cytron , Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.55-66, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99594]
• 10: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 11: Gavril, F. Algorithms for minimum coloring, maximum clique, minimum coloring by cliques, and maximum independent set of a chordal graph. SIAM J. Comput., vol. 1, no. 2, June, 1972, 180--187.
• 12: Lal George , Andrew W. Appel, Iterated register coalescing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.300-324, May 1996 [doi>10.1145/229542.229546]
• 13: Grund, D., and Hack, S. A fast cutting-plane algorithm for optimal coalescing. In Proc. of the 16th International Conference on Compiler Construction (CC '07) (Lisbon, Portugal, March 26-27, 2007) 111--125.
• 14: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 15: Sebastian Hack , Gerhard Goos, Optimal register allocation for SSA-form programs in polynomial time, Information Processing Letters, v.98 n.4, p.150-155, 31 May 2006 [doi>10.1016/j.ipl.2006.01.008]
• 16: Hack, S., Grund, D., and Goos, G. Register allocation for programs in SSA Form, In Proc. of the 15th International Conference on Compiler Construction (CC '06) (Vienna, Austria, March 30-31, 2006) 247--262.
• 17: Max Hailperin, Comparing conservative coalescing criteria, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.3, p.571-582, May 2005 [doi>10.1145/1065887.1065894]
• 18: Kaluskar, V. P. An Aggressive Live Range Splitting and Coalescing Framework for Efficient Register Allocation. M. S. Thesis, Georgia Institute of Technology, November, 2003.
• 19: Kempe, A. B. On the geographical problem of the four colors. American Journal of Mathematics, vol. 2, 1879, 193--200.
• 20: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 21: David W. Matula , Leland L. Beck, Smallest-last ordering and clustering and graph coloring algorithms, Journal of the ACM (JACM), v.30 n.3, p.417-427, July 1983 [doi>10.1145/2402.322385]
• 22: Jinpyo Park , Soo-Mook Moon, Optimistic register coalescing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.4, p.735-765, July 2004 [doi>10.1145/1011508.1011512]
• 23: 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 [doi>10.1145/330249.330250]
• 24: F. Rastello , F. de Ferrière , C. Guillon, Optimizing Translation Out of SSA Using Renaming Constraints, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.265, March 20-24, 2004, Palo Alto, California
• 25: Smith, M. D., and Holloway, G. An introduction to Machine SUIF and its portable libraries for analysis and optimization. Technical Report. Harvard University. July 15, 2002.
• 26: Vugranam C. Sreedhar , Roy Dz-Ching Ju , David M. Gillies , Vatsa Santhanam, Translating Out of Static Single Assignment Form, Proceedings of the 6th International Symposium on Static Analysis, p.194-210, September 22-24, 1999
• 27: Robert E. Tarjan , Mihalis Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM Journal on Computing, v.13 n.3, p.566-579, August 1984 [doi>10.1137/0213035]
• 28: Steven R. Vegdahl, Using node merging to enhance graph coloring, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.150-154, May 01-04, 1999, Atlanta, Georgia, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Performance

Keywords:
chordal graph, register assignment, static single assignment (ssa) form