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