[graphite] Google Summer of Code 2008 is over - Thank you

[Tobias Grosser <grosser at fim dot uni-passau dot de>]

Hi gcc community, hi graphities,

since Monday Google Summer of Code 2008 is over and I would like to
write a little bit about my SOC project.

First of all I would like to thank Sebastian for being my mentor. It was
really fun to work with you. I never felt alone and always got great
mail or phone response, if I was not sure where to go. And also thanks
to all the other gcc and graphite people, that contributed to graphite
and helped me working on my GSoC project. I got many valuable mails and
bug reports helping me improving my code.

What I really liked was the good integration in the graphite team, so
that from the first days I felt like home. I got all support I needed
and our weekly (except exceptions) phone conferences helped me to get to
know the team better. Now I know some of you by hearing your
voice, but it would be even better to see you once in real live!

I also would like to thank Laurent for the CompileFarm account. A very
useful service for gcc development.

In the last weeks I realized a little problem in my graphite work.
As I worked so well with the graphite folks, I just completely forgot to
use the gcc mailing lists and to get in touch with the countless gcc
developers. So I apologize for this and will try to change this now.

As a starter I would like to inform you, what I have done during the
last 4 months:

What I wanted to do:
====================

[â]

At the moment the general shape of the GRAPHITE framework is quite clear
and people have started to work on different areas. While they reached
new areas of development, it became quite clear, that the GRAPHITE
frontend, the translation from GIMPLE to GRAPHITE has some serious
drawbacks, which stop people to continue their development fast and
efficiently.

During Summer of Code I would like to solve these problems and build a
solid basis for further graphite development.

[â]

More on my proposal at:
http://students.fim.uni-passau.de/~grosser/gcc_soc/

What is done:
=============

     1. SCoP detection
     -----------------
	We scan the CFG to detect all parts, that we can
        transform to the polyhedral representation (GRAPHITE). 

              * This pass works and is verified by the graphite and
                polyhedron test suites.
              * We detect conditions containing (<=, <, >, >=), perfect
                loop nests with single exit, and allow parameters in
                loop borders and conditons.

     2. GIMPLE => GRAPHITE
     ---------------------

        Now the control flow of the detected SCoPs is translated to the
        polyhedral representation. This means loop borders and
        conditions are inserted into a matrix, that tells us for which
        values of the loop indeces the bbs are executed. 

              * Works for all detected SCoPs

     3. Cloog Output
     ---------------
        Cloog is the library we use to regenerate the CFG. We insert the
        polyhedral model and get an ast, describing the loop structure
        after applied optimizations. Cloog is also able to optimize in
        control structures (e.g. move conditions out of loops)  so even
        without optimizations passes we get optimizations. 

              * Works for all detected SCoPs

     4. Loop blocking 
     ----------------

              * I wrote a first experimental pass, to show how graphite
                transformations work.

So GRAPHITE has now a front end, that is able to detect most of the
common loop nests and get them into the graphite representation. In
Polyhedron e.g. we detect already 411 SCoPs with 536 loops and 1303 bbs.
These are 15% of all loops (3587).

And there is many space for improvements.

What is left to be done:
========================

     1. SCoP detection 
     -----------------
              * Conditional statements containing â||â or â&&â.
              * Switch statements.
              * Loops with multiple exits.
              * Iterative optimization to maximize SCoP size.

     2. GIMPLE => GRAPHITE
     ---------------------
              * Conditional statements containing â||â or â&&â.
              * Switch statements.
              * Loops with multiple exits.
              * Allow scev parameter detection in SCoPs, that are not
                surrounded by a loop.

     3. Graphite middle end
     ----------------------
        Here we reach hardly touched ground, where a large number of
        optimizations are possible. For example:

              * Dependency detection
              * Loop splitting
              * Loop fusing
              * â
              * Automatic parallization
ï
I will keep on working on graphite, the next weeks on the import and
after that heading to some of the open tasks.

So even if Google Summer of Code has finished. I do not want to say
âGoodbyeâ, but âHelloâ to you.
I am looking forward to work with you on gcc and graphite!

See you

Tobi