{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T20:44:15Z","timestamp":1763585055585,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,7,15]],"date-time":"2015-07-15T00:00:00Z","timestamp":1436918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ARTEMIS project","award":["COPCAMS id. 332913"],"award-info":[{"award-number":["COPCAMS id. 332913"]}]},{"name":"Swissuniversities through the Platform for Advanced Computing Initiative"},{"name":"LIACS from Intel Corporation"},{"name":"Google Europe Fellowship in Efficient Computing"},{"name":"European FP7 project","award":["CARP id. 287767"],"award-info":[{"award-number":["CARP id. 287767"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2015,8,13]]},"abstract":"<jats:p>Abstract mathematical representations such as integer polyhedra have been shown to be useful to precisely analyze computational kernels and to express complex loop transformations. Such transformations rely on abstract syntax tree (AST) generators to convert the mathematical representation back to an imperative program. Such generic AST generators avoid the need to resort to transformation-specific code generators, which may be very costly or technically difficult to develop as transformations become more complex. Existing AST generators have proven their effectiveness, but they hit limitations in more complex scenarios. Specifically, (1) they do not support or may fail to generate control flow for complex transformations using piecewise schedules or mappings involving modulo arithmetic; (2) they offer limited support for the specialization of the generated code exposing compact, straightline, vectorizable kernels with high arithmetic intensity necessary to exploit the peak performance of modern hardware; (3) they offer no support for memory layout transformations; and (4) they provide insufficient control over the AST generation strategy, preventing their application to complex domain-specific optimizations.<\/jats:p>\n          <jats:p>We present a new AST generation approach that extends classical polyhedral scanning to the full generality of Presburger arithmetic, including existentially quantified variables and piecewise schedules, and introduce new optimizations for the detection of components and shifted strides. Not limiting ourselves to control flow generation, we expose functionality to generate AST expressions from arbitrary piecewise quasi-affine expressions, which enables the use of our AST generator for data-layout transformations. We complement this with support for specialization by polyhedral unrolling, user-directed versioning, and specialization of AST expressions according to the location at which they are generated, and we complete this work with fine-grained user control over the AST generation strategies used. Using this generalized idea of AST generation, we present how to implement complex domain-specific transformations without the need to write specialized code generators, but instead relying on a generic AST generator parametrized to a specific problem domain.<\/jats:p>","DOI":"10.1145\/2743016","type":"journal-article","created":{"date-parts":[[2015,7,17]],"date-time":"2015-07-17T13:21:25Z","timestamp":1437139285000},"page":"1-50","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":47,"title":["Polyhedral AST Generation Is More Than Scanning Polyhedra"],"prefix":"10.1145","volume":"37","author":[{"given":"Tobias","family":"Grosser","sequence":"first","affiliation":[{"name":"INRIA and \u00c9COLE NORMALE SUP\u00c9RIEURE, Paris, France"}]},{"given":"Sven","family":"Verdoolaege","sequence":"additional","affiliation":[{"name":"INRIA, \u00c9COLE NORMALE SUP\u00c9RIEURE and KU Leuven, Paris, France"}]},{"given":"Albert","family":"Cohen","sequence":"additional","affiliation":[{"name":"INRIA and \u00c9COLE NORMALE SUP\u00c9RIEURE, Paris, France"}]}],"member":"320","published-online":{"date-parts":[[2015,7,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/109625.109631"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.107"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1025127.1025992"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628071.2628106"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375595"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254123"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/380466.380471"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/1988220302431"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01379404"},{"volume-title":"Encyclopedia of Parallel Computing","author":"Feautrier Paul","key":"e_1_2_1_11_1","unstructured":"Paul Feautrier and Christian Lengauer. 2011. The polyhedron model. In Encyclopedia of Parallel Computing, D. Padua (Ed.). Springer, 1581--1592."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-006-0012-3"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2003.1239870"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007516818651"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2544137.2544160"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626412500107"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2751205.2751248"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2010.5470459"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2464996.2467268"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2304576.2304619"},{"volume-title":"Programming Languages C","author":"ISO.","key":"e_1_2_1_21_1","unstructured":"ISO. 1999. ISO\/IEC 9899:1999: Programming Languages C. International Organization for Standardization."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/567097.567101"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICAPP.1995.472180"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/528717.796653"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1362622.1362691"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462187"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025117523902"},{"key":"e_1_2_1_28_1","unstructured":"Louis-No\u00ebl Pouchet. 2012. PolyBench\/C 3.2. Retrieved June 8 2015 from http:\/\/www.cs.ucla.edu\/&sim;pouchet\/software\/polybench\/."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375594"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2007.21"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/263580.263637"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/183432.183525"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007554627716"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250780"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.29"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_16"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2544137.2544141"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888390.1888455"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 1st International Workshop on Polyhedral Compilation Techniques (IMPACT\u201911)","author":"Verdoolaege Sven","year":"2011","unstructured":"Sven Verdoolaege. 2011. Counting affine calculator and applications. In Proceedings of the 1st International Workshop on Polyhedral Compilation Techniques (IMPACT\u201911)."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 5th International Workshop on Polyhedral Compilation Techniques (IMPACT\u201915)","author":"Verdoolaege Sven","year":"2015","unstructured":"Sven Verdoolaege. 2015. Integer set coalescing. In Proceedings of the 5th International Workshop on Polyhedral Compilation Techniques (IMPACT\u201915)."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 2nd International Workshop on Polyhedral Compilation Techniques (IMPACT\u201912)","author":"Verdoolaege Sven","year":"2012","unstructured":"Sven Verdoolaege and Tobias Grosser. 2012. Polyhedral extraction tool. In Proceedings of the 2nd International Workshop on Polyhedral Compilation Techniques (IMPACT\u201912). http:\/\/impact.gforge.inria.fr\/impact2012\/workshop_IMPACT\/verdoolaege.pdf."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 4th International Workshop on Polyhedral Compilation Techniques. http:\/\/impact.gforge.inria.fr\/impact2014\/papers\/impact2014-verdoolaege.pdf.","author":"Verdoolaege Sven","year":"2014","unstructured":"Sven Verdoolaege, Serge Guelton, Tobias Grosser, and Albert Cohen. 2014. Schedule trees. In Proceedings of the 4th International Workshop on Polyhedral Compilation Techniques. http:\/\/impact.gforge.inria.fr\/impact2014\/papers\/impact2014-verdoolaege.pdf."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2362389.2362390"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2400682.2400713"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015460304860"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 25th International Workshop on Languages and Compilers for Parallel Computing. http:\/\/people.rennes.inria.fr\/Tomofumi.Yuki\/papers\/yuki-lcpc2012","author":"Yuki Tomofumi","year":"2012","unstructured":"Tomofumi Yuki, Gautam Gupta, DaeGon Kim, Tanveer Pathan, and Sanjay Rajopadhye. 2012. AlphaZ: A system for design space exploration in the polyhedral model. In Proceedings of the 25th International Workshop on Languages and Compilers for Parallel Computing. http:\/\/people.rennes.inria.fr\/Tomofumi.Yuki\/papers\/yuki-lcpc2012.pdf."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/2555692.2555707"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2743016","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2743016","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:34Z","timestamp":1750227394000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2743016"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,15]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,8,13]]}},"alternative-id":["10.1145\/2743016"],"URL":"https:\/\/doi.org\/10.1145\/2743016","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2015,7,15]]},"assertion":[{"value":"2014-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}