{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T12:56:25Z","timestamp":1725627385118},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540725206"},{"type":"electronic","value":"9783540725213"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-72521-3_21","type":"book-chapter","created":{"date-parts":[[2007,6,10]],"date-time":"2007-06-10T12:53:29Z","timestamp":1181480009000},"page":"283-298","source":"Crossref","is-referenced-by-count":20,"title":["Register Allocation: What Does the NP-Completeness Proof of Chaitin et al. Really Prove? Or Revisiting Register Allocation: Why and How"],"prefix":"10.1007","author":[{"given":"Florent","family":"Bouchez","sequence":"first","affiliation":[]},{"given":"Alain","family":"Darte","sequence":"additional","affiliation":[]},{"given":"Christophe","family":"Guillon","sequence":"additional","affiliation":[]},{"given":"Fabrice","family":"Rastello","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","first-page":"243","volume-title":"Proceedings of PLDI\u201901","author":"A.W. Appel","year":"2001","unstructured":"Appel, A.W., George, L.: Optimal spilling for CISC machines with few registers. In: Proceedings of PLDI\u201901, Snowbird, Utah, USA, June 2001, pp. 243\u2013253. ACM Press, Snowbird (2001)"},{"key":"21_CR2","unstructured":"Bouchez, F., et al.: Register allocation and spill complexity under SSA. Technical Report RR2005-33, LIP, ENS-Lyon, France, (Aug. 2005)"},{"key":"21_CR3","unstructured":"Bouchez, F., et al.: On the complexity of register coalescing. Technical Report RR2006-15, LIP, ENS-Lyon, France (Apr. 2006)"},{"issue":"3","key":"21_CR4","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1145\/177492.177575","volume":"16","author":"P. Briggs","year":"1994","unstructured":"Briggs, P., Cooper, K., Torczon, L.: Improvements to graph coloring register allocation. ACM Transactions on Programming Languages and Systems\u00a016(3), 428\u2013455 (1994)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"issue":"8","key":"21_CR5","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1002\/(SICI)1097-024X(19980710)28:8<859::AID-SPE188>3.0.CO;2-8","volume":"28","author":"P. Briggs","year":"1998","unstructured":"Briggs, P., et al.: Practical improvements to the construction and destruction of static single assignment form. Software: Practice and Experience\u00a028(8), 859\u2013881 (1998)","journal-title":"Software: Practice and Experience"},{"key":"21_CR6","unstructured":"Brisk, P., et al.: Polynomial time graph coloring register allocation. In: 14th International Workshop on Logic and Synthesis, June (2005)"},{"key":"21_CR7","first-page":"25","volume-title":"Proc. of PLDI\u201902","author":"Z. Budimli\u0107","year":"2002","unstructured":"Budimli\u0107, Z., et al.: Fast copy coalescing and live range identification. In: Proc. of PLDI\u201902, pp. 25\u201332. ACM Press, New York (2002)"},{"issue":"6","key":"21_CR8","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1145\/872726.806984","volume":"17","author":"G.J. Chaitin","year":"1982","unstructured":"Chaitin, G.J.: Register allocation & spilling via graph coloring. SIGPLAN Notices, Proceedings of Compiler Construction (CC\u201982)\u00a017(6), 98\u2013105 (1982)","journal-title":"SIGPLAN Notices, Proceedings of Compiler Construction (CC\u201982)"},{"key":"21_CR9","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0096-0551(81)90048-5","volume":"6","author":"G.J. Chaitin","year":"1981","unstructured":"Chaitin, G.J., et al.: Register allocation via coloring. Computer Languages\u00a06, 47\u201357 (1981)","journal-title":"Computer Languages"},{"key":"21_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/BFb0026430","volume-title":"Compiler Construction","author":"K.D. Cooper","year":"1998","unstructured":"Cooper, K.D., Simpson, L.T.: Live range splitting in a graph coloring register allocator. In: Koskimies, K. (ed.) CC 1998 and ETAPS 1998. LNCS, vol.\u00a01383, pp. 174\u2013187. Springer, Heidelberg (1998)"},{"key":"21_CR11","first-page":"19","volume-title":"Proceedings of the 1987 International Conference on Parallel Processing","author":"R. Cytron","year":"1987","unstructured":"Cytron, R., Ferrante, J.: What\u2019s in a name? Or the value of renaming for parallelism detection and storage allocation. In: Proceedings of the 1987 International Conference on Parallel Processing, Aug. 1987, pp. 19\u201327. IEEE Computer Society Press, Los Alamitos (1987)"},{"issue":"4","key":"21_CR12","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1145\/115372.115320","volume":"13","author":"R. Cytron","year":"1991","unstructured":"Cytron, R., et al.: Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems\u00a013(4), 451\u2013490 (1991)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"21_CR13","unstructured":"Darte, A., Rastello, F.: Personal communication with Beno\u00eet Dupont de Dinechin, Jeanne Ferrante, and Christophe Guillon (2002)"},{"issue":"1","key":"21_CR14","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jagm.2000.1095","volume":"37","author":"M. Farach-Colton","year":"2000","unstructured":"Farach-Colton, M., Liberatore, V.: On local register allocation. Journal of Algorithms\u00a037(1), 37\u201365 (2000)","journal-title":"Journal of Algorithms"},{"key":"21_CR15","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)"},{"issue":"2","key":"21_CR16","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M.R. Garey","year":"1980","unstructured":"Garey, M.R., et al.: The complexity of coloring circular arcs and chords. SIAM J. of Algebr. Discrete Methods\u00a01(2), 216\u2013227 (1980)","journal-title":"SIAM J. of Algebr. Discrete Methods"},{"issue":"3","key":"21_CR17","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1145\/229542.229546","volume":"18","author":"L. George","year":"1996","unstructured":"George, L., Appel, A.W.: Iterated register coalescing. ACM Transactions on Programming Languages and Systems\u00a018(3), 300\u2013324 (1996)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"21_CR18","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"21_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_20","volume-title":"Compiler Construction","author":"S. Hack","year":"2006","unstructured":"Hack, S., Grund, D., Goos, G.: Register allocation for programs in SSA-form. In: Mycroft, A., Zeller, A. (eds.) CC 2006 and ETAPS 2006. LNCS, vol.\u00a03923, Springer, Heidelberg (2006)"},{"key":"21_CR20","unstructured":"Knobe, K., Zadeck, K.: Register allocation using control trees. Technical Report No. CS-92-13, Brown University (1992)"},{"key":"21_CR21","first-page":"204","volume-title":"Proceedings of PLDI\u201999","author":"A. Leung","year":"1999","unstructured":"Leung, A., George, L.: Static single assignment form for machine code. In: Proceedings of PLDI\u201999, pp. 204\u2013214. ACM Press, New York (1999)"},{"key":"21_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/978-3-540-49051-7_10","volume-title":"Compiler Construction","author":"V. Liberatore","year":"1999","unstructured":"Liberatore, V., Farach-Colton, M., Kremer, U.: Evaluation of algorithms for local register allocation. In: J\u00e4hnichen, S. (ed.) CC 1999 and ETAPS 1999. LNCS, vol.\u00a01575, pp. 137\u2013152. Springer, Heidelberg (1999)"},{"issue":"3","key":"21_CR23","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1145\/353926.353929","volume":"22","author":"G.-Y. Lueh","year":"2000","unstructured":"Lueh, G.-Y., Gross, T., Adl-Tabatabai, A.-R.: Fusion-based register allocation. ACM Transactions on Programming Languages and Systems\u00a022(3), 431\u2013470 (2000)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"21_CR24","first-page":"196","volume-title":"Proceedings of PACT\u201998","author":"J. Park","year":"1998","unstructured":"Park, J., Moon, S.-M.: Optimistic register coalescing. In: Proceedings of PACT\u201998, pp. 196\u2013204. IEEE Computer Society Press, Los Alamitos (1998)"},{"key":"21_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/11575467_21","volume-title":"Programming Languages and Systems","author":"F.M.Q. Pereira","year":"2005","unstructured":"Pereira, F.M.Q., Palsberg, J.: Register allocation via coloring of chordal graphs. In: Yi, K. (ed.) APLAS 2005. LNCS, vol.\u00a03780, pp. 315\u2013329. Springer, Heidelberg (2005)"},{"key":"21_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11690634_6","volume-title":"Foundations of Software Science and Computation Structures","author":"F.M.Q. Pereira","year":"2006","unstructured":"Pereira, F.M.Q., Palsberg, J.: Register allocation after classical SSA elimination is NP-complete. In: Aceto, L., Ing\u00f3lfsd\u00f3ttir, A. (eds.) FOSSACS 2006 and ETAPS 2006. LNCS, vol.\u00a03921, Springer, Heidelberg (2006)"},{"key":"21_CR27","first-page":"265","volume-title":"Proceedings of CGO\u201904","author":"F. Rastello","year":"2004","unstructured":"Rastello, F., de Ferri\u00e8re, F., Guillon, C.: Optimizing translation out of SSA using renaming constraints. In: Proceedings of CGO\u201904, pp. 265\u2013278. IEEE Computer Society Press, Los Alamitos (2004)"},{"key":"21_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/3-540-48294-6_13","volume-title":"Static Analysis","author":"V.C. Sreedhar","year":"1999","unstructured":"Sreedhar, V.C., et al.: Translating out of static single assignment form. In: Cortesi, A., Fil\u00e9, G. (eds.) SAS 1999. LNCS, vol.\u00a01694, pp. 194\u2013210. Springer, Heidelberg (1999)"}],"container-title":["Lecture Notes in Computer Science","Languages and Compilers for Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72521-3_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T09:56:44Z","timestamp":1558259804000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72521-3_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540725206","9783540725213"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72521-3_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}