Hi Tobi,<div><br></div><div><span style>Thank you very much for the elaborate advises and sorry for the long delay. I have kept thinking your advises and investigate more detail of the existing code of Polly. Now, I re-evaluate my proposal and something interesting is added to the new one. :)</span> <br>
<br><div class="gmail_quote">On Fri, Mar 30, 2012 at 5:52 AM, Tobias Grosser <span dir="ltr"><<a href="mailto:tobias@grosser.es">tobias@grosser.es</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi Qingrui Liu,<br>
<br>
sorry for replying slowly.<br>
<br>
Here some comments:<div class="im"><br>
<br>
On 03/24/2012 02:47 PM, Tsingray Liu wrote:<br>
</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
Hi all,<br>
    My name is Qingrui Liu, a student at Sun Yat-sen University, China.<br>
I have been working on high level synthesis project which is implemented<br></div>
as a back-end of LLVM, in the last two years. When I want to use Polly to<div class="im"><br>
generate parallel LLVM-IR from Polly-IR for me as input to my high level<br></div>
synthesis too ls at the begining of this year, I found that  Polly's<div class="im"><br>
back-end is not flexible and modular enough to allow user adding new<br>
platform support.<br>
</div></blockquote>
<br>
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.<div class="im">
<br></div></blockquote><div><span style>Yes, I see the appreciable improvement you did. That's great.</span> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
So I am going to improve the existing back-end to an<br>
adaptive and modular back-end which will unleash the power of Polly to<br>
other projects.<br>
</blockquote>
<br></div>
This sentence sounds very nice, but it is actually not very descriptive.<br>
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<br>
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]).<br>

<br>
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.<br>
This means simple to understand, but still flexible and well structured.<br>
<br></blockquote><div><br></div><div><span style>Sorry, maybe it is too abstract for people to understand what is the power underlying the Polly. Now, Polly do optimization on the Loop in LLVM and generate a optimized loop back to LLVM. However, something like  CodeGenForOpenMP should be independent from Polly which means, even without Polly, CodegenForOpenMP could applied individually in LLVM as a Pass which only accept the basic elements in LLVM,e.g. Loop, BasicBlock and Module etc.. The situation is the same to the PTX back-end which only accept basic elements in LLVM e.g. Loop, BasicBlock and module etc.. This is the way Polly should go and the power it should unleash.</span></div>
<div style><br></div><div style>But how to achieve this goal? It is absolutely an impasse with the existing back-end. So an adaptive and robust backend with an adapter is proposed to provide the LLVM basic element i.e. Loop in Polly to various back-ends in LLVM such as PTX back-end and OpenCL etc.</div>
<div style><br></div><div style>So It is the most pressing problem for Polly to provide an adaptive and robust backend for various back-end in LLVM. I will elaborate the adapter below.</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
To be short, I plan to implement my proposal in steps as follows:<br></div>
1. refactor the exis ting back-end to a preliminary modular back-end.<br>
</blockquote>
<br>
I think here and later in your proposal you should explain:<br>
<br>
- What are the problems with the current code?<br>
<br>
I do not say there are no problems, but to judge your proposal it is necessary to understand what you want to improve.<br>
<br>
- What changes you want to perform here?<br>
<br>
Do you want to move classes, define new interfaces, split some functionality into new classes, ...?<br>
<br>
(You do not even propose the perfect solution. Feel free to say there are several solutions, which benefits they have and what still needs<br>
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)<div class="im">
<br></div></blockquote><div> </div><div style>The propose of the first step is as I mentioned above that some code like <span style="font-size:9pt;font-family:Arial,sans-serif">codegenForSequential, codegenForVector and codegenForOpenMP should be independent form the current Polly which mean they can be an individual pass applied in LLVM without Polly.  </span></div>
<div style><span style="font-size:9pt;font-family:Arial,sans-serif"><br></span></div><div><span style>Also, some code refactor could be done by the way. such as addressing the bugs in polly while refatoring the existing backend into a modular one. such as:</span> </div>
<div><br></div><div><div style>1. we can extract more independent functionality in the existing back-end into the helper classes in different files rather than assemble them in a single file (this will take time to do so and need to be well tested), I have made the first step of it in patch[1]. More steps will be done in the coming summer of code. </div>
<div style><br></div><div style>2. as you have post in the Todo list, the existing Polly back-end <span style="font-size:9pt;font-family:Arial,sans-serif">is currently centered on the CLAST. This will be another challenge to this project.</span></div>
<div style><span style="font-size:9pt;font-family:Arial,sans-serif"><br></span></div><div style><span style="font-size:9pt;font-family:Arial,sans-serif">3. Another problem come up to me while I was fixing the bug of Polly[2]. The existing back-end use i64 everywhere to ensure a temporal correct result. Other project which may use date type larger than i64 may cause failure in Polly. So in the new code generator, we should be able to </span><span style="font-size:9pt;font-family:Arial,sans-serif">calculate the minimal type that is always large enough to ensure the correctness of the program.</span></div>
</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
2. Add A CodeGen adapter, abstract away the detail of CLAst.<br>
</blockquote>
<br></div>
How would this look like? What would be the difference to the clast?<br>
<br>
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.<br>

