• Graphite
• Code_motion

Let's say that the original program is the following:

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

This could be encoded using the following scattering functions:

# 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  4

1
s0 s1 s2

Rescheduling of statements S1 and S2 can be performed by changing the time of execution 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

for which the output of CLooG is as follows:

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