{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T10:44:11Z","timestamp":1753440251371,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T00:00:00Z","timestamp":1634256000000},"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":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2021,10,20]]},"abstract":"<jats:p>Presburger arithmetic provides the mathematical core for the polyhedral compilation techniques that drive analytical cache models, loop optimization for ML and HPC, formal verification, and even hardware design. Polyhedral compilation is widely regarded as being slow due to the potentially high computational cost of the underlying Presburger libraries. Researchers typically use these libraries as powerful black-box tools, but the perceived internal complexity of these libraries, caused by the use of C as the implementation language and a focus on end-user-facing documentation, holds back broader performance-optimization efforts. With FPL, we introduce a new library for Presburger arithmetic built from the ground up in modern C++. We carefully document its internal algorithmic foundations, use lightweight C++ data structures to minimize memory management costs, and deploy transprecision computing across the entire library to effectively exploit machine integers and vector instructions. On a newly-developed comprehensive benchmark suite for Presburger arithmetic, we show a 5.4x speedup in total runtime over the state-of-the-art library isl in its default configuration and 3.6x over a variant of isl optimized with element-wise transprecision computing. We expect that the availability of a well-documented and fast Presburger library will accelerate the adoption of polyhedral compilation techniques in production compilers.<\/jats:p>","DOI":"10.1145\/3485539","type":"journal-article","created":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T19:18:28Z","timestamp":1634325508000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["FPL: fast Presburger arithmetic through transprecision"],"prefix":"10.1145","volume":"5","author":[{"given":"Arjun","family":"Pitchanathan","sequence":"first","affiliation":[{"name":"IIIT Hyderabad, India"}]},{"given":"Christian","family":"Ulmann","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}]},{"given":"Michel","family":"Weber","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}]},{"given":"Torsten","family":"Hoefler","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}]},{"given":"Tobias","family":"Grosser","sequence":"additional","affiliation":[{"name":"University of Edinburgh, UK"}]}],"member":"320","published-online":{"date-parts":[[2021,10,15]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/3314872.3314896"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2007.08.001"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1062374"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379022.1375595"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3291168.3291211"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066100.1066102"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/1988220302431"},{"key":"e_1_2_2_8_1","unstructured":"Alexis Fouilhe. 2015. Revisiting the abstract domain of polyhedra : constraints-only representation and formal proof. Universit\u00e9 Grenoble Alpes. https:\/\/tel.archives-ouvertes.fr\/tel-01286086  Alexis Fouilhe. 2015. Revisiting the abstract domain of polyhedra : constraints-only representation and formal proof. Universit\u00e9 Grenoble Alpes. https:\/\/tel.archives-ouvertes.fr\/tel-01286086"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626412500107"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2925426.2926286"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428263"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314606"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3242953.3242964"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02658-4_52"},{"key":"e_1_2_2_15_1","first-page":"20742","volume-title":"MD","author":"Kelly Wayne","year":"1996"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2682923.2682950"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/977395.977673"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO51591.2021.9370308"},{"key":"e_1_2_2_19_1","unstructured":"Vincent Loechner. 1999. PolyLib: A library for manipulating parameterized polyhedra.  Vincent Loechner. 1999. PolyLib: A library for manipulating parameterized polyhedra."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2804870.2804887"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09766-4_515"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53413-7_19"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273442.1250746"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385989"},{"key":"e_1_2_2_25_1","doi-asserted-by":"crossref","unstructured":"Arjun Pitchanathan Christian Ulmann Michel Weber Torsten Hoefler and Tobias Grosser. 2021. Replication Package for Article: FPL: Fast Presburger Arithmetic through Transprecision. https:\/\/doi.org\/10.1145\/3462302  Arjun Pitchanathan Christian Ulmann Michel Weber Torsten Hoefler and Tobias Grosser. 2021. Replication Package for Article: FPL: Fast Presburger Arithmetic through Transprecision. https:\/\/doi.org\/10.1145\/3462302","DOI":"10.1145\/3462302"},{"volume-title":"Polybench: The polyhedral benchmark suite.","year":"2012","author":"Pouchet Louis-No\u00ebl","key":"e_1_2_2_26_1"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2435264.2435273"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/17634"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/34002.34003"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2738000"},{"volume-title":"Tensor Comprehensions: Framework-Agnostic High-Performance Machine Learning Abstractions. arXiv e-prints, Article arXiv:1802.04730, Feb., arXiv:1802.04730 pages. arxiv:cs.PL\/1802.04730.","year":"2018","author":"Vasilache Nicolas","key":"e_1_2_2_31_1"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888390.1888455"},{"volume-title":"International Workshop on Polyhedral Compilation Techniques, Date: 2015\/01\/19-2015\/01\/19","year":"2015","author":"Verdoolaege Sven","key":"e_1_2_2_33_1"},{"key":"e_1_2_2_34_1","unstructured":"Sven Verdoolaege. 2016. Presburger formulas and polyhedral compilation.  Sven Verdoolaege. 2016. Presburger formulas and polyhedral compilation."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2400682.2400713"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485539","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485539","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:40Z","timestamp":1750191520000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485539"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,15]]},"references-count":35,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2021,10,20]]}},"alternative-id":["10.1145\/3485539"],"URL":"https:\/\/doi.org\/10.1145\/3485539","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2021,10,15]]},"assertion":[{"value":"2021-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}