<br>
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.<div class="im">
<br></div></blockquote><div><br></div><div><div style>Here, we come the most controversial part of this proposal.  As I mentioned above, the adapter proposed here could provide user-friendly  interfaces to various back-ends in LLVM to get the Loop optimized by Polly. Also, some basic interfaces which can be a virtual method to be inherited by the back-ends and passes in LLVM could be established such as doAPIDefinition,<span style="font-size:9pt;font-family:Arial,sans-serif">doInitializationLoop, doFinalizationLoop, runOnLoop, doInitializationStmt, doFinalizationStmt and runOnStmt, etc.. these methods (interfaces) provide back-ends or passes in LLVM to implement their platform-specifc requirement. </span></div>
<div style><span style="font-size:9pt;font-family:Arial,sans-serif"><br></span></div><div style><font face="Arial, sans-serif"><span style="font-size:12px">Take the recently hot topic on PTX back-end for example, the PTX back-end coiuld call the doAPIDefinition method to applied their specific API to the Loop in Polly. It is greatly benefit developers who would like to make use of Polly and their parallel computing platforms.</span></font></div>
</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
3. Implementation of Specific code generation class to the new back-end.<br>
In this phase, I am going to implement a SIMD code generation class.<br>
</blockquote>
<br></div>
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<br>

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.<div class="im">
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
An ultimate construction of the new backend will be like the figure below:<br>
<br>
[Original Polly codegeneration pass]   [Click codegeneration[1]]  [whole<br>
function vectorize codegeneration[2]], ....<br>
                                               \<br>
        |                                /<br>
                                                   \<br>
        |                           /<br>
                                                      \<br>
         |                        /<br>
                                                          \<br>
         |                    /<br>
                                                              \<br>
         |                 /<br>
<br>
   CodeGen adapter<br>
<br>
/              \<br>
                                                                      /<br>
                    \<br>
                                                                   /<br>
                      \<br>
                                            Cloog AST infrastructure<br>
      XXX  AST infrastructure ...<br>
                                                                \<br>
                         /<br>
                                                                   \<br>
                     /<br>
                                                                      \<br>
                   /<br>
<br>
  SCOP (Polly IR)<br>
</blockquote>
<br></div>
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.<br>
<br>
Some examples would definitely help.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
After the new backend is done, I think it will easy for other developers<br>
to implement a code generation pass which will meet the requirements of<br>
their platforms or LLVM back-ends. So the optimized LLVM-IR could be<br>
passed to the ordinary LLVM back-ends, such as the high level synthesis<br>
back-end I mentioned above. It will be a great help to both the<br>
developers and LLVM.<br>
</blockquote>
<br></div>
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'.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Tobias Grosser and Ether, who are the contributors of Polly, have<br>
assented to be my mentor, If my proposal is approved. Is this idea good<br>
enough for the Google summer of code? If it is, I am going to write a<br>
proposal for it. Any suggestion is appreciated.<br>
</blockquote>
<br></div>
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).<br>

<br>
Besides your own ideas, you may also consider the following points:<br>
<br>
- Extract the clast logic in a simple helper class (as proposed by ether and you) [4]<br>
<br>
- Removing the independent blocks pass [5]<br>
<br>
- Integrate a new code generator<br>
<br>
We are planning to work on a new code generator that will solve several issues. Using your modularization to integrate this code generator would<br>
be a perfect use case.<br>
<br></blockquote><div><span style>Thank you for these valuable advises. My proposal will be much better with your advises.</span></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

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. ;-)<br>
<br>
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.<br>
This one might not be too difficult [3]. (Let me know if you need help).<br>
<br>
Cheers<br>
Tobi<br></blockquote><div><br></div><div style>In conclusion, Polly with a adaptive and robust back-end would greatly help developers who would like to use Polly with their parallel computing platfroms and it is the most pressing problem for Polly to make such a back-end.:)</div>
<div style> </div><div style><br></div><div style>Sincerely,</div><div><span style>Tsingray</span> </div><div><br></div><div>PS. We have come to an agreement that all these should be done patch by patch upon the current back-end.</div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
[1] <a href="http://stackoverflow.com/questions/2338656/when-is-abstraction-and-modularization-a-bad-practice-in-programming" target="_blank">http://stackoverflow.com/<u></u>questions/2338656/when-is-<u></u>abstraction-and-<u></u>modularization-a-bad-practice-<u></u>in-programming</a><br>

[2] <a href="http://students.fim.uni-passau.de/~grosser/gcc_soc/" target="_blank">http://students.fim.uni-<u></u>passau.de/~grosser/gcc_soc/</a><br>
[3] <a href="http://llvm.org/bugs/show_bug.cgi?id=12311" target="_blank">http://llvm.org/bugs/show_bug.<u></u>cgi?id=12311</a><br>
[4] <a href="http://llvm.org/bugs/show_bug.cgi?id=12406" target="_blank">http://llvm.org/bugs/show_bug.<u></u>cgi?id=12406</a><br>
[5] <a href="http://llvm.org/bugs/show_bug.cgi?id=12398" target="_blank">http://llvm.org/bugs/show_bug.<u></u>cgi?id=12398</a><br>
</blockquote></div><br></div>