Loop extension incompatible with scattering unions?

[ftynse]

Loop extension uses consecutive integers to identify loops. Any other part of the SCoP does not feature any information about loops, which only appear at a code generation stage. Semantically, loop information should not belong to the polyhedral description.

Having a scattering union with two parts may result in a statement occurring in multiple loop nests.
For example, scheduling

for (i = 0; i < N; i++)
  for (j = 0; j < M; j++)
    S[i+j] += 1;

with

SCATTERING                                                                                                                                            
# Union with 2 parts                                                                                                                                  
2                                                                                                                                                     
# Union part No.1                                                                                                                                     
6 10 5 2 0 1                                                                                                                                          
# e/i| c1   c2   c3   c4   c5 |  i    j |  N |  1                                                                                                     
   0   -1    0    0    0    0    0    0    0    1    ## c1 == 1                                                                                       
   0    0   -1    0    1    0    1    0    0    0    ## -c2+c4+i == 0                                                                                 
   0    0    0   -1    0    0    0    0    0    0    ## c3 == 0                                                                                       
   0    0    0    0   -1    0    0    1    0    0    ## c4 == j                                                                                       
   0    0    0    0    0   -1    0    0    0    0    ## c5 == 0                                                                                       
   1    0    1    0   -1    0    0    0    0   -5    ## c2-c4-5 >= 0                                                                                  
# Union part No.2                                                                                                                                     
6 10 5 2 0 1                                                                                                                                          
# e/i| c1   c2   c3   c4   c5 |  i    j |  N |  1                                                                                                     
   0   -1    0    0    0    0    0    0    0    0    ## c1 == 0                                                                                       
   0    0   -1    0    0    0    1    0    0    0    ## c2 == i                                                                                       
   0    0    0   -1    0    0    0    0    0    0    ## c3 == 0                                                                                       
   0    0    0    0   -1    0    0    1    0    0    ## c4 == j                                                                                       
   0    0    0    0    0   -1    0    0    0    0    ## c5 == 0                                                                                       
   1    0   -1    0    0    0    0    0    0    4    ## -c2+4 >= 0

results in two distinct loops due to different beta-vectors.

But the loop extension (and, apparently, internal loop processing in Candl and CLooG) assumes a statement can only be nested in a single loop nest. This becomes problematic when introducing parallelism. In this example, for the first statement occurrence (beta-vector [0,0,0]), the inner loop is parallel and the outer is not while, for the second statement occurrence (beta-vector [1,0,0]), the outer loop is parallel and the inner is not. Yet the loop extension does not allow to express this, nor does it address any of the generated loop nests separately. Declaring the inner loop parallel for the first statement occurrence will automatically make the inner loop parallel for the second occurrence, which is wrong.

Possible solutions:

1. conservative approach -- tools that generate the loop extension should consider all possible loop nests surrounding the statement given its scattering union and disable parallelism when at least one of the loops at the same depth carries dependence;
2. change loop extension to use beta-prefixes -- they are uniquely identifying the loop even in presence of scattering unions;
3. get rid of the loop extension -- add semantics information to each dimension of each relation in the union, one of possible semantics being parallelism.

Pros and cons of these solutions:

1. loses granularity and does not allow to communicate some kinds of parallelism; does not require to modify existing tools that introduce the loop extension but no scattering unions;
2. introduces the knowledge of beta-prefixes in the format, requires moving beta-related stuff from Clay to OpenScop, requires modifying existing tools so that they conform to the new format;
3. conforming to the recent papers on union-of-relations, the cleanest solution; may make the format backwards-incompatible (unless semantics is introduced as a statement-level extension and maintained throughout modifications); may require existing tool modification, but two approaches can coexist during a transition period.