{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T13:23:21Z","timestamp":1770902601168,"version":"3.50.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,3,1]],"date-time":"2023-03-01T00:00:00Z","timestamp":1677628800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>\n            A typical compiler flow relies on a uni-directional sequence of translation\/optimization steps that\n            <jats:italic>lower<\/jats:italic>\n            the program abstract representation, making it hard to preserve higher-level program information across each transformation step. On the other hand, modern ISA extensions and hardware accelerators can benefit from the compiler\u2019s ability to detect and\n            <jats:italic>raise<\/jats:italic>\n            program idioms to acceleration instructions or optimized library calls. Although recent works based on Multi-Level IR (MLIR) have been proposed for code raising, they rely on specialized languages, compiler recompilation, or in-depth dialect knowledge. This article presents\n            <jats:italic>Source Matching and Rewriting<\/jats:italic>\n            (SMR), a user-oriented source-code-based approach for MLIR idiom matching and rewriting that does not require a compiler expert\u2019s intervention. SMR uses a two-phase automaton-based DAG-matching algorithm inspired by early work on tree-pattern matching. First, the idiom\n            <jats:italic>Control-Dependency Graph<\/jats:italic>\n            (CDG) is matched against the program\u2019s CDG to rule out code fragments that do not have a control-flow structure similar to the desired idiom. Second, candidate code fragments from the previous phase have their\n            <jats:italic>Data-Dependency Graphs<\/jats:italic>\n            (DDGs) constructed and matched against the idiom DDG. Experimental results show that SMR can effectively match idioms from Fortran (FIR) and C (CIL) programs while raising them as BLAS calls to improve performance. Additional experiments also show performance improvements when using SMR to enable code replacement in areas like approximate computing and hardware acceleration.\n          <\/jats:p>","DOI":"10.1145\/3571283","type":"journal-article","created":{"date-parts":[[2022,11,18]],"date-time":"2022-11-18T12:01:26Z","timestamp":1668772886000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Source Matching and Rewriting for MLIR Using String-Based Automata"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3131-741X","authenticated-orcid":false,"given":"Vinicius","family":"Espindola","sequence":"first","affiliation":[{"name":"Institute of Computing - UNICAMP, Campinas, Brazil"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4417-163X","authenticated-orcid":false,"given":"Luciano","family":"Zago","sequence":"additional","affiliation":[{"name":"Institute of Computing - UNICAMP, Campinas, Brazil"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1214-3431","authenticated-orcid":false,"given":"Herv\u00e9","family":"Yviquel","sequence":"additional","affiliation":[{"name":"Institute of Computing - UNICAMP, Campinas, Brazil"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4869-5190","authenticated-orcid":false,"given":"Guido","family":"Araujo","sequence":"additional","affiliation":[{"name":"Institute of Computing - UNICAMP, Campinas, Brazil"}]}],"member":"320","published-online":{"date-parts":[[2023,3]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","unstructured":"Mark F. Adams Jed Brown John Shalf Brian Van Straalen Erich Strohmaier and Samuel Williams. 2014. HPGMG 1.0: A Benchmark for Ranking High Performance Computing Systems. University of California Lawrence Berkeley National Laboratory 11 pages. https:\/\/escholarship.org\/uc\/item\/00r9w79m.","DOI":"10.2172\/1131029"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/69558.75700"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321970"},{"key":"e_1_3_2_5_2","volume-title":"Compilers: Principles, Techniques, and Tools","author":"Aho Alfred V.","year":"2006","unstructured":"Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. 2006. Compilers: Principles, Techniques, and Tools (2nd Edition). Addison Wesley, Boston, MA."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1391956.1391959"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394277.3401836"},{"key":"e_1_3_2_8_2","first-page":"141","volume-title":"Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing (LCPC\u201994)","author":"Blume William","year":"1994","unstructured":"William Blume, Rudolf Eigenmann, Keith Faigin, John Grout, Jay Hoeflinger, David A. Padua, Paul Petersen, William M. Pottenger, Lawrence Rauchwerger, Peng Tu, and Stephen Weatherford. 1994. Polaris: Improving the effectiveness of parallelizing compilers. In Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing (LCPC\u201994). Springer-Verlag, Berlin, 141\u2013154."},{"key":"e_1_3_2_9_2","article-title":"High performance code generation in MLIR: An early case study with GEMM","author":"Bondhugula Uday","year":"2020","unstructured":"Uday Bondhugula. 2020. High performance code generation in MLIR: An early case study with GEMM. CoRR abs\/2003.00532 (2020), 23. https:\/\/arxiv.org\/abs\/2003.00532","journal-title":"CoRR"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO51591.2021.9370332"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3410463.3414635"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3372266"},{"key":"e_1_3_2_13_2","unstructured":"Flang Compiler. 2019. F18 LLVM Project (fir-dev branch). https:\/\/github.com\/flang-compiler\/f18-llvm-project\/tree\/fir-dev."},{"key":"e_1_3_2_14_2","unstructured":"MLIR contributors. 2020. MLIR Documentation. https:\/\/mlir.llvm.org\/docs\/."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/c2009-0-27982-7"},{"key":"e_1_3_2_16_2","series-title":"Proceedings of the 38th International Conference on Machine Learning","first-page":"2244","volume":"139","author":"Cummins Chris","year":"2021","unstructured":"Chris Cummins, Zacharias V. Fisches, Tal Ben-Nun, Torsten Hoefler, Michael F. P. O\u2019Boyle, and Hugh Leather. 2021. ProGraML: A graph-based program representation for data flow analysis and compiler optimizations. In Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 139), Marina Meila and Tong Zhang (Eds.). PMLR, A Virtual Conference, 2244\u20132253. https:\/\/proceedings.mlr.press\/v139\/cummins21a.html."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO51591.2021.9370322"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3459010"},{"key":"e_1_3_2_19_2","unstructured":"FFmpeg Developers. 2021. FFmpeg tool. https:\/\/ffmpeg.org\/."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2022.102982"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/151640.151642"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3235029"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/DAC18074.2021.9586216"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3377555.3377893"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3173162.3173182"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/1356052.1356053"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626412500107"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322295"},{"key":"e_1_3_2_29_2","unstructured":"Daniel Holden. 2015. Cello: Higher level programming in C. https:\/\/libcello.org\/."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908117"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2004.1281665"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO51591.2021.9370308"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24644-2_35"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3446804.3446844"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-85665-6_1"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/305138.305230"},{"key":"e_1_3_2_37_2","unstructured":"Sasa Misailovic Daniel M. Roy and Martin Rinard. 2011. Probabilistic and statistical analysis of perforated patterns Massachusetts Institute of Technology Computer Science & Artificial Intelligence Laboratory. http:\/\/hdl.handle.net\/1721.1\/60675."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/PACT52795.2021.00011"},{"key":"e_1_3_2_39_2","unstructured":"Mohanish Narayan and Louis-Noel Pouchet. 2012. PolyBench\/Fortran 1.0. https:\/\/www.cs.colostate.edu\/pouchet\/software\/polybench\/polybench-fortran.html."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73586"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/224538.224655"},{"key":"e_1_3_2_42_2","unstructured":"Joseph Redmon. 2016. Darknet: Open Source Neural Networks in C. http:\/\/pjreddie.com\/darknet\/."},{"key":"e_1_3_2_43_2","unstructured":"CIL repository. 2021. Commit. https:\/\/github.com\/compiler-tree-technologies\/cil\/commit\/195acc33e14715da9f5a1746b489814d56c015f7."},{"key":"e_1_3_2_44_2","unstructured":"FIR repository. 2021. Commit. https:\/\/github.com\/flang-compiler\/f18-llvm-project\/commit\/8abd290c2c791c26cd1237b218def1b85998d403."},{"key":"e_1_3_2_45_2","unstructured":"LLVM\/MLIR repository. 2021. Commit. https:\/\/github.com\/llvm\/llvm-project\/commit\/1fdec59bffc11ae37eb51a1b9869f0696bfd5312."},{"key":"e_1_3_2_46_2","unstructured":"River Riddle. 2021. Pattern Descriptor Language. https:\/\/drive.google.com\/file\/d\/17WYUvlmCzNTiqLaxWf_uz4GiLm3QVoEV\/view."},{"key":"e_1_3_2_47_2","unstructured":"River Riddle and Jeff Niu. 2021. Public communication at LLVM\/MLIR Discourse. https:\/\/llvm.discourse.group\/t\/how-can-i-use-pdl-to-match-affine-code\/4837."},{"key":"e_1_3_2_48_2","unstructured":"Offensive Security. 2021. The official Exploit Database repository. https:\/\/github.com\/offensive-security\/exploitdb."},{"key":"e_1_3_2_49_2","unstructured":"Compiler Tree Technologies. 2021. CIL. https:\/\/github.com\/compiler-tree-technologies\/cil."},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523439"},{"key":"e_1_3_2_51_2","unstructured":"Zhang Xianyi and Martin Kroeker. 2020. OpenBLAS: An optimized BLAS library. https:\/\/www.openblas.net\/."},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/MDAT.2015.2505723"},{"key":"e_1_3_2_53_2","first-page":"23","article-title":"MISIM: An end-to-end neural code similarity system","volume":"2006","author":"Ye Fangke","year":"2020","unstructured":"Fangke Ye, Shengtian Zhou, Anand Venkat, Ryan Marcus, Nesime Tatbul, Jesmin Jahan Tithi, Paul Petersen, Timothy G. Mattson, Tim Kraska, Pradeep Dubey, Vivek Sarkar, and Justin Gottschlich. 2020. MISIM: An end-to-end neural code similarity system. CoRR abs\/2006.05265 (2020), 23. arXiv:2006.05265 https:\/\/arxiv.org\/abs\/2006.05265.","journal-title":"CoRR"},{"key":"e_1_3_2_54_2","unstructured":"Jerry Zhao Ben Korpan Abraham Gonzalez and Krste Asanovic. 2020. SonicBOOM: The 3rd Generation Berkeley Out-of-Order Machine. http:\/\/people.eecs.berkeley.edu\/krste\/papers\/SonicBOOM-CARRV2020.pdf."}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571283","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3571283","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:22Z","timestamp":1750183702000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571283"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3571283"],"URL":"https:\/\/doi.org\/10.1145\/3571283","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3]]},"assertion":[{"value":"2022-05-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-27","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}