[graphite] Discuss SCoP definition

[Tobias Grosser]

Hi,

while working at graphite I had some problems with the SCoP detection.
It seems to me, that I expect the SCoPs being defined slightly
different.

At the moment a SCoP is defined like this (as I understand):

A SCoP is a part of the CFG wich can be extracted, optimized using the
polyhedral model and later on inserted back into the hole, left in the
CFG.
It is defined by two bbs - the entry and the exit - where the entry
defines the beginning of the SCoP and the exit the end of the SCoP. Both
are not part of the SCoP, but define a set of bbs, which are in the
SCoP.
All bbs in the SCoP are dominated by the entry node and postdominated by
the exit node.

My problems:

1. At the moment we only support one entry node.

If we have a SCoP like this:

a
|
v
b
|\
v ^
c |
| f
v/
d
|
v
e

entry: a
exit: e
SCoP: b, c, d, f

DOT: scop_ok.dot

everything is all right. But there are also loops after an IF-Statement
possible, where e.g. g is an difficult bound:

h
|\
| v
a g*
| |
v/
b
|\
v ^
b |
| d
v/
c
|
v
f

entry: {a,g}
exit: e
SCoP: b, c, d, f

DOT: scop_if_entry.dot

The SCoP we should detect is unchanged, but there is more than one entry
node. As both "a" and "g" can jump into the SCoP.
So what can we do? The first solution is to allow a vector of entry
nodes. This seems correct, if we only look at which bbs could jump into
the SCoP. But this is incorrect, if we look at the definition of the bbs
in our SCoP. They are neiter dominated by "a" nor by "g".
So we should mark "b" as the bb which dominates all bbs in the SCoP.
If it is necessary to know which bbs can jump into the SCoP, we can look
at the list of predecessors of "b", which is {a,b,d}, and extract all
bbs not part of the SCoP.

What we detect at the moment:
scop-bar_in_if.c
scop-bar_in_if-2.c

scop-bar_in_if.dot
scop-bar_in_if-2.dot

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.

Tobias


-------------- next part --------------

digraph scop_ok {
a -> b;
b -> c;
c -> d;
d -> f;
f -> b;
d -> e;
}
-------------- next part --------------

digraph scop_ok {
h -> a;
h -> g;
g [color = red]
g -> b;
a -> b;
b -> c;
c -> d;
d -> f;
f -> b;
d -> e;
}
-------------- next part --------------
digraph all {
0 [style="bold,filled",fillcolor="#e41a1c"];
0 -> 2;
2 [style="bold",color="#e41a1c"];
2 [style="bold,filled",fillcolor="#377eb8"];
2 -> 13;
3 -> 4;
4 -> 3;
4 -> 5;
5 -> 6;
5 -> 8;
6 [style="bold",color="#377eb8"];
6 [style="bold,filled",fillcolor="#4daf4a"];
6 [style="bold,diagonals,filled"];
6 -> 7;
7 -> 10;
8 -> 7;
9 -> 10;
10 -> 9;
10 -> 11;
11 -> 12;
11 -> 14;
12 -> 13;
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];
6 [shape=box];
14 [shape=box];
1 [shape=box];
}

-------------- next part --------------
A non-text attachment was scrubbed...
Name: scop-bar_in_if.c
Type: text/x-csrc
Size: 731 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20080208/b9e0badc/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: scop-bar_in_if-2.c
Type: text/x-csrc
Size: 731 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20080208/b9e0badc/attachment-0001.bin>
-------------- next part --------------
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 [style="bold",color="#4daf4a"];
8 [style="bold,filled",fillcolor="#984ea3"];
8 [style="bold,diagonals,filled"];
8 -> 7;
9 [style="bold",color="#377eb8"];
9 -> 10;
10 [style="bold",color="#377eb8"];
10 -> 9;
10 -> 11;
11 [style="bold",color="#377eb8"];
11 -> 12;
11 -> 14;
12 [style="bold",color="#377eb8"];
12 -> 13;
13 [style="bold",color="#377eb8"];
13 -> 4;
14 [style="bold",color="#377eb8"];
14 [style="bold,filled",fillcolor="#4daf4a"];
14 [style="bold,diagonals,filled"];
14 -> 1;
1 [style="bold",color="#984ea3"];
2 [shape=box];
14 [shape=box];
8 [shape=box];
1 [shape=box];
}