[LLVMdev] GSoC2012 proposal -- A new Back-end for polyhedral Optimization framework for LLVM (Polly)

[Tobias Grosser]

Hi Qingrui Liu,

sorry for replying slowly.

Here some comments:

On 03/24/2012 02:47 PM, Tsingray Liu wrote:
> Hi all,
>     My name is Qingrui Liu, a student at Sun Yat-sen University, China.
> I have been working on high level synthesis project which is implemented
> as a back-end of LLVM, in the last two years. When I want to use Polly to
> generate parallel LLVM-IR from Polly-IR for me as input to my high level
> synthesis too ls at the begining of this year, I found that  Polly's
> back-end is not flexible and modular enough to allow user adding new
> platform support.

You are right adding new platforms is probably not as straightforward as 
it could be and especially two months ago the Polly SIMD/OpenMP/Scalar 
code generation was strongly coupled. That made the code difficult to 
understand and to adapt. In the last weeks I restructured the code 
generation to remove the strong connection between those three. The 
situation should now be a lot better, even though there may still be 
possibilities to improve it.

> So I am going to improve the existing back-end to an
> adaptive and modular back-end which will unleash the power of Polly to
> other projects.

This sentence sounds very nice, but it is actually not very descriptive.
The problem here is that it stands in the empty space. There are a many 
ways to modularize code. Some of them may be helpful and good as they
can improve the structure of the code and can simplify the addition of 
new features. However, modularization can also be counterproductive as 
it may add unnecessary overhead that complicates the understanding of 
the code (See first answer here [1]).

Making the back end structure easier to extend is a good thing. However, 
we should make sure we understand the needs of possible back ends such 
that we can choose a modularization that matches these needs.
This means simple to understand, but still flexible and well structured.


> To be short, I plan to implement my proposal in steps as follows:
> 1. refactor the exis ting back-end to a preliminary modular back-end.

I think here and later in your proposal you should explain:

- What are the problems with the current code?

I do not say there are no problems, but to judge your proposal it is 
necessary to understand what you want to improve.

- What changes you want to perform here?

Do you want to move classes, define new interfaces, split some 
functionality into new classes, ...?

(You do not even propose the perfect solution. Feel free to say there 
are several solutions, which benefits they have and what still needs
to be investigated to decide which is best. You can even state you have 
no solution for a problem, but you plan a week to think about it. For 
such a proposal it is more important that people see you understood the 
problems and that you have an idea of how to approach them. In case you 
are unsure about something, it is better to say this and give a plan how 
you will proceed to find a solution than to propose a solution you are 
not yet sure about)

> 2. Add A CodeGen adapter, abstract away the detail of CLAst.

How would this look like? What would be the difference to the clast?

Again, I do not say we don't need this, but it would be helpful if you 
can express why this is needed and what features it should have. In 
general I prefer to have as little code as possible. That means for 
every code we add there needs to be an obvious benefit.

A solution without a CodeGen adapter may be to extract all the 
functionality within the clast into helper classes, create a very simple 
clast walker and call the helper classes there. We can do exactly the 
same for another new_codegen_ast, without having to define an CodeGen 
adapter. This does not need to be the better solution, but this is a 
possible alternative.

> 3. Implementation of Specific code generation class to the new back-end.
> In this phase, I am going to implement a SIMD code generation class.

It would be great if you could make sure that your plan consists of 
gradual improvements. This means to build up as little parallel 
infrastructure as possible. At best, you add your improvements directly 
the current code generation. This will ensure it is properly tested and
it matches the needs we have. I especially want to be sure we do not end 
up in a situation where the OpenMP code generation still works in the 
old infrastructure and SIMD is done in the new one. Better make the old 
infrastructure gradually become the new one.

> An ultimate construction of the new backend will be like the figure below:
>
> [Original Polly codegeneration pass]   [Click codegeneration[1]]  [whole
> function vectorize codegeneration[2]], ....
>                                                \
>         |                                /
>                                                    \
>         |                           /
>                                                       \
>          |                        /
>                                                           \
>          |                    /
>                                                               \
>          |                 /
>
>    CodeGen adapter
>
> /              \
>                                                                       /
>                     \
>                                                                    /
>                       \
>                                             Cloog AST infrastructure
>       XXX  AST infrastructure ...
>                                                                 \
>                          /
>                                                                    \
>                      /
>                                                                       \
>                    /
>
>   SCOP (Polly IR)

I have currently no idea how your CodeGen adapter will look like. And I 
have especially no idea how you plan to perform whole function 
vectorization and click code generation based on Polly.

Some examples would definitely help.

> After the new backend is done, I think it will easy for other developers
> to implement a code generation pass which will meet the requirements of
> their platforms or LLVM back-ends. So the optimized LLVM-IR could be
> passed to the ordinary LLVM back-ends, such as the high level synthesis
> back-end I mentioned above. It will be a great help to both the
> developers and LLVM.

In general I would rather emphasize in your proposal the individual 
steps necessary, than to build everything around a currently not yet 
described 'CodeGen adapter'.

> Tobias Grosser and Ether, who are the contributors of Polly, have
> assented to be my mentor, If my proposal is approved. Is this idea good
> enough for the Google summer of code? If it is, I am going to write a
> proposal for it. Any suggestion is appreciated.

I think working on the back end of Polly is a good idea. There is still 
a lot of stuff that needs to be done there and I am sure a good proposal 
can be written for this. However, the best thing you can do is to start 
to write your proposal. Because only by doing this you will start to get 
into Polly and to understand what kind of problems exist and how you 
could solve them. Listing the problems, finding examples, possible 
solutions and creating some timeline to implement this will help here a 
lot. I am glad to give feedback (and promise to be reactive the days up 
to the deadline).

Besides your own ideas, you may also consider the following points:

- Extract the clast logic in a simple helper class (as proposed by ether 
and you) [4]

- Removing the independent blocks pass [5]

- Integrate a new code generator

We are planning to work on a new code generator that will solve several 
issues. Using your modularization to integrate this code generator would
be a perfect use case.

To have an idea what I think a proposal might look like you can have a 
look at my proposal a couple of years ago [2]. Ether should also have 
his old proposal. As it was accepted it was apparently good enough. ;-)

Another hint. It is in general very good if you already contributed some 
code. Fixing one of the existing Polly bugs would be a good start.
This one might not be too difficult [3]. (Let me know if you need help).

Cheers
Tobi

[1] 
http://stackoverflow.com/questions/2338656/when-is-abstraction-and-modularization-a-bad-practice-in-programming
[2] http://students.fim.uni-passau.de/~grosser/gcc_soc/
[3] http://llvm.org/bugs/show_bug.cgi?id=12311
[4] http://llvm.org/bugs/show_bug.cgi?id=12406
[5] http://llvm.org/bugs/show_bug.cgi?id=12398