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>
  94 </td></tr>
  95 <tr>
  96 <th align="left">
  97 Boolean Combinations
  98 </th><td align="center" class='done'> Done
  99 </td><td>
 100 </td></tr>
 101 <tr>
 102 <th align="left">
 103 Unsigned Integers
 104 </th><td align="center" class='open'> Open
 105 </td><td>
 106 </td></tr>
 107 <tr>
 108 <th align="left">
 109 Pointer Comparisions
 110 </th><td align="center" class='done'> Done
 111 </td><td>
 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="http://llvm.org/bugs/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="http://llvm.org/bugs/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="http://llvm.org/bugs/show_bug.cgi?id=12397">Model
 182 integer wrapping</a>
 183 </th><td align="center" class='done'> Done
 184 </td><td>
 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="http://llvm.org/bugs/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="http://llvm.org/bugs/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="http://llvm.org/bugs/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="http://llvm.org/bugs/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="http://polly.llvm.org/documentation/gpgpucodegen.html">GPGPU Code
 346 Generation</a>
 347 </th><td class="niceinprogress">in progress
 348 </td><td>
 349 Yabin
 350 </td></tr>
 351 <tr>
 352 <th align="left"> <a
 353 href="http://polly.llvm.org/documentation/memaccess.html">Allow optimizers to
 354 change memory access functions</a>
 355 </th><td class="done"> Done
 356 </td><td>Johannes
 357 </td></tr>
 358 <tr>
 359 <th align="left"> <a href="http://llvm.org/bugs/show_bug.cgi?id=12406">Make code
 360 generation independent of the clast</a>
 361 </th><td class="done">Done
 362 </td><td>
 363 </td></tr>
 364
 365 <tr>
 366 <tr><td colspan='4'>&nbsp;</td></tr>
 367 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> General</th></tr>
 368 <tr style="background: rgb(239, 239, 239)">
 369   <th width="400px"> Task </th>
 370   <th width="150px"> Status </th>
 371   <th> Owner </th>
 372 </tr>
 373 <tr>
 374 <th align="left"> Teach bugpoint to extract regions
 375 </th><td class="nice"> Open
 376 </td><td>
 377 </td></tr>
 378 <tr>
 379 <th align="left"> Add <a
 380 href="http://www.cse.ohio-state.edu/~pouchet/software/polybench/">Polybench
 381 3.2</a> to the LLVM test suite
 382 </th><td class="done"> Done
 383 </td><td>
 384 </td></tr>
 385 <tr>
 386 <th align="left"> Build against an installed LLVM
 387 </th><td class="done"> Done<br />
 388 </td><td>
 389 </td></tr>
 390 <tr>
 391 <th align="left"> Setup buildbot regression testers using LNT
 392 </th><td class="done"> Done
 393 </td><td> Tobias
 394 </td></tr>
 395 </tbody></table>
 396 <h3 id="llvm"> Polly as a LLVM Project (Finished February 2012)</h3>
 397
 398 <table class="wikitable" cellpadding="2">
 399
 400 <tbody>
 401 <tr style="background: rgb(239, 239, 239);">
 402 <th>Task
 403 </th><th> Status
 404 </th><th>Owner
 405 </th></tr>
 406 <tr>
 407 <th align="left"> Move to LLVM SVN
 408 </th><td class="done" align="center">
 409 <a
 410 href="http://llvm.org/svn/llvm-project/polly"
 411 >http://llvm.org/svn/llvm-project/polly</a>
 412 </td><td> Tobias
 413
 414 </td></tr>
 415 <tr>
 416 <th align="left"> Git mirror
 417 </th><td class="done" align="center">
 418 git://llvm.org/git/polly.git
 419 </td><td> Tobias
 420 </td></tr>
 421 <tr>
 422 <th align="left"> Commit mails
 423 </th><td class="done" align="center">
 424 llvm-commits@lists.llvm.org
 425 </td><td> Tobias
 426 </td></tr>
 427 <tr>
 428
 429 <th align="left"> LLVM Bugzilla category
 430 </th><td class="done" align="center">
 431 <a href="http://llvm.org/bugs/enter_bug.cgi?product=Projects">LLVM Bugzilla</a>
 432 <br />
 433 (Product is 'Projects', Component is 'Polly')
 434 </td><td> Tobias
 435 <tr>
 436 <th align="left"> Website
 437 </th><td class="done" align="center">
 438 <a href="http://polly.llvm.org">http://polly.llvm.org</a>
 439 </td><td> Tobias
 440 </td></tr>
 441 <tr>
 442 <th align="left">Buildbot that runs 'make polly-test'
 443 </th><td class="done" align="center">
 444 <a href="http://lab.llvm.org:8011/console">Buildbot</a>
 445 </td>
 446 <td> Tobias, Andreas
 447 </td></tr>
 448 </th><td>
 449
 450 </td></tr>
 451 </tbody></table>
 452 <h3 id="phase2"> Phase 2 - First Optimizations and Enhanced User Experience (Finished
 453 February 2012)</h3>
 454 <p>
 455
 456 First optimizations to show the usefullness of Polly and enhance the user
 457 experience. We also try to increase the amount of code we can optimize.
 458 </p>
 459 <table class="wikitable" cellpadding="2">
 460
 461 <tbody>
 462 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Frontend </th></tr>
 463 <tr style="background: rgb(239, 239, 239)">
 464   <th width="400px"> Task </th>
 465   <th width="150px"> Status </th>
 466   <th> Owner </th>
 467 </tr>
 468 <tr>
 469 <tr>
 470 <th align="left"> Allow parameters in access functions
 471 </th><td align="center" class='done'> Done
 472 </td><td> Tobias
 473 </td></tr>
 474
 475 <tr>
 476 <th align="left"> Improved Scalar Evolution parsing
 477 </th><td align="center" class='done'> Done
 478 </td><td> Tobias
 479 </td></tr>
 480 <tr>
 481 <th align="left"> (Graphical) user feedback on Scop Detection
 482 </th><td align="center" class='done'> Done
 483 </td><td> Tobias
 484 </td></tr>
 485 <tr><td colspan='4'>&nbsp;</td></tr>
 486 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Optimizer </th></tr>
 487 <tr style="background: rgb(239, 239, 239)">
 488   <th width="400px"> Task </th>
 489   <th width="150px"> Status </th>
 490   <th> Owner </th>
 491 </tr>
 492 <tr>
 493 <th align="left"> Dependency Analysis
 494 </th><td class="done" align="center"> Done
 495 </td><td> Tobias
 496 </td></tr>
 497 <tr>
 498 <tr>
 499 <th align="left"> Optimizer - Connect Pluto (through PoCC)
 500 </th><td class="done" align="center"> Done
 501 </td><td> Tobias
 502 </td></tr>
 503 <tr>
 504 <tr>
 505 <th align="left"> Optimizer - Add ISL internal Pluto like optimizer
 506 </th><td class="done" align="center"> Done
 507 </td><td> Tobias
 508 </td></tr>
 509
 510 <tr>
 511 <th align="left"> Import/Export - SCoPLib 0.2 (needed for PoCC)
 512 </th><td class="done" align="center">Done
 513
 514 </td><td> Tobias
 515 </td></tr>
 516 <tr><td colspan='4'>&nbsp;</td></tr>
 517 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Back End</th></tr>
 518 <tr style="background: rgb(239, 239, 239)">
 519   <th width="400px"> Task </th>
 520   <th width="150px"> Status </th>
 521   <th> Owner </th>
 522 </tr>
 523 <tr>
 524 <th align="left">SIMD code generation for trivially vectorizable loops
 525 </th><td class="done">Done
 526 </td><td>Tobias
 527 </td></tr>
 528 <tr>
 529 <th align="left">OpenMP code generation
 530 </th><td class="done">Done
 531 </td><td> Raghesh, Tobias
 532
 533 </td></tr>
 534 <tr>
 535 <tr><td colspan='4'>&nbsp;</td></tr>
 536 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> General</th></tr>
 537 <tr style="background: rgb(239, 239, 239)">
 538   <th width="400px"> Task </th>
 539   <th width="150px"> Status </th>
 540   <th> Owner </th>
 541 </tr>
 542 <tr>
 543 <th align="left"> clang integration
 544 </th><td class="done" align="center"> done
 545
 546 </td><td> Tobias
 547 </td></tr>
 548 <tr>
 549 <th align="left"> Commit RegionPass patch upstream
 550 </th><td class="done" align="center"> done
 551
 552 </td><td> Tobias
 553 </td></tr>
 554 <tr>
 555 </tbody></table>
 556 <h3 id="phase1">Phase 1 - Get Something Working (Finished October 2010)</h3>
 557 <p>Create a minimal version of Polly that can transform an LLVM-IR program to
 558 the polyhedral model and back to LLVM-IR. No transformations are performed.
 559 </p>
 560 <table class="wikitable" cellpadding="2">
 561
 562 <tbody>
 563 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Front End</th></tr>
 564 <tr style="background: rgb(239, 239, 239)">
 565   <th width="400px"> Task </th>
 566   <th width="150px"> Status </th>
 567   <th> Owner </th>
 568 </tr>
 569
 570 <th align="left"> Region detection
 571 </td><td class="done"> Done
 572 </td><td>Ether
 573 </td></tr>
 574 <tr>
 575 <th align="left"> Access Functions
 576 </td><td class="done"> Done
 577 </td><td>John, Ether
 578 </td></tr>
 579 <tr>
 580 <th align="left"> Alias sets
 581 </td><td class="done"> Done
 582 </td><td>Ether
 583 </td></tr>
 584 <tr>
 585 <th align="left"> Scalar evolution to affine expression
 586 </td><td class="done"> Done
 587
 588 </td><td>
 589 Ether
 590 </td></tr>
 591 <tr>
 592 <th align="left"> SCoP extraction
 593 </td><td class="done"> Done
 594 </td><td>Tobias, Ether
 595
 596 </td></tr>
 597 <tr>
 598 <th align="left"> SCoPs to polyhedral model
 599 </td><td class="done"> Done
 600 </td><td>Tobias, Ether
 601 </td></tr>
 602 <tr><td colspan='4'>&nbsp;</td></tr>
 603 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Optimizer </th></tr>
 604 <tr style="background: rgb(239, 239, 239)">
 605   <th width="400px"> Task </th>
 606   <th width="150px"> Status </th>
 607   <th> Owner </th>
 608 </tr>
 609 <tr>
 610 <th align="left"> Define polyhedral description
 611 </td><td class="done"> Done
 612 </td><td>Tobias
 613
 614 </td></tr>
 615 <tr><td colspan='4'>&nbsp;</td></tr>
 616 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Back End</th></tr>
 617 <tr style="background: rgb(239, 239, 239)">
 618   <th width="400px"> Task </th>
 619   <th width="150px"> Status </th>
 620   <th> Owner </th>
 621 </tr>
 622 <tr>
 623 <th align="left"> Create LLVM-IR using CLooG
 624 </td><td class="done"> Done
 625 </td><td> Tobias
 626
 627 </td></tr>
 628 <tr><td colspan='4'>&nbsp;</td></tr>
 629 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> General</th></tr>
 630 <tr style="background: rgb(239, 239, 239)">
 631   <th width="400px"> Task </th>
 632   <th width="150px"> Status </th>
 633   <th> Owner </th>
 634 </tr>
 635 <tr>
 636 <th align="left"> Setup git repositories
 637
 638 </td><td class="done"> Done
 639 </td><td> Tobias
 640 </td></tr>
 641 <tr>
 642 <th align="left"> Add CLooG/isl to build system
 643 </td><td class="done"> Done
 644 </td><td> Tobias
 645
 646 </td></tr>
 647
 648 </tbody></table>
 649 </div>
 650 </div>
 651 </body>
 652 </html>