### Setup infrastructure at LLVM

We are currently moving to the LLVM infrastructure

Task | Status | Owner
--- | --- | ---
Move to LLVM SVN | done http://llvm.org/svn/llvm-project/polly/trunk/www | Tobias
Git mirror | done git://llvm.org/git/polly.git | Tobias
Commit mails | done llvm-commits@cs.uiuc.edu | Tobias
LLVM Bugzilla category | done LLVM Bugzilla (Product is 'Projects', Component is 'Polly') | Tobias
Website | in progress http://polly.grosser.es, later maybe polly.llvm.org | Tobias
Buildbot that runs 'make polly-test' |  | Raghesh, Andreas
Nightly performance/coverage tests (with the llvm test-suite) |  | Andreas

### Phase 2

The second phase of Polly can build on a robust, but very limited framework. In this phase work on removing limitations and extending the framework is planned. Also we plan the first very simple transformations. Furthermore the build system will be improved to simplify deployment.

Frontend
Task | Status | Owner
--- | --- | ---
Support for casts in expressions |  |  |
Support multi dimensional arrays. | planning | Tobias
Alias sets
Middle end
Task | Status | Owner
Implement ISL dependency analysis pass | working | Tobias
Connect pocc/pluto | working | Tobias
Finish OpenSCoP support |  |  |
Add SCoPLib 0.2 support to connect pocc | done | Tobias
Write simple loop blocking |  |  |
Backend
Task | Status | Owner
Code generation for non 64bit targets |  |  |
Add write support for data access functions |  |  |
Create vector loops | 70% done | Tobias
Create OpenMP loops | 90% done | Raghesh & Tobias
General tasks
Task | Status | Owner
Commit RegionPass patch upstream | done | Tobias
Build against an installed LLVM | works for cmake | ether
Setup buildbot regression testers using LNT |  |  |

### Phase 1 - Get something working (Finished October 2010)

The first iteration of this project aims to create a minimal working version of this framework, that is capable to transform an LLVM-IR program to the polyhedral model and back to LLVM-IR without applying any transformations.

Frontend
Task | Status | Owner
--- | --- | ---
Region detection | works + Committed upstream | Ether
Access Functions | Working | John + Ether
Alias sets | Still open
Scalar evolution to affine expression | Done | Ether
SCoP extraction | Working | Tobias + Ether
SCoPs to polyhedral model | Working | Tobias + Ether
Middle end
Task | Status | Owner
Define polyhedral description | Working | Tobias
Import/Export using openscop | working | Tobias
Backend
Task | Status | Owner
Create LLVM-IR using CLooG | Working | Tobias
General tasks
Task | Status | Owner
Setup git repositories | Done | Tobias
Add CLooG/isl to build system | Works on Unix | Tobias

### Further projects

There are several great projects related to polly that can already be started or are possible in the near future.

#### Extend the post dominance analysis for infinite loops (small)

At the moment the post dominance analysis cannot handle infinite loops. All basic blocks in the CFG that do not return are - at the moment - not part of the post dominance tree. However by adding some virtual edges, they could be added to the post dominator tree. Where to add the edges needs some research.

This is a small project, that is is well defined. As it is directly in LLVM it can be easily committed upstream. It is useful for polly, as the RegionInfo pass will be able to detect regions in parts of the CFG that never return.

A good starter to get into LLVM

#### Vectorization

It is planned to use Polly to support vectorization in LLVM.

The basic idea is to use Polly and the polyhedral tools to transform code such that the innermost loops can be executed in parallel. Afterwards during code generation in LLVM the loops will be created using vector instructions.

To start we plan to use Pluto to transform the loop nests. Pluto can generate vector parallel code and annotate the vector parallel loops. Some impressive results were shown on code that was afterwards vectorized by the icc enforcing vectorization. We believe LLVM can do even better, as it can interact directly with the polyhedral information.

As an example simple matrix multiplication:

    for(i=0; i<M; i++)
      for(j=0; j<N; j++)
        for(k=0; k<K; k++)
          C[i][j] = beta*C[i][j] + alpha*A[i][k] * B[k][j];

After plutos transformations with added tiling and vectorization hints:

    if ((K >= 1) && (M >= 1) && (N >= 1))
      for (t1=0;t1<=floord(M-1,32);t1++)
        for (t2=0;t2<=floord(N-1,32);t2++)
          for (t3=0;t3<=floord(K-1,32);t3++)
            for (t4=32*t1;t4<=min(M-1,32*t1+31);t4++)
              for (t5=32*t3;t5<=min(K-1,32*t3+31);t5++) {
                lbv=32*t2;
                ubv=min(N-1,32*t2+31);
                #pragma ivdep
                #pragma vector always
                for (t6=lbv; t6<=ubv; t6++)
                  C[t4][t6]=beta*C[t4][t6]+alpha*A[t4][t5]*B[t5][t6];;
             }

In this example the innermost loop is parallel without any dependencies.