{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:35:55Z","timestamp":1750221355598,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,1,30]],"date-time":"2018-01-30T00:00:00Z","timestamp":1517270400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ARC","award":["DE170101081, DP150102109 and DP170103956"],"award-info":[{"award-number":["DE170101081, DP150102109 and DP170103956"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>Compiler-based vectorization represents a promising solution to automatically generate code that makes efficient use of modern CPUs with SIMD extensions. Two main auto-vectorization techniques, superword-level parallelism vectorization (SLP) and loop-level vectorization (LLV), require precise dependence analysis on arrays and structs to vectorize isomorphic scalar instructions (in the case of SLP) and reduce dynamic dependence checks at runtime (in the case of LLV).<\/jats:p>\n          <jats:p>\n            The alias analyses used in modern vectorizing compilers are either intra-procedural (without tracking inter-procedural data-flows) or inter-procedural (by using field-sensitive models, which are too imprecise in handling arrays and structs). This article proposes an inter-procedural\n            <jats:bold>L<\/jats:bold>\n            oop-oriented\n            <jats:bold>P<\/jats:bold>\n            ointer\n            <jats:bold>A<\/jats:bold>\n            nalysis for C, called L\n            <jats:sc>pa<\/jats:sc>\n            , for analyzing arrays and structs to support aggressive SLP and LLV optimizations effectively. Unlike field-insensitive solutions that pre-allocate objects for each memory allocation site, our approach uses a lazy memory model to generate\n            <jats:italic>access-based location sets<\/jats:italic>\n            based on how structs and arrays are accessed. L\n            <jats:sc>pa<\/jats:sc>\n            can precisely analyze arrays and nested aggregate structures to enable SIMD optimizations for large programs. By separating the location set generation as an independent concern from the rest of the pointer analysis, L\n            <jats:sc>pa<\/jats:sc>\n            is designed so that existing points-to resolution algorithms (e.g., flow-insensitive and flow-sensitive pointer analysis) can be reused easily.\n          <\/jats:p>\n          <jats:p>\n            We have implemented L\n            <jats:sc>pa<\/jats:sc>\n            fully in the LLVM compiler infrastructure (version 3.8.0). We evaluate L\n            <jats:sc>pa<\/jats:sc>\n            by considering SLP and LLV, the two classic vectorization techniques, on a set of 20 C and Fortran CPU2000\/2006 benchmarks. For SLP, L\n            <jats:sc>pa<\/jats:sc>\n            outperforms LLVM\u2019s BasicAA and ScevAA by discovering 139 and 273 more vectorizable basic blocks, respectively, resulting in the best speedup of 2.95% for 173.applu. For LLV, LLVM introduces totally 551 and 652 static bound checks under BasicAA and ScevAA, respectively. In contrast, L\n            <jats:sc>pa<\/jats:sc>\n            has reduced these static checks to 220, with an average of 15.7 checks per benchmark, resulting in the best speedup of 7.23% for 177.mesa.\n          <\/jats:p>","DOI":"10.1145\/3168364","type":"journal-article","created":{"date-parts":[[2018,1,31]],"date-time":"2018-01-31T13:25:40Z","timestamp":1517405140000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Loop-Oriented Pointer Analysis for Automatic SIMD Vectorization"],"prefix":"10.1145","volume":"17","author":[{"given":"Yulei","family":"Sui","sequence":"first","affiliation":[{"name":"University of Technology Sydney (UTS), Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaokang","family":"Fan","sequence":"additional","affiliation":[{"name":"University of New South Wales (UNSW), Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hao","family":"Zhou","sequence":"additional","affiliation":[{"name":"University of New South Wales (UNSW), Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingling","family":"Xue","sequence":"additional","affiliation":[{"name":"University of New South Wales (UNSW), Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,1,30]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/190347.190423"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53413-7_5"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2010.38"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3092703.3092729"},{"volume-title":"Proceedings of the IMPACT\u201911","author":"Grosser Tobias","key":"e_1_2_1_6_1","unstructured":"Tobias Grosser , Hongbin Zheng , Raghesh Aloor , Andreas Simb\u00fcrger , Armin Gr\u00f6\u00dflinger , and Louis-No\u00ebl Pouchet . Polly-polyhedral optimization in {LLVM} . In Proceedings of the IMPACT\u201911 . Tobias Grosser, Hongbin Zheng, Raghesh Aloor, Andreas Simb\u00fcrger, Armin Gr\u00f6\u00dflinger, and Louis-No\u00ebl Pouchet. Polly-polyhedral optimization in {LLVM}. In Proceedings of the IMPACT\u201911."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250767"},{"volume-title":"Proceedings of the CGO\u201911","author":"Hardekopf B.","key":"e_1_2_1_8_1","unstructured":"B. Hardekopf and C. Lin . 2011. Flow-sensitive pointer analysis for millions of lines of code . In Proceedings of the CGO\u201911 . 289--298. B. Hardekopf and C. Lin. 2011. Flow-sensitive pointer analysis for millions of lines of code. In Proceedings of the CGO\u201911. 289--298."},{"key":"e_1_2_1_9_1","unstructured":"ISO90. 1990. ISO\/IEC. international standard ISO\/IEC 9899 programming languages C.  ISO90. 1990. ISO\/IEC. international standard ISO\/IEC 9899 programming languages C."},{"volume-title":"Software and Compilers for Embedded Systems","author":"Jung Michael","key":"e_1_2_1_10_1","unstructured":"Michael Jung and Sorin Alexander Huss . 2004. Fast points-to analysis for languages with structured types . In Software and Compilers for Embedded Systems . Springer , 107--121. Michael Jung and Sorin Alexander Huss. 2004. Fast points-to analysis for languages with structured types. In Software and Compilers for Embedded Systems. Springer, 107--121."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2190025.2190061"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349320"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/977395.977673"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926389"},{"key":"e_1_2_1_15_1","unstructured":"LLVM-Alias-Analysis. 2017. Retrieved from http:\/\/llvm.org\/docs\/AliasAnalysis.html.  LLVM-Alias-Analysis. 2017. Retrieved from http:\/\/llvm.org\/docs\/AliasAnalysis.html."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.68"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the ACSC\u201905","author":"Nguyen Phung Hua","year":"2015","unstructured":"Phung Hua Nguyen and Jingling Xue . 2015 . Interprocedural side-effect analysis and optimisation in the presence of dynamic class loading . In Proceedings of the ACSC\u201905 . 9--18. Phung Hua Nguyen and Jingling Xue. 2015. Interprocedural side-effect analysis and optimisation in the presence of dynamic class loading. In Proceedings of the ACSC\u201905. 9--18."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90047-7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1133997"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1454115.1454119"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2854038.2854050"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290520.1290524"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2009.9"},{"key":"e_1_2_1_24_1","volume-title":"Jones","author":"Porpodas Vasileios","year":"2015","unstructured":"Vasileios Porpodas , Alberto Magni , and Timothy M . Jones . 2015 . PSLP : Padded SLP automatic vectorization. In Proceedings of the CGO\u201915. IEEE , 190--201. Vasileios Porpodas, Alberto Magni, and Timothy M. Jones. 2015. PSLP: Padded SLP automatic vectorization. In Proceedings of the CGO\u201915. IEEE, 190--201."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/186025.186041"},{"key":"e_1_2_1_26_1","unstructured":"Rajiv Ravindran Rick Hank Loreena Lee. 2010. Implementing next generation points-to in open64. In Open64 Developers Forum. Retrieved from http:\/\/www.affinic.com\/documents\/open64workshop\/2010\/.  Rajiv Ravindran Rick Hank Loreena Lee. 2010. Implementing next generation points-to in open64. In Open64 Developers Forum. Retrieved from http:\/\/www.affinic.com\/documents\/open64workshop\/2010\/."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349325"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1299042.1299055"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2005.33"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134027"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2854038.2854043"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2013.6494978"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2950290.2950296"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892235"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2338965.2336784"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2009.18"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/647477.727776"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/207110.207111"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2544137.2544154"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10936-7_20"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328464"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2886101"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2854038.2854054"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3168364","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3168364","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:08Z","timestamp":1750213568000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3168364"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,30]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3168364"],"URL":"https:\/\/doi.org\/10.1145\/3168364","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2018,1,30]]},"assertion":[{"value":"2016-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}