{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T10:50:38Z","timestamp":1779879038607,"version":"3.53.1"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2017,12,27]],"date-time":"2017-12-27T00:00:00Z","timestamp":1514332800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P23499- N23, S11407-N23"],"award-info":[{"award-number":["P23499- N23, S11407-N23"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["279307: Graph Games"],"award-info":[{"award-number":["279307: Graph Games"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>A fundamental algorithmic problem at the heart of static analysis is Dyck reachability. The input is a graph where the edges are labeled with different types of opening and closing parentheses, and the reachability information is computed via paths whose parentheses are properly matched. We present new results for Dyck reachability problems with applications to alias analysis and data-dependence analysis. Our main contributions, that include improved upper bounds as well as lower bounds that establish optimality guarantees, are as follows:<\/jats:p><jats:p>First, we consider Dyck reachability on bidirected graphs, which is the standard way of performing field-sensitive points-to analysis. Given a bidirected graph with<jats:italic>n<\/jats:italic>nodes and<jats:italic>m<\/jats:italic>edges, we present: (i)\u00a0an algorithm with worst-case running time<jats:italic>O<\/jats:italic>(<jats:italic>m<\/jats:italic>+<jats:italic>n<\/jats:italic>\u00b7 \u03b1(<jats:italic>n<\/jats:italic>)), where \u03b1(<jats:italic>n<\/jats:italic>) is the inverse Ackermann function, improving the previously known<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>) time bound; (ii)\u00a0a matching lower bound that shows that our algorithm is optimal wrt to worst-case complexity; and (iii)\u00a0an optimal average-case upper bound of<jats:italic>O<\/jats:italic>(<jats:italic>m<\/jats:italic>) time, improving the previously known<jats:italic>O<\/jats:italic>(<jats:italic>m<\/jats:italic>\u00b7 log<jats:italic>n<\/jats:italic>) bound.<\/jats:p><jats:p>Second, we consider the problem of context-sensitive data-dependence analysis, where the task is to obtain analysis summaries of library code in the presence of callbacks. Our algorithm preprocesses libraries in almost linear time, after which the contribution of the library in the complexity of the client analysis is only linear, and only wrt the number of call sites.<\/jats:p><jats:p>Third, we prove that combinatorial algorithms for Dyck reachability on general graphs with truly sub-cubic bounds cannot be obtained without obtaining sub-cubic combinatorial algorithms for Boolean Matrix Multiplication, which is a long-standing open problem. Thus we establish that the existing combinatorial algorithms for Dyck reachability are (conditionally) optimal for general graphs. We also show that the same hardness holds for graphs of constant treewidth.<\/jats:p><jats:p>Finally, we provide a prototype implementation of our algorithms for both alias analysis and data-dependence analysis. Our experimental evaluation demonstrates that the new algorithms significantly outperform all existing methods on the two problems, over real-world benchmarks.<\/jats:p>","DOI":"10.1145\/3158118","type":"journal-article","created":{"date-parts":[[2017,12,29]],"date-time":"2017-12-29T14:21:49Z","timestamp":1514557309000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Optimal Dyck reachability for data-dependence and alias analysis"],"prefix":"10.1145","volume":"2","author":[{"given":"Krishnendu","family":"Chatterjee","sequence":"first","affiliation":[{"name":"IST Austria, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bhavya","family":"Choudhary","sequence":"additional","affiliation":[{"name":"IIT Bombay, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Pavlogiannis","sequence":"additional","affiliation":[{"name":"IST Austria, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,12,27]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2003. T. J. Watson Libraries for Analysis (WALA). https:\/\/github.com. 2003. T. J. Watson Libraries for Analysis (WALA). https:\/\/github.com."},{"key":"e_1_2_2_2_1","unstructured":"2008. GitHub Home. https:\/\/github.com. 2008. GitHub Home. https:\/\/github.com."},{"key":"e_1_2_2_3_1","unstructured":"2008. SPECjvm2008 Benchmark Suit. http:\/\/www.spec.org\/jvm2008\/. 2008. SPECjvm2008 Benchmark Suit. http:\/\/www.spec.org\/jvm2008\/."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_2_2_5_1","volume-title":"Linear time algorithms for NP-hard problems restricted to partial k-trees . Discrete Appl Math","author":"Arnborg Stefan","year":"1989","unstructured":"Stefan Arnborg and Andrzej Proskurowski . 1989. Linear time algorithms for NP-hard problems restricted to partial k-trees . Discrete Appl Math ( 1989 ). Stefan Arnborg and Andrzej Proskurowski. 1989. Linear time algorithms for NP-hard problems restricted to partial k-trees . Discrete Appl Math (1989)."},{"key":"e_1_2_2_6_1","volume-title":"Software Change Impact Analysis","author":"Arnold Robert S.","unstructured":"Robert S. Arnold . 1996. Software Change Impact Analysis . IEEE Computer Society Press , Los Alamitos, CA, USA . Robert S. Arnold. 1996. Software Change Impact Analysis. IEEE Computer Society Press, Los Alamitos, CA, USA."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90001-0"},{"key":"e_1_2_2_8_1","volume-title":"Linear-time computation of optimal subgraphs of decomposable graphs. J Algorithm","author":"Bern M.W","year":"1987","unstructured":"M.W Bern , E.L Lawler , and A.L Wong . 1987. Linear-time computation of optimal subgraphs of decomposable graphs. J Algorithm ( 1987 ). M.W Bern, E.L Lawler, and A.L Wong. 1987. Linear-time computation of optimal subgraphs of decomposable graphs. J Algorithm (1987)."},{"key":"e_1_2_2_9_1","volume-title":"Nonserial Dynamic Programming","author":"Bertele Umberto","unstructured":"Umberto Bertele and Francesco Brioschi . 1972. Nonserial Dynamic Programming . Academic Press, Inc. , Orlando, FL, USA . Umberto Bertele and Francesco Brioschi. 1972. Nonserial Dynamic Programming. Academic Press, Inc., Orlando, FL, USA."},{"key":"e_1_2_2_10_1","volume-title":"Blackburn","author":"Stephen M.","year":"2006","unstructured":"Stephen M. et al. Blackburn . 2006 . The DaCapo Benchmarks: Java Benchmarking Development and Analysis. In OOPSLA. Stephen M. et al. Blackburn. 2006. The DaCapo Benchmarks: Java Benchmarking Development and Analysis. In OOPSLA."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2259051.2259052"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60084-1_80"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-19488-6_110"},{"key":"e_1_2_2_14_1","volume-title":"A partial k-arboretum of graphs with bounded treewidth. TCS","author":"Bodlaender Hans L.","year":"1998","unstructured":"Hans L. Bodlaender . 1998. A partial k-arboretum of graphs with bounded treewidth. TCS ( 1998 ). Hans L. Bodlaender. 1998. A partial k-arboretum of graphs with bounded treewidth. TCS (1998)."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837624"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676979"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21690-4_9"},{"key":"e_1_2_2_19_1","volume-title":"24th Annual European Symposium on Algorithms, ESA 2016","author":"Chatterjee Krishnendu","year":"2016","unstructured":"Krishnendu Chatterjee , Rasmus Ibsen-Jensen , and Andreas Pavlogiannis . 2016 b. Optimal Reachability and a Space-Time Tradeoff for Distance Queries in Constant-Treewidth Graphs . In 24th Annual European Symposium on Algorithms, ESA 2016 , August 22-24, 2016, Aarhus, Denmark. 28:1\u201328:17. Krishnendu Chatterjee, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. 2016b. Optimal Reachability and a Space-Time Tradeoff for Distance Queries in Constant-Treewidth Graphs. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark. 28:1\u201328:17."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328460"},{"key":"e_1_2_2_21_1","volume-title":"Zaroliagis","author":"Chaudhuri Shiva","year":"1995","unstructured":"Shiva Chaudhuri and Christos D . Zaroliagis . 1995 . Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms. Algorithmica ( 1995). Shiva Chaudhuri and Christos D. Zaroliagis. 1995. Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms. Algorithmica (1995)."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158639"},{"key":"e_1_2_2_23_1","unstructured":"T.H. Cormen C.E. Leiserson R.L. Rivest and C. Stein. 2001. Introduction To Algorithms. MIT Press. T.H. Cormen C.E. Leiserson R.L. Rivest and C. Stein. 2001. Introduction To Algorithms. MIT Press."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90061-2"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90014-5"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116878"},{"key":"e_1_2_2_27_1","volume-title":"Algorithm Engineering and Experiments","author":"Gustedt Jens","unstructured":"Jens Gustedt , Ole A. M\u00e6hle , and JanArne Telle . 2002. The Treewidth of Java Programs . In Algorithm Engineering and Experiments . Springer . Jens Gustedt, OleA. M\u00e6hle, and JanArne Telle. 2002. The Treewidth of Java Programs. In Algorithm Engineering and Experiments. Springer."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1997.614960"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/379605.379665"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/239912.239913"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/567532.567555"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/143095.143137"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/505241.505242"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_5"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2968444"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/186025.186041"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/360204.360208"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/215465.215466"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/271338.271343"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/345099.345137"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/195274.195287"},{"key":"e_1_2_2_45_1","series-title":"Series B","volume-title":"Graph minors. III. Planar tree-width. Journal of Combinatorial Theory","author":"Robertson Neil","year":"1984","unstructured":"Neil Robertson and P.D Seymour . 1984. Graph minors. III. Planar tree-width. Journal of Combinatorial Theory , Series B ( 1984 ). Neil Robertson and P.D Seymour. 1984. Graph minors. III. Planar tree-width. Journal of Combinatorial Theory, Series B (1984)."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2259016.2259050"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133255.1134027"},{"key":"e_1_2_2_48_1","doi-asserted-by":"crossref","unstructured":"Manu Sridharan Satish Chandra Julian Dolby Stephen J. Fink and Eran Yahav. 2013. Aliasing in Object-Oriented Programming. Chapter Alias Analysis for Object-oriented Programs 196\u2013232. Manu Sridharan Satish Chandra Julian Dolby Stephen J. Fink and Eran Yahav. 2013. Aliasing in Object-Oriented Programming. Chapter Alias Analysis for Object-oriented Programs 196\u2013232.","DOI":"10.1007\/978-3-642-36946-9_8"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094817"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676997"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90042-4"},{"key":"e_1_2_2_54_1","volume-title":"All Structured Programs Have Small Tree Width and Good Register Allocation. Information and Computation","author":"Thorup Mikkel","year":"1998","unstructured":"Mikkel Thorup . 1998. All Structured Programs Have Small Tree Width and Good Register Allocation. Information and Computation ( 1998 ). Mikkel Thorup. 1998. All Structured Programs Have Small Tree Width and Good Register Allocation. Information and Computation (1998)."},{"key":"e_1_2_2_55_1","volume-title":"CASCON \u201999","author":"Vall\u00e9e-Rai Raja","unstructured":"Raja Vall\u00e9e-Rai , Phong Co , Etienne Gagnon , Laurie Hendren , Patrick Lam , and Vijay Sundaresan . 1999. Soot - a Java bytecode optimization framework . In CASCON \u201999 . IBM Press . Raja Vall\u00e9e-Rai, Phong Co, Etienne Gagnon, Laurie Hendren, Patrick Lam, and Vijay Sundaresan. 1999. Soot - a Java bytecode optimization framework. In CASCON \u201999. IBM Press."},{"key":"e_1_2_2_57_1","doi-asserted-by":"crossref","unstructured":"Virginia Vassilevska Williams and Ryan Williams. 2010. Subcubic Equivalences between Path Matrix and Triangle Problems. In FOCS. 645\u2013654. Virginia Vassilevska Williams and Ryan Williams. 2010. Subcubic Equivalences between Path Matrix and Triangle Problems. In FOCS. 645\u2013654.","DOI":"10.1109\/FOCS.2010.67"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806617"},{"key":"e_1_2_2_59_1","volume-title":"Scaling CFL-Reachability-Based Points-To Analysis Using ContextSensitive Must-Not-Alias Analysis","author":"Xu Guoqing","unstructured":"Guoqing Xu , Atanas Rountev , and Manu Sridharan . 2009. Scaling CFL-Reachability-Based Points-To Analysis Using ContextSensitive Must-Not-Alias Analysis . Springer Berlin Heidelberg , 98\u2013122. Guoqing Xu, Atanas Rountev, and Manu Sridharan. 2009. Scaling CFL-Reachability-Based Points-To Analysis Using ContextSensitive Must-Not-Alias Analysis. Springer Berlin Heidelberg, 98\u2013122."},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2001420.2001440"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2001420.2001440"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298576"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214010"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00590-9_13"},{"key":"e_1_2_2_65_1","doi-asserted-by":"crossref","unstructured":"Qirun Zhang Michael R. Lyu Hao Yuan and Zhendong Su. 2013. Fast Algorithms for Dyck-CFL-reachability with Applications to Alias Analysis (PLDI). ACM. Qirun Zhang Michael R. Lyu Hao Yuan and Zhendong Su. 2013. Fast Algorithms for Dyck-CFL-reachability with Applications to Alias Analysis (PLDI). ACM.","DOI":"10.1145\/2491956.2462159"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009848"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328464"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158118","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3158118","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T09:15:51Z","timestamp":1751188551000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158118"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,27]]},"references-count":65,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1145\/3158118"],"URL":"https:\/\/doi.org\/10.1145\/3158118","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,27]]},"assertion":[{"value":"2017-12-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}