polly/www/todo.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> <META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
   6   <title>Polly - Todo</title>
   7   <link type="text/css" rel="stylesheet" href="menu.css">
   8   <link type="text/css" rel="stylesheet" href="content.css">
   9 </head>
  10 <body>
  11 <div id="box">
  12 <!--#include virtual="menu.html.incl"-->
  13 <div id="content">
  14 <h1> TODO </h1>
  15
  16 <h2> Overview</h2>
  17 <ul>
  18 <li><a href="#phase3">Phase 4</a></li>
  19 <li><a href="#phase3">Phase 3 - Improve Robustness, Interoperability and
  20 Optimizations (ongoing)</a></li>
  21 <li><a href="#llvm">Polly as a LLVM Project (Finished February 2012)</a></li>
  22 <li><a href="#phase2">Phase 2 - First Optimizations and Enhanced User Experience (Finished
  23 February 2012)</a></li>
  24 <li><a href="#phase1">Phase 1 - Get Something Working (Finished October 2010)</a>
  25 </li>
  26 </ul>
  27 <h2> Individual Phases</h3>
  28
  29 <h3 id="phase4"> Phase 4</h3>
  30 <table class="wikitable" cellpadding="2">
  31 <p> </p>
  32
  33 <tbody>
  34 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Infrastructure </th></tr>
  35 <tr style="background: rgb(239, 239, 239)">
  36   <th width="400px"> Task </th>
  37   <th width="150px"> Status </th>
  38   <th> Owner </th>
  39 </tr>
  40 <tr>
  41 <th align="left"> Move to isl C++ bindings
  42 </th><td align="center" class='open'> Open
  43 </td><td>
  44 </td>
  45 </tr>
  46 <th align="left"> &nbsp; &nbsp; - Add isl C++ bindings generator to isl
  47 </th><td align="center" class='open'> Open
  48 </td><td>
  49 </td>
  50 </tr>
  51 <tr>
  52 <th align="left"> Add isl as an external library to Polly SVN
  53 </th><td align="center" class='done'> Done
  54 </td><td>
  55 </td>
  56 </tr>
  57 <tr>
  58 <th align="left"> Compile-time: Speed up transformations
  59 </th><td align="center">
  60 </td><td>
  61 </td>
  62 </tr>
  63 <th align="left"> &nbsp; &nbsp; - Optimize isl_int for small integers
  64 </th><td align="center" class='done'> Done
  65 </td><td>
  66 </td>
  67 </tr>
  68 <tr>
  69 <th align="left"> Compile-time: Minimize SCoP detection time
  70 </th><td align="center" class='open'> Open
  71 </td><td>
  72 </td>
  73 </tr>
  74 <th align="left"> &nbsp; &nbsp; - Reconsider pass-ordering (move Polly later)
  75 </th><td align="center" class='open'> Open
  76 </td><td>
  77 </td>
  78 </tr>
  79
  80 <tr><td colspan='4'>&nbsp;</td></tr>
  81 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Increase coverage
  82 </th></tr>
  83 <tr style="background: rgb(239, 239, 239)">
  84   <th width="400px"> Task </th>
  85   <th width="150px"> Status </th>
  86   <th> Owner </th>
  87 </tr>
  88
  89 <tr>
  90 <th align="left">
  91 Support for Modulos
  92 </th><td align="center" class='done'> Done
  93 </td><td> Johannes
  94 </td></tr>
  95 <tr>
  96 <th align="left">
  97 Boolean Combinations
  98 </th><td align="center" class='done'> Done
  99 </td><td> Johannes
 100 </td></tr>
 101 <tr>
 102 <th align="left">
 103 Unsigned Integers
 104 </th><td align="center" class='done'> Done
 105 </td><td> Johannes
 106 </td></tr>
 107 <tr>
 108 <th align="left">
 109 Pointer Comparisons
 110 </th><td align="center" class='done'> Done
 111 </td><td> Johannes
 112 </td></tr>
 113 <tr>
 114 <th align="left">
 115 Non-affine subregions
 116 </th><td align="center" class='done'> Done
 117 </td><td> Johannes
 118 </td></tr>
 119
 120 <tr><td colspan='4'>&nbsp;</td></tr>
 121 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Polly as an
 122 analysis </th></tr>
 123 <tr style="background: rgb(239, 239, 239)">
 124   <th width="400px"> Task </th>
 125   <th width="150px"> Status </th>
 126   <th> Owner </th>
 127 </tr>
 128
 129 <tr>
 130 <th align="left">
 131 Model scalars dependences directly in Polly
 132 </th><td align="center" class='done'> Done
 133 </td><td>
 134 </td></tr>
 135 <tr>
 136 <th align="left">
 137 Code generate scalar dependences
 138 </th><td align="center" class='done'> Done
 139 </td><td>
 140 </td></tr>
 141 <tr>
 142 <th align="left">
 143 Model PHI dependences directly in Polly
 144 </th><td align="center" class='done'> Done
 145 </td><td>
 146 </td></tr>
 147 <tr>
 148 <th align="left">
 149 Code generate PHI dependences
 150 </th><td align="center" class='done'> Done
 151 </td><td>
 152 </td></tr>
 153 <tr>
 154 <th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=12398">Remove
 155 the need for independent blocks</a>
 156 </th><td class="done"> Done
 157 </td><td>
 158 </td></tr>
 159 <tr>
 160 <th align="left">
 161 Remove polly-prepare pass
 162 </th><td align="center" class='open'> Open
 163 </td><td>
 164 </td></tr>
 165
 166 <tr><td colspan='4'>&nbsp;</td></tr>
 167 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Correctness in
 168 cornercases </th></tr>
 169 <tr style="background: rgb(239, 239, 239)">
 170   <th width="400px"> Task </th>
 171   <th width="150px"> Status </th>
 172   <th> Owner </th>
 173 </tr>
 174 <tr>
 175 <th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=10381">Derive
 176 optimal types (instead of always using i64)</a>
 177 </th><td class="open"> Open
 178 </td><td>
 179 </td></tr>
 180 <tr>
 181 <th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=12397">Model
 182 integer wrapping</a>
 183 </th><td align="center" class='done'> Done
 184 </td><td> Johannes
 185 </td></tr
 186
 187 <tr><td colspan='4'>&nbsp;</td></tr>
 188 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Optimize Julia
 189 code with Polly
 190 analysis </th></tr>
 191 <tr style="background: rgb(239, 239, 239)">
 192   <th width="400px"> Task </th>
 193   <th width="150px"> Status </th>
 194   <th> Owner </th>
 195 </tr>
 196
 197 <th align="left">
 198 Integrate Polly into Julia
 199 </th><td align="center" class='open'> Open
 200 </td><td>
 201 </td></tr>
 202 <tr>
 203 <th align="left">
 204 Eliminate run-time bounds checks
 205 </th><td align="center" class='open'> Open
 206 </td><td>
 207 </td></tr>
 208 <tr>
 209 <th align="left"> &nbsp; &nbsp; - Reconsider unreachables in post-dominance tree
 210 </th><td align="center" class='open'> Open
 211 </td><td>
 212 </td></tr>
 213
 214 <th align="left"> &nbsp; &nbsp; - Actually eliminate statements
 215 </th><td align="center" class='done'> Done
 216 </td><td>
 217 </td></tr>
 218
 219 <tr><td colspan='4'>&nbsp;</td></tr>
 220 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Improved
 221 Optimizations in Polly
 222 </th></tr>
 223 <tr style="background: rgb(239, 239, 239)">
 224   <th width="400px"> Task </th>
 225   <th width="150px"> Status </th>
 226   <th> Owner </th>
 227 </tr>
 228
 229 <th align="left">
 230 Multi-level tiling
 231 </th><td align="center" class='open'> Open
 232 </td><td>
 233 </td></tr>
 234 <tr>
 235 <th align="left">
 236 Register Tiling
 237 </th><td align="center" class='open'> Open
 238 </td><td>
 239 </td></tr>
 240 <tr>
 241 <th align="left">
 242 Full/partial tile separation for vectorization
 243 </th><td align="center" class='done'> Done
 244 </td><td>
 245 </td></tr>
 246 <th align="left">
 247 Loop interchange after vectorization to maximize stride-one accesses
 248 </th><td align="center" class='open'> Open
 249 </td><td>
 250 </td></tr>
 251 </table>
 252
 253
 254 <h3 id="phase3"> Phase 3 - Improve Robustness, Interoperability and
 255 Optimizations (ongoing)</h3>
 256 <table class="wikitable" cellpadding="2">
 257 <p> </p>
 258
 259 <tbody>
 260 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Frontend </th></tr>
 261 <tr style="background: rgb(239, 239, 239)">
 262   <th width="400px"> Task </th>
 263   <th width="150px"> Status </th>
 264   <th> Owner </th>
 265 </tr>
 266 <tr>
 267 <th align="left"> Non-affine access functions
 268 </th><td align="center" class='done'> Done, needs testing
 269 </td><td>Marcello
 270 </td>
 271 </tr>
 272
 273
 274 <tr>
 275 <tr>
 276 <th align="left"> <a
 277 href="https://bugs.llvm.org/show_bug.cgi?id=12403">Variable-size
 278 multi-dimensional arrays</a>
 279 </th><td align="center" class='done'> Done
 280 </td><td>Sebastian
 281 </td></tr>
 282 <tr>
 283 <th align="left"> <a
 284 href="https://bugs.llvm.org/show_bug.cgi?id=12407">Derive information for
 285 the SCoP context
 286 </a>
 287 </th>
 288 <td align="center" class='nice'> Open
 289 </td><td>
 290 </td></tr>
 291 <tr>
 292 <th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=12402">Finer
 293 grained statements</a>
 294 </th><td align="center" class='nice'> Open
 295 </td><td>
 296 </td></tr>
 297 <tr>
 298 <th align="left"> Detect reductions
 299 </th><td align="center" class='done'>Done
 300 </td><td>Johannes
 301 </td></tr>
 302 <tr>
 303 <th align="left"> Generate code for reductions
 304 </th><td align="center" class='niceinprogress'>in progress
 305 </td><td>Johannes
 306 </td></tr>
 307 <tr>
 308 <th align="left"> Assume static sized arrays are only accessed in-bounds
 309 </th><td align="center" class='done'>Done
 310 </td><td>Tobias
 311 </td></tr>
 312 <tr><td colspan='4'>&nbsp;</td></tr>
 313 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Optimizer </th></tr>
 314 <tr style="background: rgb(239, 239, 239)">
 315   <th width="400px"> Task </th>
 316   <th width="150px"> Status </th>
 317   <th> Owner </th>
 318 </tr>
 319 <tr>
 320 <th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=12405">Polyhedral
 321 dead code elimination</a>
 322 </th><td class="done">Done
 323 </td><td>
 324 </td></tr>
 325
 326 <tr><td colspan='4'>&nbsp;</td></tr>
 327 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Back End</th></tr>
 328 <tr style="background: rgb(239, 239, 239)">
 329   <th width="400px"> Task </th>
 330   <th width="150px"> Status </th>
 331   <th> Owner </th>
 332 </tr>
 333 <tr>
 334 <th align="left"> OpenMP code generation support in isl backend
 335 (requirement to drop CLooG)
 336 </th><td class="done"> Done
 337 </td><td> Tobias
 338 </td></tr>
 339 <tr>
 340 <th align="left"> Run-time alias checks
 341 </th><td class="done"> Done
 342 </td><td>Johannes
 343 <tr>
 344 <th align="left"> <a
 345 href="https://polly.llvm.org/documentation/memaccess.html">Allow optimizers to
 346 change memory access functions</a>
 347 </th><td class="done"> Done
 348 </td><td>Johannes
 349 </td></tr>
 350 <tr>
 351 <th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=12406">Make code
 352 generation independent of the clast</a>
 353 </th><td class="done">Done
 354 </td><td>
 355 </td></tr>
 356
 357 <tr>
 358 <tr><td colspan='4'>&nbsp;</td></tr>
 359 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> General</th></tr>
 360 <tr style="background: rgb(239, 239, 239)">
 361   <th width="400px"> Task </th>
 362   <th width="150px"> Status </th>
 363   <th> Owner </th>
 364 </tr>
 365 <tr>
 366 <th align="left"> Teach bugpoint to extract regions
 367 </th><td class="nice"> Open
 368 </td><td>
 369 </td></tr>
 370 <tr>
 371 <th align="left"> Add <a
 372 href="https://web.cse.ohio-state.edu/~pouchet.2/software/polybench/">Polybench
 373 3.2</a> to the LLVM test suite
 374 </th><td class="done"> Done
 375 </td><td>
 376 </td></tr>
 377 <tr>
 378 <th align="left"> Build against an installed LLVM
 379 </th><td class="done"> Done<br />
 380 </td><td>
 381 </td></tr>
 382 <tr>
 383 <th align="left"> Setup buildbot regression testers using LNT
 384 </th><td class="done"> Done
 385 </td><td> Tobias
 386 </td></tr>
 387 </tbody></table>
 388 <h3 id="llvm"> Polly as a LLVM Project (Finished February 2012)</h3>
 389
 390 <table class="wikitable" cellpadding="2">
 391
 392 <tbody>
 393 <tr style="background: rgb(239, 239, 239);">
 394 <th>Task
 395 </th><th> Status
 396 </th><th>Owner
 397 </th></tr>
 398 <tr>
 399 <th align="left"> Move to LLVM SVN
 400 </th><td class="done" align="center">
 401 <a
 402 href="https://llvm.org/svn/llvm-project/polly"
 403 >https://llvm.org/svn/llvm-project/polly</a>
 404 </td><td> Tobias
 405
 406 </td></tr>
 407 <tr>
 408 <th align="left"> Commit mails
 409 </th><td class="done" align="center">
 410 llvm-commits@lists.llvm.org
 411 </td><td> Tobias
 412 </td></tr>
 413 <tr>
 414
 415 <th align="left"> LLVM Bugzilla category
 416 </th><td class="done" align="center">
 417 <a href="https://bugs.llvm.org/enter_bug.cgi?product=Projects">LLVM Bugzilla</a>
 418 <br />
 419 (Product is 'Projects', Component is 'Polly')
 420 </td><td> Tobias
 421 <tr>
 422 <th align="left"> Website
 423 </th><td class="done" align="center">
 424 <a href="https://polly.llvm.org">https://polly.llvm.org</a>
 425 </td><td> Tobias
 426 </td></tr>
 427 <tr>
 428 <th align="left">Buildbot that runs 'make polly-test'
 429 </th><td class="done" align="center">
 430 <a href="http://lab.llvm.org:8011/console">Buildbot</a>
 431 </td>
 432 <td> Tobias, Andreas
 433 </td></tr>
 434 </th><td>
 435
 436 </td></tr>
 437 </tbody></table>
 438 <h3 id="phase2"> Phase 2 - First Optimizations and Enhanced User Experience (Finished
 439 February 2012)</h3>
 440 <p>
 441
 442 First optimizations to show the usefulness of Polly and enhance the user
 443 experience. We also try to increase the amount of code we can optimize.
 444 </p>
 445 <table class="wikitable" cellpadding="2">
 446
 447 <tbody>
 448 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Frontend </th></tr>
 449 <tr style="background: rgb(239, 239, 239)">
 450   <th width="400px"> Task </th>
 451   <th width="150px"> Status </th>
 452   <th> Owner </th>
 453 </tr>
 454 <tr>
 455 <tr>
 456 <th align="left"> Allow parameters in access functions
 457 </th><td align="center" class='done'> Done
 458 </td><td> Tobias
 459 </td></tr>
 460
 461 <tr>
 462 <th align="left"> Improved Scalar Evolution parsing
 463 </th><td align="center" class='done'> Done
 464 </td><td> Tobias
 465 </td></tr>
 466 <tr>
 467 <th align="left"> (Graphical) user feedback on Scop Detection
 468 </th><td align="center" class='done'> Done
 469 </td><td> Tobias
 470 </td></tr>
 471 <tr><td colspan='4'>&nbsp;</td></tr>
 472 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Optimizer </th></tr>
 473 <tr style="background: rgb(239, 239, 239)">
 474   <th width="400px"> Task </th>
 475   <th width="150px"> Status </th>
 476   <th> Owner </th>
 477 </tr>
 478 <tr>
 479 <th align="left"> Dependency Analysis
 480 </th><td class="done" align="center"> Done
 481 </td><td> Tobias
 482 </td></tr>
 483 <tr>
 484 <tr>
 485 <th align="left"> Optimizer - Connect Pluto (through PoCC)
 486 </th><td class="done" align="center"> Done
 487 </td><td> Tobias
 488 </td></tr>
 489 <tr>
 490 <tr>
 491 <th align="left"> Optimizer - Add ISL internal Pluto like optimizer
 492 </th><td class="done" align="center"> Done
 493 </td><td> Tobias
 494 </td></tr>
 495
 496 <tr>
 497 <th align="left"> Import/Export - SCoPLib 0.2 (needed for PoCC)
 498 </th><td class="done" align="center">Done
 499
 500 </td><td> Tobias
 501 </td></tr>
 502 <tr><td colspan='4'>&nbsp;</td></tr>
 503 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Back End</th></tr>
 504 <tr style="background: rgb(239, 239, 239)">
 505   <th width="400px"> Task </th>
 506   <th width="150px"> Status </th>
 507   <th> Owner </th>
 508 </tr>
 509 <tr>
 510 <th align="left">SIMD code generation for trivially vectorizable loops
 511 </th><td class="done">Done
 512 </td><td>Tobias
 513 </td></tr>
 514 <tr>
 515 <th align="left">OpenMP code generation
 516 </th><td class="done">Done
 517 </td><td> Raghesh, Tobias
 518
 519 </td></tr>
 520 <tr>
 521 <tr><td colspan='4'>&nbsp;</td></tr>
 522 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> General</th></tr>
 523 <tr style="background: rgb(239, 239, 239)">
 524   <th width="400px"> Task </th>
 525   <th width="150px"> Status </th>
 526   <th> Owner </th>
 527 </tr>
 528 <tr>
 529 <th align="left"> clang integration
 530 </th><td class="done" align="center"> done
 531
 532 </td><td> Tobias
 533 </td></tr>
 534 <tr>
 535 <th align="left"> Commit RegionPass patch upstream
 536 </th><td class="done" align="center"> done
 537
 538 </td><td> Tobias
 539 </td></tr>
 540 <tr>
 541 </tbody></table>
 542 <h3 id="phase1">Phase 1 - Get Something Working (Finished October 2010)</h3>
 543 <p>Create a minimal version of Polly that can transform an LLVM-IR program to
 544 the polyhedral model and back to LLVM-IR. No transformations are performed.
 545 </p>
 546 <table class="wikitable" cellpadding="2">
 547
 548 <tbody>
 549 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Front End</th></tr>
 550 <tr style="background: rgb(239, 239, 239)">
 551   <th width="400px"> Task </th>
 552   <th width="150px"> Status </th>
 553   <th> Owner </th>
 554 </tr>
 555
 556 <th align="left"> Region detection
 557 </td><td class="done"> Done
 558 </td><td>Ether
 559 </td></tr>
 560 <tr>
 561 <th align="left"> Access Functions
 562 </td><td class="done"> Done
 563 </td><td>John, Ether
 564 </td></tr>
 565 <tr>
 566 <th align="left"> Alias sets
 567 </td><td class="done"> Done
 568 </td><td>Ether
 569 </td></tr>
 570 <tr>
 571 <th align="left"> Scalar evolution to affine expression
 572 </td><td class="done"> Done
 573
 574 </td><td>
 575 Ether
 576 </td></tr>
 577 <tr>
 578 <th align="left"> SCoP extraction
 579 </td><td class="done"> Done
 580 </td><td>Tobias, Ether
 581
 582 </td></tr>
 583 <tr>
 584 <th align="left"> SCoPs to polyhedral model
 585 </td><td class="done"> Done
 586 </td><td>Tobias, Ether
 587 </td></tr>
 588 <tr><td colspan='4'>&nbsp;</td></tr>
 589 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Optimizer </th></tr>
 590 <tr style="background: rgb(239, 239, 239)">
 591   <th width="400px"> Task </th>
 592   <th width="150px"> Status </th>
 593   <th> Owner </th>
 594 </tr>
 595 <tr>
 596 <th align="left"> Define polyhedral description
 597 </td><td class="done"> Done
 598 </td><td>Tobias
 599
 600 </td></tr>
 601 <tr><td colspan='4'>&nbsp;</td></tr>
 602 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Back End</th></tr>
 603 <tr style="background: rgb(239, 239, 239)">
 604   <th width="400px"> Task </th>
 605   <th width="150px"> Status </th>
 606   <th> Owner </th>
 607 </tr>
 608 <tr>
 609 <th align="left"> Create LLVM-IR using CLooG
 610 </td><td class="done"> Done
 611 </td><td> Tobias
 612
 613 </td></tr>
 614 <tr><td colspan='4'>&nbsp;</td></tr>
 615 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> General</th></tr>
 616 <tr style="background: rgb(239, 239, 239)">
 617   <th width="400px"> Task </th>
 618   <th width="150px"> Status </th>
 619   <th> Owner </th>
 620 </tr>
 621 <tr>
 622 <th align="left"> Setup git repositories
 623
 624 </td><td class="done"> Done
 625 </td><td> Tobias
 626 </td></tr>
 627 <tr>
 628 <th align="left"> Add CLooG/isl to build system
 629 </td><td class="done"> Done
 630 </td><td> Tobias
 631
 632 </td></tr>
 633
 634 </tbody></table>
 635 </div>
 636 </div>
 637 </body>
 638 </html>