{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T17:23:25Z","timestamp":1783445005562,"version":"3.54.6"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T00:00:00Z","timestamp":1634256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP200101328,DP210101348"],"award-info":[{"award-number":["DP200101328,DP210101348"]}],"id":[{"id":"10.13039\/501100000923","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":[[2021,10,20]]},"abstract":"<jats:p>Inclusion-based set constraint solving is the most popular technique for whole-program points-to analysis whereby an analysis is typically formulated as repeatedly resolving constraints between points-to sets of program variables. The set union operation is central to this process. The number of points-to sets can grow as analyses become more precise and input programs become larger, resulting in more time spent performing unions and more space used storing these points-to sets. Most existing approaches focus on improving scalability of precise points-to analyses from an algorithmic perspective and there has been less research into improving the data structures behind the analyses.<\/jats:p>\n          <jats:p>Bit-vectors as one of the more popular data structures have been used in several mainstream analysis frameworks to represent points-to sets. To store memory objects in bit-vectors, objects need to mapped to integral identifiers. We observe that this object-to-identifier mapping is critical for a compact points-to set representation and the set union operation. If objects in the same points-to sets (co-pointees) are not given numerically close identifiers, points-to resolution can cost significantly more space and time. Without data on the unpredictable points-to relations which would be discovered by the analysis, an ideal mapping is extremely challenging.<\/jats:p>\n          <jats:p>In this paper, we present a new approach to inclusion-based analysis by compacting points-to sets through object clustering. Inspired by recent staged analysis where an auxiliary analysis produces results approximating a more precise main analysis, we formulate points-to set compaction as an optimisation problem solved by integer programming using constraints generated from the auxiliary analysis\u2019s results in order to produce an effective mapping. We then develop a more approximate mapping, yet much more efficiently, using hierarchical clustering to compact bit-vectors. We also develop an improved representation of bit-vectors (called core bit-vectors) to fully take advantage of the newly produced mapping. Our approach requires no algorithmic change to the points-to analysis. We evaluate our object clustering on flow sensitive points-to analysis using 8 open-source programs (&gt;3.1 million lines of LLVM instructions) and our results show that our approach can successfully improve the analysis with an up to 1.83\u00d7 speed up and an up to 4.05\u00d7 reduction in memory usage.<\/jats:p>","DOI":"10.1145\/3485547","type":"journal-article","created":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T19:18:28Z","timestamp":1634325508000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Compacting points-to sets through object clustering"],"prefix":"10.1145","volume":"5","author":[{"given":"Mohamad","family":"Barbar","sequence":"first","affiliation":[{"name":"University of Technology Sydney, Australia \/ CSIRO\u2019s Data61, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9510-6574","authenticated-orcid":false,"given":"Yulei","family":"Sui","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,15]]},"reference":[{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53413-7_5"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.5507442"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2020.24"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO51591.2021.9370334"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781144"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640108"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61053-7_66"},{"key":"e_1_2_2_9_1","volume-title":"crux-bitcode. https:\/\/github.com\/mbarbar\/crux-bitcode Last accessed on","year":"2021"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277667"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1348250.1348255"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250767"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74061-2_17"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480911"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2011.5764696"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378855"},{"key":"e_1_2_2_17_1","volume-title":"ISO\/IEC. 2017. ISO\/IEC 14882:2017 \u2014 Programming languages \u2014 C++"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1469-8137.1912.tb05611.x"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276510"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428247"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.23919\/FMCAD.2019.8894275"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2004.1281665"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32304-2_3"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926389"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1765931.1765948"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293606"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2644805"},{"key":"e_1_2_2_28_1","volume-title":"https:\/\/llvm.org\/doxygen\/BitVector_8h_source.html Last accessed on","year":"2021"},{"key":"e_1_2_2_29_1","volume-title":"https:\/\/llvm.org\/doxygen\/SparseBitVector_8h_source.html Last accessed on","year":"2021"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/b107408"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869459.1869495"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/26.4.354"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v053.i09"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254092"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCAM.2003.1238026"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290520.1290524"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2009.9"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349310"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17465-1_22"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509524"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926390"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2950290.2950296"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892235"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2338965.2336784"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54807-9_2"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.7763\/IJCTE.2013.V5.736"},{"key":"e_1_2_2_47_1","unstructured":"2021. The T. J. Watson Libraries for Analysis (WALA). http:\/\/wala.sf.net\/ Last accessed on 14 September 2021.  2021. The T. J. Watson Libraries for Analysis (WALA). http:\/\/wala.sf.net\/ Last accessed on 14 September 2021."},{"key":"e_1_2_2_49_1","volume-title":"Whole Program LLVM in Go. https:\/\/github.com\/SRI-CSL\/gllvm Last accessed on","year":"2021"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996860"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485547","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485547","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:40Z","timestamp":1750191520000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485547"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,15]]},"references-count":48,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2021,10,20]]}},"alternative-id":["10.1145\/3485547"],"URL":"https:\/\/doi.org\/10.1145\/3485547","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,15]]},"assertion":[{"value":"2021-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}