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 Comparisions
 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="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> 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="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"> Commit mails
 417 </th><td class="done" align="center">
 418 llvm-commits@lists.llvm.org
 419 </td><td> Tobias
 420 </td></tr>
 421 <tr>
 422
 423 <th align="left"> LLVM Bugzilla category
 424 </th><td class="done" align="center">
 425 <a href="http://llvm.org/bugs/enter_bug.cgi?product=Projects">LLVM Bugzilla</a>
 426 <br />
 427 (Product is 'Projects', Component is 'Polly')
 428 </td><td> Tobias
 429 <tr>
 430 <th align="left"> Website
 431 </th><td class="done" align="center">
 432 <a href="http://polly.llvm.org">http://polly.llvm.org</a>
 433 </td><td> Tobias
 434 </td></tr>
 435 <tr>
 436 <th align="left">Buildbot that runs 'make polly-test'
 437 </th><td class="done" align="center">
 438 <a href="http://lab.llvm.org:8011/console">Buildbot</a>
 439 </td>
 440 <td> Tobias, Andreas
 441 </td></tr>
 442 </th><td>
 443
 444 </td></tr>
 445 </tbody></table>
 446 <h3 id="phase2"> Phase 2 - First Optimizations and Enhanced User Experience (Finished
 447 February 2012)</h3>
 448 <p>
 449
 450 First optimizations to show the usefullness of Polly and enhance the user
 451 experience. We also try to increase the amount of code we can optimize.
 452 </p>
 453 <table class="wikitable" cellpadding="2">
 454
 455 <tbody>
 456 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Frontend </th></tr>
 457 <tr style="background: rgb(239, 239, 239)">
 458   <th width="400px"> Task </th>
 459   <th width="150px"> Status </th>
 460   <th> Owner </th>
 461 </tr>
 462 <tr>
 463 <tr>
 464 <th align="left"> Allow parameters in access functions
 465 </th><td align="center" class='done'> Done
 466 </td><td> Tobias
 467 </td></tr>
 468
 469 <tr>
 470 <th align="left"> Improved Scalar Evolution parsing
 471 </th><td align="center" class='done'> Done
 472 </td><td> Tobias
 473 </td></tr>
 474 <tr>
 475 <th align="left"> (Graphical) user feedback on Scop Detection
 476 </th><td align="center" class='done'> Done
 477 </td><td> Tobias
 478 </td></tr>
 479 <tr><td colspan='4'>&nbsp;</td></tr>
 480 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Optimizer </th></tr>
 481 <tr style="background: rgb(239, 239, 239)">
 482   <th width="400px"> Task </th>
 483   <th width="150px"> Status </th>
 484   <th> Owner </th>
 485 </tr>
 486 <tr>
 487 <th align="left"> Dependency Analysis
 488 </th><td class="done" align="center"> Done
 489 </td><td> Tobias
 490 </td></tr>
 491 <tr>
 492 <tr>
 493 <th align="left"> Optimizer - Connect Pluto (through PoCC)
 494 </th><td class="done" align="center"> Done
 495 </td><td> Tobias
 496 </td></tr>
 497 <tr>
 498 <tr>
 499 <th align="left"> Optimizer - Add ISL internal Pluto like optimizer
 500 </th><td class="done" align="center"> Done
 501 </td><td> Tobias
 502 </td></tr>
 503
 504 <tr>
 505 <th align="left"> Import/Export - SCoPLib 0.2 (needed for PoCC)
 506 </th><td class="done" align="center">Done
 507
 508 </td><td> Tobias
 509 </td></tr>
 510 <tr><td colspan='4'>&nbsp;</td></tr>
 511 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Back End</th></tr>
 512 <tr style="background: rgb(239, 239, 239)">
 513   <th width="400px"> Task </th>
 514   <th width="150px"> Status </th>
 515   <th> Owner </th>
 516 </tr>
 517 <tr>
 518 <th align="left">SIMD code generation for trivially vectorizable loops
 519 </th><td class="done">Done
 520 </td><td>Tobias
 521 </td></tr>
 522 <tr>
 523 <th align="left">OpenMP code generation
 524 </th><td class="done">Done
 525 </td><td> Raghesh, Tobias
 526
 527 </td></tr>
 528 <tr>
 529 <tr><td colspan='4'>&nbsp;</td></tr>
 530 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> General</th></tr>
 531 <tr style="background: rgb(239, 239, 239)">
 532   <th width="400px"> Task </th>
 533   <th width="150px"> Status </th>
 534   <th> Owner </th>
 535 </tr>
 536 <tr>
 537 <th align="left"> clang integration
 538 </th><td class="done" align="center"> done
 539
 540 </td><td> Tobias
 541 </td></tr>
 542 <tr>
 543 <th align="left"> Commit RegionPass patch upstream
 544 </th><td class="done" align="center"> done
 545
 546 </td><td> Tobias
 547 </td></tr>
 548 <tr>
 549 </tbody></table>
 550 <h3 id="phase1">Phase 1 - Get Something Working (Finished October 2010)</h3>
 551 <p>Create a minimal version of Polly that can transform an LLVM-IR program to
 552 the polyhedral model and back to LLVM-IR. No transformations are performed.
 553 </p>
 554 <table class="wikitable" cellpadding="2">
 555
 556 <tbody>
 557 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Front End</th></tr>
 558 <tr style="background: rgb(239, 239, 239)">
 559   <th width="400px"> Task </th>
 560   <th width="150px"> Status </th>
 561   <th> Owner </th>
 562 </tr>
 563
 564 <th align="left"> Region detection
 565 </td><td class="done"> Done
 566 </td><td>Ether
 567 </td></tr>
 568 <tr>
 569 <th align="left"> Access Functions
 570 </td><td class="done"> Done
 571 </td><td>John, Ether
 572 </td></tr>
 573 <tr>
 574 <th align="left"> Alias sets
 575 </td><td class="done"> Done
 576 </td><td>Ether
 577 </td></tr>
 578 <tr>
 579 <th align="left"> Scalar evolution to affine expression
 580 </td><td class="done"> Done
 581
 582 </td><td>
 583 Ether
 584 </td></tr>
 585 <tr>
 586 <th align="left"> SCoP extraction
 587 </td><td class="done"> Done
 588 </td><td>Tobias, Ether
 589
 590 </td></tr>
 591 <tr>
 592 <th align="left"> SCoPs to polyhedral model
 593 </td><td class="done"> Done
 594 </td><td>Tobias, Ether
 595 </td></tr>
 596 <tr><td colspan='4'>&nbsp;</td></tr>
 597 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Optimizer </th></tr>
 598 <tr style="background: rgb(239, 239, 239)">
 599   <th width="400px"> Task </th>
 600   <th width="150px"> Status </th>
 601   <th> Owner </th>
 602 </tr>
 603 <tr>
 604 <th align="left"> Define polyhedral description
 605 </td><td class="done"> Done
 606 </td><td>Tobias
 607
 608 </td></tr>
 609 <tr><td colspan='4'>&nbsp;</td></tr>
 610 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Back End</th></tr>
 611 <tr style="background: rgb(239, 239, 239)">
 612   <th width="400px"> Task </th>
 613   <th width="150px"> Status </th>
 614   <th> Owner </th>
 615 </tr>
 616 <tr>
 617 <th align="left"> Create LLVM-IR using CLooG
 618 </td><td class="done"> Done
 619 </td><td> Tobias
 620
 621 </td></tr>
 622 <tr><td colspan='4'>&nbsp;</td></tr>
 623 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> General</th></tr>
 624 <tr style="background: rgb(239, 239, 239)">
 625   <th width="400px"> Task </th>
 626   <th width="150px"> Status </th>
 627   <th> Owner </th>
 628 </tr>
 629 <tr>
 630 <th align="left"> Setup git repositories
 631
 632 </td><td class="done"> Done
 633 </td><td> Tobias
 634 </td></tr>
 635 <tr>
 636 <th align="left"> Add CLooG/isl to build system
 637 </td><td class="done"> Done
 638 </td><td> Tobias
 639
 640 </td></tr>
 641
 642 </tbody></table>
 643 </div>
 644 </div>
 645 </body>
 646 </html>