| blob | 87642324eadb47ac0ce7fa080aa7708d3baeedbd |
3 <!-- Material used from: HTML 4.01 specs: http://www.w3.org/TR/html401/ -->
4 <html>
5 <head>
10 </head>
11 <body>
13 <!--#include virtual="menu.html.incl"-->
15 <!--*********************************************************************-->
17 <!--*********************************************************************-->
19 <p> Polly is a high-level loop and data-locality optimizer and optimization
20 infrastructure for LLVM. It uses an abstract mathematical representation based
21 on integer polyhedra to analyze and optimize the memory access pattern of a
22 program. We currently perform classical loop transformations, especially
23 tiling and loop fusion to improve data-locality. Polly can also exploit
24 OpenMP level parallelism, expose SIMDization opportunities.</p>
26 For many users, however, it's not the existing optimizations in Polly that are
27 of most interest, but the new analyses and optimizations enabled by the Polly
28 infrastructure. At
30 what has already been done and what is possible in the context of polyhedral
31 compilation.
33 <!--=====================================================================-->
35 <!--=====================================================================-->
40 <td>
42 Polly automatically detects and optimizes generalized matrix
47 beta is not equal to zero. It allows to obtain the highly optimized form
48 structured similar to the expert implementation of GEMM that can be found
49 in GotoBLAS and its successors.
52 </td>
55 <td>
59 </td>
60 </tr>
63 <td>
65 International Workshop on Polyhedral Compilation Techniques will take place
67 a great opportunity to discuss and present work on Polyhedral Compilation,
68 including work on Polly.
69 </td>
70 </tr>
72 <td>
73 A source checkout that contains Polly now provides Polly functionality
74 by default in clang/opt/bugpoint without the need to load an additional
75 module.
76 </td>
77 </tr>
80 <td>
82 The July issue of TOPLAS contains a 50 page discussion of the AST
83 generation techniques used in Polly. This discussion gives not only an
84 in-depth description of how we (re)generate an imperative AST from our
85 polyhedral based mathematical program description, but also gives
86 interesting insights about:
87 <ul>
89 that enables us to perform loop transformations on an abstract level,
90 while issues like the generation of the correct loop structure and loop
91 bounds will be taken care of by our AST generator.
93 unrolling of non-trivial loops in the context of parameteric loop bounds,
94 complex tile shapes and conditionally executed statements. Such unrolling
95 support enables the generation of predicated code e.g. in the context of
96 GPGPU computing.
98 support for handling full/partial tile separation and -- in general --
99 native support for isolation of boundary cases to enable smooth code
100 generation for core computations.
102 mappings are lowered to efficient C/LLVM code.
104 arbitrary sets of constraints can be used to automatically create run-time
105 checks that ensure a set of constraints actually hold. This feature is
106 very useful to verify at run-time various assumptions that have been taken
107 program optimization.
108 </ul>
112 Tobias Grosser, Sven Verdoolaege, Albert Cohen<br />
114 July 2015
116 <br>
117 <br>
118 <br>
119 <br>
120 </td>
121 </tr>
123 <td>
125 Data-dependent or floating point conditionals inside a SCoP can now be
126 overapproximated in order to increase the applicability on general purpose
127 code.
128 </td>
129 </tr>
132 <td>
134 The support for ScopLib as an exchange format has been removed as recent
135 versions of clan, candl and pluto all support the OpenScop exchange format.
137 The support of the external optimizer PoCC has been dropped in favor of the
138 isl optimizer (default) and the still available pluto support.
139 </td>
140 </tr>
143 <td>
145 Pop's
146 and David Peixotto's (both Qualcomm) recent <a
148 to isl, isl's latest development version can be built with imath instead of
149 GMP. With both CLooG and gmp having become optional, the last obligatory
150 dependency to GPL licensed software has been removed. Now Polly only depends
151 on isl (and the included imath), which are both MIT licensed.
152 </td>
153 </tr>
155 <td>
157 We had a polly phone call about delinearizing array accesses (II)<a
158 href="https://docs.google.com/document/d/1IZewI8Up0iEkCNIPr6gVtwJxF7RV6KmXkdwOBM_Q5Cs/edit?usp=sharing ">Meeting notes</a> are available online.
160 We had a polly phone call about delinearizing array accesses <a
161 href="https://docs.google.com/document/d/14d3ehkH2MsvBdqsEOSYjysH0Ztyzb75Lp843hnxh2IA/edit?usp=sharing">Meeting notes</a> are available online.
163 We had a polly phone call. <a
164 href="https://docs.google.com/document/d/12W-qZjiZGEQ_lVrob4OzvKJI3EooonC-ap1b9f9KCUE/edit?usp=sharing">Meeting notes</a> are available online.
166 We had a polly phone call. <a
167 href="https://drive.google.com/folderview?id=0B7OMOXTgCYIUWkpJbWVJcW04ams&usp=sharing">Meeting notes</a> are available online.
168 </td>
169 </tr>
171 <td>
173 -D LINK_POLLY_INTO_TOOLS:Bool=ON' to be statically linked in the tools (opt,
174 bugpoint, and clang.) This makes it easier to use polly without having to load
175 a shared library, and it also reduces the complexity of compiling Polly on
176 Windows.
177 </td>
178 </tr>
180 <td>
183 FOSDEM LLVM developer's meeting.
187 correctness and performance when compiling the LLVM test-suite. For now five
188 of them are used to provide <a
190 reports</a> (almost per-commit)
191 for 'clang -O3' (no polly). We also have six machines that track different
192 configurations of polly.
193 </td>
194 </tr>
196 <td>
199 generates illustrations of integer sets and maps. It relies on <a
202 them. Plotting is performed with <a
204 href="https://nbviewer.ipython.org/github/tobig/islplot/blob/master/notebooks/islplot-examples.ipynb">
205 Examples</a> show its use.
206 </td>
207 </tr>
210 <td>
213 </a> there will be a loop optimization BoF discussing Polly and other high
214 level loop optimizers.
215 </td>
216 </tr>
218 <td>
220 Sylvestre Ledru set up automatic tests for <a
223 which run at least once a day and which include results for Polly.
225 With the move to an isl 0.12 version Polly can be compiled without the
226 need to link directly to GMP (if isl is used for code generation). Currently
227 isl is still internally using GMP, but private patches exist to also remove
229 is possible.
230 </td></tr>
234 <td>
235 <h4> New publication in the PPL Journal
236 </h4>
238 We published a journal version of the Polly paper named
239 <em>
240 Polly - Performing polyhedral optimizations on a low-level intermediate
242 </td></tr>
244 <td>
246 The code generator can be parameterized on a fine-grained
247 level. It gives direct control for example over unrolling, the amount of
248 control overhead and the code size. It can also be used to
249 create loops to handle border conditions or to perform full-partial tile
250 separation.<br />
252 exception of GMP (LGPL), there is no other (L)GPL licensed software used in
253 Polly. The
254 use of GMP is limited to a well defined interface. Replacing it with
255 a BSD licensed replacement is a tractable engineering project we would
256 be very interested in. For more information about isl see the <a
258 </p>
259 </td></tr>
261 <td>
264 already able to perform Pluto-like optimizations with Polly, as a similar
265 algorithm was added to isl half a year ago. However, being able to directly
266 compare with the original implementation will not only bring in competition in
267 the optimizer field. It will also allow new experiments with a cutting edge
269 This support was on of the outcomes of the 1-day Polly workshop and the
270 following week of joint work at IISC Bangalore and in cooperation with
271 AMD India.
272 </td></tr>
273 <td>
274 </td></tr>
276 <td>
279 </td></tr>
281 <td>
283 Polly can now automatically optimize all <a
286 an external optimizer. The compile time is reasonable and we can show
287 notable speedups for various kernels.
288 </td></tr>
290 <tr>
293 <td>
294 <p>
297 New SCEV parser<br>
298 (Allows parameters in array subscript and max/signextend)
299 </td></tr>
301 <tr>
303 <td>
305 (The optimizer is similar to the one in Pluto, but it is part of isl)
306 </p>
307 </td></tr>
309 <tr>
311 <td>
312 <p>
314 clang plugin</a></p>
315 </td>
316 </tr>
318 <tr>
320 <td>
323 </p>
324 </td>
325 </tr>
327 <tr>
329 <td>
331 three years by a <a
333 Google Europe Fellowship in Efficient Computing</a>.
334 </p>
335 </td>
336 </tr>
338 <tr>
341 Raghesh's master thesis. See our <a
343 </tr>
345 <tr>
348 </tr>
350 <tr>
354 <p>Polly can compile
356 </td>
357 </tr>
358 <tr>
360 <td><p>pollycc - a script to automatically compile with
361 polyhedral optimizations </p></td>
362 </tr>
364 <tr>
366 <td><p> Basic OpenMP support, Alias analysis integration,
367 Pluto/POCC support </p></td>
368 </tr>
371 <tr>
374 </tr>
376 <tr>
380 </tr>
382 <tr>
387 </td>
388 </tr>
390 <tr>
394 </td>
395 </tr>
397 <tr>
400 </tr>
402 <tr>
405 </td>
406 </tr>
408 <tr>
411 </tr>
413 <tr>
416 </tr>
418 <tr>
420 <td><p>Translate a simple loop to Polly-IR and regenerate a loop structure
421 with CLooG works. </p>
423 </tr>
425 </tr>
427 <tr>
430 </tr>
433 <tr>
436 </tr>
437 </table>
438 </ul>
439 </div>
440 </div>
441 </body>
442 </html>