{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:20:08Z","timestamp":1750306808277,"version":"3.41.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,12,1]],"date-time":"2013-12-01T00:00:00Z","timestamp":1385856000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>\n            Compilation of real-world programs often requires hours. The term\n            <jats:italic>nightly build<\/jats:italic>\n            known to industrial researchers is an artifact of long compilation times. Our goal is to reduce the absolute analysis times for large C codes (of the order of millions of lines). Pointer analysis is one of the key analyses performed during compilation. Its scalability is paramount to achieve the efficiency of the overall compilation process and its precision directly affects that of the client analyses. In this work, we design a time- and space-efficient flow-sensitive pointer analysis and parallelize it on graphics processing units. Our analysis proposes to use an extended bloom filter, called multibloom, to store points-to information in an approximate manner and develops an analysis in terms of the operations over the multibloom. Since bloom filter is a probabilistic data structure, we develop ways to gain back the analysis precision. We achieve effective parallelization by achieving memory coalescing, reducing thread divergence, and improving load balance across GPU warps. Compared to a state-of-the-art sequential solution, our parallel version achieves a 7.8 \u00d7 speedup with less than 5% precision loss on a suite of six large programs. Using two client transformations, we show that this loss in precision only minimally affects a client\u2019s precision.\n          <\/jats:p>","DOI":"10.1145\/2541228.2555296","type":"journal-article","created":{"date-parts":[[2014,1,14]],"date-time":"2014-01-14T13:39:57Z","timestamp":1389706797000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Time- and space-efficient flow-sensitive points-to analysis"],"prefix":"10.1145","volume":"10","author":[{"given":"Rupesh","family":"Nasre","sequence":"first","affiliation":[{"name":"The University of Texas at Austin, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,12]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781144"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455770.1455778"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158639"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872787"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31057-7_29"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944862.1944872"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/178243.178264"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277667"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.851975"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1348250.1348255"},{"key":"e_1_2_1_13_1","volume-title":"Retrieved","author":"GCC.","year":"2013","unstructured":"GCC. 2013 . GCC, the GNU Compiler Collection . Retrieved November 22, 2013 from http:\/\/gcc.gnu.org\/. GCC. 2013. GCC, the GNU Compiler Collection. Retrieved November 22, 2013 from http:\/\/gcc.gnu.org\/."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/358628.358632"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2005.02.005"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250767"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480911"},{"volume-title":"Proceedings of the 9th Annual IEEE\/ACM International Symposium on Code Generation and Optimization (CGO\u201911)","author":"Hardekopf B.","key":"e_1_2_1_18_1","unstructured":"Hardekopf , B. and Lin , C . 2011. Flow-sensitive pointer analysis for millions of lines of code . In Proceedings of the 9th Annual IEEE\/ACM International Symposium on Code Generation and Optimization (CGO\u201911) . IEEE Computer Society, Washington, DC, 289--298. Hardekopf, B. and Lin, C. 2011. Flow-sensitive pointer analysis for millions of lines of code. In Proceedings of the 9th Annual IEEE\/ACM International Symposium on Code Generation and Optimization (CGO\u201911). IEEE Computer Society, Washington, DC, 289--298."},{"volume-title":"Proceedings of the 5th International Symposium on Static Analysis (SAS\u201998)","author":"Hind M.","key":"e_1_2_1_19_1","unstructured":"Hind , M. and Pioli , A . 1998. Assessing the Effects of Flow-Sensitivity on Pointer Alias Analyses . In Proceedings of the 5th International Symposium on Static Analysis (SAS\u201998) . Springer-Verlag, London, 57--81. Hind, M. and Pioli, A. 1998. Assessing the Effects of Flow-Sensitivity on Pointer Alias Analyses. In Proceedings of the 5th International Symposium on Static Analysis (SAS\u201998). Springer-Verlag, London, 57--81."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/347324.348916"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375613"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPPS.1992.222990"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/143095.143137"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/155090.155096"},{"volume-title":"Proceedings of the 2004 International Symposium on Code Generation and Optimization (CGO&rsquo;\u201904)","author":"Lattner C.","key":"e_1_2_1_25_1","unstructured":"Lattner , C. and Adve , V . 2004. LLVM: A compilation framework for lifelong program analysis & transformation . In Proceedings of the 2004 International Symposium on Code Generation and Optimization (CGO&rsquo;\u201904) . Lattner, C. and Adve, V. 2004. LLVM: A compilation framework for lifelong program analysis & transformation. In Proceedings of the 2004 International Symposium on Code Generation and Optimization (CGO&rsquo;\u201904)."},{"volume-title":"Proceedings of Supercomputing. 942--951","author":"Lee Y.-F.","key":"e_1_2_1_26_1","unstructured":"Lee , Y.-F. , Marlowe , T. , and Ryder , B . 1990. Performing data flow analysis in parallel . In Proceedings of Supercomputing. 942--951 . Lee, Y.-F., Marlowe, T., and Ryder, B. 1990. Performing data flow analysis in parallel. In Proceedings of Supercomputing. 942--951."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926389"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2025113.2025160"},{"volume-title":"Proceedings of the 12th International Conference on Very Large Data Bases (VLDB\u201986)","author":"Mackert L. F.","key":"e_1_2_1_29_1","unstructured":"Mackert , L. F. and Lohman , G. M . 1986. R&ast; optimizer validation and performance evaluation for distributed queries . In Proceedings of the 12th International Conference on Very Large Data Bases (VLDB\u201986) . Morgan Kaufmann Publishers Inc., San Francisco, CA, 149--159. Mackert, L. F. and Lohman, G. M. 1986. R&ast; optimizer validation and performance evaluation for distributed queries. In Proceedings of the 12th International Conference on Very Large Data Bases (VLDB\u201986). Morgan Kaufmann Publishers Inc., San Francisco, CA, 149--159."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00032-8"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145831"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869459.1869495"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/383962.384004"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442531"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10672-9_6"},{"key":"e_1_2_1_36_1","volume-title":"Retreived","author":"NVPTX.","year":"2012","unstructured":"NVPTX. 2012 . NVPTX backend for LLVM . Retreived May 20, 2013 from https:\/\/github.com\/llvm-mirror\/llvm\/tree\/master\/lib\/Target\/NVPTX. NVPTX. 2012. NVPTX backend for LLVM. Retreived May 20, 2013 from https:\/\/github.com\/llvm-mirror\/llvm\/tree\/master\/lib\/Target\/NVPTX."},{"key":"e_1_2_1_37_1","volume-title":"Retrieved","author":"Partow A.","year":"2013","unstructured":"Partow , A. 2013 . General Purpose Hash Function Algorithms . Retrieved November 22, 2013 from http:\/\/www.partow.net\/programming\/hashfunctions\/. Partow, A. 2013. General Purpose Hash Function Algorithms. Retrieved November 22, 2013 from http:\/\/www.partow.net\/programming\/hashfunctions\/."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:SQJO.0000039791.93071.a2"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926445"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28652-0_4"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263705"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/379539.379553"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161005"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807207"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237727"},{"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\/207110.207111"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772954.1772985"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/250707.239112"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996860"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2541228.2555296","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2541228.2555296","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:35:01Z","timestamp":1750232101000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2541228.2555296"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1145\/2541228.2555296"],"URL":"https:\/\/doi.org\/10.1145\/2541228.2555296","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2013,12]]},"assertion":[{"value":"2013-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}