{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T03:54:14Z","timestamp":1752983654305,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T00:00:00Z","timestamp":1697414400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"TCS Foundation","award":["TCS Research Scholar Program"],"award-info":[{"award-number":["TCS Research Scholar Program"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2023,10,16]]},"abstract":"<jats:p>Interprocedural alias analyses often sacrifice precision for scalability. Thus, modern compilers such as GCC and LLVM implement more scalable but less precise intraprocedural alias analyses. This compromise makes the compilers miss out on potential optimization opportunities, affecting the performance of the application. Modern compilers implement loop-versioning with dynamic checks for pointer disambiguation to enable the missed optimizations. Polyhedral access range analysis and symbolic range analysis enable \ud835\udc42 (1) range checks for non-overlapping of memory accesses inside loops. However, these approaches work only for the loops in which the loop bounds are loop invariants. To address this limitation, researchers proposed a technique that requires \ud835\udc42 (\ud835\udc59\ud835\udc5c\ud835\udc54 \ud835\udc5b) memory accesses for pointer disambiguation. Others improved the performance of dynamic checks to single memory access by constraining the object size and alignment. However, the former approach incurs noticeable overhead due to its dynamic checks, whereas the latter has a noticeable allocator overhead. Thus, scalability remains a challenge.<\/jats:p>\n          <jats:p>In this work, we present a tool, Rapid, that further reduces the overheads of the allocator and dynamic checks proposed in the existing approaches. The key idea is to identify objects that need disambiguation checks using a profiler and allocate them in different regions, which are disjoint memory areas. The disambiguation checks simply compare the regions corresponding to the objects. The regions are aligned such that the top 32 bits in the addresses of any two objects allocated in different regions are always different. As a consequence, the dynamic checks do not require any memory access to ensure that the objects belong to different regions, making them efficient.<\/jats:p>\n          <jats:p>Rapid achieved a maximum performance benefit of around 52.94% for Polybench and 1.88% for CPU SPEC 2017 benchmarks. The maximum CPU overhead of our allocator is 0.57% with a geometric mean of -0.2% for CPU SPEC 2017 benchmarks. Due to the low overhead of the allocator and dynamic checks, Rapid could improve the performance of 12 out of 16 CPU SPEC 2017 benchmarks. In contrast, a state-of-the-art approach used in the comparison could improve only five CPU SPEC 2017 benchmarks.<\/jats:p>","DOI":"10.1145\/3622859","type":"journal-article","created":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T15:41:29Z","timestamp":1697470889000},"page":"1729-1757","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Rapid: Region-Based Pointer Disambiguation"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6950-1055","authenticated-orcid":false,"given":"Khushboo","family":"Chitre","sequence":"first","affiliation":[{"name":"IIIT Delhi, Delhi, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9569-4089","authenticated-orcid":false,"given":"Piyus","family":"Kedia","sequence":"additional","affiliation":[{"name":"IIIT Delhi, Delhi, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8677-0601","authenticated-orcid":false,"given":"Rahul","family":"Purandare","sequence":"additional","affiliation":[{"name":"University of Nebraska-Lincoln, Lincoln, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,10,16]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2016 (accessed Aug 12 2023). Tutorial-Perf Wiki. https:\/\/perf.wiki.kernel.org\/index.php\/Tutorial \t\t\t\t  2016 (accessed Aug 12 2023). Tutorial-Perf Wiki. https:\/\/perf.wiki.kernel.org\/index.php\/Tutorial"},{"key":"e_1_2_1_2_1","unstructured":"2023 (accessed Apr 11 2023). Mimalloc source code. https:\/\/github.com\/microsoft\/mimalloc \t\t\t\t  2023 (accessed Apr 11 2023). Mimalloc source code. https:\/\/github.com\/microsoft\/mimalloc"},{"key":"e_1_2_1_3_1","unstructured":"2023 (accessed Apr 11 2023). Runtime Checks of Pointers. https:\/\/llvm.org\/docs\/Vectorizers.html##runtime-checks-of-pointers \t\t\t\t  2023 (accessed Apr 11 2023). Runtime Checks of Pointers. https:\/\/llvm.org\/docs\/Vectorizers.html##runtime-checks-of-pointers"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.8321488"},{"key":"e_1_2_1_5_1","unstructured":"2023 (accessed Sep 2 2023). Rapid Artifact Github Repository. https:\/\/github.com\/khushboochitre\/artifact_rapid.git \t\t\t\t  2023 (accessed Sep 2 2023). Rapid Artifact Github Repository. https:\/\/github.com\/khushboochitre\/artifact_rapid.git"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814285"},{"key":"e_1_2_1_7_1","unstructured":"Lars Ole Andersen and Peter Lee. 2005. Program Analysis and Specialization for the C Programming Language. \t\t\t\t  Lars Ole Andersen and Peter Lee. 2005. Program Analysis and Specialization for the C Programming Language."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375595"},{"volume-title":"Effective automatic parallelization and locality optimization using the polyhedral model. Ph. D. Dissertation","author":"Bondhugula Uday Kumar","key":"e_1_2_1_9_1","unstructured":"Uday Kumar Bondhugula . 2008. Effective automatic parallelization and locality optimization using the polyhedral model. Ph. D. Dissertation . The Ohio State University . Uday Kumar Bondhugula. 2008. Effective automatic parallelization and locality optimization using the polyhedral model. Ph. D. Dissertation. The Ohio State University."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/872726.806984"},{"key":"e_1_2_1_11_1","volume-title":"Register allocation via coloring. Computer languages, 6, 1","author":"Chaitin Gregory J","year":"1981","unstructured":"Gregory J Chaitin , Marc A Auslander , Ashok K Chandra , John Cocke , Martin E Hopkins , and Peter W Markstein . 1981. Register allocation via coloring. Computer languages, 6, 1 ( 1981 ), 47\u201357. Gregory J Chaitin, Marc A Auslander, Ashok K Chandra, John Cocke, Martin E Hopkins, and Peter W Markstein. 1981. Register allocation via coloring. Computer languages, 6, 1 (1981), 47\u201357."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24723-4_5"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563316"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/258916.258940"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75282"},{"key":"e_1_2_1_16_1","unstructured":"Robert Engelen. 2000. Symbolic Evaluation of Chains of Recurrences for Loop Optimization. 03. \t\t\t\t  Robert Engelen. 2000. Symbolic Evaluation of Chains of Recurrences for Loop Optimization. 03."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45306-7_9"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2002.1106020"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250767"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480911"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2190025.2190075"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/325478.325519"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/192007.192012"},{"key":"e_1_2_1_25_1","volume-title":"Whole-Function Vectorization. In Proceedings of the 9th Annual IEEE\/ACM International Symposium on Code Generation and Optimization (CGO \u201911)","author":"Karrenberg Ralf","year":"2011","unstructured":"Ralf Karrenberg and Sebastian Hack . 2011 . Whole-Function Vectorization. In Proceedings of the 9th Annual IEEE\/ACM International Symposium on Code Generation and Optimization (CGO \u201911) . IEEE Computer Society, USA. 141\u2013150. isbn:9781612843568 Ralf Karrenberg and Sebastian Hack. 2011. Whole-Function Vectorization. In Proceedings of the 9th Annual IEEE\/ACM International Symposium on Code Generation and Optimization (CGO \u201911). IEEE Computer Society, USA. 141\u2013150. isbn:9781612843568"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250766"},{"key":"e_1_2_1_27_1","volume-title":"Mimalloc: Free List Sharding in Action. In APLAS.","author":"Leijen Daan","year":"2019","unstructured":"Daan Leijen , Benjamin G. Zorn , and Leonardo Mendon\u00e7a de Moura . 2019 . Mimalloc: Free List Sharding in Action. In APLAS. Daan Leijen, Benjamin G. Zorn, and Leonardo Mendon\u00e7a de Moura. 2019. Mimalloc: Free List Sharding in Action. In APLAS."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781164"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 2004 GCC Developers Summit. 105\u2013118","author":"Naishlos Dorit","year":"2004","unstructured":"Dorit Naishlos . 2004 . Autovectorization in GCC . In Proceedings of the 2004 GCC Developers Summit. 105\u2013118 . Dorit Naishlos. 2004. Autovectorization in GCC. In Proceedings of the 2004 GCC Developers Summit. 105\u2013118."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2714064.2660205"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2854038.2854050"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290520.1290524"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2009.9"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/330249.330250"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/358438.349325"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1759937.1759950"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892225"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237727"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892235"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Rishi Surendran Rajkishore Barik Jisheng Zhao and Vivek Sarkar. 2014. Inter-iteration Scalar Replacement Using Array SSA Form. In CC. \t\t\t\t  Rishi Surendran Rajkishore Barik Jisheng Zhao and Vivek Sarkar. 2014. Inter-iteration Scalar Replacement Using Array SSA Form. In CC.","DOI":"10.1007\/978-3-642-54807-9_3"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277714"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772954.1772979"},{"key":"e_1_2_1_43_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\/3622859","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3622859","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:57:27Z","timestamp":1750298247000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3622859"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,16]]},"references-count":43,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2023,10,16]]}},"alternative-id":["10.1145\/3622859"],"URL":"https:\/\/doi.org\/10.1145\/3622859","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2023,10,16]]},"assertion":[{"value":"2023-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}