On Fri, 2008-02-08 at 10:11 -0600, Sebastian Pop wrote:
> 2008/2/7 Tobias Grosser <[EMAIL PROTECTED]>:
> > 2. Which loops are part of a SCoP:
> >
> > At the moment we detect the loops, which are part of a SCoP like this:
> >
> > FORALL_BB_IN_SCOP(bb)
> > {
> > VEC_loops_add(bb->loop_father);
> > }
> >
> > This seems incorrect if we look at this SCoP:
> >
> > h #loop0
> > |
> > a # loop0
> > |
> > v
> > b # loop1
> > |\
> > v ^
> > b | #loop1
> > | d #loop1
> > v/
> > c #loop1
> > |
> > v
> > f #loop0
> >
> > entry: h
> > exit: e
> > SCoP: a, b, c, d, f
> >
> > So there may be bbs like "a", which have a loop_father, but the
> > loop_father is not completely contained in the SCoP. Therefore I do not
> > think, it is correct to make these loops part of the SCoP.
>
> FORALL_BB_IN_SCOP(bb)
> {
> loop = bb->loop_father;
> entry_loop = scop_entry (scop)->loop_father;
> if (loop != entry_loop)
> VEC_loops_add(loop);
> }
This is only in the case of a single loop nest correct. And even there
only if we keep the definition of the entry being not part of the loop.
Look at two loops in a row (which we do not detect properly at the
moment):
a
|
v
b
|\
v ^
c |
| f
v/
d
|
v
k
|
v
e
|\
v ^
h |
| j
v/
l
|
i
entry: a
exit: i
SCoP: b,c,d,f,k,e,h,l,j
There we would add "loop_father(k)", which would be incorrect. What we
can do is something like this:
FORALL_BB_IN_SCOP(bb)
{
loop = bb->loop_father;
if (bb_in_scop(loop->header) && bb_in_scop (loop->latch))
VEC_loops_add(loop);
}
If the header and the latch of a loop are part of the SCoP, all bbs of
the loop are part of the SCoP?
As every bb in the loop is dominated by the header and the header is
dominated by the entry of the SCoP all bbs in the loop are dominated by
the entry of the SCoP.
If the latch is part of the SCoP, the blocks before also have to be part
of the SCoP, so it seems that the complete loop is in the SCoP.
But in the case of the latch it is not easy to proof, as our SCoP
definition needs an extension.
At the moment we add all bbs which are dominated by entry and
postdominated by exit. This is not correct, if we only add the first
part of a loop:
a
|
v
b
|\
v ^
c |
| h
v |
d ^
| |
v |
e |
| |
v/
f
|
v
g
entry: a
exit: e
SCoP: b,c,d
Example code:
scop-latch_in_scop.c
scop-latch_in_scop.c.dot
(If you generate this dot file it may be possible, that the latch is not
shown as part of the SCoP. This is because this bb is incorrectly part
of two SCoPs and therefore overwritten with the color of the second
SCoP)
In this case "h" is dominated by "a" and postdominated by "d", and at
the moment graphite adds "h" to the SCoP, what is incorrect.
At the moment I am not sure how to define the bbs in a SCoP correctly.
Tobias
/* { dg-do compile } */
/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
void bar (void);
int toto()
{
/* Scop 1. */
int i, j, k;
int a[100][100];
int b[100];
/* End scop 1. */
for (i = 1; i < 100; i++)
{
/* Scop 2. */
for (j = 1; j < 100; j++)
b[i+j] = b[i+j-1] + 2;
/* End Scop 2. */
if (i * 2 == i + 8)
a[i+2][i] = 2;
else
a[i][i] = 2;
for (k = 1; k < 100; k++)
b[i+k] = b[i+k-5] + 2;
bar();
}
/* Scop 4. */
return a[3][5] + b[1];
/* End scop 4. */
}
/* { dg-final { scan-tree-dump-times "number of SCoPs: 4" 1 "graphite"} } */
/* { dg-final { cleanup-tree-dump "graphite" } } */
digraph all {
0 [style="bold,filled",fillcolor="#e41a1c"];
0 -> 2;
2 [style="bold",color="#e41a1c"];
2 [style="bold,filled",fillcolor="#377eb8"];
2 -> 13;
3 [style="bold",color="#377eb8"];
3 -> 4;
4 [style="bold",color="#377eb8"];
4 -> 3;
4 -> 5;
5 [style="bold",color="#377eb8"];
5 -> 6;
5 -> 8;
6 [style="bold",color="#377eb8"];
6 -> 7;
7 [style="bold",color="#377eb8"];
7 -> 10;
8 [style="bold",color="#377eb8"];
8 -> 7;
9 [style="bold",color="#377eb8"];
9 -> 10;
10 [style="bold",color="#377eb8"];
10 -> 9;
10 -> 11;
11 [style="bold",color="#377eb8"];
11 [style="bold,filled",fillcolor="#4daf4a"];
11 [style="bold,diagonals,filled"];
11 -> 12;
11 -> 14;
12 [style="bold",color="#4daf4a"];
12 [style="bold",color="#377eb8"];
12 -> 13;
13 [style="bold",color="#377eb8"];
13 -> 4;
14 [style="bold",color="#4daf4a"];
14 [style="bold,filled",fillcolor="#984ea3"];
14 [style="bold,diagonals,filled"];
14 -> 1;
1 [style="bold",color="#984ea3"];
2 [shape=box];
11 [shape=box];
14 [shape=box];
1 [shape=box];
}
