{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:47:57Z","timestamp":1725544077990},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540330455"},{"type":"electronic","value":"9783540330462"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11690634_6","type":"book-chapter","created":{"date-parts":[[2006,3,28]],"date-time":"2006-03-28T09:15:28Z","timestamp":1143537328000},"page":"79-93","source":"Crossref","is-referenced-by-count":13,"title":["Register Allocation After Classical SSA Elimination is NP-Complete"],"prefix":"10.1007","author":[{"given":"Fernando Magno Quint\u00e3o","family":"Pereira","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Palsberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511811432","volume-title":"Modern Compiler Implementation in Java","author":"A.W. Appel","year":"2002","unstructured":"Appel, A.W., Palsberg, J.: Modern Compiler Implementation in Java, 2nd edn. Cambridge University Press, Cambridge (2002)","edition":"2"},{"key":"6_CR2","first-page":"267","volume-title":"Discrete Mathematics","author":"M. Bir\u00f3","year":"1992","unstructured":"Bir\u00f3, M., Hujter, M.: Precoloring extension. I: interval graphs. In: Discrete Mathematics, pp. 267\u2013279. ACM Press, New York (1992); Special volume (part 1) to mark the centennial of Julius Petersen\u2019s \u201cDie theorie der regularen graphs\u201d"},{"key":"6_CR3","unstructured":"Bodlaender, H., Gustedt, J., Telle, J.A.: Linear-time register allocation for a fixed number of registers. In: SIAM Symposium on Discrete Algorithms, pp. 574\u2013583 (1998)"},{"key":"6_CR4","unstructured":"Bouchez, F.: Allocation de registres et vidage en m\u00e9moire. Master\u2019s thesis, ENS Lyon (2005)"},{"issue":"8","key":"6_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., Cooper, K.D., Harvey, T.J., Simpson, L.T.: 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":"6_CR6","volume-title":"14th International Workshop on Logic and Synthesis","author":"P. Brisk","year":"2005","unstructured":"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)"},{"key":"6_CR7","first-page":"25","volume-title":"International Conference on Programming Languages Design and Implementation","author":"Z. Budimlic","year":"2002","unstructured":"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\u201332. ACM Press, New York (2002)"},{"key":"6_CR8","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., Auslander, M.A., Chandra, A.K., Cocke, J., Hopkins, M.E., Markstein, P.W.: Register allocation via coloring. Computer Languages\u00a06, 47\u201357 (1981)","journal-title":"Computer Languages"},{"issue":"4","key":"6_CR9","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1145\/115372.115320","volume":"13","author":"R. Cytron","year":"1991","unstructured":"Cytron, R., Ferrante, J., Rosen, B.K., Wegman, M.N., Zadeck, F.K.: 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"},{"issue":"2","key":"6_CR10","first-page":"81","volume":"1","author":"F. Ferri\u00e9re de","year":"2004","unstructured":"de Ferri\u00e9re, F., Guillon, C., Rastello, F.: Optimizing the translation out-of-SSA with renaming constraints. ST Journal of Research Processor Architecture and Compilation for Embedded Systems\u00a01(2), 81\u201396 (2004)","journal-title":"ST Journal of Research Processor Architecture and Compilation for Embedded Systems"},{"key":"6_CR11","first-page":"564","volume-title":"9th ACM-SIAM symposium on Discrete Algorithms","author":"M. Farach","year":"1998","unstructured":"Farach, M., Liberatore, V.: On local register allocation. In: 9th ACM-SIAM symposium on Discrete Algorithms, pp. 564\u2013573. ACM Press, New York (1998)"},{"issue":"2","key":"6_CR12","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M.R. Garey","year":"1980","unstructured":"Garey, M.R., Johnson, D.S., Miller, G.L., Papadimitriou, C.H.: The complexity of coloring circular arcs and chords. SIAM J. Algebraic Discrete Methods\u00a01(2), 216\u2013227 (1980)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"3","key":"6_CR13","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. Theoretical Computer Science\u00a01(3), 193\u2013267 (1976)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"6_CR14","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SICOMP\u00a01(2), 180\u2013187 (1972)","journal-title":"SICOMP"},{"issue":"16","key":"6_CR15","first-page":"46","volume":"B","author":"F. Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees of a tree are exactly the chordal graphs. Journal of Combinatoric\u00a0B(16), 46\u201356 (1974)","journal-title":"Journal of Combinatoric"},{"key":"6_CR16","unstructured":"Hack, S.: Interference graphs of programs in SSA-form. Technical Report ISSN 1432-7864, Universitat Karlsruhe (2005)"},{"key":"6_CR17","volume-title":"15th International Conference on Compiler Construction","author":"S. Hack","year":"2006","unstructured":"Hack, S., Grund, D., Goos, G.: Register allocation for programs in SSA-form. In: 15th International Conference on Compiler Construction, Springer, Heidelberg (2006)"},{"key":"6_CR18","first-page":"204","volume-title":"Conference on Programming Language Design and Implementation","author":"A. Leung","year":"1999","unstructured":"Leung, A., George, L.: Static single assignment form for machine code. In: Conference on Programming Language Design and Implementation, pp. 204\u2013214. ACM Press, New York (1999)"},{"key":"6_CR19","unstructured":"Marx, D.: A short proof of the NP-completeness of circular arc coloring (2003)"},{"key":"6_CR20","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":"6_CR21","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/73560.73562","volume-title":"ACM SIGPLAN-SIGACT symposium on Principles of Programming languages","author":"B.K. Rosen","year":"1988","unstructured":"Rosen, B.K., Zadeck, F.K., Wegman, M.N.: Global value numbers and redundant computations. In: ACM SIGPLAN-SIGACT symposium on Principles of Programming languages, pp. 12\u201327. ACM Press, New York (1988)"},{"key":"6_CR22","first-page":"182","volume-title":"5th annual ACM symposium on Theory of computing","author":"R. Sethi","year":"1973","unstructured":"Sethi, R.: Complete register allocation problems. In: 5th annual ACM symposium on Theory of computing, pp. 182\u2013195. ACM Press, New York (1973)"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11690634_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,12]],"date-time":"2019-03-12T01:20:57Z","timestamp":1552353657000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11690634_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540330455","9783540330462"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11690634_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}