www/index.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   <script src="video-js/video.js" type="text/javascript" charset="utf-8"></script>
  11   <script type="text/javascript">
  12     VideoJS.setupAllWhenReady();
  13   </script>
  14
  15   <!-- Include the VideoJS Stylesheet -->
  16   <link rel="stylesheet" href="video-js/video-js.css" type="text/css" media="screen" title="Video JS">
  17 </head>
  18 <body>
  19 <div id="box">
  20 <!--#include virtual="menu.html.incl"-->
  21 <div id="content">
  22   <!--*********************************************************************-->
  23   <h1>About Polly</h1>
  24   <!--*********************************************************************-->
  25
  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>
  33
  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
  36   infrastructure. At
  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
  39   compilation.
  40
  41   <!--=====================================================================-->
  42   <h2>News</h2>
  43   <!--=====================================================================-->
  44
  45   <table id="news">
  46   <tr><td><b>2017</b></td></tr>
  47   <tr><td width="120"><p>January</p></td>
  48   <td>
  49   <a href="http://impact.gforge.inria.fr/impact2017">IMPACT 2017</a> program
  50   announced. Join IMPACT 2017 on January 23rd in Stockholm <a
  51   href="https://www.hipeac.net/2017/stockholm/">@HiPEAC'17</a>.
  52   </td>
  53   </tr>
  54   <tr><td><b>2016</b></td></tr>
  55   <tr><td width="120"><p>August</p></td>
  56   <td>
  57   <a href="http://impact.gforge.inria.fr/impact2017">IMPACT 2017</a> the 7th
  58   International Workshop on Polyhedral Compilation Techniques will take place
  59   at January 23-25, 2017 together with HiPEAC 2017 in Stockholm, Sweden. It is
  60   a great opportunity to discuss and present work on Polyhedral Compilation,
  61   including work on Polly.
  62   </td>
  63   </tr>
  64   <tr><td width="120"><p>April</p></td>
  65   <td>
  66     A source checkout that contains Polly now provides Polly functionality
  67     by default in clang/opt/bugpoint without the need to load an additional
  68     module.
  69   </td>
  70   </tr>
  71   <tr><td><b>2015</b></td></tr>
  72   <tr><td width="120"><p>July</p></td>
  73   <td>
  74     <h4>AST Generation Paper published in TOPLAS</h4>
  75     The July issue of TOPLAS contains a 50 page discussion of the AST
  76     generation techniques used in Polly. This discussion gives not only an
  77     in-depth description of how we (re)generate an imperative AST from our
  78     polyhedral based mathematical program description, but also gives
  79     interesting insights about:
  80     <ul>
  81       <li><b>Schedule trees:</b> A tree-based mathematical program description
  82       that enables us to perform loop transformations on an abstract level,
  83       while issues like the generation of the correct loop structure and loop
  84       bounds will be taken care of by our AST generator.
  85       <li><b>Polyhedral unrolling:</b> We discuss techniques that allow the
  86       unrolling of non-trivial loops in the context of parameteric loop bounds,
  87       complex tile shapes and conditionally executed statements. Such unrolling
  88       support enables the generation of predicated code e.g. in the context of
  89       GPGPU computing.
  90       <li><b>Isolation for full/partial tile separation:</b> We discuss native
  91       support for handling full/partial tile separation and -- in general --
  92       native support for isolation of boundary cases to enable smooth code
  93       generation for core computations.
  94       <li><b>AST generation with modulo constraints:</b> We discuss how modulo
  95       mappings are lowered to efficient C/LLVM code.
  96       <li><b>User-defined constraint sets for run-time checks</b> We discuss how
  97       arbitrary sets of constraints can be used to automatically create run-time
  98       checks that ensure a set of constrainst actually hold. This feature is
  99       very useful to verify at run-time various assumptions that have been taken
 100       program optimization.
 101     </ul>
 102
 103    <a href="http://www.grosser.es#pub-polyhedral-AST-generation">
 104    <em>Polyhedral AST generation is more than scanning polyhedra</em></a><br />
 105     Tobias Grosser, Sven Verdoolaege, Albert Cohen<br />
 106     ACM Transations on Programming Languages and Systems (TOPLAS), 37(4),
 107     July 2015
 108
 109     <br>
 110     <br>
 111     <br>
 112     <br>
 113   </td>
 114   </tr>
 115   <tr><td width="120"><p>February</p></td>
 116   <td>
 117     <h4>Polly allows now non-affine subregions</h4>
 118     Data-dependent or floating point conditionals inside a SCoP can now be
 119     overapproximated in order to increase the applicability on general purpose
 120     code.
 121   </td>
 122   </tr>
 123   <tr><td><b>2014</b></td></tr>
 124   <tr><td width="120"><p>August</p></td>
 125   <td>
 126   <h4>Polly drops the support of ScopLib and the external optimizer PoCC</h4>
 127   The support for ScopLib as an exchange format has been removed as recent
 128   versions of clan, candl and pluto all support the OpenScop exchange format.
 129
 130   The support of the external optmizer PoCC has been dropped in favor of the
 131   isl optimizer (default) and the still available pluto support.
 132   </td>
 133   </tr>
 134   <tr><td><b>2014</b></td></tr>
 135   <tr><td width="120"><p>June</p></td>
 136   <td>
 137   <h4>Polly can be built without GPL licensed software</h4> After Sebastian
 138   Pop's
 139   and David Peixotto's (both Qualcomm) recent <a
 140   href="http://repo.or.cz/w/isl.git/commit/60703e3ee89b9d5d4d1afb6a3f611292c0884574">commit</a>
 141   to isl, isl's latest development version can be built with imath instead of
 142   GMP. With both CLooG and gmp having become optional, the last obilgatory
 143   dependency to GPL licensed software has been removed. Now Polly only depends
 144   on isl (and the included imath), which are both MIT licensed.
 145   </td>
 146   </tr>
 147   <tr><td width="120"><p>April</p></td>
 148   <td>
 149   <h4>Polly Phone Call - 23April</h4>
 150   We had a polly phone call about delinearizing array accesses (II)<a
 151   href="https://docs.google.com/document/d/1IZewI8Up0iEkCNIPr6gVtwJxF7RV6KmXkdwOBM_Q5Cs/edit?usp=sharing ">Meeting notes</a> are available online.
 152   <h4>Polly Phone Call - 17th April</h4>
 153   We had a polly phone call about delinearizing array accesses <a
 154   href="https://docs.google.com/document/d/14d3ehkH2MsvBdqsEOSYjysH0Ztyzb75Lp843hnxh2IA/edit?usp=sharing">Meeting notes</a> are available online.
 155   <h4>Polly Phone Call - 10th April</h4>
 156   We had a polly phone call. <a
 157   href="https://docs.google.com/document/d/12W-qZjiZGEQ_lVrob4OzvKJI3EooonC-ap1b9f9KCUE/edit?usp=sharing">Meeting notes</a> are available online.
 158   <h4>Polly Phone Call - 4th April</h4>
 159   We had a polly phone call. <a
 160   href="https://drive.google.com/folderview?id=0B7OMOXTgCYIUWkpJbWVJcW04ams&usp=sharing">Meeting notes</a> are available online.
 161   </td>
 162   </tr>
 163   <tr><td width="120"><p>March</p></td>
 164   <td>
 165   <h4>Static link Polly into tools</h4> Polly can now be configured with 'cmake
 166   -D LINK_POLLY_INTO_TOOLS:Bool=ON' to be statically linked in the tools (opt,
 167   bugpoint, and clang.) This makes it easier to use polly without having to load
 168   a shared library, and it also reduces the complexity of compiling Polly on
 169   Windows.
 170   </td>
 171   </tr>
 172   <tr><td width="120"><p>February</p></td>
 173   <td>
 174   <h4>Polly presentation at FOSDEM 2014</h4> Polly was <a
 175   href="https://fosdem.org/2014/schedule/event/polly/">presented</a> at the
 176   FOSDEM LLVM developer's meeting.
 177   <h4>New LLVM test-suite buildbots</h4>
 178   The set of <a href="http://lab.llvm.org:8011/console?category=polly">Polly
 179   buildbots</a> has been extended. We now have 16 new blades that track
 180   correctness and performance when compiling the LLVM test-suite. For now five
 181   of them are used to provide <a
 182   href="http://llvm.org/perf/db_default/v4/nts/22463">fine granularity
 183   reports</a> (almost per-commit)
 184   for 'clang -O3' (no polly). We also have six machines that track different
 185   configurations of polly.
 186   </td>
 187   </tr>
 188   <tr><td width="120"><p>January</p></td>
 189   <td>
 190   <h4>islplot released</h4>
 191   <a href="https://github.com/tobig/islplot">islplot</a> is a library that
 192   generates illustrations of integer sets and maps. It relies on <a
 193   href="http://repo.or.cz/w/isl.git">isl</a> to model the integer sets and uses the <a
 194   href="https://pypi.python.org/pypi/islpy">islpy</a> Python bindings to access
 195   them. Plotting is performed with <a
 196   href="http://matplotlib.org">matplotlib</a>. The following <a
 197   href="http://nbviewer.ipython.org/github/tobig/islplot/blob/master/notebooks/islplot-examples.ipynb">
 198   Examples</a> show its use.
 199   </td>
 200   </tr>
 201   <tr><td><b>2013</b></td></tr>
 202   <tr><td width="120"><p>November</p></td>
 203   <td>
 204   <h4>Loop optimization BoF at upcoming LLVM conference</h4>
 205   At the upcoming <a href="http://llvm.org/devmtg/2013-11/#bof5">LLVM conference
 206   </a> there will be a loop optimization BoF discussing Polly and other high
 207   level loop optimizers.
 208   </td>
 209   </tr>
 210   <tr><td width="120"><p>October</p></td>
 211   <td>
 212   <h4>Automatic code coverage and static analysis tests</h4>
 213   Sylvestre Ledru set up automatic tests for <a
 214   href="http://buildd-clang.debian.net/coverage/">code coverage</a> and
 215   <a href="http://buildd-clang.debian.net/scan-build/">static analysis</a>
 216   which run at least once a day and which include results for Polly.
 217   <h4>Move to CLooG 0.18.1 and isl 0.12.1</h4>
 218   With the move to an isl 0.12 version Polly can be compiled without the
 219   need to link directly to GMP (if isl is used for code generation). Currently
 220   isl is still internally using GMP, but private patches exist to also remove
 221   this dependency. Without the use of GMP, a <b>GPL free</b> version of Polly
 222   is possible.
 223   </td></tr>
 224
 225   <tr><td><b>2012</b></td></tr>
 226   <tr><td width="120"><p>December</p></td>
 227   <td>
 228   <h4> New publication in the PPL Journal
 229      </h4>
 230
 231       We published a journal version of the Polly paper named
 232       <em>
 233       Polly - Performing polyhedral optimizations on a low-level intermediate
 234       representation</em> in the Parallel Processing Letters 2012.
 235   </td></tr>
 236   <tr><td width="120"><p>September</p></td>
 237   <td>
 238   <h4>Experimental support for the <b>new isl code generator</b></h4>
 239      The code generator can be parameterized on a fine-grained
 240      level. It gives direct control for example over unrolling, the amount of
 241      control overhead and the code size. It can also be used to
 242      create loops to handle border conditions or to perform full-partial tile
 243      separation.<br />
 244      We also relicensed isl under the <b>MIT license</b>. This means, with the
 245      exception of GMP (LGPL), there is no other (L)GPL licensed software used in
 246      Polly. The
 247      use of GMP is limited to a well defined interface. Replacing it with
 248      a BSD licensed replacement is a tractable engineering project we would
 249      be very interested in. For more information about isl see the <a
 250      href="http://www.kotnet.org/~skimo/isl/manual.pdf">isl manual</a>.
 251      </p>
 252   </td></tr>
 253   <tr><td width="120"><p>July</p></td>
 254   <td>
 255   <p> Polly can now be directly linked to the <a
 256 href="http://pluto-compiler.sourceforge.net/">Pluto optimizer</a>. We were
 257 already able to perform Pluto-like optimizations with Polly, as a similar
 258 algorithm was added to isl half a year ago. However, being able to directly
 259 compare with the original implementation will not only bring in competition in
 260 the optimizer field. It will also allow new experiments with a cutting edge
 261 research tool.<br \>
 262   This support was on of the outcomes of the 1-day Polly workshop and the
 263   following week of joint work at IISC Bangalore and in cooperation with
 264   AMD India.
 265   </td></tr>
 266   <td>
 267   </td></tr>
 268   <tr><td width="120"><p>February</p></td>
 269   <td>
 270   <p>Polly is an official LLVM project, reachable at <a
 271   href="http://polly.llvm.org">http://polly.llvm.org</a></p>
 272   </td></tr>
 273   <tr><td width="120"><p>January</p></td>
 274   <td>
 275   <p>Improved support for the isl scheduling optimizer</p>
 276   Polly can now automatically optimize all <a
 277   href="http://www.cse.ohio-state.edu/~pouchet/software/polybench/">polybench
 278   2.0</a> kernels without the help of
 279   an external optimizer. The compile time is reasonable and we can show
 280   notable speedups for various kernels.
 281   </td></tr>
 282
 283   <tr>
 284   <tr><td><b><br/>2011</b></td></tr>
 285   <tr><td width="120"><p>November</p></td>
 286   <td>
 287   <p>
 288   Talk at the <a href="http://llvm.org/devmtg/2011-11/">
 289       LLVM Developer Meeting 2011</a></p>
 290   New SCEV parser<br>
 291   (Allows parameters in array subscript and max/signextend)
 292   </td></tr>
 293
 294   <tr>
 295   <td><p>October</p></td>
 296   <td>
 297   <p>Polly can use the isl schedule optimizer<br>
 298     (The optimizer is similar to the one in Pluto, but it is part of isl)
 299   </p>
 300   </td></tr>
 301
 302   <tr>
 303   <td><p>August</p></td>
 304   <td>
 305   <p>
 306   <a href="example_load_Polly_into_clang.html">Use Polly as
 307   clang plugin</a></p>
 308   </td>
 309   </tr>
 310
 311   <tr>
 312   <td><p>July</p></td>
 313   <td>
 314   <p> Polly builder as part of the <a
 315   href="http://lab.llvm.org:8011/console">LLVM Buildbots</a>
 316   </p>
 317   </td>
 318   </tr>
 319
 320   <tr>
 321   <td><p>June</p></td>
 322   <td>
 323   <p><a href="http://www.grosser.es">Tobias</a> is founded for
 324   three years by a <a
 325   href="http://research.google.com/university/relations/fellowship_recipients.html">
 326   Google Europe Fellowship in Efficient Computing</a>.
 327   </p>
 328   </td>
 329   </tr>
 330
 331   <tr>
 332   <td><p>May </p></td>
 333   <td><p><a href="http://www.grosser.es">Tobias</a>' diploma thesis and
 334   Raghesh's master thesis. See our <a
 335   href="publications.html">list of publications</a>.</p></td>
 336   </tr>
 337
 338   <tr>
 339   <td><p>April</p></td>
 340   <td><p>Polly moves to the LLVM infrastructure (svn, bugtracker)</p></td>
 341   </tr>
 342
 343   <tr>
 344   <td><p>March</p></td>
 345   <td><p>Presentation at <a
 346   href="http://impact2011.inrialpes.fr/">CGO/IMPACT</a></p>
 347   <p>Polly can compile
 348   polybench 2.0 with vectorization and OpenMP code generation</p>
 349   </td>
 350   </tr>
 351   <tr>
 352   <td><p>Februar</p></td>
 353   <td><p>pollycc - a script to automatically compile with
 354   polyhedral optimizations </p></td>
 355   </tr>
 356
 357   <tr>
 358   <td><p> Januar</p></td>
 359   <td><p> Basic OpenMP support, Alias analysis integration,
 360   Pluto/POCC support </p></td>
 361   </tr>
 362
 363   <tr><td><b><br>2010</b></td></tr>
 364   <tr>
 365   <td><p> Dezember </p></td>
 366   <td><p>Basic vectorization support </p></td>
 367   </tr>
 368
 369   <tr>
 370   <td><p> November </p></td>
 371   <td><p>Talk at the <a
 372   href="http://llvm.org/devmtg/2010-11/">LLVM Developer Meeting</a> </p></td>
 373   </tr>
 374
 375   <tr>
 376   <td><p>October</p></td>
 377   <td><p>Dependency analysis </p>
 378   <p>Finished Phase 1 - Get something working </p>
 379   <p>Support scalar dependences and sequential SCoPs </p>
 380   </td>
 381   </tr>
 382
 383   <tr>
 384   <td><p>August</p></td>
 385   <td><p>RegionInfo pass committed to LLVM</p>
 386   <p>llvm-test suite compiles </p>
 387   </td>
 388   </tr>
 389
 390   <tr>
 391   <td><p>July</p></td>
 392   <td><p>Code generation works for normal SCoPs.  </p></td>
 393   </tr>
 394
 395   <tr>
 396   <td><p>May</p></td>
 397   <td><p>The CLooG AST can be parsed.</p>
 398   </td>
 399   </tr>
 400
 401   <tr>
 402   <td><p>April</p></td>
 403   <td><p>SCoPs can automatically be detected. </p></td>
 404   </tr>
 405
 406   <tr>
 407   <td><p>March</p></td>
 408   <td><p>The RegionInfo framework is almost completed.  </p></td>
 409   </tr>
 410
 411   <tr>
 412   <td><p>February</p></td>
 413   <td><p>Translate a simple loop to Polly-IR and regenerate a loop structure
 414          with CLooG works.  </p>
 415   <p>ISL and CLooG are integrated.  </p></td>
 416   </tr>
 417
 418   </tr>
 419
 420   <tr>
 421   <td><p>January</p></td>
 422   <td><p>The RegionInfo pass is finished.  </p></td>
 423   </tr>
 424
 425   <tr><td><b><br>2009</b></td></tr>
 426   <tr>
 427   <td><p>End of the year</p></td>
 428   <td><p>Work on the infrastructure started.  </p></td>
 429   </tr>
 430   </table>
 431   </ul>
 432 </div>
 433 </div>
 434 </body>
 435 </html>