Re: [GSoC] checking for the loop parallelism

[Roman Gareev]

> This looks very similar to what we reported to the isl mailing list. It is
> definitely not the best test case for the parallelism patch. In fact, I
> doubt this requires the parallelism test at all.

I've found out, that Graphite generates the expected code using the
separate option for all dimensions:

{
  for (int c1 = 0; c1 < min(n, mid); c1 += 1) {
    S_6(c1);
    S_8(c1);
  }
  for (int c1 = max(mid, 0); c1 < n; c1 += 1) {
    S_7(c1);
    S_8(c1);
  }
}

However, there are problems in vectorization of this code (I've
attached .vect files generated by versions, which use CLooG and ISL).
It seems that it is related to inappropriate type sizes. Do you know
anything about it?

> You should have a look at the following test case for openmp tests:
> libgomp/testsuite/libgomp.graphite

Graphite successfully passes all the tests from
libgomp/testsuite/libgomp.graphite except graphite-isl-ast-to-gimple.c
and graphite-poly.h.

If we consider the code generated by ISL and by CLooG from
force-parallel-5.c, we'll see, that they are similar:

the code generated by ISL:

for (int c1 = 0; c1 <= 1499; c1 += 1)
  S_3(c1);

for (int c1 = 0; c1 <= 497; c1 += 1)
  for (int c3 = 0; c3 <= c1; c3 += 1)
    S_7(c1, c3);

the code generated by ClooG:


for (scat_1=0;scat_1<=1499;scat_1++) {
  (scat_1);
}

for (scat_1=0;scat_1<=497;scat_1++) {
  for (scat_3=0;scat_3<=scat_1;scat_3++) {
    (scat_1,scat_3);
  }
}

the source code:

void abort (void);

#define N 500

void foo(void)
{
  int i,j;
  int A[3*N], B[3*N];

  for (i = 0; i < 3*N; i++)
    B[i] = A[i] = i;

  for (i = 1; i < N; i++)
    for (j = 1; j < i; j++)
      /* This loop carried no dependency, it fails
at code generation part.*/
      A[j+N] = A[j] + j;

  for (i = 1; i < N; i++)
    for (j = 1; j < i; j++)
      if (A[j+N] != B[j] + j)
abort();
}

int main(void)
{
  foo();

  return 0;
}

The previous implementation of dependence analysis marks “for
(scat_1=0;scat_1<=497;scat_1++) {“ as parallelizable. However, the
current dependence analysis finds must_waw dependence:

{ [i0] -> [1 + i0] : i0 >= 1 and i0 <= 496 }

(schedule:

{ S_7[i0, i1] -> [i0] : exists (e0 = [(i0)/4294967296]: i0 >= 0 and i0
<= 497 and i1 >= 0 and 4294967296e0 <= i0 and 4294967296e0 >=
-4294967295 + i0 and 4294967296e0 <= i0 - i1 and i1 <= 498) }

dependence:

{ S_7[i0, i1] -> S_7[1 + i0, i1] : exists (e0 = [(1 + i0)/4294967296],
e1 = [(i0)/4294967296]: i1 >= 0 and i1 <= 498 and i0 >= 0 and i0 <=
496 and 4294967296e0 <= 1 + i0 - i1 and 4294967296e0 <= 1 + i0 and
4294967296e0 >= -4294967294 + i0 and i1 <= i0 and 4294967296e1 <= i0 -
i1 and 4294967296e1 >= -4294967295 + i0 and 4294967296e1 <= i0) })

Could you please advise me what can be improved in the the current analysis?

> Why did you copy this code, instead of exposing the carries_deps functions
> from graphite-dependences?

If I'm not mistaken, the carries_deps functions can't be called in
graphite-isl-ast-to-gimple.c. Should we add its declaration to
graphite-poly.h to allow this?

-- 
                                    Cheers, Roman Gareev.

vect-pr43423.c.114t.vect(cloog)
Description: Binary data

vect-pr43423.c.114t.vect(isl)
Description: Binary data