First, let's say that the original program is like this:

for (s1=0;s1<=n;s1++) {
  S2(i = s1) ;
  S1(i = s1) ;
}

This could be encoded in CLooG format as follows:

# language: C
c

# parameter {n | n>= 0}
1 3 
#  n  1
1  1  0
1
n

2 # Number of statements:

1
# {i | 0<=i<=n}
2 4
#  i  n   1
1  1  0   0
1 -1  1   0
0  0  0

1
# {i | 0<=i<=n}
2 4
#  i  n   1
1  1  0   0
1 -1  1   0
0  0  0

1
i

2 # Scattering functions

3 7
# s0 s1 s2  i  n  1
0  1  0  0  0  0  0
0  0  1  0 -1  0  0
0  0  0  1  0  0  5

3 7
# s0 s1 s2  i  n  1
0  1  0  0  0  0  0
0  0  1  0 -1  0  0
0  0  0  1  0  0  6

1
s0 s1 s2

Loop fission, aka. loop distribution, could be performed by changing the schedule of the loop containing the statement S1 as follows: (see the dimension s0 of the scattering polyhedron)

# language: C
c

# parameter {n | n>= 0}
1 3 
#  n  1
1  1  0
1
n

2 # Number of statements:

1
# {i | 0<=i<=n}
2 4
#  i  n   1
1  1  0   0
1 -1  1   0
0  0  0

1
# {i | 0<=i<=n}
2 4
#  i  n   1
1  1  0   0
1 -1  1   0
0  0  0

1
i

2 # Scattering functions

3 7
# s0 s1 s2  i  n  1
0  1  0  0  0  0  1
0  0  1  0 -1  0  0
0  0  0  1  0  0  5

3 7
# s0 s1 s2  i  n  1
0  1  0  0  0  0  0
0  0  1  0 -1  0  0
0  0  0  1  0  0  6

1
s0 s1 s2

for which the output of CLooG is as follows:

for (s1=0;s1<=n;s1++) {
  S1(i = s1) ;
}
for (s1=0;s1<=n;s1++) {
  S2(i = s1) ;
}

From this form, one can fuse the loops back, by changing the execution time of the loops to be the same.

None: Graphite/Fusion_fission (last edited 2009-02-18 00:26:29 by 163)