{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T12:59:02Z","timestamp":1790859542735,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642253171","type":"print"},{"value":"9783642253188","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-25318-8_13","type":"book-chapter","created":{"date-parts":[[2011,12,3]],"date-time":"2011-12-03T21:54:45Z","timestamp":1322949285000},"page":"137-154","source":"Crossref","is-referenced-by-count":7,"title":["A Non-iterative Data-Flow Algorithm for Computing Liveness Sets in Strict SSA Programs"],"prefix":"10.1007","author":[{"given":"Benoit","family":"Boissinot","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Florian","family":"Brandner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alain","family":"Darte","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Beno\u00eet Dupont","family":"de Dinechin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabrice","family":"Rastello","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"13_CR1","unstructured":"Aho, A.V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools. Addison-Wesley (2006)"},{"issue":"3","key":"13_CR2","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1145\/360018.360025","volume":"19","author":"F.E. Allen","year":"1976","unstructured":"Allen, F.E., Cocke, J.: A program data flow analysis procedure. Communications ACM\u00a019(3), 137 (1976)","journal-title":"Communications ACM"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Appel, A.W., Palsberg, J.: Modern Compiler Implementation in Java, 2nd edn. Cambridge University Press (2002)","DOI":"10.1017\/CBO9780511811432"},{"key":"13_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"M. Bender","year":"2000","unstructured":"Bender, M., Farach-Colton, M.: The LCA Problem Revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000)"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Boissinot, B., Darte, A., Dupont de Dinechin, B., Guillon, C., Rastello, F.: Revisiting out-of-SSA translation for correctness, code quality, and efficiency. In: Symp. on Code Generation and Optimization (CGO 2009), pp. 114\u2013125. ACM (2009)","DOI":"10.1109\/CGO.2009.19"},{"key":"13_CR6","unstructured":"Boissinot, B.: Towards an SSA-Based Compiler Back-End: Some Interesting Properties of SSA and its Extensions. PhD thesis, ENS-Lyon (September 2010)"},{"key":"13_CR7","unstructured":"Boissinot, B., Brandner, F., Darte, A., de Dinechin, B.D., Rastello, F.: Computing liveness sets for SSA-form programs. TR Inria RR-7503 (2011)"},{"key":"13_CR8","unstructured":"Boissinot, B., Brisk, P., Darte, A., Rastello, F.: SSI properties revisited. ACM Transactions on Embedded Computing Systems, Special Issue on Software and Compilers for Embedded Systems (2009) (to appear)"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Boissinot, B., Hack, S., Grund, D., de Dinechin, B.D., Rastello, F.: Fast liveness checking for SSA-programs. In: IEEE\/ACM Symposium on Code Generation and Optimization (CGO 2008), pp. 35\u201344. ACM (2008)","DOI":"10.1145\/1356058.1356064"},{"key":"13_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/978-3-540-72521-3_21","volume-title":"Languages and Compilers for Parallel Computing","author":"F. Bouchez","year":"2007","unstructured":"Bouchez, F., Darte, A., Guillon, C., Rastello, F.: Register Allocation: What does the NP-Completeness Proof of Chaitin et al. Really Prove? In: Alm\u00e1si, G.S., Ca\u015fcaval, C., Wu, P. (eds.) KSEM 2006. LNCS, vol.\u00a04382, pp. 283\u2013298. Springer, Heidelberg (2007)"},{"issue":"8","key":"13_CR11","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\u2014Practice and Experience\u00a028(8), 859\u2013881 (1998)","journal-title":"Software\u2014Practice and Experience"},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1145\/176454.176484","volume":"2","author":"P. Briggs","year":"1993","unstructured":"Briggs, P., Torczon, L.: An efficient representation for sparse sets. ACM Letters on Programming Languages and Systems (LOPLAS)\u00a02, 59\u201369 (1993)","journal-title":"ACM Letters on Programming Languages and Systems (LOPLAS)"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Carter, L., Ferrante, J., Thomborson, C.: Folklore confirmed: Reducible flow graphs are exponentially larger. In: ACM SIGACT\/SIGPLAN Symposium on Principles of Programming Languages (POPL 2003), pp. 106\u2013114. ACM (2003)","DOI":"10.1145\/604131.604141"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Click, C., Paleczny, M.: A simple graph-based intermediate representation. In: ACM Workshop on Intermediate Representations, pp. 35\u201349. ACM (1995)","DOI":"10.1145\/202529.202534"},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1109\/CIC.2006.22","volume-title":"15th International Conference on Computing (ICC 2006)","author":"K.D. Cooper","year":"2006","unstructured":"Cooper, K.D., Harvey, T.J., Kennedy, K.: An empirical study of iterative data-flow analysis. In: 15th International Conference on Computing (ICC 2006), pp. 266\u2013276. IEEE Computer Society, Washington, DC, USA (2006)"},{"issue":"4","key":"13_CR16","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., Zadek, 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"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"de Dinechin, B.D., de Ferri\u00e8re, F., Guillon, C., Stoutchinin, A.: Code generator optimizations for the ST120 DSP-MCU core. In: Compilers, Architecture, and Synthesis for Embedded Systems (CASES 2000), pp. 93\u2013102. ACM (2000)","DOI":"10.1145\/354880.354894"},{"key":"13_CR18","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)"},{"issue":"4","key":"13_CR19","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1145\/262004.262005","volume":"19","author":"P. Havlak","year":"1997","unstructured":"Havlak, P.: Nesting of reducible and irreducible loops. ACM Transactions on Programming Languages and Systems\u00a019(4), 557\u2013567 (1997)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"issue":"3","key":"13_CR20","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1145\/321832.321835","volume":"21","author":"M.S. Hecht","year":"1974","unstructured":"Hecht, M.S., Ullman, J.D.: Characterizations of reducible flow graphs. Journal of the ACM\u00a021(3), 367\u2013375 (1974)","journal-title":"Journal of the ACM"},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Hecht, M.S., Ullman, J.D.: Analysis of a simple algorithm for global data flow problems. In: 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL 1973), pp. 207\u2013217. ACM (1973)","DOI":"10.1145\/512927.512946"},{"key":"13_CR22","doi-asserted-by":"publisher","first-page":"1031","DOI":"10.1145\/267959.269971","volume":"19","author":"J. Janssen","year":"1997","unstructured":"Janssen, J., Corporaal, H.: Making graphs reducible with controlled node splitting. ACM Trans. on Programming Languages and Systems\u00a019, 1031\u20131052 (1997)","journal-title":"ACM Trans. on Programming Languages and Systems"},{"issue":"1","key":"13_CR23","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1145\/321921.321938","volume":"23","author":"J.B. Kam","year":"1976","unstructured":"Kam, J.B., Ullman, J.D.: Global data flow analysis and iterative algorithms. Journal of the ACM\u00a023(1), 158\u2013171 (1976)","journal-title":"Journal of the ACM"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Kildall, G.A.: A unified approach to global program optimization. In: Symposium on Principles of Programming Languages (POPL 1973), pp. 194\u2013206. ACM (1973)","DOI":"10.1145\/512927.512945"},{"key":"13_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1369396.1370017","volume":"5","author":"T. Kotzmann","year":"2008","unstructured":"Kotzmann, T., Wimmer, C., M\u00f6ssenb\u00f6ck, H., Rodriguez, T., Russell, K., Cox, D.: Design of the Java HotSpotTM client compiler for Java 6. ACM Transactions on Architecture and Code Optimization\u00a05, 1\u201332 (2008)","journal-title":"ACM Transactions on Architecture and Code Optimization"},{"key":"13_CR26","doi-asserted-by":"crossref","unstructured":"Leung, A., George, L.: Static single assignment form for machine code. In: ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 999), pp. 204\u2013214. ACM Press (1999)","DOI":"10.1145\/301618.301667"},{"key":"13_CR27","unstructured":"LibFirm: A library that provides an intermediate representation and optimisations for compilers, http:\/\/pp.info.uni-karlsruhe.de\/firm"},{"key":"13_CR28","unstructured":"LLVM: The LLVM compiler infrastructure, http:\/\/llvm.org"},{"key":"13_CR29","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1145\/581771.581774","volume":"49","author":"D. McAllester","year":"2002","unstructured":"McAllester, D.: On the complexity analysis of static analyses. Journal of the ACM\u00a049, 512\u2013537 (2002)","journal-title":"Journal of the ACM"},{"key":"13_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(88)90124-X","volume":"29","author":"M. Minoux","year":"1988","unstructured":"Minoux, M.: LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation. Inform. Processing Letters\u00a029, 1\u201312 (1988)","journal-title":"Inform. Processing Letters"},{"key":"13_CR31","unstructured":"Mono: NET development framework, http:\/\/www.mono-project.com"},{"key":"13_CR32","doi-asserted-by":"crossref","unstructured":"Nielson, F., Nielson, H.R., Hankin, C.: Principles of Program Analysis. Springer-Verlag New York, Inc. (1999)","DOI":"10.1007\/978-3-662-03811-6"},{"key":"13_CR33","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)"},{"issue":"2","key":"13_CR34","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1145\/316686.316687","volume":"21","author":"G. Ramalingam","year":"1999","unstructured":"Ramalingam, G.: Identifying loops in almost linear time. ACM Transactions on Programming Languages and Systems\u00a021(2), 175\u2013188 (1999)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"issue":"5","key":"13_CR35","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1145\/570886.570887","volume":"24","author":"G. Ramalingam","year":"2002","unstructured":"Ramalingam, G.: On loops, dominators, and dominance frontiers. ACM Transactions on Programming Languages and Systems\u00a024(5), 455\u2013490 (2002)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"issue":"3","key":"13_CR36","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/27632.27649","volume":"18","author":"B.G. Ryder","year":"1986","unstructured":"Ryder, B.G., Paull, M.C.: Elimination algorithms for data flow analysis. ACM Computing Surveys\u00a018(3), 277\u2013316 (1986)","journal-title":"ACM Computing Surveys"},{"key":"13_CR37","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)"},{"issue":"3","key":"13_CR38","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/S0022-0000(74)80049-8","volume":"9","author":"R.E. Tarjan","year":"1974","unstructured":"Tarjan, R.E.: Testing flow graph reducibility. Journal of Computer and System Sciences\u00a09(3), 355\u2013365 (1974)","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR39","doi-asserted-by":"crossref","unstructured":"Wimmer, C., Franz, M.: Linear scan register allocation on SSA form. In: Symp. on Code Generation and Optimization (CGO 2010), pp. 170\u2013179. ACM (2010)","DOI":"10.1145\/1772954.1772979"}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-25318-8_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T08:00:44Z","timestamp":1561017644000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-25318-8_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642253171","9783642253188"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-25318-8_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}