639 lines · 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 and20Optimizations (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 (Finished23February 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++ bindings42</th><td align="center" class='open'> Open43</td><td>44</td>45</tr>46<th align="left"> - Add isl C++ bindings generator to isl47</th><td align="center" class='open'> Open48</td><td>49</td>50</tr>51<tr>52<th align="left"> Add isl as an external library to Polly SVN53</th><td align="center" class='done'> Done54</td><td>55</td>56</tr>57<tr>58<th align="left"> Compile-time: Speed up transformations59</th><td align="center">60</td><td>61</td>62</tr>63<th align="left"> - Optimize isl_int for small integers64</th><td align="center" class='done'> Done65</td><td>66</td>67</tr>68<tr>69<th align="left"> Compile-time: Minimize SCoP detection time70</th><td align="center" class='open'> Open71</td><td>72</td>73</tr>74<th align="left"> - Reconsider pass-ordering (move Polly later)75</th><td align="center" class='open'> Open76</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 coverage82</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 Modulos92</th><td align="center" class='done'> Done93</td><td> Johannes94</td></tr>95<tr>96<th align="left">97Boolean Combinations98</th><td align="center" class='done'> Done99</td><td> Johannes100</td></tr>101<tr>102<th align="left">103Unsigned Integers104</th><td align="center" class='done'> Done105</td><td> Johannes106</td></tr>107<tr>108<th align="left">109Pointer Comparisons110</th><td align="center" class='done'> Done111</td><td> Johannes112</td></tr>113<tr>114<th align="left">115Non-affine subregions116</th><td align="center" class='done'> Done117</td><td> Johannes118</td></tr>119 120<tr><td colspan='4'> </td></tr>121<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Polly as an122analysis </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 Polly132</th><td align="center" class='done'> Done133</td><td>134</td></tr>135<tr>136<th align="left">137Code generate scalar dependences138</th><td align="center" class='done'> Done139</td><td>140</td></tr>141<tr>142<th align="left">143Model PHI dependences directly in Polly144</th><td align="center" class='done'> Done145</td><td>146</td></tr>147<tr>148<th align="left">149Code generate PHI dependences150</th><td align="center" class='done'> Done151</td><td>152</td></tr>153<tr>154<th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=12398">Remove155the need for independent blocks</a>156</th><td class="done"> Done157</td><td>158</td></tr>159<tr>160<th align="left">161Remove polly-prepare pass162</th><td align="center" class='open'> Open163</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 in168cornercases </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">Derive176optimal types (instead of always using i64)</a>177</th><td class="open"> Open178</td><td>179</td></tr>180<tr>181<th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=12397">Model182integer wrapping</a>183</th><td align="center" class='done'> Done184</td><td> Johannes185</td></tr186 187<tr><td colspan='4'> </td></tr>188<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Optimize Julia189code with Polly190analysis </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 Julia199</th><td align="center" class='open'> Open200</td><td>201</td></tr>202<tr>203<th align="left">204Eliminate run-time bounds checks205</th><td align="center" class='open'> Open206</td><td>207</td></tr>208<tr>209<th align="left"> - Reconsider unreachables in post-dominance tree210</th><td align="center" class='open'> Open211</td><td>212</td></tr>213 214<th align="left"> - Actually eliminate statements215</th><td align="center" class='done'> Done216</td><td>217</td></tr>218 219<tr><td colspan='4'> </td></tr>220<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Improved221Optimizations in Polly222</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 tiling231</th><td align="center" class='open'> Open232</td><td>233</td></tr>234<tr>235<th align="left">236Register Tiling237</th><td align="center" class='open'> Open238</td><td>239</td></tr>240<tr>241<th align="left">242Full/partial tile separation for vectorization243</th><td align="center" class='done'> Done244</td><td>245</td></tr>246<th align="left">247Loop interchange after vectorization to maximize stride-one accesses248</th><td align="center" class='open'> Open249</td><td>250</td></tr>251</table>252 253 254<h3 id="phase3"> Phase 3 - Improve Robustness, Interoperability and255Optimizations (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 functions268</th><td align="center" class='done'> Done, needs testing269</td><td>Marcello270</td>271</tr>272 273 274<tr>275<tr>276<th align="left"> <a277href="https://bugs.llvm.org/show_bug.cgi?id=12403">Variable-size278multi-dimensional arrays</a>279</th><td align="center" class='done'> Done280</td><td>Sebastian281</td></tr>282<tr>283<th align="left"> <a284href="https://bugs.llvm.org/show_bug.cgi?id=12407">Derive information for285the SCoP context286</a>287</th>288<td align="center" class='nice'> Open289</td><td>290</td></tr>291<tr>292<th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=12402">Finer293grained statements</a>294</th><td align="center" class='nice'> Open295</td><td>296</td></tr>297<tr>298<th align="left"> Detect reductions299</th><td align="center" class='done'>Done300</td><td>Johannes301</td></tr>302<tr>303<th align="left"> Generate code for reductions304</th><td align="center" class='niceinprogress'>in progress305</td><td>Johannes306</td></tr>307<tr>308<th align="left"> Assume static sized arrays are only accessed in-bounds309</th><td align="center" class='done'>Done310</td><td>Tobias311</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">Polyhedral321dead code elimination</a>322</th><td class="done">Done323</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 backend335(requirement to drop CLooG)336</th><td class="done"> Done337</td><td> Tobias338</td></tr>339<tr>340<th align="left"> Run-time alias checks341</th><td class="done"> Done342</td><td>Johannes343<tr>344<th align="left"> <a345href="https://polly.llvm.org/documentation/memaccess.html">Allow optimizers to346change memory access functions</a>347</th><td class="done"> Done348</td><td>Johannes349</td></tr>350<tr>351<th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=12406">Make code352generation independent of the clast</a>353</th><td class="done">Done354</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 regions367</th><td class="nice"> Open368</td><td>369</td></tr>370<tr>371<th align="left"> Add <a372href="https://web.cse.ohio-state.edu/~pouchet.2/software/polybench/">Polybench3733.2</a> to the LLVM test suite374</th><td class="done"> Done375</td><td>376</td></tr>377<tr>378<th align="left"> Build against an installed LLVM379</th><td class="done"> Done<br />380</td><td>381</td></tr>382<tr>383<th align="left"> Setup buildbot regression testers using LNT384</th><td class="done"> Done385</td><td> Tobias386</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>Task395</th><th> Status396</th><th>Owner397</th></tr>398<tr>399<th align="left"> Move to LLVM SVN400</th><td class="done" align="center">401<a402href="https://llvm.org/svn/llvm-project/polly"403>https://llvm.org/svn/llvm-project/polly</a>404</td><td> Tobias405 406</td></tr>407<tr>408<th align="left"> Commit mails409</th><td class="done" align="center">410llvm-commits@lists.llvm.org411</td><td> Tobias412</td></tr>413<tr>414 415<th align="left"> LLVM Bugzilla category416</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> Tobias421<tr>422<th align="left"> Website423</th><td class="done" align="center">424<a href="https://polly.llvm.org">https://polly.llvm.org</a>425</td><td> Tobias426</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, Andreas433</td></tr>434</th><td>435 436</td></tr>437</tbody></table>438<h3 id="phase2"> Phase 2 - First Optimizations and Enhanced User Experience (Finished439February 2012)</h3>440<p>441 442First optimizations to show the usefulness of Polly and enhance the user443experience. 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 functions457</th><td align="center" class='done'> Done458</td><td> Tobias459</td></tr>460 461<tr>462<th align="left"> Improved Scalar Evolution parsing463</th><td align="center" class='done'> Done464</td><td> Tobias465</td></tr>466<tr>467<th align="left"> (Graphical) user feedback on Scop Detection468</th><td align="center" class='done'> Done469</td><td> Tobias470</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 Analysis480</th><td class="done" align="center"> Done481</td><td> Tobias482</td></tr>483<tr>484<tr>485<th align="left"> Optimizer - Connect Pluto (through PoCC)486</th><td class="done" align="center"> Done487</td><td> Tobias488</td></tr>489<tr>490<tr>491<th align="left"> Optimizer - Add ISL internal Pluto like optimizer492</th><td class="done" align="center"> Done493</td><td> Tobias494</td></tr>495 496<tr>497<th align="left"> Import/Export - SCoPLib 0.2 (needed for PoCC)498</th><td class="done" align="center">Done499 500</td><td> Tobias501</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 loops511</th><td class="done">Done512</td><td>Tobias513</td></tr>514<tr>515<th align="left">OpenMP code generation516</th><td class="done">Done517</td><td> Raghesh, Tobias518 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 integration530</th><td class="done" align="center"> done531 532</td><td> Tobias533</td></tr>534<tr>535<th align="left"> Commit RegionPass patch upstream536</th><td class="done" align="center"> done537 538</td><td> Tobias539</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 to544the 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 detection557</td><td class="done"> Done558</td><td>Ether559</td></tr>560<tr>561<th align="left"> Access Functions562</td><td class="done"> Done563</td><td>John, Ether564</td></tr>565<tr>566<th align="left"> Alias sets567</td><td class="done"> Done568</td><td>Ether569</td></tr>570<tr>571<th align="left"> Scalar evolution to affine expression572</td><td class="done"> Done573 574</td><td>575Ether576</td></tr>577<tr>578<th align="left"> SCoP extraction579</td><td class="done"> Done580</td><td>Tobias, Ether581 582</td></tr>583<tr>584<th align="left"> SCoPs to polyhedral model585</td><td class="done"> Done586</td><td>Tobias, Ether587</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 description597</td><td class="done"> Done598</td><td>Tobias599 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 CLooG610</td><td class="done"> Done611</td><td> Tobias612 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 repositories623 624</td><td class="done"> Done625</td><td> Tobias626</td></tr>627<tr>628<th align="left"> Add CLooG/isl to build system629</td><td class="done"> Done630</td><td> Tobias631 632</td></tr>633 634</tbody></table>635</div>636</div>637</body>638</html>639