Interference graphs for procedures in static single information form are interval graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Interference graphs for procedures in static single information form are interval graphs

Full text

Pdf (165 KB)

Source

ACM International Conference Proceeding Series; Vol. 235 archive
Proceedingsof the 10th international workshop on Software & compilers for embedded systems table of contents

Nice, France

SESSION: Recent advances in static single-assignment representations table of contents

Pages: 101 - 110

Year of Publication: 2007

Authors

Philip Brisk	Ecole Polytechnique Federale de Lausanne (EPFL), Lausanne, Switzerland
Majid Sarrafzadeh	University of California Los Angeles, Los Angeles, CA

Sponsors

: Artist2 European NoE
: ACE Associated Compiler Experts bv
SIGBED: ACM Special Interest Group on Embedded Systems
: European Design and Automation Association, EDAA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 75, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1269843.1269858 What is a DOI?

ABSTRACT

Static Single Information (SSI) Form is a compiler intermediate representation that extends the more well-known Static Single Assignment (SSA) Form. In 2005, several research groups independently proved that interference graphs for procedures represented in SSA Form are chordal graphs. This paper performs a similar analysis concerning SSI Form, and proves that interference graphs are interval graphs. The primary consequences of this paper are threefold: (1) Linear scan register allocation for programs in SSI Form can be implemented in such a way that there are no lifetime holes, thereby sidestepping one of the drawbacks that plagued non-SSI implementations; (2) the k-colorable subgraph problem can be solved in polynomial-time for interval graphs, but remains NP-Complete for chordal graphs---to date, no register allocation algorithms have been implemented that solve the k-colorable subgraph problem directly; and (3) liveness analysis converges after a single iteration for programs represented in SSI Form.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
	2	Ananian, C. S. The Static Single Information Form. M.S. Thesis. Massachusetts Institute of Technology, Cambridge, MA, 1999.
	3	Belady, L. A. A study of replacement algorithms for a virtual storage computer. IBM Systems Journal, vol. 5, no. 2, 1966, 78--101.
	4	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.
	5	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.
	6	Deming Chen , Jason Cong, Register binding and port assignment for multiplexer optimization, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan
	7	Keith D. Cooper , Anshuman Dasgupta, Tailoring Graph-coloring Register Allocation For Runtime Compilation, Proceedings of the International Symposium on Code Generation and Optimization, p.39-49, March 26-29, 2006 [doi>10.1109/CGO.2006.35]
	8	Cooper, K. D., and Torczon, L. Engineering a Compiler, Morgan-Kaufmann, San Francisco, CA, USA, 2003.
	9	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]
	10	Martin Farach , Vincenzo Liberatore, On local register allocation, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.564-573, January 25-27, 1998, San Francisco, California, United States
	11	Frank, A. On chain and antichain families of a partially ordered set. J. Combin. Theory Ser. B., vol. 29, 1980, 176--184.
	12	Frank, A. Some polynomial algorithms for certain graphs and hypergraphs. In Proceedings of the Fifth British Combinatorial Conference, University of Aberdeen, (Canada, July 14--18, 1975); Nash-Williams, C, and Sheehan, J., Eds. Congressus Numerantium XV, 211--226.
	13	Fulkerson, D. R., and Gross, O. A. Incidence matrices and interval graphs. Pacific Journal of Mathematics, vol. 15, 1965, 838--855.
	14	Gavril, F. Algorithms for minimal coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput., vol. 1, no. 2, June, 1972, 108--187.
	15	Loukas Georgiadis , Robert E. Tarjan, Finding dominators revisited: extended abstract, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	16	Gilmore, P. C., and Hoffman, A. J. A characterization of comparability graphs and interval graphs. Canadian Journal of Mathematics, vol. 16, 1964, 539--548.
	17	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]
	18	Hack, S., Grund, D., and Goos, G. Register allocation for programs in SSA form. In Proc. of the 15<sup>th</sup> International Conf. on Compiler Construction (CC '06) (Vienna, Austria, March 30--31, 2006) 247--262.
	19	Lekkerkerker, C, and Boland, D. Representation of finite graphs by a set of intervals on the real line. Fund. Math., vol. 51, 1962, 45--61.
	20	Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
	21	Hanspeter Mössenböck , Michael Pfeiffer, Linear Scan Register Allocation in the Context of SSA Form and Register Constraints, Proceedings of the 11th International Conference on Compiler Construction, p.229-246, April 08-12, 2002
	22	Cindy Norris , Lori L. Pollock, Register allocation over the program dependence graph, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.266-277, June 20-24, 1994, Orlando, Florida, United States
	23	Pereira, F. M. Q., and Palsberg, J. Register allocation after classical SSA elimination is NP-Complete. In Proc. of the 9<sup>th</sup> International Conference on Foundations of Software Science and Computation Structure (FoSSaCS '06) (Vienna, Austria, March 25-31, 2006), 79--93.
	24	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]
	25	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
	26	B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73562]
	27	Sagonas, K. F., and Stenman, E. Experimental evaluation and improvements to linear scan register allocation. Software---Practice and Experience, vol. 35, no. 11, September, 2003, 1003--1034.
	28	Singer, J. Static Program Analysis Based on Virtual Register Renaming. Ph.D. Thesis, University of Cambridge, Cambridge, England, 2006.
	29	Omri Traub , Glenn Holloway , Michael D. Smith, Quality and speed in linear-scan register allocation, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.142-151, June 17-19, 1998, Montreal, Quebec, Canada
	30	Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]
	31	Christian Wimmer , Hanspeter Mössenböck, Optimized interval splitting in a linear scan register allocator, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1064998]
	32	Mihalis Yannakakis , Fanica Gavril, The maximum k-colorable subgraph problem for chordal graphs, Information Processing Letters, v.24 n.2, p.133-137, January 1987 [doi>10.1016/0020-0190(87)90107-4]