[graphite] Get graphite backend working again

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

Hi Sebastian, hi Jan, hi graphities,

while trying to work on graphite I saw, that the last changes made the
code generation fail for every case.

1. Cloog-PPL creates many unnecessary conditional statements.
=============================================================

Problem since: cloog-ppl change.

At the moment cloog ppl generates at least one unnecessary condition in 
ïevery loop:

For example in (scop-0.c):

for (s_1=0;s_1<=T_4-1;s_1++) {
  if ((s_1 >= 0) && (s_1 <= T_4-1)) {
    for (s_3=0;s_3<=199;s_3++) {
      if ((s_1 >= 0) && (s_1 <= T_4-1) && (s_3 >= 0) && (s_3 <= 199)) {
        if ((s_1 >= 0) && (s_1 <= T_4-1) && (s_3 >= 0) && (s_3 <= 199)) {
          if ((s_1 >= 0) && (s_1 <= T_4-1) && (s_3 >= 0) && (s_3 <= 199)) {
            S5(s_1,s_3) ;
          }
        }
      }
    }
  }
}


As the current code generation does not support conditional statements,
we fail to generate code for them.

Who will work on that one?
Sebastian, do you think cloog ppl can be fixed easily? Or can we support
conditional statements (guards) in graphite codegen. For me it seems,
that most of the infrastructure is already available.

2. Gloog expects that only one edge leads to the SCoP.
======================================================

Problem since: scop_limit_scops(), that fixed parameter detection.

As at the moment every SCoP is surrounded by a loop:
----------------------------------------------------------------------
We limit all SCoPs to SCoPs, that are completely surrounded by a loop. 

   Example:

   for (i      |
     {         |
       for (j  |  SCoP 1
       for (k  |
     }         |

   * SCoP frontier, as this line is not surrounded by any loop. *

   for (l      |  SCoP 2

   This is necessary as scalar evolution and parameter detection need a
   outermost loop to initialize parameters correctly.  
ï----------------------------------------------------------------------

So the SCoP entry is always a loop header that has more than one
predecessor edge and again we fail to generate code, as graphite expects
at the moment only a single entry and exit edge for the SCoPs.

My thoughts about this representation:

I understand, that a SCoP should be single entry/single exit. But I am
not sure, if the representation with edges is the right one.

As far as I can see, we have something like this.

The original code:

1 3  <- 3 = difficult bb
|/
2    <- 2 = condition header   -
|\                             |
4 5  <- 5 = loop header        |
| |\                           |ï   SCoP
| |/                           |   2 -> (8)
| 6                            |
| |                            |
| 7                            -
|/
8    <- 8 = difficult bb

So we have {2, 4, 5, 6, 7} in our SCoP.

The single entry point is "bb_2". This means in the original code, all
entry edges {1->2, 3->2} lead to "bb_2". The single exit point is
"bb_8", as in the original code all edges leaving the SCoP {4->8, 7->8}
lead to "bb_8".

While in graphite, we freely move around all bbs in the SCoP and
generate a new CFG part. 


20  <- new generated to regenerate control flow
|\
| 5
| |\
| |/
| 6
| |
| 7
|/
21 ï<- new generated to regenerate control flow
|\
| 4
|/
2

So how do we connect this? We need to know all bbs, that lead to the
first bb in the new CFG part. (Here bb_20) These are scop->entry->preds.
(Here bb_2->preds = {bb_1, bb_3}).

And we have to know, what follows the last bbs of the new CFG. The next
bb
will be scop->exit. (Here bb_8)

So I think a single edge is not sufficient to represent the scop entry.
We could use a VEC of entry edges (Here {1->2, 3->2}) or we use a VEC of
bbs leading to the SCoP (Here {1, 3}) or we keep the current solution
and use the first bb in the original code (Here bb_2) and it's list
of predecessors (Here bb_2->preds = {1->2, 3->2}).

The exit seems to be easy. We need just a basic block to jump to. So we
keep this bb in scop->exit. (Here bb_8)

Is someone working on this one? Otherwise I will think about these.

See you
Tobias