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 Comparisions 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/gpgpucodegen.html">GPGPU Code 346Generation</a> 347</th><td class="niceinprogress">in progress 348</td><td> 349Yabin 350</td></tr> 351<tr> 352<th align="left"> <a 353href="https://polly.llvm.org/documentation/memaccess.html">Allow optimizers to 354change 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="https://bugs.llvm.org/show_bug.cgi?id=12406">Make code 360generation 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'> </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 380href="https://web.cse.ohio-state.edu/~pouchet.2/software/polybench/">Polybench 3813.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 410href="https://llvm.org/svn/llvm-project/polly" 411>https://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"> 418llvm-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="https://bugs.llvm.org/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="https://polly.llvm.org">https://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 447February 2012)</h3> 448<p> 449 450First optimizations to show the usefullness of Polly and enhance the user 451experience. 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'> </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'> </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'> </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 552the 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> 583Ether 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'> </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'> </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'> </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> 647