{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T17:30:16Z","timestamp":1771954216020,"version":"3.50.1"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["406377\/2018-9"],"award-info":[{"award-number":["406377\/2018-9"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2020,11,13]]},"abstract":"<jats:p>\n            This paper describes a compiler optimization to eliminates dynamic occurrences of expressions in the format\n            <jats:italic>a<\/jats:italic>\n            \u2190\n            <jats:italic>a<\/jats:italic>\n            \u2295\n            <jats:italic>b<\/jats:italic>\n            \u2297\n            <jats:italic>c<\/jats:italic>\n            . The operation \u2295 must admit an identity element\n            <jats:italic>z<\/jats:italic>\n            , such that\n            <jats:italic>a<\/jats:italic>\n            \u2295\n            <jats:italic>z<\/jats:italic>\n            =\n            <jats:italic>a<\/jats:italic>\n            . Also,\n            <jats:italic>z<\/jats:italic>\n            must be the absorbing element of \u2297, such that\n            <jats:italic>b<\/jats:italic>\n            \u2297\n            <jats:italic>z<\/jats:italic>\n            =\n            <jats:italic>z<\/jats:italic>\n            \u2297\n            <jats:italic>c<\/jats:italic>\n            =\n            <jats:italic>z<\/jats:italic>\n            . Semirings where \u2295 is the additive operator and \u2297 is the multiplicative operator meet this contract. This pattern is common in high-performance benchmarks\u2014its canonical representative being the multiply-add operation\n            <jats:italic>a<\/jats:italic>\n            \u2190\n            <jats:italic>a<\/jats:italic>\n            +\n            <jats:italic>b<\/jats:italic>\n            \u00d7\n            <jats:italic>c<\/jats:italic>\n            . However, several other expressions involving arithmetic and logic operations satisfy the required algebra. We show that the runtime elimination of such assignments can be implemented in a performance-safe way via online profiling. The elimination of dynamic redundancies involving identity and absorbing elements in 35 programs of the LLVM test suite that present semiring patterns brings an average speedup of 1.19x (total optimized time over total unoptimized time) on top of clang -O3. When projected onto the entire test suite (259 programs) the optimization leads to a speedup of 1.025x. Once added onto clang, semiring optimizations approximates it to TACO, a specialized tensor compiler.\n          <\/jats:p>","DOI":"10.1145\/3428199","type":"journal-article","created":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T23:40:14Z","timestamp":1606261214000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Semiring optimizations: dynamic elision of expressions with identity and absorbing elements"],"prefix":"10.1145","volume":"4","author":[{"given":"Guilherme Vieira","family":"Leobas","sequence":"first","affiliation":[{"name":"Federal University of Minas Gerais, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0375-1657","authenticated-orcid":false,"given":"Fernando Magno Quint\u00e3o","family":"Pereira","sequence":"additional","affiliation":[{"name":"Federal University of Minas Gerais, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96983-1_51"},{"key":"e_1_2_2_2_1","first-page":"133","article-title":"Characterization of Silent Stores. In PACT. IEEE, Washington","author":"Bell Gordon B.","year":"2000","journal-title":"DC, USA"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2926697.2926704"},{"key":"e_1_2_2_4_1","first-page":"91","article-title":"Optimal and Eficient Speculation-Based Partial Redundancy Elimination","author":"Cai Qiong","year":"2003","journal-title":"CGO. IEEE, USA"},{"key":"e_1_2_2_5_1","first-page":"259","article-title":"Value Profiling","author":"Calder Brad","year":"1997","journal-title":"MICRO. IEEE, USA"},{"key":"e_1_2_2_6_1","volume-title":"Vectorizing Compilers: A Test Suite and Results. In Supercomputing (Orlando, Florida, USA)","author":"Callahan D.","year":"1988"},{"key":"e_1_2_2_7_1","volume-title":"TVM: An Automated End-to-end Optimizing Compiler for Deep Learning. In OSDI (Carlsbad, CA, USA)","author":"Chen Tianqi","year":"2018"},{"key":"e_1_2_2_8_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","edition":"3"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75280"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/301618.301683"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"David Hilbert. 1904. Die Theorie der algebraischen Zahlk\u00f6rper. Jahresbericht der Deutschen Mathematiker-Vereinigung Germany.  David Hilbert. 1904. Die Theorie der algebraischen Zahlk\u00f6rper. Jahresbericht der Deutschen Mathematiker-Vereinigung Germany.","DOI":"10.1007\/978-3-663-16019-9_4"},{"key":"e_1_2_2_12_1","volume-title":"Hough and Mike Cowlishaw","author":"David","year":"2019"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205185"},{"key":"e_1_2_2_14_1","volume-title":"Reconsidering Complex Branch Predictors. In HPCA (HPCA '03)","author":"Jim\u00e9nez Daniel A.","year":"2003"},{"key":"e_1_2_2_15_1","first-page":"27","article-title":"Detecting and Mitigating Data-dependent DRAM Failures by Exploiting Current Memory Content. In MICRO. ACM, New York","author":"Khan Samira","year":"2017","journal-title":"NY, USA"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428199","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428199","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:56Z","timestamp":1750197776000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428199"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":15,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2020,11,13]]}},"alternative-id":["10.1145\/3428199"],"URL":"https:\/\/doi.org\/10.1145\/3428199","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,13]]},"assertion":[{"value":"2020-11-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}