{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T11:48:31Z","timestamp":1769341711990,"version":"3.49.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T00:00:00Z","timestamp":1718841600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/creativecommons.org\/licenses\/by-sa\/4.0\/"}],"funder":[{"name":"Australian Research Grants","award":["DP210101348 and FT220100391"],"award-info":[{"award-number":["DP210101348 and FT220100391"]}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Generous Aspire Gift Grant"],"award-info":[{"award-number":["Generous Aspire Gift Grant"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2114627 and 2237440"],"award-info":[{"award-number":["2114627 and 2237440"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["N66001-21-C-4024"],"award-info":[{"award-number":["N66001-21-C-4024"]}],"id":[{"id":"10.13039\/100000185","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":[[2024,6,20]]},"abstract":"<jats:p>\n            Context-free language reachability (CFL-reachability) is a prominent model for formulating program analysis problems. Almost all CFL-reachability algorithms are based on the Reps-Horwitz-Sagiv (RHS) tabulation. In essence, the RHS tabulation, based on normalized context-free grammars, is similar to the CYK algorithm for CFL-parsing. Consider a normalized rule\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mrow>\n                  <mml:mi>S<\/mml:mi>\n                  <mml:mo>:<\/mml:mo>\n                  <mml:mo>:<\/mml:mo>\n                  <mml:mo>=<\/mml:mo>\n                  <mml:mi>A<\/mml:mi>\n                  <mml:mo>\u00a0<\/mml:mo>\n                  <mml:mi>B<\/mml:mi>\n                <\/mml:mrow>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            and a CFL-reachability problem instance of computing\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            -edges in the input graph. The RHS tabulation obtains all summary edges (\n            <jats:italic toggle=\"yes\">i.e., S<\/jats:italic>\n            -,\n            <jats:italic toggle=\"yes\">A-,<\/jats:italic>\n            and\n            <jats:italic toggle=\"yes\">B<\/jats:italic>\n            -edges) based on the grammar rules. However, many\n            <jats:italic toggle=\"yes\">A<\/jats:italic>\n            - and\n            <jats:italic toggle=\"yes\">B<\/jats:italic>\n            -edges are wasted because only a subset of those edges eventually contributes to generating\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            -edges in the input graph.\n          <\/jats:p>\n          <jats:p>\n            This paper proposes a new tabulation strategy for speeding up CFL-reachability by eliminating wasted and unnecessary summary edges. We particularly focus on recursive nonterminals. Our key technical insight is that the wasted edge generations and insertions caused by recursive nonterminals can be avoided by modifying the parse trees either statically (by transforming the grammar) or dynamically (using a specialized online CFL-reachability solver). For example, if a recursive nonterminal\n            <jats:italic toggle=\"yes\">B<\/jats:italic>\n            , generated by a rule\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mrow>\n                  <mml:mi>B<\/mml:mi>\n                  <mml:mo>:<\/mml:mo>\n                  <mml:mo>:<\/mml:mo>\n                  <mml:mo>=<\/mml:mo>\n                  <mml:mi>B<\/mml:mi>\n                  <mml:mi>X<\/mml:mi>\n                <\/mml:mrow>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            , appears on the right-hand side of a rule\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mrow>\n                  <mml:mi>S<\/mml:mi>\n                  <mml:mo>:<\/mml:mo>\n                  <mml:mo>:<\/mml:mo>\n                  <mml:mo>=<\/mml:mo>\n                  <mml:mi>A<\/mml:mi>\n                  <mml:mi>B<\/mml:mi>\n                <\/mml:mrow>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            , we can make\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            recursive (by introducing a new rule\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mrow>\n                  <mml:mi>S<\/mml:mi>\n                  <mml:mo>:<\/mml:mo>\n                  <mml:mo>:<\/mml:mo>\n                  <mml:mo>=<\/mml:mo>\n                  <mml:mi>S<\/mml:mi>\n                  <mml:mi>X<\/mml:mi>\n                <\/mml:mrow>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            ) and eliminate the original recursive rule (\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mrow>\n                  <mml:mi>B<\/mml:mi>\n                  <mml:mo>:<\/mml:mo>\n                  <mml:mo>:<\/mml:mo>\n                  <mml:mo>=<\/mml:mo>\n                  <mml:mi>B<\/mml:mi>\n                  <mml:mi>X<\/mml:mi>\n                <\/mml:mrow>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            ). Due to the rule\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mrow>\n                  <mml:mi>S<\/mml:mi>\n                  <mml:mo>:<\/mml:mo>\n                  <mml:mo>:<\/mml:mo>\n                  <mml:mo>=<\/mml:mo>\n                  <mml:mi>S<\/mml:mi>\n                  <mml:mi>X<\/mml:mi>\n                <\/mml:mrow>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            , the shapes of the parse trees associated with the left-hand-side nonterminal\n            <jats:italic toggle=\"yes\">S<\/jats:italic>\n            become more \u201cskewed\u201d. Thus, we name our approach\n            <jats:italic toggle=\"yes\">skewed tabulation<\/jats:italic>\n            for CFL-reachability.\n          <\/jats:p>\n          <jats:p>Skewed tabulation can significantly improve the scalability of CFL-reachability by reducing wasted and unnecessary summary edges. We have implemented skewed tabulation and applied the corresponding CFL- reachability algorithm to an alias analysis, a value-flow analysis, and a taint analysis. Our extensive evaluation based on SPEC 2017 benchmarks yields promising results. For the three client analyses, CFL-reachability based on skewed tabulation can achieve 3.34\u00d7, 1.13\u00d7 and 2.05\u00d7 speedup over the state-of-the-art RHS-tabulation- based CFL-reachability solver and consume 60.05%, 20.38% and 63.06% less memory, respectively. Furthermore, the cost of grammar transformation for skewed tabulation is negligible, typically taking less than one second.<\/jats:p>","DOI":"10.1145\/3656451","type":"journal-article","created":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T16:27:20Z","timestamp":1718900840000},"page":"1830-1853","update-policy":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Context-Free Language Reachability via Skewed Tabulation"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0002-4484-8172","authenticated-orcid":false,"given":"Yuxiang","family":"Lei","sequence":"first","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0009-0002-9659-7990","authenticated-orcid":false,"given":"Camille","family":"Bossut","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0002-9510-6574","authenticated-orcid":false,"given":"Yulei","family":"Sui","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0001-5367-9377","authenticated-orcid":false,"given":"Qirun","family":"Zhang","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,20]]},"reference":[{"key":"e_1_3_2_2_1","unstructured":"Alfred V. Aho Monica S. Lam Ravi Sethi and Jeffrey D. Ullman .2006. Compilers: Principles Techniques and Tools (2nd Edition). Addison-Wesley Longman Publishing Co. Inc. USA."},{"key":"e_1_3_2_3_1","unstructured":"Alfred V. Aho Ravi Sethi and Jeffrey D. Ullman. 1986. Compilers: Principles Techniques and Tools.Addison-Wesley."},{"key":"e_1_3_2_4_1","first-page":"1","article-title":"Magic Sets and Other Strange Ways to Implement Logic Programs","author":"Bancilhon Frangois","year":"1986","unstructured":"Frangois Bancilhon, David Maier, Yehoshua Sagiv, and Jeffrey D. Ullman. 1986. Magic Sets and Other Strange Ways to Implement Logic Programs. In Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (PODS). 1-15.","journal-title":"In Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (PODS)."},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/28659.28689"},{"key":"e_1_3_2_6_1","first-page":"243","article-title":"Strictly declarative specification of sophisticated points-to analyses","author":"Bravenboer Martin","year":"2009","unstructured":"Martin Bravenboer and Yannis Smaragdakis. 2009. Strictly declarative specification of sophisticated points-to analyses. In Proceedings of the 24th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2009). 243-262.","journal-title":"In Proceedings of the 24th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2009)."},{"key":"e_1_3_2_7_1","doi-asserted-by":"crossref","unstructured":"Krishnendu Chatterjee Bhavya Choudhary and Andreas Pavlogiannis. 2018. Optimal Dyck reachability for data-dependence and alias analysis. Proc. ACM Program. Lang. 2 POPL (2018) 30:1-30:30.","DOI":"10.1145\/3158118"},{"key":"e_1_3_2_8_1","doi-asserted-by":"crossref","unstructured":"Krishnendu Chatterjee Amir Kafshdar Goharshady Prateesh Goyal Rasmus Ibsen-Jensen and Andreas Pavlogiannis. 2019. Faster Algorithms for Dynamic Algebraic Queries in Basic RSMs with Constant Treewidth. ACM Trans. Program. Lang. Syst. 41 4 (2019) 23:1-23:46.","DOI":"10.1145\/3363525"},{"key":"e_1_3_2_9_1","first-page":"59","article-title":"Subcubic algorithms for recursive state machines","author":"Chaudhuri Swarat","year":"2008","unstructured":"Swarat Chaudhuri. 2008. Subcubic algorithms for recursive state machines. In Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2008, San Francisco, California, USA, January 7-12, 2008. ACM, 159-169.","journal-title":"In Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2008, San Francisco, California, USA, January 7-12, 2008. ACM, 1"},{"key":"e_1_3_2_10_1","doi-asserted-by":"crossref","unstructured":"Edmund M Clarke Masahiro Fujita Sreeranga P Rajan T Reps Subash Shankar and Tim Teitelbaum. 1999. ware description languages. In AdvancedResearch Working Conference on Correct Hardware Design and Verification Methods. Springer 298-313.","DOI":"10.1007\/3-540-48153-2_22"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","unstructured":"Sheila A. Greibach. 1966. The Unsolvability of the Recognition of Linear Context-Free Languages. J. ACM 13 4 (1966). https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1145\/321356.321365 10.1145\/321356.321365","DOI":"10.1145\/321356.321365"},{"key":"e_1_3_2_12_1","unstructured":"Jelle Hellings. 2014. Conjunctive Context-Free Path Queries. In Proc. 17th International Conference on Database Theory (ICDT) Greece March 24-28 2014. 119-130."},{"key":"e_1_3_2_13_1","doi-asserted-by":"crossref","unstructured":"Nicholas Hollingum and Bernhard Scholz. 2015. Towards a Scalable Framework for Context-Free Language Reachability. In Compiler Construction - 24th International Conference (CC 2015). 193-211.","DOI":"10.1007\/978-3-662-46663-6_10"},{"key":"e_1_3_2_14_1","doi-asserted-by":"crossref","unstructured":"John Kodumal and Alexander Aiken. 2004. The set constraint\/CFL reachability connection in practice. In PLDI. 207-218.","DOI":"10.1145\/996841.996867"},{"key":"e_1_3_2_15_1","unstructured":"Martin Lange and Hans Leifi. 2009. To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm. Informatica Didact. 8 (2009)."},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","unstructured":"Yuxiang Lei Camille Bossut Yulei Sui and Qirun Zhang. 2024. Artifact of \u201cContext-Free Language Reachability via Skewed Tabulation\u201d. Zenodo. https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.5281\/zenodo.10892936 10.5281\/zenodo.10892936","DOI":"10.5281\/zenodo.10892936"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","unstructured":"Yuxiang Lei Yulei Sui Shuo Ding and Qirun Zhang. 2022a. Artifact of \u201cTaming Transitive Redundancy for Context-Free Language ReachabilityZenodo. https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.5281\/zenodo.7066401 10.5281\/zenodo.7066401","DOI":"10.5281\/zenodo.7066401"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563343"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","unstructured":"Yuanbo Li Qirun Zhang and Thomas Reps. 2020. Fast graph simplification for interleaved Dyck-reachability. In PLDI \u201820: 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation. https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1145\/3385412.3386021 10.1145\/3385412.3386021.","DOI":"10.1145\/3385412.3386021"},{"key":"e_1_3_2_20_1","first-page":"61","article-title":"An Incremental Points-to Analysis with CFL-Reachability","volume":"7791","author":"Lu Yi","year":"2013","unstructured":"Yi Lu, Lei Shang, Xinwei Xie, and Jingling Xue. 2013. An Incremental Points-to Analysis with CFL-Reachability. In Compiler Construction - 22nd International Conference, CC 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings (Lecture Notes in Computer Science, Vol. 7791). Springer, 61-81.","journal-title":"In Compiler Construction - 22nd International Conference, CC 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings (Lecture Notes in Computer Science,"},{"key":"e_1_3_2_21_1","doi-asserted-by":"crossref","unstructured":"David A. McAllester. 2002. On the complexity analysis of static analyses. J. ACM 49 4 (2002) 512-537.","DOI":"10.1145\/581771.581774"},{"key":"e_1_3_2_22_1","doi-asserted-by":"crossref","unstructured":"David Melski and Thomas W. Reps. 2000. Interconvertibility of a class of set constraints and context-free-language reachability. Theor. Comput. Sci. 248 1-2 (2000) 29-98.","DOI":"10.1016\/S0304-3975(00)00049-9"},{"key":"e_1_3_2_23_1","doi-asserted-by":"crossref","unstructured":"AnaL. Milanova. 2020. FlowCFL: generalized type-based reachability analysis: graph reduction and equivalence ofCFL-based and type-based reachability. Proc. ACMProgram. Lang. 4 OOPSLA (2020) 178:1-178:29.","DOI":"10.1145\/3428246"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","unstructured":"Nomair A Naeem and Ondrej Lhotak. 2008. Typestate-like analysis of multiple interacting objects. ACM Sigplan Notices 43 10 (2008) 347-366. https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1145\/1449764.1449792 10.1145\/1449764.1449792","DOI":"10.1145\/1449764.1449792"},{"key":"e_1_3_2_25_1","doi-asserted-by":"crossref","unstructured":"Nomair A. Naeem Ondrej Lhotak and Jonathan Rodriguez. 2010. Practical Extensions to the IFDS Algorithm. In Compiler Construction 19th International Conference CC 2010. 124-144.","DOI":"10.1007\/978-3-642-11970-5_8"},{"key":"e_1_3_2_26_1","doi-asserted-by":"crossref","unstructured":"Andreas Pavlogiannis. 2022. CFL\/Dyck Reachability: An Algorithmic Perspective. ACM SIGLOGNews 9 4 (2022) 5-25.","DOI":"10.1145\/3583660.3583664"},{"key":"e_1_3_2_27_1","doi-asserted-by":"crossref","unstructured":"Jakob Rehof and Manuel F\u00e4hndrich. 2001. Type-base flow analysis: from polymorphic subtyping to CFL-reachability. In Conference Record ofPOPL 2001: The 28th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 54-66.","DOI":"10.1145\/360204.360208"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","unstructured":"Thomas Reps Susan Horwitz and Mooly Sagiv. 1995. Precise interprocedural dataflow analysis via graph reachability. In Pro ceedings of the 22nd ACM SIGPLAN-SIGACT symp osium on Principles of programming languages. 49-61. https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1145\/199448.199462 10.1145\/199448.199462","DOI":"10.1145\/199448.199462"},{"key":"e_1_3_2_29_1","doi-asserted-by":"crossref","unstructured":"Thomas W. Reps. 1998. Program analysis viagraph reachability. Inf. Softw. Technol. 40 11-12 (1998) 701-726.","DOI":"10.1016\/S0950-5849(98)00093-7"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349310"},{"key":"e_1_3_2_31_1","first-page":"196","article-title":"On fast large-scale program analysis in Datalog","author":"Scholz Bernhard","year":"2016","unstructured":"Bernhard Scholz, Herbert Jordan, Pavle Subotic, and Till Westmann. 2016. On fast large-scale program analysis in Datalog.In Proceedings of the 25th International Conference on Compiler Construction (CC). 196-206.","journal-title":"In Proceedings of the 25th International Conference on Compiler Construction (CC)."},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","unstructured":"C. Shi H. Li Y. Sui J. Lu L. Li and J. Xue. 2023. Two Birds with One Stone: Multi-Derivation for Fast Context-Free Language Reachability Analysis. In 2023 38th IEEE\/ACM International Conference on Automated Software Engineering (ASE). IEEE Computer Society Los Alamitos CA USA 624-636. https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1109\/ASE56229.2023.00118 10.1109\/ASE56229.2023.00118","DOI":"10.1109\/ASE56229.2023.00118"},{"key":"e_1_3_2_33_1","first-page":"265","article-title":"SVF: interprocedural static value-flow analysis in LLVM","author":"Sui Yulei","year":"2016","unstructured":"Yulei Sui and Jingling Xue. 2016. SVF: interprocedural static value-flow analysis in LLVM. In Proceedings of the 25th International Conference on Compiler Construction, CC 2016, Barcelona, Spain, March 12-18, 2016. ACM, 265-266.","journal-title":"In Proceedings of the 25th International Conference on Compiler Construction, CC 2016, Barcelona, Spain, March 12-18, 2016. ACM,"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","unstructured":"Yulei Sui Ding Ye and Jingling Xue. 2014. Detecting memory leaks statically with full-sparse value-flow analysis. IEEE Transactions on Software Engineering 40 2 (2014) 107-122. https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1109\/TSE.2014.2302311 10.1109\/TSE.2014.2302311","DOI":"10.1109\/TSE.2014.2302311"},{"key":"e_1_3_2_35_1","first-page":"83","article-title":"Summary-Based Context-Sensitive Data-Dependence Analysis in Presence of Callbacks","author":"Tang Hao","year":"2015","unstructured":"Hao Tang, Xiaoyin Wang, Lingming Zhang, Bing Xie, Lu Zhang, and Hong Mei. 2015. Summary-Based Context-Sensitive Data-Dependence Analysis in Presence of Callbacks. In Proceedings of the 42ndAnnual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015,. 83-95.","journal-title":"In Proceedings of the 42ndAnnual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015,."},{"key":"e_1_3_2_36_1","doi-asserted-by":"crossref","unstructured":"Robert Endre Tarjan . 1972. Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1 2 (1972) 146-160.","DOI":"10.1137\/0201010"},{"key":"e_1_3_2_37_1","first-page":"140","article-title":"Bottom-Up Beats Top-Down for Datalog","author":"Ullman Jeffrey D.","year":"1989","unstructured":"Jeffrey D. Ullman. 1989. Bottom-Up Beats Top-Down for Datalog. In Proceedings of theEighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania, USA. ACM Press, 140-149.","journal-title":"In Proceedings of theEighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania, USA. ACM Press,"},{"key":"e_1_3_2_38_1","first-page":"389","article-title":"Graspan: A Single-machine Disk-based Graph System for Interprocedural Static Analyses of Large-scale Systems Code","author":"Wang Kai","year":"2017","unstructured":"Kai Wang, Aftab Hussain, Zhiqiang Zuo, Guoqing Xu, and Ardalan Amiri Sani. 2017. Graspan: A Single-machine Disk-based Graph System for Interprocedural Static Analyses of Large-scale Systems Code. In Proceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). 389-404.","journal-title":"In Proceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)."},{"key":"e_1_3_2_39_1","doi-asserted-by":"crossref","unstructured":"David ScottWarren. 1992. Memoing forLogic Programs. Commun. ACM 35 3 (1992) 93-111.","DOI":"10.1145\/131295.131299"},{"key":"e_1_3_2_40_1","doi-asserted-by":"crossref","unstructured":"John Whaley Dzintars Avots Michael Carbin and Monica S. Lam. 2005. Using Datalog with Binary Decision Diagrams for Program Analysis. In Programming Languages and Systems Third Asian Symposium (APLAS). 97-118.","DOI":"10.1007\/11575467_8"},{"key":"e_1_3_2_41_1","first-page":"230","article-title":"Graph-Theoretic Methods in Database Theory","author":"Yannakakis Mihalis","year":"1990","unstructured":"Mihalis Yannakakis. 1990. Graph-Theoretic Methods in Database Theory. In Proceedings of theNinth ACM SIGACT-SIGMOD- SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee, USA. 230-242.","journal-title":"In Proceedings of theNinth ACM SIGACT-SIGMOD- SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee, USA."},{"key":"e_1_3_2_42_1","doi-asserted-by":"crossref","unstructured":"Daniel H. Younger. 1967. Recognition and Parsing of Context-Free Languages in Time n3. Inf. Control. 10 2 (1967) 189-208.","DOI":"10.1016\/S0019-9958(67)80007-X"},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009848"},{"key":"e_1_3_2_44_1","first-page":"829","article-title":"Efficient subcubic alias analysis for C","author":"Zhang Qirun","year":"2014","unstructured":"Qirun Zhang, Xiao Xiao, Charles Zhang, Hao Yuan, and Zhendong Su. 2014. Efficient subcubic alias analysis for C. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications (OOPSLA 2014). 829-845.","journal-title":"In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications (OOPSLA 2014)."},{"key":"e_1_3_2_45_1","first-page":"197","article-title":"Demand-driven alias analysis for C","author":"Zheng Xin","year":"2008","unstructured":"Xin Zheng and Radu Rugina. 2008. Demand-driven alias analysis for C. In Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2008, San Francisco, California, USA, January 7-12, 2008. ACM, 197-208.","journal-title":"In Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2008, San Francisco, California, USA, January 7-12, 2008. ACM,"},{"key":"e_1_3_2_46_1","doi-asserted-by":"crossref","unstructured":"Zhiqiang Zuo Kai Wang Aftab Hussain Ardalan Amiri Sani Yiyu Zhang Shenming Lu Wensheng Dou Linzhang Wang Xuandong Li Chenxi Wang et al. 2021. Systemizing Interprocedural Static Analysis of Large-scale Systems Code with Graspan. ACM Transactions on Computer Systems (TOCS) 38 1-2 (2021) 1-39.","DOI":"10.1145\/3466820"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3656451","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/3656451","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:42:57Z","timestamp":1751661777000},"score":1,"resource":{"primary":{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3656451"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,20]]},"references-count":45,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2024,6,20]]}},"alternative-id":["10.1145\/3656451"],"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1145\/3656451","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,20]]},"assertion":[{"value":"2024-06-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}