443 lines · html
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/ -->4<html>5<head>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</head>11<body>12<div id="box">13<!--#include virtual="menu.html.incl"-->14<div id="content">15 <!--*********************************************************************-->16 <h1>About Polly</h1>17 <!--*********************************************************************-->18 19 <p> Polly is a high-level loop and data-locality optimizer and optimization20 infrastructure for LLVM. It uses an abstract mathematical representation based21 on integer polyhedra to analyze and optimize the memory access pattern of a22 program. We currently perform classical loop transformations, especially23 tiling and loop fusion to improve data-locality. Polly can also exploit24 OpenMP level parallelism, expose SIMDization opportunities.</p>25 26 For many users, however, it's not the existing optimizations in Polly that are27 of most interest, but the new analyses and optimizations enabled by the Polly28 infrastructure. At29 <a href="https://polyhedral.info">polyhedral.info</a> you can get an idea of30 what has already been done and what is possible in the context of polyhedral31 compilation.32 33 <!--=====================================================================-->34 <h2>News</h2>35 <!--=====================================================================-->36 37 <table id="news">38 <tr><td><b>2017</b></td></tr>39 <tr><td width="120"><p>September</p></td>40 <td>41 <h4>High-Performance Generalized Matrix Multiplication</h4>42 Polly automatically detects and optimizes generalized matrix43 multiplication, the computation C ← α ⊗ C ⊕ β44 ⊗ A ⊗ B, where A, B, and C are three appropriately sized45 matrices, ⊕ and ⊗ operations are originating from the46 corresponding matrix semiring, and α and β are constants, and47 beta is not equal to zero. It allows to obtain the highly optimized form48 structured similar to the expert implementation of GEMM that can be found49 in GotoBLAS and its successors.50 <h4>The performance evaluation of GEMM</h4>51 <img src="images/GEMM_double.png" /><br />52 </td>53 <tr><td><b>2017</b></td></tr>54 <tr><td width="120"><p>January</p></td>55 <td>56 <a href="http://impact.gforge.inria.fr/impact2017">IMPACT 2017</a> program57 announced. Join IMPACT 2017 on January 23rd in Stockholm <a58 href="https://www.hipeac.net/2017/stockholm/">@HiPEAC'17</a>.59 </td>60 </tr>61 <tr><td><b>2016</b></td></tr>62 <tr><td width="120"><p>August</p></td>63 <td>64 <a href="http://impact.gforge.inria.fr/impact2017">IMPACT 2017</a> the 7th65 International Workshop on Polyhedral Compilation Techniques will take place66 at January 23-25, 2017 together with HiPEAC 2017 in Stockholm, Sweden. It is67 a great opportunity to discuss and present work on Polyhedral Compilation,68 including work on Polly.69 </td>70 </tr>71 <tr><td width="120"><p>April</p></td>72 <td>73 A source checkout that contains Polly now provides Polly functionality74 by default in clang/opt/bugpoint without the need to load an additional75 module.76 </td>77 </tr>78 <tr><td><b>2015</b></td></tr>79 <tr><td width="120"><p>July</p></td>80 <td>81 <h4>AST Generation Paper published in TOPLAS</h4>82 The July issue of TOPLAS contains a 50 page discussion of the AST83 generation techniques used in Polly. This discussion gives not only an84 in-depth description of how we (re)generate an imperative AST from our85 polyhedral based mathematical program description, but also gives86 interesting insights about:87 <ul>88 <li><b>Schedule trees:</b> A tree-based mathematical program description89 that enables us to perform loop transformations on an abstract level,90 while issues like the generation of the correct loop structure and loop91 bounds will be taken care of by our AST generator.92 <li><b>Polyhedral unrolling:</b> We discuss techniques that allow the93 unrolling of non-trivial loops in the context of parametric loop bounds,94 complex tile shapes and conditionally executed statements. Such unrolling95 support enables the generation of predicated code e.g. in the context of96 GPGPU computing.97 <li><b>Isolation for full/partial tile separation:</b> We discuss native98 support for handling full/partial tile separation and -- in general --99 native support for isolation of boundary cases to enable smooth code100 generation for core computations.101 <li><b>AST generation with modulo constraints:</b> We discuss how modulo102 mappings are lowered to efficient C/LLVM code.103 <li><b>User-defined constraint sets for run-time checks</b> We discuss how104 arbitrary sets of constraints can be used to automatically create run-time105 checks that ensure a set of constraints actually hold. This feature is106 very useful to verify at run-time various assumptions that have been taken107 program optimization.108 </ul>109 110 <a href="https://www.grosser.es#pub-polyhedral-AST-generation">111 <em>Polyhedral AST generation is more than scanning polyhedra</em></a><br />112 Tobias Grosser, Sven Verdoolaege, Albert Cohen<br />113 ACM Transactions on Programming Languages and Systems (TOPLAS), 37(4),114 July 2015115 116 <br>117 <br>118 <br>119 <br>120 </td>121 </tr>122 <tr><td width="120"><p>February</p></td>123 <td>124 <h4>Polly allows now non-affine subregions</h4>125 Data-dependent or floating point conditionals inside a SCoP can now be126 overapproximated in order to increase the applicability on general purpose127 code.128 </td>129 </tr>130 <tr><td><b>2014</b></td></tr>131 <tr><td width="120"><p>August</p></td>132 <td>133 <h4>Polly drops the support of ScopLib and the external optimizer PoCC</h4>134 The support for ScopLib as an exchange format has been removed as recent135 versions of clan, candl and pluto all support the OpenScop exchange format.136 137 The support of the external optimizer PoCC has been dropped in favor of the138 isl optimizer (default) and the still available pluto support.139 </td>140 </tr>141 <tr><td><b>2014</b></td></tr>142 <tr><td width="120"><p>June</p></td>143 <td>144 <h4>Polly can be built without GPL licensed software</h4> After Sebastian145 Pop's146 and David Peixotto's (both Qualcomm) recent <a147 href="https://repo.or.cz/w/isl.git/commit/60703e3ee89b9d5d4d1afb6a3f611292c0884574">commit</a>148 to isl, isl's latest development version can be built with imath instead of149 GMP. With both CLooG and gmp having become optional, the last obligatory150 dependency to GPL licensed software has been removed. Now Polly only depends151 on isl (and the included imath), which are both MIT licensed.152 </td>153 </tr>154 <tr><td width="120"><p>April</p></td>155 <td>156 <h4>Polly Phone Call - 23April</h4>157 We had a polly phone call about delinearizing array accesses (II)<a158 href="https://docs.google.com/document/d/1IZewI8Up0iEkCNIPr6gVtwJxF7RV6KmXkdwOBM_Q5Cs/edit?usp=sharing ">Meeting notes</a> are available online.159 <h4>Polly Phone Call - 17th April</h4>160 We had a polly phone call about delinearizing array accesses <a161 href="https://docs.google.com/document/d/14d3ehkH2MsvBdqsEOSYjysH0Ztyzb75Lp843hnxh2IA/edit?usp=sharing">Meeting notes</a> are available online.162 <h4>Polly Phone Call - 10th April</h4>163 We had a polly phone call. <a164 href="https://docs.google.com/document/d/12W-qZjiZGEQ_lVrob4OzvKJI3EooonC-ap1b9f9KCUE/edit?usp=sharing">Meeting notes</a> are available online.165 <h4>Polly Phone Call - 4th April</h4>166 We had a polly phone call. <a167 href="https://drive.google.com/folderview?id=0B7OMOXTgCYIUWkpJbWVJcW04ams&usp=sharing">Meeting notes</a> are available online.168 </td>169 </tr>170 <tr><td width="120"><p>March</p></td>171 <td>172 <h4>Static link Polly into tools</h4> Polly can now be configured with 'cmake173 -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 load175 a shared library, and it also reduces the complexity of compiling Polly on176 Windows.177 </td>178 </tr>179 <tr><td width="120"><p>February</p></td>180 <td>181 <h4>Polly presentation at FOSDEM 2014</h4> Polly was <a182 href="https://fosdem.org/2014/schedule/event/polly/">presented</a> at the183 FOSDEM LLVM developer's meeting.184 <h4>New LLVM test-suite buildbots</h4>185 The set of <a href="http://lab.llvm.org:8011/console?category=polly">Polly186 buildbots</a> has been extended. We now have 16 new blades that track187 correctness and performance when compiling the LLVM test-suite. For now five188 of them are used to provide <a189 href="https://llvm.org/perf/db_default/v4/nts/22463">fine granularity190 reports</a> (almost per-commit)191 for 'clang -O3' (no polly). We also have six machines that track different192 configurations of polly.193 </td>194 </tr>195 <tr><td width="120"><p>January</p></td>196 <td>197 <h4>islplot released</h4>198 <a href="https://github.com/tobig/islplot">islplot</a> is a library that199 generates illustrations of integer sets and maps. It relies on <a200 href="https://repo.or.cz/w/isl.git">isl</a> to model the integer sets and uses the <a201 href="https://pypi.python.org/pypi/islpy">islpy</a> Python bindings to access202 them. Plotting is performed with <a203 href="https://matplotlib.org">matplotlib</a>. The following <a204 href="https://nbviewer.ipython.org/github/tobig/islplot/blob/master/notebooks/islplot-examples.ipynb">205 Examples</a> show its use.206 </td>207 </tr>208 <tr><td><b>2013</b></td></tr>209 <tr><td width="120"><p>November</p></td>210 <td>211 <h4>Loop optimization BoF at upcoming LLVM conference</h4>212 At the upcoming <a href="https://llvm.org/devmtg/2013-11/#bof5">LLVM conference213 </a> there will be a loop optimization BoF discussing Polly and other high214 level loop optimizers.215 </td>216 </tr>217 <tr><td width="120"><p>October</p></td>218 <td>219 <h4>Automatic code coverage and static analysis tests</h4>220 Sylvestre Ledru set up automatic tests for <a221 href="https://llvm.org/reports/coverage/">code coverage</a> and222 <a href="https://llvm.org/reports/scan-build/">static analysis</a>223 which run at least once a day and which include results for Polly.224 <h4>Move to CLooG 0.18.1 and isl 0.12.1</h4>225 With the move to an isl 0.12 version Polly can be compiled without the226 need to link directly to GMP (if isl is used for code generation). Currently227 isl is still internally using GMP, but private patches exist to also remove228 this dependency. Without the use of GMP, a <b>GPL free</b> version of Polly229 is possible.230 </td></tr>231 232 <tr><td><b>2012</b></td></tr>233 <tr><td width="120"><p>December</p></td>234 <td>235 <h4> New publication in the PPL Journal236 </h4>237 238 We published a journal version of the Polly paper named239 <em>240 Polly - Performing polyhedral optimizations on a low-level intermediate241 representation</em> in the Parallel Processing Letters 2012.242 </td></tr>243 <tr><td width="120"><p>September</p></td>244 <td>245 <h4>Experimental support for the <b>new isl code generator</b></h4>246 The code generator can be parameterized on a fine-grained247 level. It gives direct control for example over unrolling, the amount of248 control overhead and the code size. It can also be used to249 create loops to handle border conditions or to perform full-partial tile250 separation.<br />251 We also relicensed isl under the <b>MIT license</b>. This means, with the252 exception of GMP (LGPL), there is no other (L)GPL licensed software used in253 Polly. The254 use of GMP is limited to a well defined interface. Replacing it with255 a BSD licensed replacement is a tractable engineering project we would256 be very interested in. For more information about isl see the <a257 href="http://www.kotnet.org/~skimo/isl/manual.pdf">isl manual</a>.258 </p>259 </td></tr>260 <tr><td width="120"><p>July</p></td>261 <td>262 <p> Polly can now be directly linked to the <a263href="http://pluto-compiler.sourceforge.net/">Pluto optimizer</a>. We were264already able to perform Pluto-like optimizations with Polly, as a similar265algorithm was added to isl half a year ago. However, being able to directly266compare with the original implementation will not only bring in competition in267the optimizer field. It will also allow new experiments with a cutting edge268research tool.<br \>269 This support was on of the outcomes of the 1-day Polly workshop and the270 following week of joint work at IISC Bangalore and in cooperation with271 AMD India.272 </td></tr>273 <td>274 </td></tr>275 <tr><td width="120"><p>February</p></td>276 <td>277 <p>Polly is an official LLVM project, reachable at <a278 href="https://polly.llvm.org">https://polly.llvm.org</a></p>279 </td></tr>280 <tr><td width="120"><p>January</p></td>281 <td>282 <p>Improved support for the isl scheduling optimizer</p>283 Polly can now automatically optimize all <a284 href="https://web.cse.ohio-state.edu/~pouchet.2/software/polybench/">polybench285 2.0</a> kernels without the help of286 an external optimizer. The compile time is reasonable and we can show287 notable speedups for various kernels.288 </td></tr>289 290 <tr>291 <tr><td><b><br/>2011</b></td></tr>292 <tr><td width="120"><p>November</p></td>293 <td>294 <p>295 Talk at the <a href="https://llvm.org/devmtg/2011-11/">296 LLVM Developer Meeting 2011</a></p>297 New SCEV parser<br>298 (Allows parameters in array subscript and max/signextend)299 </td></tr>300 301 <tr>302 <td><p>October</p></td>303 <td>304 <p>Polly can use the isl schedule optimizer<br>305 (The optimizer is similar to the one in Pluto, but it is part of isl)306 </p>307 </td></tr>308 309 <tr>310 <td><p>August</p></td>311 <td>312 <p>313 <a href="example_load_Polly_into_clang.html">Use Polly as314 clang plugin</a></p>315 </td>316 </tr>317 318 <tr>319 <td><p>July</p></td>320 <td>321 <p> Polly builder as part of the <a322 href="http://lab.llvm.org:8011/console">LLVM Buildbots</a>323 </p>324 </td>325 </tr>326 327 <tr>328 <td><p>June</p></td>329 <td>330 <p><a href="https://www.grosser.es">Tobias</a> is founded for331 three years by a <a332 href="https://ai.google/research/outreach/phd-fellowship/recipients/?category=2011">333 Google Europe Fellowship in Efficient Computing</a>.334 </p>335 </td>336 </tr>337 338 <tr>339 <td><p>May </p></td>340 <td><p><a href="https://www.grosser.es">Tobias</a>' diploma thesis and341 Raghesh's master thesis. See our <a342 href="publications.html">list of publications</a>.</p></td>343 </tr>344 345 <tr>346 <td><p>April</p></td>347 <td><p>Polly moves to the LLVM infrastructure (svn, bugtracker)</p></td>348 </tr>349 350 <tr>351 <td><p>March</p></td>352 <td><p>Presentation at <a353 href="http://impact2011.inrialpes.fr/">CGO/IMPACT</a></p>354 <p>Polly can compile355 polybench 2.0 with vectorization and OpenMP code generation</p>356 </td>357 </tr>358 <tr>359 <td><p>February</p></td>360 <td><p>pollycc - a script to automatically compile with361 polyhedral optimizations </p></td>362 </tr>363 364 <tr>365 <td><p> January</p></td>366 <td><p> Basic OpenMP support, Alias analysis integration,367 Pluto/POCC support </p></td>368 </tr>369 370 <tr><td><b><br>2010</b></td></tr>371 <tr>372 <td><p> December </p></td>373 <td><p>Basic vectorization support </p></td>374 </tr>375 376 <tr>377 <td><p> November </p></td>378 <td><p>Talk at the <a379 href="https://llvm.org/devmtg/2010-11/">LLVM Developer Meeting</a> </p></td>380 </tr>381 382 <tr>383 <td><p>October</p></td>384 <td><p>Dependency analysis </p>385 <p>Finished Phase 1 - Get something working </p>386 <p>Support scalar dependences and sequential SCoPs </p>387 </td>388 </tr>389 390 <tr>391 <td><p>August</p></td>392 <td><p>RegionInfo pass committed to LLVM</p>393 <p>llvm-test suite compiles </p>394 </td>395 </tr>396 397 <tr>398 <td><p>July</p></td>399 <td><p>Code generation works for normal SCoPs. </p></td>400 </tr>401 402 <tr>403 <td><p>May</p></td>404 <td><p>The CLooG AST can be parsed.</p>405 </td>406 </tr>407 408 <tr>409 <td><p>April</p></td>410 <td><p>SCoPs can automatically be detected. </p></td>411 </tr>412 413 <tr>414 <td><p>March</p></td>415 <td><p>The RegionInfo framework is almost completed. </p></td>416 </tr>417 418 <tr>419 <td><p>February</p></td>420 <td><p>Translate a simple loop to Polly-IR and regenerate a loop structure421 with CLooG works. </p>422 <p>ISL and CLooG are integrated. </p></td>423 </tr>424 425 </tr>426 427 <tr>428 <td><p>January</p></td>429 <td><p>The RegionInfo pass is finished. </p></td>430 </tr>431 432 <tr><td><b><br>2009</b></td></tr>433 <tr>434 <td><p>End of the year</p></td>435 <td><p>Work on the infrastructure started. </p></td>436 </tr>437 </table>438 </ul>439</div>440</div>441</body>442</html>443