{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T03:45:37Z","timestamp":1780371937532,"version":"3.54.1"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T00:00:00Z","timestamp":1589846400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"TCS Research Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2020,6,30]]},"abstract":"<jats:p>Computing precise (fully flow- and context-sensitive) and exhaustive (as against demand-driven) points-to information is known to be expensive. Top-down approaches require repeated analysis of a procedure for separate contexts. Bottom-up approaches need to model unknown pointees accessed indirectly through pointers that may be defined in the callers and hence do not scale while preserving precision. Therefore, most approaches to precise points-to analysis begin with a scalable but imprecise method and then seek to increase its precision. We take the opposite approach in that we begin with a precise method and increase its scalability. In a nutshell, we create naive but possibly non-scalable procedure summaries and then use novel optimizations to compact them while retaining their soundness and precision.<\/jats:p>\n          <jats:p>\n            For this purpose, we propose a novel abstraction called the\n            <jats:italic>generalized points-to graph<\/jats:italic>\n            (GPG), which views points-to relations as memory updates and generalizes them using the counts of indirection levels leaving the unknown pointees implicit. This allows us to construct GPGs as compact representations of bottom-up procedure summaries in terms of memory updates and control flow between them. Their compactness is ensured by strength reduction (which reduces the indirection levels), control flow minimization (which removes control flow edges while preserving soundness and precision), and call inlining (which enhances the opportunities of these optimizations).\n          <\/jats:p>\n          <jats:p>The effectiveness of GPGs lies in the fact that they discard as much control flow as possible without losing precision. This is the reason GPGs are very small even for main procedures that contain the effect of the entire program. This allows our implementation to scale to 158 kLoC for C programs.<\/jats:p>\n          <jats:p>At a more general level, GPGs provide a convenient abstraction to represent and transform memory in the presence of pointers. Future investigations can try to combine it with other abstractions for static analyses that can benefit from points-to information.<\/jats:p>","DOI":"10.1145\/3382092","type":"journal-article","created":{"date-parts":[[2020,5,25]],"date-time":"2020-05-25T18:15:24Z","timestamp":1590430524000},"page":"1-78","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Generalized Points-to Graphs"],"prefix":"10.1145","volume":"42","author":[{"given":"Pritam M.","family":"Gharat","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Bombay, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Uday P.","family":"Khedker","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Bombay, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7013-8572","authenticated-orcid":false,"given":"Alan","family":"Mycroft","sequence":"additional","affiliation":[{"name":"University of Cambridge, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,5,19]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"2006","unstructured":"Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. 2006. Compilers: Principles, Techniques, and Tools (2nd ed.). Addison Wesley Longman, Boston, MA."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/503272.503274"},{"key":"e_1_2_2_3_1","first-page":"746","article-title":"Analysis of programs for parallel processing","volume":"5","author":"Bernstein A. J.","year":"1996","unstructured":"A. J. Bernstein. 1996. Analysis of programs for parallel processing. IEEE Trans. Elec. Comp. EC-15, 5 (1996), 746--757. https:\/\/ci.nii.ac.jp\/naid\/10009998541\/en\/.","journal-title":"IEEE Trans. Elec. Comp. EC-15"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2009.08.002"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/292540.292554"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349311"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375615"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/178243.178264"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26529-2_25"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53413-7_11"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1181775.1181785"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378802"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49727-7_4"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/347324.348916"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375613"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2931098"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/176454.176510"},{"key":"e_1_2_2_19_1","volume-title":"Allen","author":"Kennedy Ken","year":"2002","unstructured":"Ken Kennedy and John R. Allen. 2002. Optimizing Compilers for Modern Architectures: A Dependence-Based Approach. Morgan Kaufmann, San Francisco, CA."},{"key":"e_1_2_2_20_1","volume-title":"Proceedings of the Joint European Conferences on Theory and Practice of Software and the 17th International Conference on Compiler Construction (CC\u201908\/ETAPS\u201908)","author":"Uday","unstructured":"Uday P. Khedker and Bageshri Karkare. 2008. Efficiency, precision, simplicity, and generality in interprocedural data flow analysis: Resurrecting the classical call strings method. In Proceedings of the Joint European Conferences on Theory and Practice of Software and the 17th International Conference on Compiler Construction (CC\u201908\/ETAPS\u201908)."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33125-1_19"},{"key":"e_1_2_2_22_1","unstructured":"U. P. Khedker A. Sanyal and B. Sathe. 2009. Data Flow Analysis: Theory and Practice. Taylor 8 Francis (CRC Press) Boca Raton FL."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250766"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/DagRep.3.4.91"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491894.2466483"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33125-1_25"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1561\/2500000020"},{"key":"e_1_2_2_28_1","volume-title":"Advanced Compiler Design and Implementation. Morgan Kaufmann","author":"Muchnick Steven S.","unstructured":"Steven S. Muchnick. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann, San Francisco, CA."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487568.2487569"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/383043.381532"},{"key":"e_1_2_2_32_1","volume-title":"Selected Papers from the 6th International Joint Conference on Theory and Practice of Software Development (TAPSOFT\u201995)","author":"Sagiv Mooly","unstructured":"Mooly Sagiv, Thomas Reps, and Susan Horwitz. 1996. Precise interprocedural dataflow analysis with applications to constant propagation. In Selected Papers from the 6th International Joint Conference on Theory and Practice of Software Development (TAPSOFT\u201995). Elsevier Science Publishers B. V., Amsterdam, The Netherlands. http:\/\/dl.acm.org\/citation.cfm?id=243753.243762"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2259016.2259050"},{"key":"e_1_2_2_34_1","unstructured":"M. Sharir and A. Pneuli. 1981. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications S. S. Muchnick and N. D. Jones (Eds.). Prentice Hall 189\u2013234."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1561\/2500000014"},{"key":"e_1_2_2_36_1","volume-title":"Proceedings of the European Conference on Object-Oriented Programming (ECOOP\u201916)","author":"Sp\u00e4th Johannes","year":"2016","unstructured":"Johannes Sp\u00e4th, Lisa Nguyen, Karim Ali, and Eric Bodden. 2016. Boomerang: Demand-driven flow- and context-sensitive pointer analysis for Java. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP\u201916)."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094817"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450136.2450140"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30579-8_14"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2950290.2950296"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892235"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/320384.320400"},{"key":"e_1_2_2_43_1","volume-title":"Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI\u201995)","author":"Wilson R. P.","unstructured":"R. P. Wilson and M. S. Lam. 1995. Efficient context-sensitive pointer analysis for C programs. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI\u201995). citeseer.ist.psu.edu\/wilson95efficient.html"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2259051.2259053"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328467"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772954.1772985"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594328"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.844092"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382092","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3382092","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:08Z","timestamp":1750197728000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382092"}},"subtitle":["A Precise and Scalable Abstraction for Points-to Analysis"],"short-title":[],"issued":{"date-parts":[[2020,5,19]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6,30]]}},"alternative-id":["10.1145\/3382092"],"URL":"https:\/\/doi.org\/10.1145\/3382092","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,19]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}