{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T18:54:35Z","timestamp":1771959275757,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T00:00:00Z","timestamp":1667174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"TCS Foundation","award":["TCS Research Fellow"],"award-info":[{"award-number":["TCS Research Fellow"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>Context-sensitive inter-procedural alias analyses are more precise than intra-procedural alias analyses. However, context-sensitive inter-procedural alias analyses are not scalable. As a consequence, most of the production compilers sacrifice precision for scalability and implement intra-procedural alias analysis. The alias analysis is used by many compiler optimizations, including loop transformations. Due to the imprecision of alias analysis, the program\u2019s performance may suffer, especially in the presence of loops.<\/jats:p>\n          <jats:p>Previous work proposed a general approach based on code-versioning with dynamic checks to disambiguate pointers at runtime. However, the overhead of dynamic checks in this approach is O(log n), which is substantially high to enable interesting optimizations. Other suggested approaches, e.g., polyhedral and symbolic range analysis, have O(1) overheads, but they only work for loops with certain constraints. The production compilers, such as LLVM and GCC, use scalar evolution analysis to compute an O(1) range check for loops to resolve memory dependencies at runtime. However, this approach also can only be applied to loops with certain constraints.<\/jats:p>\n          <jats:p>In this work, we present our tool, Scout, that can disambiguate two pointers at runtime using single memory access. Scout is based on the key idea to constrain the allocation size and alignment during memory allocations. Scout can also disambiguate array accesses within a loop for which the existing O(1) range checks technique cannot be applied. In addition, Scout uses feedback from static optimizations to reduce the number of dynamic checks needed for optimizations.<\/jats:p>\n          <jats:p>Our technique enabled new opportunities for loop-invariant code motion, dead store elimination, loop vectorization, and load elimination in an already optimized code. Our performance improvements are up to 51.11% for Polybench and up to 0.89% for CPU SPEC 2017 suites. The geometric means for our allocator\u2019s CPU and memory overheads for CPU SPEC 2017 benchmarks are 1.05%, and 7.47%, respectively. For Polybench benchmarks, the geometric mean of CPU and memory overheads are 0.21% and 0.13%, respectively.<\/jats:p>","DOI":"10.1145\/3563316","type":"journal-article","created":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T20:23:35Z","timestamp":1667247815000},"page":"786-810","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["The road not taken: exploring alias analysis based optimizations missed by the compiler"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6950-1055","authenticated-orcid":false,"given":"Khushboo","family":"Chitre","sequence":"first","affiliation":[{"name":"IIIT Delhi, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9569-4089","authenticated-orcid":false,"given":"Piyus","family":"Kedia","sequence":"additional","affiliation":[{"name":"IIIT Delhi, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8677-0601","authenticated-orcid":false,"given":"Rahul","family":"Purandare","sequence":"additional","affiliation":[{"name":"IIIT Delhi, India \/ University of Nebraska-Lincoln, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,10,31]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2016 (accessed Apr 14 2022). Intel 64 and ia-32 architectures software developer\u2019s manual volume 2b. https:\/\/www.intel.com\/content\/dam\/www\/public\/us\/en\/documents\/manuals\/64-ia-32-architectures-software-developer-vol-2b-manual.pdf \t\t\t\t  2016 (accessed Apr 14 2022). Intel 64 and ia-32 architectures software developer\u2019s manual volume 2b. https:\/\/www.intel.com\/content\/dam\/www\/public\/us\/en\/documents\/manuals\/64-ia-32-architectures-software-developer-vol-2b-manual.pdf"},{"key":"e_1_2_1_2_1","unstructured":"2019 (accessed Apr 13 2022). Restrict Keyword in LLVM. https:\/\/lists.llvm.org\/pipermail\/llvm-dev\/2019-March\/131127.html \t\t\t\t  2019 (accessed Apr 13 2022). Restrict Keyword in LLVM. https:\/\/lists.llvm.org\/pipermail\/llvm-dev\/2019-March\/131127.html"},{"key":"e_1_2_1_3_1","volume-title":"CPU SPEC 2017 benchmark suite. https:\/\/www.spec.org\/cpu2017\/Docs\/overview.html##benchmarks","author":"Apr","year":"2022","unstructured":"2021 (accessed Apr 13 , 2022 ). CPU SPEC 2017 benchmark suite. https:\/\/www.spec.org\/cpu2017\/Docs\/overview.html##benchmarks 2021 (accessed Apr 13, 2022). CPU SPEC 2017 benchmark suite. https:\/\/www.spec.org\/cpu2017\/Docs\/overview.html##benchmarks"},{"key":"e_1_2_1_4_1","unstructured":"2022 (accessed Apr 13 2022). Intrinsic Functions. https:\/\/llvm.org\/docs\/LangRef.html##intrinsic-functions \t\t\t\t  2022 (accessed Apr 13 2022). Intrinsic Functions. https:\/\/llvm.org\/docs\/LangRef.html##intrinsic-functions"},{"key":"e_1_2_1_5_1","unstructured":"2022 (accessed Apr 13 2022). Runtime Checks of Pointers. https:\/\/llvm.org\/docs\/Vectorizers.html##runtime-checks-of-pointers \t\t\t\t  2022 (accessed Apr 13 2022). Runtime Checks of Pointers. https:\/\/llvm.org\/docs\/Vectorizers.html##runtime-checks-of-pointers"},{"key":"e_1_2_1_6_1","unstructured":"2022 (accessed Apr 13 2022). \u2018noalias\u2019 and \u2018alias.scope\u2019 Metadata. https:\/\/llvm.org\/docs\/LangRef.html##noalias-and-alias-scope-metadata \t\t\t\t  2022 (accessed Apr 13 2022). \u2018noalias\u2019 and \u2018alias.scope\u2019 Metadata. https:\/\/llvm.org\/docs\/LangRef.html##noalias-and-alias-scope-metadata"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7089827"},{"key":"e_1_2_1_8_1","unstructured":"2022 (accessed Sep 9 2022). Scout Artifact Github Repository. https:\/\/github.com\/khushboochitre\/Scout-Artifact.git \t\t\t\t  2022 (accessed Sep 9 2022). Scout Artifact Github Repository. https:\/\/github.com\/khushboochitre\/Scout-Artifact.git"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814285"},{"key":"e_1_2_1_10_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_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/780822.781144"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375595"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3185768.3185771"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24723-4_5"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/258915.258940"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75282"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168908"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277670"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2017.7863748"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/645989.674312"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250767"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480911"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2011.5764696"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/325478.325519"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/192007.192012"},{"key":"e_1_2_1_27_1","volume-title":"Demand-driven Alias Analysis : Formalizing Bidirectional Analyses for Soundness and Precision. ArXiv, abs\/1802.00932","author":"Jaiswal S.","year":"2018","unstructured":"S. Jaiswal , Uday P. Khedker , and Supratik Chakraborty . 2018. Demand-driven Alias Analysis : Formalizing Bidirectional Analyses for Soundness and Precision. ArXiv, abs\/1802.00932 ( 2018 ). S. Jaiswal, Uday P. Khedker, and Supratik Chakraborty. 2018. Demand-driven Alias Analysis : Formalizing Bidirectional Analyses for Soundness and Precision. ArXiv, abs\/1802.00932 (2018)."},{"key":"e_1_2_1_28_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_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/161494.161501"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250766"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781164"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353534.1346296"},{"key":"e_1_2_1_33_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_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2714064.2660205"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2854038.2854050"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290520.1290524"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/186025.186041"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/358438.349325"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3079079.3079098"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/647166.717860"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892225"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237727"},{"key":"e_1_2_1_43_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_44_1","unstructured":"R Van Engelen. 2000. Symbolic evaluation of chains of recurrences for loop optimization. Citeseer. \t\t\t\t  R Van Engelen. 2000. Symbolic evaluation of chains of recurrences for loop optimization. Citeseer."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45306-7_9"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996859"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328897.1328464"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065579.1065798"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563316","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3563316","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:38:10Z","timestamp":1750178290000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563316"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,31]]},"references-count":48,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3563316"],"URL":"https:\/\/doi.org\/10.1145\/3563316","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,31]]},"assertion":[{"value":"2022-10-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}