blob: d39e27c6ccdaa8d4cbe67a2ff3d48f61191e46c0 [file] [log] [blame]
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
"http://www.w3.org/TR/html4/strict.dtd">
<!-- Material used from: HTML 4.01 specs: http://www.w3.org/TR/html401/ -->
<html>
<head> <META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>Polly - Todo</title>
<link type="text/css" rel="stylesheet" href="menu.css">
<link type="text/css" rel="stylesheet" href="content.css">
</head>
<body>
<div id="box">
<!--#include virtual="menu.html.incl"-->
<div id="content">
<h1> TODO </h1>
<h2> Overview</h2>
<ul>
<li><a href="#phase3">Phase 4</a></li>
<li><a href="#phase3">Phase 3 - Improve Robustness, Interoperability and
Optimizations (ongoing)</a></li>
<li><a href="#llvm">Polly as a LLVM Project (Finished February 2012)</a></li>
<li><a href="#phase2">Phase 2 - First Optimizations and Enhanced User Experience (Finished
February 2012)</a></li>
<li><a href="#phase1">Phase 1 - Get Something Working (Finished October 2010)</a>
</li>
</ul>
<h2> Individual Phases</h3>
<h3 id="phase4"> Phase 4</h3>
<table class="wikitable" cellpadding="2">
<p> </p>
<tbody>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Infrastructure </th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<tr>
<th align="left"> Move to isl C++ bindings
</th><td align="center" class='open'> Open
</td><td>
</td>
</tr>
<th align="left"> &nbsp; &nbsp; - Add isl C++ bindings generator to isl
</th><td align="center" class='open'> Open
</td><td>
</td>
</tr>
<tr>
<th align="left"> Add isl as an external library to Polly SVN
</th><td align="center" class='done'> Done
</td><td>
</td>
</tr>
<tr>
<th align="left"> Compile-time: Speed up transformations
</th><td align="center">
</td><td>
</td>
</tr>
<th align="left"> &nbsp; &nbsp; - Optimize isl_int for small integers
</th><td align="center" class='done'> Done
</td><td>
</td>
</tr>
<tr>
<th align="left"> Compile-time: Minimize SCoP detection time
</th><td align="center" class='open'> Open
</td><td>
</td>
</tr>
<th align="left"> &nbsp; &nbsp; - Reconsider pass-ordering (move Polly later)
</th><td align="center" class='open'> Open
</td><td>
</td>
</tr>
<tr><td colspan='4'>&nbsp;</td></tr>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Increase coverage
</th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<tr>
<th align="left">
Support for Modulos
</th><td align="center" class='done'> Done
</td><td> Johannes
</td></tr>
<tr>
<th align="left">
Boolean Combinations
</th><td align="center" class='done'> Done
</td><td> Johannes
</td></tr>
<tr>
<th align="left">
Unsigned Integers
</th><td align="center" class='done'> Done
</td><td> Johannes
</td></tr>
<tr>
<th align="left">
Pointer Comparisions
</th><td align="center" class='done'> Done
</td><td> Johannes
</td></tr>
<tr>
<th align="left">
Non-affine subregions
</th><td align="center" class='done'> Done
</td><td> Johannes
</td></tr>
<tr><td colspan='4'>&nbsp;</td></tr>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Polly as an
analysis </th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<tr>
<th align="left">
Model scalars dependences directly in Polly
</th><td align="center" class='done'> Done
</td><td>
</td></tr>
<tr>
<th align="left">
Code generate scalar dependences
</th><td align="center" class='done'> Done
</td><td>
</td></tr>
<tr>
<th align="left">
Model PHI dependences directly in Polly
</th><td align="center" class='done'> Done
</td><td>
</td></tr>
<tr>
<th align="left">
Code generate PHI dependences
</th><td align="center" class='done'> Done
</td><td>
</td></tr>
<tr>
<th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=12398">Remove
the need for independent blocks</a>
</th><td class="done"> Done
</td><td>
</td></tr>
<tr>
<th align="left">
Remove polly-prepare pass
</th><td align="center" class='open'> Open
</td><td>
</td></tr>
<tr><td colspan='4'>&nbsp;</td></tr>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Correctness in
cornercases </th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<tr>
<th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=10381">Derive
optimal types (instead of always using i64)</a>
</th><td class="open"> Open
</td><td>
</td></tr>
<tr>
<th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=12397">Model
integer wrapping</a>
</th><td align="center" class='done'> Done
</td><td> Johannes
</td></tr
<tr><td colspan='4'>&nbsp;</td></tr>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Optimize Julia
code with Polly
analysis </th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<th align="left">
Integrate Polly into Julia
</th><td align="center" class='open'> Open
</td><td>
</td></tr>
<tr>
<th align="left">
Eliminate run-time bounds checks
</th><td align="center" class='open'> Open
</td><td>
</td></tr>
<tr>
<th align="left"> &nbsp; &nbsp; - Reconsider unreachables in post-dominance tree
</th><td align="center" class='open'> Open
</td><td>
</td></tr>
<th align="left"> &nbsp; &nbsp; - Actually eliminate statements
</th><td align="center" class='done'> Done
</td><td>
</td></tr>
<tr><td colspan='4'>&nbsp;</td></tr>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Improved
Optimizations in Polly
</th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<th align="left">
Multi-level tiling
</th><td align="center" class='open'> Open
</td><td>
</td></tr>
<tr>
<th align="left">
Register Tiling
</th><td align="center" class='open'> Open
</td><td>
</td></tr>
<tr>
<th align="left">
Full/partial tile separation for vectorization
</th><td align="center" class='done'> Done
</td><td>
</td></tr>
<th align="left">
Loop interchange after vectorization to maximize stride-one accesses
</th><td align="center" class='open'> Open
</td><td>
</td></tr>
</table>
<h3 id="phase3"> Phase 3 - Improve Robustness, Interoperability and
Optimizations (ongoing)</h3>
<table class="wikitable" cellpadding="2">
<p> </p>
<tbody>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Frontend </th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<tr>
<th align="left"> Non-affine access functions
</th><td align="center" class='done'> Done, needs testing
</td><td>Marcello
</td>
</tr>
<tr>
<tr>
<th align="left"> <a
href="https://bugs.llvm.org/show_bug.cgi?id=12403">Variable-size
multi-dimensional arrays</a>
</th><td align="center" class='done'> Done
</td><td>Sebastian
</td></tr>
<tr>
<th align="left"> <a
href="https://bugs.llvm.org/show_bug.cgi?id=12407">Derive information for
the SCoP context
</a>
</th>
<td align="center" class='nice'> Open
</td><td>
</td></tr>
<tr>
<th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=12402">Finer
grained statements</a>
</th><td align="center" class='nice'> Open
</td><td>
</td></tr>
<tr>
<th align="left"> Detect reductions
</th><td align="center" class='done'>Done
</td><td>Johannes
</td></tr>
<tr>
<th align="left"> Generate code for reductions
</th><td align="center" class='niceinprogress'>in progress
</td><td>Johannes
</td></tr>
<tr>
<th align="left"> Assume static sized arrays are only accessed in-bounds
</th><td align="center" class='done'>Done
</td><td>Tobias
</td></tr>
<tr><td colspan='4'>&nbsp;</td></tr>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Optimizer </th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<tr>
<th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=12405">Polyhedral
dead code elimination</a>
</th><td class="done">Done
</td><td>
</td></tr>
<tr><td colspan='4'>&nbsp;</td></tr>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Back End</th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<tr>
<th align="left"> OpenMP code generation support in isl backend
(requirement to drop CLooG)
</th><td class="done"> Done
</td><td> Tobias
</td></tr>
<tr>
<th align="left"> Run-time alias checks
</th><td class="done"> Done
</td><td>Johannes
<tr>
<th align="left"> <a
href="https://polly.llvm.org/documentation/gpgpucodegen.html">GPGPU Code
Generation</a>
</th><td class="niceinprogress">in progress
</td><td>
Yabin
</td></tr>
<tr>
<th align="left"> <a
href="https://polly.llvm.org/documentation/memaccess.html">Allow optimizers to
change memory access functions</a>
</th><td class="done"> Done
</td><td>Johannes
</td></tr>
<tr>
<th align="left"> <a href="https://bugs.llvm.org/show_bug.cgi?id=12406">Make code
generation independent of the clast</a>
</th><td class="done">Done
</td><td>
</td></tr>
<tr>
<tr><td colspan='4'>&nbsp;</td></tr>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> General</th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<tr>
<th align="left"> Teach bugpoint to extract regions
</th><td class="nice"> Open
</td><td>
</td></tr>
<tr>
<th align="left"> Add <a
href="https://web.cse.ohio-state.edu/~pouchet.2/software/polybench/">Polybench
3.2</a> to the LLVM test suite
</th><td class="done"> Done
</td><td>
</td></tr>
<tr>
<th align="left"> Build against an installed LLVM
</th><td class="done"> Done<br />
</td><td>
</td></tr>
<tr>
<th align="left"> Setup buildbot regression testers using LNT
</th><td class="done"> Done
</td><td> Tobias
</td></tr>
</tbody></table>
<h3 id="llvm"> Polly as a LLVM Project (Finished February 2012)</h3>
<table class="wikitable" cellpadding="2">
<tbody>
<tr style="background: rgb(239, 239, 239);">
<th>Task
</th><th> Status
</th><th>Owner
</th></tr>
<tr>
<th align="left"> Move to LLVM SVN
</th><td class="done" align="center">
<a
href="https://llvm.org/svn/llvm-project/polly"
>https://llvm.org/svn/llvm-project/polly</a>
</td><td> Tobias
</td></tr>
<tr>
<th align="left"> Commit mails
</th><td class="done" align="center">
llvm-commits@lists.llvm.org
</td><td> Tobias
</td></tr>
<tr>
<th align="left"> LLVM Bugzilla category
</th><td class="done" align="center">
<a href="https://bugs.llvm.org/enter_bug.cgi?product=Projects">LLVM Bugzilla</a>
<br />
(Product is 'Projects', Component is 'Polly')
</td><td> Tobias
<tr>
<th align="left"> Website
</th><td class="done" align="center">
<a href="https://polly.llvm.org">https://polly.llvm.org</a>
</td><td> Tobias
</td></tr>
<tr>
<th align="left">Buildbot that runs 'make polly-test'
</th><td class="done" align="center">
<a href="http://lab.llvm.org:8011/console">Buildbot</a>
</td>
<td> Tobias, Andreas
</td></tr>
</th><td>
</td></tr>
</tbody></table>
<h3 id="phase2"> Phase 2 - First Optimizations and Enhanced User Experience (Finished
February 2012)</h3>
<p>
First optimizations to show the usefullness of Polly and enhance the user
experience. We also try to increase the amount of code we can optimize.
</p>
<table class="wikitable" cellpadding="2">
<tbody>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Frontend </th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<tr>
<tr>
<th align="left"> Allow parameters in access functions
</th><td align="center" class='done'> Done
</td><td> Tobias
</td></tr>
<tr>
<th align="left"> Improved Scalar Evolution parsing
</th><td align="center" class='done'> Done
</td><td> Tobias
</td></tr>
<tr>
<th align="left"> (Graphical) user feedback on Scop Detection
</th><td align="center" class='done'> Done
</td><td> Tobias
</td></tr>
<tr><td colspan='4'>&nbsp;</td></tr>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Optimizer </th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<tr>
<th align="left"> Dependency Analysis
</th><td class="done" align="center"> Done
</td><td> Tobias
</td></tr>
<tr>
<tr>
<th align="left"> Optimizer - Connect Pluto (through PoCC)
</th><td class="done" align="center"> Done
</td><td> Tobias
</td></tr>
<tr>
<tr>
<th align="left"> Optimizer - Add ISL internal Pluto like optimizer
</th><td class="done" align="center"> Done
</td><td> Tobias
</td></tr>
<tr>
<th align="left"> Import/Export - SCoPLib 0.2 (needed for PoCC)
</th><td class="done" align="center">Done
</td><td> Tobias
</td></tr>
<tr><td colspan='4'>&nbsp;</td></tr>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Back End</th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<tr>
<th align="left">SIMD code generation for trivially vectorizable loops
</th><td class="done">Done
</td><td>Tobias
</td></tr>
<tr>
<th align="left">OpenMP code generation
</th><td class="done">Done
</td><td> Raghesh, Tobias
</td></tr>
<tr>
<tr><td colspan='4'>&nbsp;</td></tr>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> General</th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<tr>
<th align="left"> clang integration
</th><td class="done" align="center"> done
</td><td> Tobias
</td></tr>
<tr>
<th align="left"> Commit RegionPass patch upstream
</th><td class="done" align="center"> done
</td><td> Tobias
</td></tr>
<tr>
</tbody></table>
<h3 id="phase1">Phase 1 - Get Something Working (Finished October 2010)</h3>
<p>Create a minimal version of Polly that can transform an LLVM-IR program to
the polyhedral model and back to LLVM-IR. No transformations are performed.
</p>
<table class="wikitable" cellpadding="2">
<tbody>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Front End</th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<th align="left"> Region detection
</td><td class="done"> Done
</td><td>Ether
</td></tr>
<tr>
<th align="left"> Access Functions
</td><td class="done"> Done
</td><td>John, Ether
</td></tr>
<tr>
<th align="left"> Alias sets
</td><td class="done"> Done
</td><td>Ether
</td></tr>
<tr>
<th align="left"> Scalar evolution to affine expression
</td><td class="done"> Done
</td><td>
Ether
</td></tr>
<tr>
<th align="left"> SCoP extraction
</td><td class="done"> Done
</td><td>Tobias, Ether
</td></tr>
<tr>
<th align="left"> SCoPs to polyhedral model
</td><td class="done"> Done
</td><td>Tobias, Ether
</td></tr>
<tr><td colspan='4'>&nbsp;</td></tr>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Optimizer </th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<tr>
<th align="left"> Define polyhedral description
</td><td class="done"> Done
</td><td>Tobias
</td></tr>
<tr><td colspan='4'>&nbsp;</td></tr>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Back End</th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<tr>
<th align="left"> Create LLVM-IR using CLooG
</td><td class="done"> Done
</td><td> Tobias
</td></tr>
<tr><td colspan='4'>&nbsp;</td></tr>
<tr><th colspan="3" style="background: rgb(239, 239, 239);"> General</th></tr>
<tr style="background: rgb(239, 239, 239)">
<th width="400px"> Task </th>
<th width="150px"> Status </th>
<th> Owner </th>
</tr>
<tr>
<th align="left"> Setup git repositories
</td><td class="done"> Done
</td><td> Tobias
</td></tr>
<tr>
<th align="left"> Add CLooG/isl to build system
</td><td class="done"> Done
</td><td> Tobias
</td></tr>
</tbody></table>
</div>
</div>
</body>
</html>