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 20Optimizations (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 23February 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"> - 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"> - 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"> - 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'> </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"> 91Support for Modulos 92</th><td align="center" class='done'> Done 93</td><td> Johannes 94</td></tr> 95<tr> 96<th align="left"> 97Boolean Combinations 98</th><td align="center" class='done'> Done 99</td><td> Johannes 100</td></tr> 101<tr> 102<th align="left"> 103Unsigned Integers 104</th><td align="center" class='done'> Done 105</td><td> Johannes 106</td></tr> 107<tr> 108<th align="left"> 109Pointer Comparisons 110</th><td align="center" class='done'> Done 111</td><td> Johannes 112</td></tr> 113<tr> 114<th align="left"> 115Non-affine subregions 116</th><td align="center" class='done'> Done 117</td><td> Johannes 118</td></tr> 119 120<tr><td colspan='4'> </td></tr> 121<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Polly as an 122analysis </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"> 131Model 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"> 137Code generate scalar dependences 138</th><td align="center" class='done'> Done 139</td><td> 140</td></tr> 141<tr> 142<th align="left"> 143Model 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"> 149Code 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 155the need for independent blocks</a> 156</th><td class="done"> Done 157</td><td> 158</td></tr> 159<tr> 160<th align="left"> 161Remove polly-prepare pass 162</th><td align="center" class='open'> Open 163</td><td> 164</td></tr> 165 166<tr><td colspan='4'> </td></tr> 167<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Correctness in 168cornercases </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 176optimal 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 182integer wrapping</a> 183</th><td align="center" class='done'> Done 184</td><td> Johannes 185</td></tr 186 187<tr><td colspan='4'> </td></tr> 188<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Optimize Julia 189code with Polly 190analysis </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"> 198Integrate Polly into Julia 199</th><td align="center" class='open'> Open 200</td><td> 201</td></tr> 202<tr> 203<th align="left"> 204Eliminate run-time bounds checks 205</th><td align="center" class='open'> Open 206</td><td> 207</td></tr> 208<tr> 209<th align="left"> - 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"> - Actually eliminate statements 215</th><td align="center" class='done'> Done 216</td><td> 217</td></tr> 218 219<tr><td colspan='4'> </td></tr> 220<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Improved 221Optimizations 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"> 230Multi-level tiling 231</th><td align="center" class='open'> Open 232</td><td> 233</td></tr> 234<tr> 235<th align="left"> 236Register Tiling 237</th><td align="center" class='open'> Open 238</td><td> 239</td></tr> 240<tr> 241<th align="left"> 242Full/partial tile separation for vectorization 243</th><td align="center" class='done'> Done 244</td><td> 245</td></tr> 246<th align="left"> 247Loop 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 255Optimizations (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 277href="https://bugs.llvm.org/show_bug.cgi?id=12403">Variable-size 278multi-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 284href="https://bugs.llvm.org/show_bug.cgi?id=12407">Derive information for 285the 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 293grained 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'> </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 321dead code elimination</a> 322</th><td class="done">Done 323</td><td> 324</td></tr> 325 326<tr><td colspan='4'> </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 345href="https://polly.llvm.org/documentation/memaccess.html">Allow optimizers to 346change 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 352generation 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'> </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 372href="https://web.cse.ohio-state.edu/~pouchet.2/software/polybench/">Polybench 3733.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 402href="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"> 410llvm-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 439February 2012)</h3> 440<p> 441 442First optimizations to show the usefulness of Polly and enhance the user 443experience. 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'> </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'> </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'> </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 544the 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> 575Ether 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'> </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'> </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'> </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> 639