{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T10:49:11Z","timestamp":1747133351918,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":42,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819606016"},{"type":"electronic","value":"9789819606023"}],"license":[{"start":{"date-parts":[[2024,11,25]],"date-time":"2024-11-25T00:00:00Z","timestamp":1732492800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,11,25]],"date-time":"2024-11-25T00:00:00Z","timestamp":1732492800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-981-96-0602-3_21","type":"book-chapter","created":{"date-parts":[[2024,11,24]],"date-time":"2024-11-24T03:46:47Z","timestamp":1732420007000},"page":"382-398","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Faster Lifetime-Optimal Speculative Partial Redundancy Elimination for\u00a0Goto-Free Programs"],"prefix":"10.1007","author":[{"given":"Xuran","family":"Cai","sequence":"first","affiliation":[]},{"given":"Amir","family":"Goharshady","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,11,25]]},"reference":[{"key":"21_CR1","unstructured":"Ahmadi, A., Chatterjee, K., Goharshady, A.K., Meggendorfer, T., Safavi, R., Zikelic, \u0110.: Algorithms and hardness results for computing cores of Markov chains. In: FSTTCS, pp. 29:1\u201329:20 (2022)"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Ahmadi, A., Daliri, M., Goharshady, A.K., Pavlogiannis, A.: Efficient approximations for cache-conscious data placement. In: PLDI, pp. 857\u2013871 (2022)","DOI":"10.1145\/3519939.3523436"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"Asadi, A., Chatterjee, K., Goharshady, A.K., Mohammadi, K., Pavlogiannis, A.: Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth. In: ATVA, vol. 12302, pp. 253\u2013270 (2020)","DOI":"10.1007\/978-3-030-59152-6_14"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Barakbayeva, T., Farokhnia, S., Goharshady, A.K., Gufler, M., Novozhilov, S.: Pixiu: optimal block production revenues on Cardano. In: Blockchain (2024)","DOI":"10.1109\/Blockchain62396.2024.00072"},{"key":"21_CR5","unstructured":"Bodlaender, H.L., Gustedt, J., Telle, J.A.: Linear-time register allocation for a fixed number of registers. In: SODA, pp. 574\u2013583 (1998)"},{"key":"21_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-24841-5_6","volume-title":"Reliable Software Technologies - Ada-Europe 2004","author":"B Burgstaller","year":"2004","unstructured":"Burgstaller, B., Blieberger, J., Scholz, B.: On the tree width of ADA programs. In: Llamos\u00ed, A., Strohmeier, A. (eds.) Ada-Europe 2004. LNCS, vol. 3063, pp. 78\u201390. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24841-5_6"},{"key":"21_CR7","unstructured":"Cai, Q., Xue, J.: Optimal and efficient speculation-based partial redundancy elimination, pp. 91\u2013102. CGO (2003)"},{"key":"21_CR8","unstructured":"Cai, X., Goharshady, A.K., Hitarth, S., Lam, C.K.: Faster register allocation via grammatical decompositions of control-flow graphs (2024). https:\/\/hal.science\/hal-04672403"},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Goharshady, A.K., Goharshady, E.K.: The treewidth of smart contracts. In: SAC, pp. 400\u2013408. ACM (2019)","DOI":"10.1145\/3297280.3297322"},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Goharshady, A.K., Goyal, P., Ibsen-Jensen, R., Pavlogiannis, A.: Faster algorithms for dynamic algebraic queries in basic RSMs with constant treewidth. ACM Trans. Program. Lang. Syst. 41(4), 23:1\u201323:46 (2019)","DOI":"10.1145\/3363525"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Goharshady, A.K., Ibsen-Jensen, R., Pavlogiannis, A.: Algorithms for algebraic path properties in concurrent systems of constant treewidth components. In: POPL, pp. 733\u2013747 (2016)","DOI":"10.1145\/2837614.2837624"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Goharshady, A.K., Ibsen-Jensen, R., Pavlogiannis, A.: Optimal and perfectly parallel algorithms for on-demand data-flow analysis. In: ESOP, pp. 112\u2013140 (2020)","DOI":"10.1007\/978-3-030-44914-8_5"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Goharshady, A.K., Okati, N., Pavlogiannis, A.: Efficient parameterized algorithms for data packing. Proc. ACM Program. Lang. 3(POPL), 53:1\u201353:28 (2019)","DOI":"10.1145\/3290366"},{"key":"21_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-319-68167-2_4","volume-title":"Automated Technology for Verification and Analysis","author":"K Chatterjee","year":"2017","unstructured":"Chatterjee, K., Goharshady, A.K., Pavlogiannis, A.: JTDec: a tool for tree decompositions in soot. In: D\u2019Souza, D., Narayan Kumar, K. (eds.) ATVA 2017. LNCS, vol. 10482, pp. 59\u201366. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-68167-2_4"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Ibsen-Jensen, R., Goharshady, A.K., Pavlogiannis, A.: Algorithms for algebraic path properties in concurrent systems of constant treewidth components. ACM Trans. Program. Lang. Syst. 40(3), 9:1\u20139:43 (2018)","DOI":"10.1145\/3210257"},{"key":"21_CR16","doi-asserted-by":"publisher","unstructured":"Chatterjee, K., Lacki, J.: Faster algorithms for Markov decision processes with low treewidth. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 543\u2013558. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39799-8_36","DOI":"10.1007\/978-3-642-39799-8_36"},{"key":"21_CR17","doi-asserted-by":"publisher","unstructured":"Cocke, J.: Global common subexpression elimination, pp. 20\u201324 (1970). https:\/\/doi.org\/10.1145\/390013.808480","DOI":"10.1145\/390013.808480"},{"key":"21_CR18","unstructured":"Conrado, G.K., Goharshady, A.K., Hudec, P., Li, P., Motwani, H.J.: Faster treewidth-based approximations for Wiener index. In: SEA, vol.\u00a0301, pp. 6:1\u20136:19 (2024)"},{"issue":"OOPSLA2","key":"21_CR19","doi-asserted-by":"publisher","first-page":"1993","DOI":"10.1145\/3622868","volume":"7","author":"GK Conrado","year":"2023","unstructured":"Conrado, G.K., Goharshady, A.K., Kochekov, K., Tsai, Y.C., Zaher, A.K.: Exploiting the sparseness of control-flow and call graphs for efficient and on-demand algebraic program analysis. Proc. ACM Program. Lang. 7(OOPSLA2), 1993\u20132022 (2023)","journal-title":"Proc. ACM Program. Lang."},{"issue":"OOPSLA2","key":"21_CR20","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1145\/3622807","volume":"7","author":"GK Conrado","year":"2023","unstructured":"Conrado, G.K., Goharshady, A.K., Lam, C.K.: The bounded pathwidth of control-flow graphs. Proc. ACM Program. Lang. 7(OOPSLA2), 292\u2013317 (2023)","journal-title":"Proc. ACM Program. Lang."},{"key":"21_CR21","unstructured":"Dutta, S.: Anatomy of a compiler: a retargetable ANSI-C compiler. Circ. Cellar 121(5) (2000)"},{"key":"21_CR22","unstructured":"Dutta, S., Drotos, D., Vigor, K., et\u00a0al.: Small device C compiler (2003). http:\/\/sdcc.sourceforge.net\/"},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"Ferrara, A., Pan, G., Vardi, M.Y.: Treewidth in verification: local vs. global. In: LPAR, vol. 3835, pp. 489\u2013503 (2005)","DOI":"10.1007\/11591191_34"},{"key":"21_CR24","unstructured":"Goharshady, A.K.: Parameterized and Algebro-geometric Advances in Static Program Analysis. Ph.D. thesis, Institute of Science and Technology Austria, Klosterneuburg, Austria (2020)"},{"key":"21_CR25","doi-asserted-by":"crossref","unstructured":"Goharshady, A.K., Lam, C.K., Parreaux, L.: Fast and optimal extraction for sparse equality graphs. In: OOPSLA (2024)","DOI":"10.1145\/3689801"},{"key":"21_CR26","doi-asserted-by":"publisher","first-page":"106665","DOI":"10.1016\/j.ress.2019.106665","volume":"193","author":"AK Goharshady","year":"2020","unstructured":"Goharshady, A.K., Mohammadi, F.: An efficient algorithm for computing network reliability in small treewidth. Reliab. Eng. Syst. Saf. 193, 106665 (2020)","journal-title":"Reliab. Eng. Syst. Saf."},{"key":"21_CR27","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-031-24950-1_9","volume-title":"VMCAI 2023","author":"AK Goharshady","year":"2023","unstructured":"Goharshady, A.K., Zaher, A.K.: Efficient interprocedural data-flow analysis using treedepth and treewidth. In: Dragoi, C., Emmi, M., Wang, J. (eds.) VMCAI 2023. LNCS, vol. 13881, pp. 177\u2013202. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-24950-1_9"},{"key":"21_CR28","doi-asserted-by":"crossref","unstructured":"Gupta, R., Berson, D., Fang, J.: Path profile guided partial redundancy elimination using speculation. In: Proceedings of the 1998 International Conference on Computer Languages (Cat. No.98CB36225), pp. 230\u2013239 (1998)","DOI":"10.1109\/ICCL.1998.674173"},{"key":"21_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/3-540-45643-0_7","volume-title":"Algorithm Engineering and Experiments","author":"J Gustedt","year":"2002","unstructured":"Gustedt, J., M\u00e6hle, O.A., Telle, J.A.: The treewidth of java programs. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol. 2409, pp. 86\u201397. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45643-0_7"},{"key":"21_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/11860990_22","volume-title":"Modular Programming Languages","author":"RN Horspool","year":"2006","unstructured":"Horspool, R.N., Pereira, D.J., Scholz, B.: Fast profile-based partial redundancy elimination. In: Lightfoot, D.E., Szyperski, C. (eds.) JMLC 2006. LNCS, vol. 4228, pp. 362\u2013376. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11860990_22"},{"key":"21_CR31","unstructured":"Jaiyen, B., Liu, J.: Implementing profile-guided speculative code motion in LLVM (2012)"},{"key":"21_CR32","doi-asserted-by":"crossref","unstructured":"Karger, D.R., Stein, C.: An \u00d5(n2) algorithm for minimum cuts. In: STOC, pp. 757\u2013765 (1993)","DOI":"10.1145\/167088.167281"},{"key":"21_CR33","doi-asserted-by":"crossref","unstructured":"Knoop, J., R\u00fcthing, O., Steffen, B.: Lazy code motion. In: PLDI, pp. 224\u2013234 (1992)","DOI":"10.1145\/143095.143136"},{"key":"21_CR34","doi-asserted-by":"crossref","unstructured":"Krause, P.K.: lospre in linear time. In: SCOPES, pp. 35\u201341 (2021)","DOI":"10.1145\/3493229.3493304"},{"key":"21_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-37051-9_1","volume-title":"Compiler Construction","author":"PK Krause","year":"2013","unstructured":"Krause, P.K.: Optimal register allocation in polynomial time. In: Jhala, R., De Bosschere, K. (eds.) CC 2013. LNCS, vol. 7791, pp. 1\u201320. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-37051-9_1"},{"key":"21_CR36","doi-asserted-by":"crossref","unstructured":"Meybodi, M.A., Goharshady, A.K., Hooshmandasl, M.R., Shakiba, A.: Optimal mining: maximizing Bitcoin miners\u2019 revenues from transaction fees. In: Blockchain, pp. 266\u2013273 (2022)","DOI":"10.1109\/Blockchain55522.2022.00044"},{"key":"21_CR37","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1145\/359060.359069","volume":"22","author":"E Morel","year":"1979","unstructured":"Morel, E., Renvoise, C.: Global optimization by suppression of partial redundancies. Commun. ACM 22, 96\u2013103 (1979)","journal-title":"Commun. ACM"},{"key":"21_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/978-3-540-45069-6_7","volume-title":"Computer Aided Verification","author":"J Obdr\u017e\u00e1lek","year":"2003","unstructured":"Obdr\u017e\u00e1lek, J.: Fast mu-calculus model checking when tree-width is bounded. In: Hunt, W.A., Somenzi, F. (eds.) CAV 2003. LNCS, vol. 2725, pp. 80\u201392. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45069-6_7"},{"key":"21_CR39","unstructured":"Pereira, D.J.: Isothermality: making speculative optimizations affordable (2007). https:\/\/api.semanticscholar.org\/CorpusID:64227807"},{"key":"21_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1007\/978-3-030-53288-8_30","volume-title":"Computer Aided Verification","author":"S Sankaranarayanan","year":"2020","unstructured":"Sankaranarayanan, S.: Reachability analysis using message passing over tree decompositions. In: Lahiri, S.K., Wang, C. (eds.) CAV 2020. LNCS, vol. 12224, pp. 604\u2013628. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-53288-8_30"},{"issue":"2","key":"21_CR41","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1006\/inco.1997.2697","volume":"142","author":"M Thorup","year":"1998","unstructured":"Thorup, M.: All structured programs have small tree width and good register allocation. Inf. Comput. 142(2), 159\u2013181 (1998)","journal-title":"Inf. Comput."},{"key":"21_CR42","doi-asserted-by":"crossref","unstructured":"Xue, J., Cai, Q.: A lifetime optimal algorithm for speculative PRE. ACM Trans. Archit. Code Optim, 115\u2013155 (2006)","DOI":"10.1145\/1138035.1138036"}],"container-title":["Lecture Notes in Computer Science","Dependable Software Engineering. Theories, Tools, and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-0602-3_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,24]],"date-time":"2024-11-24T04:20:33Z","timestamp":1732422033000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-0602-3_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,25]]},"ISBN":["9789819606016","9789819606023"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-0602-3_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,11,25]]},"assertion":[{"value":"25 November 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SETTA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Dependable Software Engineering: Theories, Tools, and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hong Kong","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 November 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 November 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"setta2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/setta2024.cs.cityu.edu.hk\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}