{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:40Z","timestamp":1750308820526,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2011,12,1]],"date-time":"2011-12-01T00:00:00Z","timestamp":1322697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p>\n            In this article we provide an interprocedural analysis of linear two-variable equalities. The novel algorithm has a worst-case complexity of \ud835\udcaa(\n            <jats:italic>n<\/jats:italic>\n            \u22c5\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            ), where\n            <jats:italic>k<\/jats:italic>\n            is the number of variables and\n            <jats:italic>n<\/jats:italic>\n            is the program size. Thus, it saves a factor of\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            in comparison to a related algorithm based on full linear algebra. We also indicate how the practical runtime can be further reduced significantly. The analysis can be applied, for example, for register coalescing, for identifying local variables and thus for interprocedurally observing stack pointer modifications as well as for an analysis of array index expressions, when analyzing low-level code.\n          <\/jats:p>","DOI":"10.1145\/2049706.2049710","type":"journal-article","created":{"date-parts":[[2011,12,30]],"date-time":"2011-12-30T17:01:45Z","timestamp":1325264505000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast interprocedural linear two-variable equalities"],"prefix":"10.1145","volume":"33","author":[{"given":"Andrea","family":"Flexeder","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen, Garching, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"M\u00fcller-olm","sequence":"additional","affiliation":[{"name":"Westf\u00e4lische Wilhelms-Universit\u00e4t M\u00fcnster, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Petter","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen, Garching, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Helmut","family":"Seidl","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen, Garching, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,1,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73561"},{"key":"e_1_2_1_2_1","first-page":"304","article-title":"Propagating differences: An efficient new fixpoint algorithm for distributive constraint systems","volume":"5","author":"Fecht C.","year":"1998","unstructured":"Fecht , C. and Seidl , H. 1998 . Propagating differences: An efficient new fixpoint algorithm for distributive constraint systems . Nord. J. Comput. 5 , 4, 304 -- 329 . Fecht, C. and Seidl, H. 1998. Propagating differences: An efficient new fixpoint algorithm for distributive constraint systems. Nord. J. Comput. 5, 4, 304--329.","journal-title":"Nord. J. Comput."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/229542.229546"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 11th International Static Analysis Symposium (SAS). Lecture Notes in Computer Science","volume":"3148","author":"Gulwani S.","unstructured":"Gulwani , S. and Necula , G. C . 2004. A polynomial-time algorithm for global value numbering . In Proceedings of the 11th International Static Analysis Symposium (SAS). Lecture Notes in Computer Science , vol. 3148 , Springer, Berlin, 212--227. Gulwani, S. and Necula, G. C. 2004. A polynomial-time algorithm for global value numbering. In Proceedings of the 11th International Static Analysis Symposium (SAS). Lecture Notes in Computer Science, vol. 3148, Springer, Berlin, 212--227."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Compiler Construction Conference (CC). Lecture Notes in Computer Science","volume":"541","author":"Knoop J.","unstructured":"Knoop , J. and Steffen , B . 1992. The interprocedural coincidence theorem . In Proceedings of the Compiler Construction Conference (CC). Lecture Notes in Computer Science , vol. 541 , Springer, Berlin, 125--140. Knoop, J. and Steffen, B. 1992. The interprocedural coincidence theorem. In Proceedings of the Compiler Construction Conference (CC). Lecture Notes in Computer Science, vol. 541, Springer, Berlin, 125--140."},{"key":"e_1_2_1_7_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 2d Symposium on Programs as Data Objects (PADO II)","author":"Min\u00e9 A.","unstructured":"Min\u00e9 , A. 2001a. A new numerical abstract domain based on difference bound matrices . In Proceedings of the 2d Symposium on Programs as Data Objects (PADO II) . Lecture Notes in Computer Science , vol. 2053 , Springer , Berlin , 155--172. Min\u00e9, A. 2001a. A new numerical abstract domain based on difference bound matrices. In Proceedings of the 2d Symposium on Programs as Data Objects (PADO II). Lecture Notes in Computer Science, vol. 2053, Springer, Berlin, 155--172."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/832308.837141"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30579-8_6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/964001.964029"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31987-0_4"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1275497.1275504"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 17th European Symposium on Programming (ESOP). Lecture Notes in Computer Science","volume":"4960","author":"M\u00fcller-Olm M.","unstructured":"M\u00fcller-Olm , M. and Seidl , H . 2008. Upper adjoints for fast inter-procedural variable equalities . In Proceedings of the 17th European Symposium on Programming (ESOP). Lecture Notes in Computer Science , vol. 4960 , Springer, Berlin. M\u00fcller-Olm, M. and Seidl, H. 2008. Upper adjoints for fast inter-procedural variable equalities. In Proceedings of the 17th European Symposium on Programming (ESOP). Lecture Notes in Computer Science, vol. 4960, Springer, Berlin."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(96)00072-2"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30579-8_2"},{"key":"e_1_2_1_16_1","unstructured":"Sharir M. and Pnueli A. 1981. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Application Prentice Hall Englewood Cliffs NJ 189--234.  Sharir M. and Pnueli A. 1981. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Application Prentice Hall Englewood Cliffs NJ 189--234."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Conference on Logic Based Program Development and Transformation (LOPSTR). Lecture Notes in Computer Science","volume":"2664","author":"Simon A.","unstructured":"Simon , A. , King , A. , and Howe , J. M . 2002. Two variables per linear inequality as an abstract domain . In Proceedings of the Conference on Logic Based Program Development and Transformation (LOPSTR). Lecture Notes in Computer Science , vol. 2664 , Springer, Berlin, 71--89. Simon, A., King, A., and Howe, J. M. 2002. Two variables per linear inequality as an abstract domain. In Proceedings of the Conference on Logic Based Program Development and Transformation (LOPSTR). Lecture Notes in Computer Science, vol. 2664, Springer, Berlin, 71--89."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 3rd European Symposium on Programming (ESOP). Lecture Notes in Computer Science","volume":"432","author":"Steffen B.","unstructured":"Steffen , B. , Knoop , J. , and R\u00fcthing , O . 1990. The value flow graph: A program representation for optimal program transformations . In Proceedings of the 3rd European Symposium on Programming (ESOP). Lecture Notes in Computer Science , vol. 432 , Springer, Berlin, 389--405. Steffen, B., Knoop, J., and R\u00fcthing, O. 1990. The value flow graph: A program representation for optimal program transformations. In Proceedings of the 3rd European Symposium on Programming (ESOP). Lecture Notes in Computer Science, vol. 432, Springer, Berlin, 389--405."},{"key":"e_1_2_1_19_1","unstructured":"Votum. 2010. http:\/\/www2.in.tum.de\/votum.  Votum. 2010. http:\/\/www2.in.tum.de\/votum."},{"key":"e_1_2_1_20_1","unstructured":"Zucker S. and Karhi K. 1995. System V application binary interface: PowerPC processor supplement. http:\/\/refspecs.freestandards.org\/elf\/elfspec_ppc.pdf.  Zucker S. and Karhi K. 1995. System V application binary interface: PowerPC processor supplement. http:\/\/refspecs.freestandards.org\/elf\/elfspec_ppc.pdf."}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2049706.2049710","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2049706.2049710","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:41Z","timestamp":1750278401000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2049706.2049710"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1145\/2049706.2049710"],"URL":"https:\/\/doi.org\/10.1145\/2049706.2049710","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2011,12]]},"assertion":[{"value":"2010-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}