{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T17:59:52Z","timestamp":1791395992718,"version":"4.3.3"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642007217","type":"print"},{"value":"9783642007224","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-00722-4_12","type":"book-chapter","created":{"date-parts":[[2009,3,27]],"date-time":"2009-03-27T01:00:16Z","timestamp":1238115616000},"page":"158-173","source":"Crossref","is-referenced-by-count":12,"title":["SSA Elimination after Register Allocation"],"prefix":"10.1007","author":[{"given":"Fernando Magno Quint\u00e3o","family":"Pereira","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jens","family":"Palsberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"4","key":"12_CR1","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/278283.278285","volume":"33","author":"A.W. Appel","year":"1998","unstructured":"Appel, A.W.: SSA is functional programming. SIGPLAN Notices\u00a033(4), 17\u201320 (1998)","journal-title":"SIGPLAN Notices"},{"key":"12_CR2","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":"12_CR3","unstructured":"Bouchez, F.: Allocation de registres et vidage en m\u00e9moire. Master\u2019s thesis, ENS Lyon (October 2005)"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Bouchez, F., Darte, A., Guillon, C., Rastello, F.: Register allocation: What does the NP-completeness proof of chaitin et al. really prove? or revisiting register allocation: Why and how. In: 19th International Workshop on Languages and Compilers for Parallel Computing, pp. 283\u2013298 (2006)","DOI":"10.1007\/978-3-540-72521-3_21"},{"issue":"8","key":"12_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":"12_CR6","unstructured":"Brisk, P.: Advances in Static Single Assignment Form and Register Allocation. PhD thesis, UCLA, University of California, Los Angeles (2006)"},{"issue":"5","key":"12_CR7","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1109\/TCAD.2006.870409","volume":"25","author":"P. Brisk","year":"2006","unstructured":"Brisk, P., Dabiri, F., Jafari, R., Sarrafzadeh, M.: Optimal register sharing for high-level synthesis of SSA form programs. IEEE Trans. on CAD of Integrated Circuits and Systems\u00a025(5), 772\u2013779 (2006)","journal-title":"IEEE Trans. on CAD of Integrated Circuits and Systems"},{"key":"12_CR8","first-page":"25","volume-title":"PLDI, ACM SIGPLAN Conference on Programming Language 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: PLDI, ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 25\u201332. ACM Press, New York (2002)"},{"issue":"4","key":"12_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. TOPLAS\u00a013(4), 451\u2013490 (1991)","journal-title":"TOPLAS"},{"issue":"2","key":"12_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":"12_CR11","unstructured":"Gough, B.J.: An Introduction to GCC, 1st edn. Network Theory Ltd. (2005)"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Hack, S., Goos, G.: Copy coalescing by graph recoloring. In: PLDI, ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 227\u2013237 (2008)","DOI":"10.1145\/1375581.1375610"},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","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. LNCS, vol.\u00a03923, pp. 247\u2013262. Springer, Heidelberg (2006)"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Koes, D.R., Goldstein, S.C.: A global progressive register allocator. In: PLDI, ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 204\u2013215 (2006)","DOI":"10.1145\/1133981.1134006"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Lattner, C., Adve, V.: LLVM: A compilation framework for lifelong program analysis & transformation. In: CGO, International Symposium on Code Generation and Optimization, pp. 75\u201388 (2004)","DOI":"10.1109\/CGO.2004.1281665"},{"issue":"6","key":"12_CR16","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1109\/32.24735","volume":"15","author":"C. May","year":"1989","unstructured":"May, C.: The parallel assignment problem redefined. IEEE Trans. Software Eng.\u00a015(6), 821\u2013824 (1989)","journal-title":"IEEE Trans. Software Eng."},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"Nandivada, V.K., Pereira, F., Palsberg, J.: A framework for end-to-end verification and evaluation of register allocators. In: Proceedings of SAS, International Static Analysis Symposium, Kongens Lyngby, Denmark, August 2007, pp. 153\u2013169 (2007)","DOI":"10.1007\/978-3-540-74061-2_10"},{"key":"12_CR18","unstructured":"Pereira, F.M.Q.: Register Allocation by Puzzle Solving. PhD thesis, UCLA, University of California, Los Angeles (2008)"},{"key":"12_CR19","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":"12_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"79","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. LNCS, vol.\u00a03921, pp. 79\u201393. Springer, Heidelberg (2006)"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"Pereira, F.M.Q., Palsberg, J.: Register allocation by puzzle solving. In: PLDI, ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 216\u2013226 (2008)","DOI":"10.1145\/1379022.1375609"},{"issue":"5","key":"12_CR22","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1145\/330249.330250","volume":"21","author":"M. Poletto","year":"1999","unstructured":"Poletto, M., Sarkar, V.: Linear scan register allocation. Transactions on Programming Languages and Systems (TOPLAS)\u00a021(5), 895\u2013913 (1999)","journal-title":"Transactions on Programming Languages and Systems (TOPLAS)"},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Rideau, L., Serpette, B.P., Leroy, X.: Tilting at windmills with Coq: formal verification of a compilation algorithm for parallel moves (2008)","DOI":"10.1007\/s10817-007-9096-8"},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/73560.73562","volume-title":"POPL, 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: POPL, ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 12\u201327. ACM Press, New York (1988)"},{"key":"12_CR25","doi-asserted-by":"publisher","first-page":"1003","DOI":"10.1002\/spe.533","volume":"33","author":"K. Sagonas","year":"2003","unstructured":"Sagonas, K., Stenman, E.: Experimental evaluation and improvements to linear scan register allocation. Software, Practice and Experience\u00a033, 1003\u20131034 (2003)","journal-title":"Software, Practice and Experience"},{"key":"12_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/978-3-540-71229-9_10","volume-title":"Compiler Construction","author":"V. Sarkar","year":"2007","unstructured":"Sarkar, V., Barik, R.: Extended linear scan: An alternate foundation for global register allocation. In: Krishnamurthi, S., Odersky, M. (eds.) CC 2007. LNCS, vol.\u00a04420, pp. 141\u2013155. Springer, Heidelberg (2007)"},{"key":"12_CR27","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1145\/800125.804049","volume-title":"STOC, 5th Annual ACM Symposium on Theory of Computing","author":"R. Sethi","year":"1973","unstructured":"Sethi, R.: Complete register allocation problems. In: STOC, 5th Annual ACM Symposium on Theory of Computing, pp. 182\u2013195. ACM Press, New York (1973)"},{"key":"12_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., Ju, R.D.-C., Gillies, D.M., Santhanam, V.: 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)"},{"key":"12_CR29","unstructured":"JVM Team. The java HotSpot virtual machine. Technical Report Technical White Paper, Sun Microsystems (2006)"},{"key":"12_CR30","unstructured":"The\u00a0Jikes Team. Jikes RVM home page (2007), http:\/\/jikesrvm.sourceforge.net\/"},{"key":"12_CR31","doi-asserted-by":"crossref","unstructured":"Traub, O., Holloway, G.H., Smith, M.D.: Quality and speed in linear-scan register allocation. In: PLDI, ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 142\u2013151 (1998)","DOI":"10.1145\/277650.277714"},{"issue":"12","key":"12_CR32","doi-asserted-by":"publisher","first-page":"1175","DOI":"10.1002\/spe.4380131208","volume":"13","author":"P.H. Welch","year":"1983","unstructured":"Welch, P.H.: Parallel assignment revisited. Software Practice and Experience\u00a013(12), 1175\u20131180 (1983)","journal-title":"Software Practice and Experience"}],"container-title":["Lecture Notes in Computer Science","Compiler Construction"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-00722-4_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T18:23:57Z","timestamp":1739039037000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-00722-4_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642007217","9783642007224"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-00722-4_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}