Unroll re-executes statement instances

[ftynse]

Example

#include <stdio.h>

int main() {
  int i;
#pragma scop
/* Clay
   unroll([0], 3);
 */
  for (i = 0; i < 10; i++) {
    printf("%d\n", i);
  }
#pragma endscop
  return 0;
}

statements instances printf(..., 7) and printf(..., 8) are executed twice: inside unrolled loop as (i+1) and (i+2) and inside epilog.

Epilog statement does not have a lower bound in the loop and the unrolled loops stops incrementing too early.

[ftynse]

Furthermore, in case of lower bounds in the scattering relation, e.g. introduced by an index-set splitting, the epilog has wrong lower bound.

[ftynse]

b2101c347ed937ab468b25732b5f79f40055b043 addresses the post-iss lower bound problem by removing all lower bounds from the epilog scattering relations. It is a hack, and I would like to have a nicer solution.

[ftynse]

The original problem may be related to the code generation rather than to transformation. ClooG generates different codes for this example with respect to -strides option. And these codes are not semantically equivalent:

for (i=0;i<=N-4;i++) {
  if (i%3 == 0) {
    foo();
  }
}

and

for (i=0;i<=N-4;i+=3) {
  foo();
}

have different side effects! The value of i is different after executing these loops. So if it is used again without reinitialization, like the unroll epilog does, the semantics becomes different.

The correct lower bound for i in the epilog would be floord(N, factor) * factor, but I do not see a way to put it to the scattering relation.

[Ced]

Hi, yes this is true. But compilers have to handle that problem separately (just like the fact that an iterator may overflow). From CLooG's point of view they are equivalent (the problem CLooG solves to produce a code that scans all integer points inside polyhedra, once and only once, according to a specified order).

Unroll in Clay is clearly using a "feature" to generate the epilog. It's not really a "polyhedral" transformation. It is dangerous and should be used only at the end of a script with the appropriate options for CLooG...

[ftynse]

Okay then. This bug is either wontfix or I can do more hackery to workaround it, namely introduce a statement i = floord(N, factor) * factor just before the epilog loop.

[ftynse]

https://github.com/ftynse/clay/commit/2a8e9660299896bc200b61cb375cafc55cd94adf attempts at purely polyhedral implementation of unroll, without epilog problems.