1 <!DOCTYPE HTML PUBLIC
"-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
3 <!-- Material used from: HTML 4.01 specs: http://www.w3.org/TR/html401/ -->
6 <META http-equiv=
"Content-Type" content=
"text/html; charset=ISO-8859-1">
7 <title>Polly - Polyhedral optimizations for LLVM
</title>
8 <link type=
"text/css" rel=
"stylesheet" href=
"menu.css">
9 <link type=
"text/css" rel=
"stylesheet" href=
"content.css">
10 <script src=
"video-js/video.js" type=
"text/javascript" charset=
"utf-8"></script>
11 <script type=
"text/javascript">
12 VideoJS
.setupAllWhenReady();
15 <!-- Include the VideoJS Stylesheet -->
16 <link rel=
"stylesheet" href=
"video-js/video-js.css" type=
"text/css" media=
"screen" title=
"Video JS">
20 <!--#include virtual="menu.html.incl"-->
22 <!--*********************************************************************-->
24 <!--*********************************************************************-->
26 <p> Polly is a high-level loop and data-locality optimizer and optimization
27 infrastructure for LLVM. It uses an abstract mathematical representation based
28 on integer polyhedra to analyze and optimize the memory access pattern of a
29 program. We currently perform classical loop transformations, especially
30 tiling and loop fusion to improve data-locality. Polly can also exploit
31 OpenMP level parallelism, expose SIMDization opportunities. Work has also be
32 done in the area of automatic GPU code generation.
</p>
34 For many users, however, it's not the existing optimizations in Polly that are
35 of most interest, but the new analyses and optimizations enabled by the Polly
37 <a href=
"http://polyhedral.info">polyhedral.info
</a> you can get an idea of
38 what has already been done and what is possible in the context of polyhedral
41 <!--=====================================================================-->
43 <!--=====================================================================-->
46 <tr><td><b>2017</b></td></tr>
47 <tr><td width=
"120"><p>September
</p></td>
49 <h4>High-Performance Generalized Matrix Multiplication
</h4>
50 Polly automatically detects and optimizes generalized matrix
51 multiplication, the computation C
← α ⊗ C
⊕ β
52 ⊗ A
⊗ B, where A, B, and C are three appropriately sized
53 matrices,
⊕ and
⊗ operations are originating from the
54 corresponding matrix semiring, and
α and
β are constants, and
55 beta is not equal to zero. It allows to obtain the highly optimized form
56 structured similar to the expert implementation of GEMM that can be found
57 in GotoBLAS and its successors.
58 <h4>The performance evaluation of GEMM
</h4>
59 <img src=
"images/GEMM_double.png" /><br />
61 <tr><td><b>2017</b></td></tr>
62 <tr><td width=
"120"><p>January
</p></td>
64 <a href=
"http://impact.gforge.inria.fr/impact2017">IMPACT
2017</a> program
65 announced. Join IMPACT
2017 on January
23rd in Stockholm
<a
66 href=
"https://www.hipeac.net/2017/stockholm/">@HiPEAC'
17</a>.
69 <tr><td><b>2016</b></td></tr>
70 <tr><td width=
"120"><p>August
</p></td>
72 <a href=
"http://impact.gforge.inria.fr/impact2017">IMPACT
2017</a> the
7th
73 International Workshop on Polyhedral Compilation Techniques will take place
74 at January
23-
25,
2017 together with HiPEAC
2017 in Stockholm, Sweden. It is
75 a great opportunity to discuss and present work on Polyhedral Compilation,
76 including work on Polly.
79 <tr><td width=
"120"><p>April
</p></td>
81 A source checkout that contains Polly now provides Polly functionality
82 by default in clang/opt/bugpoint without the need to load an additional
86 <tr><td><b>2015</b></td></tr>
87 <tr><td width=
"120"><p>July
</p></td>
89 <h4>AST Generation Paper published in TOPLAS
</h4>
90 The July issue of TOPLAS contains a
50 page discussion of the AST
91 generation techniques used in Polly. This discussion gives not only an
92 in-depth description of how we (re)generate an imperative AST from our
93 polyhedral based mathematical program description, but also gives
94 interesting insights about:
96 <li><b>Schedule trees:
</b> A tree-based mathematical program description
97 that enables us to perform loop transformations on an abstract level,
98 while issues like the generation of the correct loop structure and loop
99 bounds will be taken care of by our AST generator.
100 <li><b>Polyhedral unrolling:
</b> We discuss techniques that allow the
101 unrolling of non-trivial loops in the context of parameteric loop bounds,
102 complex tile shapes and conditionally executed statements. Such unrolling
103 support enables the generation of predicated code e.g. in the context of
105 <li><b>Isolation for full/partial tile separation:
</b> We discuss native
106 support for handling full/partial tile separation and -- in general --
107 native support for isolation of boundary cases to enable smooth code
108 generation for core computations.
109 <li><b>AST generation with modulo constraints:
</b> We discuss how modulo
110 mappings are lowered to efficient C/LLVM code.
111 <li><b>User-defined constraint sets for run-time checks
</b> We discuss how
112 arbitrary sets of constraints can be used to automatically create run-time
113 checks that ensure a set of constrainst actually hold. This feature is
114 very useful to verify at run-time various assumptions that have been taken
115 program optimization.
118 <a href=
"http://www.grosser.es#pub-polyhedral-AST-generation">
119 <em>Polyhedral AST generation is more than scanning polyhedra
</em></a><br />
120 Tobias Grosser, Sven Verdoolaege, Albert Cohen
<br />
121 ACM Transations on Programming Languages and Systems (TOPLAS),
37(
4),
130 <tr><td width=
"120"><p>February
</p></td>
132 <h4>Polly allows now non-affine subregions
</h4>
133 Data-dependent or floating point conditionals inside a SCoP can now be
134 overapproximated in order to increase the applicability on general purpose
138 <tr><td><b>2014</b></td></tr>
139 <tr><td width=
"120"><p>August
</p></td>
141 <h4>Polly drops the support of ScopLib and the external optimizer PoCC
</h4>
142 The support for ScopLib as an exchange format has been removed as recent
143 versions of clan, candl and pluto all support the OpenScop exchange format.
145 The support of the external optmizer PoCC has been dropped in favor of the
146 isl optimizer (default) and the still available pluto support.
149 <tr><td><b>2014</b></td></tr>
150 <tr><td width=
"120"><p>June
</p></td>
152 <h4>Polly can be built without GPL licensed software
</h4> After Sebastian
154 and David Peixotto's (both Qualcomm) recent
<a
155 href=
"http://repo.or.cz/w/isl.git/commit/60703e3ee89b9d5d4d1afb6a3f611292c0884574">commit
</a>
156 to isl, isl's latest development version can be built with imath instead of
157 GMP. With both CLooG and gmp having become optional, the last obilgatory
158 dependency to GPL licensed software has been removed. Now Polly only depends
159 on isl (and the included imath), which are both MIT licensed.
162 <tr><td width=
"120"><p>April
</p></td>
164 <h4>Polly Phone Call -
23April
</h4>
165 We had a polly phone call about delinearizing array accesses (II)
<a
166 href=
"https://docs.google.com/document/d/1IZewI8Up0iEkCNIPr6gVtwJxF7RV6KmXkdwOBM_Q5Cs/edit?usp=sharing ">Meeting notes
</a> are available online.
167 <h4>Polly Phone Call -
17th April
</h4>
168 We had a polly phone call about delinearizing array accesses
<a
169 href=
"https://docs.google.com/document/d/14d3ehkH2MsvBdqsEOSYjysH0Ztyzb75Lp843hnxh2IA/edit?usp=sharing">Meeting notes
</a> are available online.
170 <h4>Polly Phone Call -
10th April
</h4>
171 We had a polly phone call.
<a
172 href=
"https://docs.google.com/document/d/12W-qZjiZGEQ_lVrob4OzvKJI3EooonC-ap1b9f9KCUE/edit?usp=sharing">Meeting notes
</a> are available online.
173 <h4>Polly Phone Call -
4th April
</h4>
174 We had a polly phone call.
<a
175 href=
"https://drive.google.com/folderview?id=0B7OMOXTgCYIUWkpJbWVJcW04ams&usp=sharing">Meeting notes
</a> are available online.
178 <tr><td width=
"120"><p>March
</p></td>
180 <h4>Static link Polly into tools
</h4> Polly can now be configured with 'cmake
181 -D LINK_POLLY_INTO_TOOLS:Bool=ON' to be statically linked in the tools (opt,
182 bugpoint, and clang.) This makes it easier to use polly without having to load
183 a shared library, and it also reduces the complexity of compiling Polly on
187 <tr><td width=
"120"><p>February
</p></td>
189 <h4>Polly presentation at FOSDEM
2014</h4> Polly was
<a
190 href=
"https://fosdem.org/2014/schedule/event/polly/">presented
</a> at the
191 FOSDEM LLVM developer's meeting.
192 <h4>New LLVM test-suite buildbots
</h4>
193 The set of
<a href=
"http://lab.llvm.org:8011/console?category=polly">Polly
194 buildbots
</a> has been extended. We now have
16 new blades that track
195 correctness and performance when compiling the LLVM test-suite. For now five
196 of them are used to provide
<a
197 href=
"http://llvm.org/perf/db_default/v4/nts/22463">fine granularity
198 reports
</a> (almost per-commit)
199 for 'clang -O3' (no polly). We also have six machines that track different
200 configurations of polly.
203 <tr><td width=
"120"><p>January
</p></td>
205 <h4>islplot released
</h4>
206 <a href=
"https://github.com/tobig/islplot">islplot
</a> is a library that
207 generates illustrations of integer sets and maps. It relies on
<a
208 href=
"http://repo.or.cz/w/isl.git">isl
</a> to model the integer sets and uses the
<a
209 href=
"https://pypi.python.org/pypi/islpy">islpy
</a> Python bindings to access
210 them. Plotting is performed with
<a
211 href=
"http://matplotlib.org">matplotlib
</a>. The following
<a
212 href=
"http://nbviewer.ipython.org/github/tobig/islplot/blob/master/notebooks/islplot-examples.ipynb">
213 Examples
</a> show its use.
216 <tr><td><b>2013</b></td></tr>
217 <tr><td width=
"120"><p>November
</p></td>
219 <h4>Loop optimization BoF at upcoming LLVM conference
</h4>
220 At the upcoming
<a href=
"http://llvm.org/devmtg/2013-11/#bof5">LLVM conference
221 </a> there will be a loop optimization BoF discussing Polly and other high
222 level loop optimizers.
225 <tr><td width=
"120"><p>October
</p></td>
227 <h4>Automatic code coverage and static analysis tests
</h4>
228 Sylvestre Ledru set up automatic tests for
<a
229 href=
"http://llvm.org/reports/coverage/">code coverage
</a> and
230 <a href=
"http://llvm.org/reports/scan-build/">static analysis
</a>
231 which run at least once a day and which include results for Polly.
232 <h4>Move to CLooG
0.18.1 and isl
0.12.1</h4>
233 With the move to an isl
0.12 version Polly can be compiled without the
234 need to link directly to GMP (if isl is used for code generation). Currently
235 isl is still internally using GMP, but private patches exist to also remove
236 this dependency. Without the use of GMP, a
<b>GPL free
</b> version of Polly
240 <tr><td><b>2012</b></td></tr>
241 <tr><td width=
"120"><p>December
</p></td>
243 <h4> New publication in the PPL Journal
246 We published a journal version of the Polly paper named
248 Polly - Performing polyhedral optimizations on a low-level intermediate
249 representation
</em> in the Parallel Processing Letters
2012.
251 <tr><td width=
"120"><p>September
</p></td>
253 <h4>Experimental support for the
<b>new isl code generator
</b></h4>
254 The code generator can be parameterized on a fine-grained
255 level. It gives direct control for example over unrolling, the amount of
256 control overhead and the code size. It can also be used to
257 create loops to handle border conditions or to perform full-partial tile
259 We also relicensed isl under the
<b>MIT license
</b>. This means, with the
260 exception of GMP (LGPL), there is no other (L)GPL licensed software used in
262 use of GMP is limited to a well defined interface. Replacing it with
263 a BSD licensed replacement is a tractable engineering project we would
264 be very interested in. For more information about isl see the
<a
265 href=
"http://www.kotnet.org/~skimo/isl/manual.pdf">isl manual
</a>.
268 <tr><td width=
"120"><p>July
</p></td>
270 <p> Polly can now be directly linked to the
<a
271 href=
"http://pluto-compiler.sourceforge.net/">Pluto optimizer
</a>. We were
272 already able to perform Pluto-like optimizations with Polly, as a similar
273 algorithm was added to isl half a year ago. However, being able to directly
274 compare with the original implementation will not only bring in competition in
275 the optimizer field. It will also allow new experiments with a cutting edge
277 This support was on of the outcomes of the
1-day Polly workshop and the
278 following week of joint work at IISC Bangalore and in cooperation with
283 <tr><td width=
"120"><p>February
</p></td>
285 <p>Polly is an official LLVM project, reachable at
<a
286 href=
"http://polly.llvm.org">http://polly.llvm.org
</a></p>
288 <tr><td width=
"120"><p>January
</p></td>
290 <p>Improved support for the isl scheduling optimizer
</p>
291 Polly can now automatically optimize all
<a
292 href=
"http://www.cse.ohio-state.edu/~pouchet/software/polybench/">polybench
293 2.0</a> kernels without the help of
294 an external optimizer. The compile time is reasonable and we can show
295 notable speedups for various kernels.
299 <tr><td><b><br/>2011</b></td></tr>
300 <tr><td width=
"120"><p>November
</p></td>
303 Talk at the
<a href=
"http://llvm.org/devmtg/2011-11/">
304 LLVM Developer Meeting
2011</a></p>
306 (Allows parameters in array subscript and max/signextend)
310 <td><p>October
</p></td>
312 <p>Polly can use the isl schedule optimizer
<br>
313 (The optimizer is similar to the one in Pluto, but it is part of isl)
318 <td><p>August
</p></td>
321 <a href=
"example_load_Polly_into_clang.html">Use Polly as
329 <p> Polly builder as part of the
<a
330 href=
"http://lab.llvm.org:8011/console">LLVM Buildbots
</a>
338 <p><a href=
"http://www.grosser.es">Tobias
</a> is founded for
340 href=
"http://research.google.com/university/relations/fellowship_recipients.html">
341 Google Europe Fellowship in Efficient Computing
</a>.
348 <td><p><a href=
"http://www.grosser.es">Tobias
</a>' diploma thesis and
349 Raghesh's master thesis. See our
<a
350 href=
"publications.html">list of publications
</a>.
</p></td>
354 <td><p>April
</p></td>
355 <td><p>Polly moves to the LLVM infrastructure (svn, bugtracker)
</p></td>
359 <td><p>March
</p></td>
360 <td><p>Presentation at
<a
361 href=
"http://impact2011.inrialpes.fr/">CGO/IMPACT
</a></p>
363 polybench
2.0 with vectorization and OpenMP code generation
</p>
367 <td><p>Februar
</p></td>
368 <td><p>pollycc - a script to automatically compile with
369 polyhedral optimizations
</p></td>
373 <td><p> Januar
</p></td>
374 <td><p> Basic OpenMP support, Alias analysis integration,
375 Pluto/POCC support
</p></td>
378 <tr><td><b><br>2010</b></td></tr>
380 <td><p> Dezember
</p></td>
381 <td><p>Basic vectorization support
</p></td>
385 <td><p> November
</p></td>
386 <td><p>Talk at the
<a
387 href=
"http://llvm.org/devmtg/2010-11/">LLVM Developer Meeting
</a> </p></td>
391 <td><p>October
</p></td>
392 <td><p>Dependency analysis
</p>
393 <p>Finished Phase
1 - Get something working
</p>
394 <p>Support scalar dependences and sequential SCoPs
</p>
399 <td><p>August
</p></td>
400 <td><p>RegionInfo pass committed to LLVM
</p>
401 <p>llvm-test suite compiles
</p>
407 <td><p>Code generation works for normal SCoPs.
</p></td>
412 <td><p>The CLooG AST can be parsed.
</p>
417 <td><p>April
</p></td>
418 <td><p>SCoPs can automatically be detected.
</p></td>
422 <td><p>March
</p></td>
423 <td><p>The RegionInfo framework is almost completed.
</p></td>
427 <td><p>February
</p></td>
428 <td><p>Translate a simple loop to Polly-IR and regenerate a loop structure
429 with CLooG works.
</p>
430 <p>ISL and CLooG are integrated.
</p></td>
436 <td><p>January
</p></td>
437 <td><p>The RegionInfo pass is finished.
</p></td>
440 <tr><td><b><br>2009</b></td></tr>
442 <td><p>End of the year
</p></td>
443 <td><p>Work on the infrastructure started.
</p></td>