[PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 5013 bytes --]

Hi,

This patch fixes PR69110, a wrong-code bug in autopar.


I.

consider testcase test.c:
...
#define N 1000

unsigned int i = 0;

static void __attribute__((noinline, noclone))
foo (void)
{
   unsigned int z;

   for (z = 0; z < N; ++z)
     ++i;
}

extern void abort (void);

int
main (void)
{
   foo ();
   if (i != N)
     abort ();

   return 0;
}
...

When compiled with -O1 -ftree-parallelize-loops=2 -fno-tree-loop-im, the 
test fails:
...
$ gcc test.c -O1 -ftree-parallelize-loops=2 -Wl,-rpath=$(pwd 
-P)//install/lib64 -fno-tree-loop-im
$ ./a.out
Aborted (core dumped)
$
...


II.

Before parloops, at ivcanon we have the loop body:
...
   <bb 3>:
   # z_10 = PHI <z_7(4), 0(2)>
   # ivtmp_12 = PHI <ivtmp_2(4), 1000(2)>
   i.1_4 = i;
   _5 = i.1_4 + 1;
   i = _5;
   z_7 = z_10 + 1;
   ivtmp_2 = ivtmp_12 - 1;
   if (ivtmp_2 != 0)
     goto <bb 4>;
   else
     goto <bb 5>;
...

There's a loop-carried dependency in i, that is, the read from i in 
iteration z == 1 depends on the write to i in iteration z == 0. So the 
loop cannot be parallelized. The test-case fails because parloops still 
parallelizes the loop.


III.

Since the loop carried dependency is in-memory, it is not handled by the 
code analyzing reductions, since that code ignores the virtual phi.

So, AFAIU, this loop carried dependency should be handled by the 
dependency testing in loop_parallel_p. And loop_parallel_p returns true 
for this loop.

A comment in loop_parallel_p reads: "Check for problems with 
dependences.  If the loop can be reversed, the iterations are independent."

AFAIU, the loop order can actually be reversed. But, it cannot be 
executed in parallel.

So from this perspective, it seems in this case the comment matches the 
check, but the check is not sufficient.


IV.

OTOH, if we replace the declaration of i with i[1], and replace the 
references of i with i[0], we see that loop_parallel_p fails.  So the 
loop_parallel_p check in this case seems sufficient, and there's 
something else that causes the check to fail in this case.

The difference is in the generated data ref:
- in the 'i[1]' case, we set DR_ACCESS_FNS in dr_analyze_indices to
   vector with a single element: access function 0.
- in the 'i' case, we set DR_ACCESS_FNS to NULL.

This difference causes different handling in the dependency generation, 
in particular in add_distance_for_zero_overlaps which has no effect for 
the 'i' case because  DDR_NUM_SUBSCRIPTS (ddr) == 0 (as a consequence of 
the NULL access_fns of both the source and sink data refs).

 From this perspective, it seems that the loop_parallel_p check is 
sufficient, and that dr_analyze_indices shouldn't return a NULL 
access_fns for 'i'.


V.

When compiling with graphite using -floop-parallelize-all --param 
graphite-min-loops-per-function=1, we find:
...
[scop-detection-fail] Graphite cannot handle data-refs in stmt:
# VUSE <.MEM_11>
i.1_4 = i;
...

The function scop_detection::stmt_has_simple_data_refs_p returns false 
because of the code recently added for PR66980 at r228357:
...
       int nb_subscripts = DR_NUM_DIMENSIONS (dr);

       if (nb_subscripts < 1)
	{
           free_data_refs (drs);
           return false;
         }
...

[ DR_NUM_DIMENSIONS (dr) is 0 as a consequence of the NULL access_fns. ]

This code labels DR_NUM_DIMENSIONS (dr) == 0 as 'data reference analysis 
has failed'.

 From this perspective, it seems that the dependence handling should 
bail out once it finds a data ref with DR_NUM_DIMENSIONS (dr) == 0 (or 
DR_ACCESS_FNS == 0).


VI.

This test-case used to pass in 4.6 because in 
find_data_references_in_stmt we had:
...
       /* FIXME -- data dependence analysis does not work correctly for
          objects with invariant addresses in loop nests.  Let us fail
          here until the problem is fixed.  */
       if (dr_address_invariant_p (dr) && nest)
	{
           free_data_ref (dr);
           if (dump_file && (dump_flags & TDF_DETAILS))
             fprintf (dump_file,
                      "\tFAILED as dr address is invariant\n");
           ret = false;
           break;
	}
...

That FIXME was removed in the fix for PR46787, at r175704.

The test-case fails in 4.8, and I guess from there onwards.


VII.

The attached patch fixes the problem by returning a zero access function 
for 'i' in dr_analyze_indices.

[ But I can also imagine a solution similar to the graphite fix:
...
@@ -3997,6 +3999,12 @@ find_data_references_in_stmt
        dr = create_data_ref (nest, loop_containing_stmt (stmt),
                             ref->ref, stmt, ref->is_read);
        gcc_assert (dr != NULL);
+      if (DR_NUM_DIMENSIONS (dr) == 0)
+       {
+         datarefs->release ();
+         return false;
+       }
+
        datarefs->safe_push (dr);
      }
    references.release ();
...

I'm not familiar enough with the dependency analysis code to know where 
exactly this should be fixed. ]

Bootstrapped and reg-tested on x86_64.

OK for trunk?

OK for release branches?

Thanks,
- Tom

[-- Attachment #2: 0001-Don-t-return-NULL-access_fns-in-dr_analyze_indices.patch --]
[-- Type: text/x-patch, Size: 2275 bytes --]

Don't return NULL access_fns in dr_analyze_indices

2016-01-12  Tom de Vries  <tom@codesourcery.com>

	* tree-data-ref.c (dr_analyze_indices): Don't return NULL access_fns.

	* gcc.dg/autopar/pr69110.c: New test.

	* testsuite/libgomp.c/pr69110.c: New test.

---
 gcc/testsuite/gcc.dg/autopar/pr69110.c | 20 ++++++++++++++++++++
 gcc/tree-data-ref.c                    |  3 +++
 libgomp/testsuite/libgomp.c/pr69110.c  | 27 +++++++++++++++++++++++++++
 3 files changed, 50 insertions(+)

diff --git a/gcc/testsuite/gcc.dg/autopar/pr69110.c b/gcc/testsuite/gcc.dg/autopar/pr69110.c
new file mode 100644
index 0000000..0eca411
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/autopar/pr69110.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -ftree-parallelize-loops=2 -fno-tree-loop-im -fdump-tree-parloops-details" } */
+
+#define N 1000
+
+unsigned int i = 0;
+
+void
+foo (void)
+{
+  unsigned int z;
+  unsigned int *p = &i;
+  for (z = 0; z < N; ++z)
+    ++i;
+}
+
+/* { dg-final { scan-tree-dump-times "SUCCESS: may be parallelized" 0 "parloops" } } */
+/* { dg-final { scan-tree-dump-times "FAILED: data dependencies exist across iterations" 1 "parloops" } } */
+
+
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index a40f40d..862589b 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1021,6 +1021,9 @@ dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
       ref = build2 (MEM_REF, TREE_TYPE (ref),
 		    build_fold_addr_expr (ref),
 		    build_int_cst (reference_alias_ptr_type (ref), 0));
+
+      if (access_fns == vNULL)
+	access_fns.safe_push (integer_zero_node);
     }
 
   DR_BASE_OBJECT (dr) = ref;
diff --git a/libgomp/testsuite/libgomp.c/pr69110.c b/libgomp/testsuite/libgomp.c/pr69110.c
new file mode 100644
index 0000000..049f014
--- /dev/null
+++ b/libgomp/testsuite/libgomp.c/pr69110.c
@@ -0,0 +1,27 @@
+/* { dg-do run } */
+/* { dg-options "-ftree-parallelize-loops=2 -O1 -fno-tree-loop-im" } */
+
+#define N 1000
+
+unsigned int i = 0;
+
+static void __attribute__((noinline, noclone))
+foo (void)
+{
+  unsigned int z;
+  unsigned int *p = &i;
+  for (z = 0; z < N; ++z)
+    ++i;
+}
+
+extern void abort (void);
+
+int
+main (void)
+{
+  foo ();
+  if (i != N)
+    abort ();
+
+  return 0;
+}

Re: [PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[Richard Biener]

On Tue, 12 Jan 2016, Tom de Vries wrote:

> Hi,
> 
> This patch fixes PR69110, a wrong-code bug in autopar.
> 
> 
> I.
> 
> consider testcase test.c:
> ...
> #define N 1000
> 
> unsigned int i = 0;
> 
> static void __attribute__((noinline, noclone))
> foo (void)
> {
>   unsigned int z;
> 
>   for (z = 0; z < N; ++z)
>     ++i;
> }
> 
> extern void abort (void);
> 
> int
> main (void)
> {
>   foo ();
>   if (i != N)
>     abort ();
> 
>   return 0;
> }
> ...
> 
> When compiled with -O1 -ftree-parallelize-loops=2 -fno-tree-loop-im, the test
> fails:
> ...
> $ gcc test.c -O1 -ftree-parallelize-loops=2 -Wl,-rpath=$(pwd
> -P)//install/lib64 -fno-tree-loop-im
> $ ./a.out
> Aborted (core dumped)
> $
> ...
> 
> 
> II.
> 
> Before parloops, at ivcanon we have the loop body:
> ...
>   <bb 3>:
>   # z_10 = PHI <z_7(4), 0(2)>
>   # ivtmp_12 = PHI <ivtmp_2(4), 1000(2)>
>   i.1_4 = i;
>   _5 = i.1_4 + 1;
>   i = _5;
>   z_7 = z_10 + 1;
>   ivtmp_2 = ivtmp_12 - 1;
>   if (ivtmp_2 != 0)
>     goto <bb 4>;
>   else
>     goto <bb 5>;
> ...
> 
> There's a loop-carried dependency in i, that is, the read from i in iteration
> z == 1 depends on the write to i in iteration z == 0. So the loop cannot be
> parallelized. The test-case fails because parloops still parallelizes the
> loop.
> 
> 
> III.
> 
> Since the loop carried dependency is in-memory, it is not handled by the code
> analyzing reductions, since that code ignores the virtual phi.
> 
> So, AFAIU, this loop carried dependency should be handled by the dependency
> testing in loop_parallel_p. And loop_parallel_p returns true for this loop.
> 
> A comment in loop_parallel_p reads: "Check for problems with dependences.  If
> the loop can be reversed, the iterations are independent."
> 
> AFAIU, the loop order can actually be reversed. But, it cannot be executed in
> parallel.
> 
> So from this perspective, it seems in this case the comment matches the check,
> but the check is not sufficient.
> 
> 
> IV.
> 
> OTOH, if we replace the declaration of i with i[1], and replace the references
> of i with i[0], we see that loop_parallel_p fails.  So the loop_parallel_p
> check in this case seems sufficient, and there's something else that causes
> the check to fail in this case.
> 
> The difference is in the generated data ref:
> - in the 'i[1]' case, we set DR_ACCESS_FNS in dr_analyze_indices to
>   vector with a single element: access function 0.
> - in the 'i' case, we set DR_ACCESS_FNS to NULL.
> 
> This difference causes different handling in the dependency generation, in
> particular in add_distance_for_zero_overlaps which has no effect for the 'i'
> case because  DDR_NUM_SUBSCRIPTS (ddr) == 0 (as a consequence of the NULL
> access_fns of both the source and sink data refs).
> 
> From this perspective, it seems that the loop_parallel_p check is sufficient,
> and that dr_analyze_indices shouldn't return a NULL access_fns for 'i'.
> 
> 
> V.
> 
> When compiling with graphite using -floop-parallelize-all --param
> graphite-min-loops-per-function=1, we find:
> ...
> [scop-detection-fail] Graphite cannot handle data-refs in stmt:
> # VUSE <.MEM_11>
> i.1_4 = i;
> ...
> 
> The function scop_detection::stmt_has_simple_data_refs_p returns false because
> of the code recently added for PR66980 at r228357:
> ...
>       int nb_subscripts = DR_NUM_DIMENSIONS (dr);
> 
>       if (nb_subscripts < 1)
> 	{
>           free_data_refs (drs);
>           return false;
>         }
> ...
> 
> [ DR_NUM_DIMENSIONS (dr) is 0 as a consequence of the NULL access_fns. ]
> 
> This code labels DR_NUM_DIMENSIONS (dr) == 0 as 'data reference analysis has
> failed'.
> 
> From this perspective, it seems that the dependence handling should bail out
> once it finds a data ref with DR_NUM_DIMENSIONS (dr) == 0 (or DR_ACCESS_FNS ==
> 0).
> 
> 
> VI.
> 
> This test-case used to pass in 4.6 because in find_data_references_in_stmt we
> had:
> ...
>       /* FIXME -- data dependence analysis does not work correctly for
>          objects with invariant addresses in loop nests.  Let us fail
>          here until the problem is fixed.  */
>       if (dr_address_invariant_p (dr) && nest)
> 	{
>           free_data_ref (dr);
>           if (dump_file && (dump_flags & TDF_DETAILS))
>             fprintf (dump_file,
>                      "\tFAILED as dr address is invariant\n");
>           ret = false;
>           break;
> 	}
> ...
> 
> That FIXME was removed in the fix for PR46787, at r175704.
> 
> The test-case fails in 4.8, and I guess from there onwards.
> 
> 
> VII.
> 
> The attached patch fixes the problem by returning a zero access function for
> 'i' in dr_analyze_indices.
> 
> [ But I can also imagine a solution similar to the graphite fix:
> ...
> @@ -3997,6 +3999,12 @@ find_data_references_in_stmt
>        dr = create_data_ref (nest, loop_containing_stmt (stmt),
>                             ref->ref, stmt, ref->is_read);
>        gcc_assert (dr != NULL);
> +      if (DR_NUM_DIMENSIONS (dr) == 0)
> +       {
> +         datarefs->release ();
> +         return false;
> +       }
> +
>        datarefs->safe_push (dr);
>      }
>    references.release ();
> ...
> 
> I'm not familiar enough with the dependency analysis code to know where
> exactly this should be fixed. ]
> 
> Bootstrapped and reg-tested on x86_64.
> 
> OK for trunk?
> 
> OK for release branches?

Bah - attachement [please post patches inline]

So without quote ;)

Doesnt' the same issue apply to 

> unsigned int *p;
>       
> static void __attribute__((noinline, noclone))
> foo (void)
> {         
>   unsigned int z;
>   
>   for (z = 0; z < N; ++z)
>     ++(*p);
> }

thus when we have a MEM_REF[p_1]?  SCEV will not analyze
its evolution to a POLYNOMIAL_CHREC and thus access_fns will
be NULL again.

I think avoiding a NULL access_fns is ok but it should be done
unconditionally, not only for the DECL_P case.

Thanks,
Richard.

Re: [PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 771 bytes --]

On 12/01/16 12:22, Richard Biener wrote:
> Doesnt' the same issue apply to
>
>> >unsigned int *p;
>> >
>> >static void __attribute__((noinline, noclone))
>> >foo (void)
>> >{
>> >   unsigned int z;
>> >
>> >   for (z = 0; z < N; ++z)
>> >     ++(*p);
>> >}
> thus when we have a MEM_REF[p_1]?  SCEV will not analyze
> its evolution to a POLYNOMIAL_CHREC and thus access_fns will
> be NULL again.
>

I didn't manage to trigger this scenario, though I could probably make 
it happen by modifying ftree-loop-im to work in one case (the load of 
the value of p) but not the other (the *p load and store).

> I think avoiding a NULL access_fns is ok but it should be done
> unconditionally, not only for the DECL_P case.

Ok, I'll retest and commit this patch.

Thanks,
- Tom

[-- Attachment #2: 0001-Don-t-return-NULL-access_fns-in-dr_analyze_indices.patch --]
[-- Type: text/x-patch, Size: 2179 bytes --]

Don't return NULL access_fns in dr_analyze_indices

2016-01-12  Tom de Vries  <tom@codesourcery.com>

	* tree-data-ref.c (dr_analyze_indices): Don't return NULL access_fns.

	* gcc.dg/autopar/pr69110.c: New test.

	* testsuite/libgomp.c/pr69110.c: New test.

---
 gcc/testsuite/gcc.dg/autopar/pr69110.c | 19 +++++++++++++++++++
 gcc/tree-data-ref.c                    |  3 +++
 libgomp/testsuite/libgomp.c/pr69110.c  | 26 ++++++++++++++++++++++++++
 3 files changed, 48 insertions(+)

diff --git a/gcc/testsuite/gcc.dg/autopar/pr69110.c b/gcc/testsuite/gcc.dg/autopar/pr69110.c
new file mode 100644
index 0000000..e236015
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/autopar/pr69110.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -ftree-parallelize-loops=2 -fno-tree-loop-im -fdump-tree-parloops-details" } */
+
+#define N 1000
+
+unsigned int i = 0;
+
+void
+foo (void)
+{
+  unsigned int z;
+  for (z = 0; z < N; ++z)
+    ++i;
+}
+
+/* { dg-final { scan-tree-dump-times "SUCCESS: may be parallelized" 0 "parloops" } } */
+/* { dg-final { scan-tree-dump-times "FAILED: data dependencies exist across iterations" 1 "parloops" } } */
+
+
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index a40f40d..6503012 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1023,6 +1023,9 @@ dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
 		    build_int_cst (reference_alias_ptr_type (ref), 0));
     }
 
+  if (access_fns == vNULL)
+    access_fns.safe_push (integer_zero_node);
+
   DR_BASE_OBJECT (dr) = ref;
   DR_ACCESS_FNS (dr) = access_fns;
 }
diff --git a/libgomp/testsuite/libgomp.c/pr69110.c b/libgomp/testsuite/libgomp.c/pr69110.c
new file mode 100644
index 0000000..0d9e5ca
--- /dev/null
+++ b/libgomp/testsuite/libgomp.c/pr69110.c
@@ -0,0 +1,26 @@
+/* { dg-do run } */
+/* { dg-options "-ftree-parallelize-loops=2 -O1 -fno-tree-loop-im" } */
+
+#define N 1000
+
+unsigned int i = 0;
+
+static void __attribute__((noinline, noclone))
+foo (void)
+{
+  unsigned int z;
+  for (z = 0; z < N; ++z)
+    ++i;
+}
+
+extern void abort (void);
+
+int
+main (void)
+{
+  foo ();
+  if (i != N)
+    abort ();
+
+  return 0;
+}

Re: [PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[Richard Biener]

On Tue, 12 Jan 2016, Tom de Vries wrote:

> On 12/01/16 12:22, Richard Biener wrote:
> > Doesnt' the same issue apply to
> > 
> > > >unsigned int *p;
> > > >
> > > >static void __attribute__((noinline, noclone))
> > > >foo (void)
> > > >{
> > > >   unsigned int z;
> > > >
> > > >   for (z = 0; z < N; ++z)
> > > >     ++(*p);
> > > >}
> > thus when we have a MEM_REF[p_1]?  SCEV will not analyze
> > its evolution to a POLYNOMIAL_CHREC and thus access_fns will
> > be NULL again.
> > 
> 
> I didn't manage to trigger this scenario, though I could probably make it
> happen by modifying ftree-loop-im to work in one case (the load of the value
> of p) but not the other (the *p load and store).
> 
> > I think avoiding a NULL access_fns is ok but it should be done
> > unconditionally, not only for the DECL_P case.
> 
> Ok, I'll retest and commit this patch.

Please add a comment as well.

> Thanks,
> - Tom
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: [PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 1685 bytes --]

On 12/01/16 14:04, Richard Biener wrote:
> On Tue, 12 Jan 2016, Tom de Vries wrote:
>
>> On 12/01/16 12:22, Richard Biener wrote:
>>> Doesnt' the same issue apply to
>>>
>>>>> unsigned int *p;
>>>>>
>>>>> static void __attribute__((noinline, noclone))
>>>>> foo (void)
>>>>> {
>>>>>    unsigned int z;
>>>>>
>>>>>    for (z = 0; z < N; ++z)
>>>>>      ++(*p);
>>>>> }
>>> thus when we have a MEM_REF[p_1]?  SCEV will not analyze
>>> its evolution to a POLYNOMIAL_CHREC and thus access_fns will
>>> be NULL again.
>>>
>>
>> I didn't manage to trigger this scenario, though I could probably make it
>> happen by modifying ftree-loop-im to work in one case (the load of the value
>> of p) but not the other (the *p load and store).
>>
>>> I think avoiding a NULL access_fns is ok but it should be done
>>> unconditionally, not only for the DECL_P case.
>>
>> Ok, I'll retest and commit this patch.
>
> Please add a comment as well.

Patch updated with comment.

During testing however, I ran into two testsuite regressions:

1.

-PASS: gfortran.dg/graphite/pr39516.f   -O  (test for excess errors)
+FAIL: gfortran.dg/graphite/pr39516.f   -O  (internal compiler error)
+FAIL: gfortran.dg/graphite/pr39516.f   -O  (test for excess errors)

AFAIU, this is a duplicate of PR68976.

Should I wait with committing the patch until PR68976 is fixed?

2.

-XFAIL: gcc.dg/graphite/scop-pr66980.c scan-tree-dump-times graphite 
"number of SCoPs: 1" 1
+XPASS: gcc.dg/graphite/scop-pr66980.c scan-tree-dump-times graphite 
"number of SCoPs: 1" 1

AFAIU, this is not a real regression, but the testcase needs to be 
updated. I'm not sure how. Sebastian, perhaps you have an idea there?

Thanks,
- Tom


[-- Attachment #2: 0001-Don-t-return-NULL-access_fns-in-dr_analyze_indices.patch --]
[-- Type: text/x-patch, Size: 2527 bytes --]

From 24dfdb5a8a536203ad159bcbeaee6931be032f32 Mon Sep 17 00:00:00 2001
From: Tom de Vries <tom@codesourcery.com>
Date: Tue, 12 Jan 2016 01:45:11 +0100
Subject: [PATCH] Don't return NULL access_fns in dr_analyze_indices

2016-01-12  Tom de Vries  <tom@codesourcery.com>

	* tree-data-ref.c (dr_analyze_indices): Don't return NULL access_fns.

	* gcc.dg/autopar/pr69110.c: New test.

	* testsuite/libgomp.c/pr69110.c: New test.
---
 gcc/testsuite/gcc.dg/autopar/pr69110.c | 19 +++++++++++++++++++
 gcc/tree-data-ref.c                    |  4 ++++
 libgomp/testsuite/libgomp.c/pr69110.c  | 26 ++++++++++++++++++++++++++
 3 files changed, 49 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/autopar/pr69110.c
 create mode 100644 libgomp/testsuite/libgomp.c/pr69110.c

diff --git a/gcc/testsuite/gcc.dg/autopar/pr69110.c b/gcc/testsuite/gcc.dg/autopar/pr69110.c
new file mode 100644
index 0000000..e236015
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/autopar/pr69110.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -ftree-parallelize-loops=2 -fno-tree-loop-im -fdump-tree-parloops-details" } */
+
+#define N 1000
+
+unsigned int i = 0;
+
+void
+foo (void)
+{
+  unsigned int z;
+  for (z = 0; z < N; ++z)
+    ++i;
+}
+
+/* { dg-final { scan-tree-dump-times "SUCCESS: may be parallelized" 0 "parloops" } } */
+/* { dg-final { scan-tree-dump-times "FAILED: data dependencies exist across iterations" 1 "parloops" } } */
+
+
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index a40f40d..7ff5db7 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1023,6 +1023,10 @@ dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
 		    build_int_cst (reference_alias_ptr_type (ref), 0));
     }
 
+  /* Ensure that DR_NUM_DIMENSIONS (dr) != 0.  */
+  if (access_fns == vNULL)
+    access_fns.safe_push (integer_zero_node);
+
   DR_BASE_OBJECT (dr) = ref;
   DR_ACCESS_FNS (dr) = access_fns;
 }
diff --git a/libgomp/testsuite/libgomp.c/pr69110.c b/libgomp/testsuite/libgomp.c/pr69110.c
new file mode 100644
index 0000000..0d9e5ca
--- /dev/null
+++ b/libgomp/testsuite/libgomp.c/pr69110.c
@@ -0,0 +1,26 @@
+/* { dg-do run } */
+/* { dg-options "-ftree-parallelize-loops=2 -O1 -fno-tree-loop-im" } */
+
+#define N 1000
+
+unsigned int i = 0;
+
+static void __attribute__((noinline, noclone))
+foo (void)
+{
+  unsigned int z;
+  for (z = 0; z < N; ++z)
+    ++i;
+}
+
+extern void abort (void);
+
+int
+main (void)
+{
+  foo ();
+  if (i != N)
+    abort ();
+
+  return 0;
+}
-- 
1.9.1

Re: [PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[Richard Biener]

On Tue, 12 Jan 2016, Tom de Vries wrote:

> On 12/01/16 14:04, Richard Biener wrote:
> > On Tue, 12 Jan 2016, Tom de Vries wrote:
> > 
> > > On 12/01/16 12:22, Richard Biener wrote:
> > > > Doesnt' the same issue apply to
> > > > 
> > > > > > unsigned int *p;
> > > > > > 
> > > > > > static void __attribute__((noinline, noclone))
> > > > > > foo (void)
> > > > > > {
> > > > > >    unsigned int z;
> > > > > > 
> > > > > >    for (z = 0; z < N; ++z)
> > > > > >      ++(*p);
> > > > > > }
> > > > thus when we have a MEM_REF[p_1]?  SCEV will not analyze
> > > > its evolution to a POLYNOMIAL_CHREC and thus access_fns will
> > > > be NULL again.
> > > > 
> > > 
> > > I didn't manage to trigger this scenario, though I could probably make it
> > > happen by modifying ftree-loop-im to work in one case (the load of the
> > > value
> > > of p) but not the other (the *p load and store).
> > > 
> > > > I think avoiding a NULL access_fns is ok but it should be done
> > > > unconditionally, not only for the DECL_P case.
> > > 
> > > Ok, I'll retest and commit this patch.
> > 
> > Please add a comment as well.
> 
> Patch updated with comment.
> 
> During testing however, I ran into two testsuite regressions:
> 
> 1.
> 
> -PASS: gfortran.dg/graphite/pr39516.f   -O  (test for excess errors)
> +FAIL: gfortran.dg/graphite/pr39516.f   -O  (internal compiler error)
> +FAIL: gfortran.dg/graphite/pr39516.f   -O  (test for excess errors)
> 
> AFAIU, this is a duplicate of PR68976.
> 
> Should I wait with committing the patch until PR68976 is fixed?

Yes - we shouldn't introduce new testsuite regressions willingly at this 
point.

> 2.
> 
> -XFAIL: gcc.dg/graphite/scop-pr66980.c scan-tree-dump-times graphite "number
> of SCoPs: 1" 1
> +XPASS: gcc.dg/graphite/scop-pr66980.c scan-tree-dump-times graphite "number
> of SCoPs: 1" 1
> 
> AFAIU, this is not a real regression, but the testcase needs to be updated.
> I'm not sure how. Sebastian, perhaps you have an idea there?

It looks like simply removing the xfail might be ok.  But the comment in
the testcase doesn't suggest its dependency analysis fault that the
situation is not handled so I'd like Sebastian to chime in (who also
should know the dependence code very well).

Thanks,
Richard.

Re: [PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[Tom de Vries]

On 13/01/16 09:42, Richard Biener wrote:
> On Tue, 12 Jan 2016, Tom de Vries wrote:
>
>> >On 12/01/16 14:04, Richard Biener wrote:
>>> > >On Tue, 12 Jan 2016, Tom de Vries wrote:
>>> > >
>>>> > > >On 12/01/16 12:22, Richard Biener wrote:
>>>>> > > > >Doesnt' the same issue apply to
>>>>> > > > >
>>>>>>> > > > > > >unsigned int *p;
>>>>>>> > > > > > >
>>>>>>> > > > > > >static void __attribute__((noinline, noclone))
>>>>>>> > > > > > >foo (void)
>>>>>>> > > > > > >{
>>>>>>> > > > > > >    unsigned int z;
>>>>>>> > > > > > >
>>>>>>> > > > > > >    for (z = 0; z < N; ++z)
>>>>>>> > > > > > >      ++(*p);
>>>>>>> > > > > > >}
>>>>> > > > >thus when we have a MEM_REF[p_1]?  SCEV will not analyze
>>>>> > > > >its evolution to a POLYNOMIAL_CHREC and thus access_fns will
>>>>> > > > >be NULL again.
>>>>> > > > >
>>>> > > >
>>>> > > >I didn't manage to trigger this scenario, though I could probably make it
>>>> > > >happen by modifying ftree-loop-im to work in one case (the load of the
>>>> > > >value
>>>> > > >of p) but not the other (the *p load and store).
>>>> > > >
>>>>> > > > >I think avoiding a NULL access_fns is ok but it should be done
>>>>> > > > >unconditionally, not only for the DECL_P case.
>>>> > > >
>>>> > > >Ok, I'll retest and commit this patch.
>>> > >
>>> > >Please add a comment as well.
>> >
>> >Patch updated with comment.
>> >
>> >During testing however, I ran into two testsuite regressions:
>> >
>> >1.
>> >
>> >-PASS: gfortran.dg/graphite/pr39516.f   -O  (test for excess errors)
>> >+FAIL: gfortran.dg/graphite/pr39516.f   -O  (internal compiler error)
>> >+FAIL: gfortran.dg/graphite/pr39516.f   -O  (test for excess errors)
>> >
>> >AFAIU, this is a duplicate of PR68976.
>> >
>> >Should I wait with committing the patch until PR68976 is fixed?
> Yes - we shouldn't introduce new testsuite regressions willingly at this
> point.
>

I've looked in more detail at both PR68976 and the pr39516.f regression 
using this patch, and I now think they are independent.

Furthermore, I managed to reproduce the pr39516.f regression without the 
patch (filed as PR69292 - '[graphite] ICE with -floop-nest-optimize').

So, AFAIU, committing this patch does not introduce a new type of ICE, 
but it makes it more likely that you run into it.

Does that still mean we need to wait with committing, and first fix PR69292?

Thanks,
- Tom

Re: [PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[Richard Biener]

On Fri, 15 Jan 2016, Tom de Vries wrote:

> On 13/01/16 09:42, Richard Biener wrote:
> > On Tue, 12 Jan 2016, Tom de Vries wrote:
> > 
> > > >On 12/01/16 14:04, Richard Biener wrote:
> > > > > >On Tue, 12 Jan 2016, Tom de Vries wrote:
> > > > > >
> > > > > > > >On 12/01/16 12:22, Richard Biener wrote:
> > > > > > > > > >Doesnt' the same issue apply to
> > > > > > > > > >
> > > > > > > > > > > > > >unsigned int *p;
> > > > > > > > > > > > > >
> > > > > > > > > > > > > >static void __attribute__((noinline, noclone))
> > > > > > > > > > > > > >foo (void)
> > > > > > > > > > > > > >{
> > > > > > > > > > > > > >    unsigned int z;
> > > > > > > > > > > > > >
> > > > > > > > > > > > > >    for (z = 0; z < N; ++z)
> > > > > > > > > > > > > >      ++(*p);
> > > > > > > > > > > > > >}
> > > > > > > > > >thus when we have a MEM_REF[p_1]?  SCEV will not analyze
> > > > > > > > > >its evolution to a POLYNOMIAL_CHREC and thus access_fns will
> > > > > > > > > >be NULL again.
> > > > > > > > > >
> > > > > > > >
> > > > > > > >I didn't manage to trigger this scenario, though I could probably
> > > > > make it
> > > > > > > >happen by modifying ftree-loop-im to work in one case (the load
> > > > > of the
> > > > > > > >value
> > > > > > > >of p) but not the other (the *p load and store).
> > > > > > > >
> > > > > > > > > >I think avoiding a NULL access_fns is ok but it should be
> > > > > > done
> > > > > > > > > >unconditionally, not only for the DECL_P case.
> > > > > > > >
> > > > > > > >Ok, I'll retest and commit this patch.
> > > > > >
> > > > > >Please add a comment as well.
> > > >
> > > >Patch updated with comment.
> > > >
> > > >During testing however, I ran into two testsuite regressions:
> > > >
> > > >1.
> > > >
> > > >-PASS: gfortran.dg/graphite/pr39516.f   -O  (test for excess errors)
> > > >+FAIL: gfortran.dg/graphite/pr39516.f   -O  (internal compiler error)
> > > >+FAIL: gfortran.dg/graphite/pr39516.f   -O  (test for excess errors)
> > > >
> > > >AFAIU, this is a duplicate of PR68976.
> > > >
> > > >Should I wait with committing the patch until PR68976 is fixed?
> > Yes - we shouldn't introduce new testsuite regressions willingly at this
> > point.
> > 
> 
> I've looked in more detail at both PR68976 and the pr39516.f regression using
> this patch, and I now think they are independent.
> 
> Furthermore, I managed to reproduce the pr39516.f regression without the patch
> (filed as PR69292 - '[graphite] ICE with -floop-nest-optimize').
> 
> So, AFAIU, committing this patch does not introduce a new type of ICE, but it
> makes it more likely that you run into it.
> 
> Does that still mean we need to wait with committing, and first fix PR69292?

Yes as it introduces a testsuite regression.

Richard.

Re: [PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[Tom de Vries]

On 13/01/16 09:42, Richard Biener wrote:
> On Tue, 12 Jan 2016, Tom de Vries wrote:
>
>> On 12/01/16 14:04, Richard Biener wrote:
>>> On Tue, 12 Jan 2016, Tom de Vries wrote:
>>>
>>>> On 12/01/16 12:22, Richard Biener wrote:
>>>>> Doesnt' the same issue apply to
>>>>>
>>>>>>> unsigned int *p;
>>>>>>>
>>>>>>> static void __attribute__((noinline, noclone))
>>>>>>> foo (void)
>>>>>>> {
>>>>>>>     unsigned int z;
>>>>>>>
>>>>>>>     for (z = 0; z < N; ++z)
>>>>>>>       ++(*p);
>>>>>>> }
>>>>> thus when we have a MEM_REF[p_1]?  SCEV will not analyze
>>>>> its evolution to a POLYNOMIAL_CHREC and thus access_fns will
>>>>> be NULL again.
>>>>>
>>>>
>>>> I didn't manage to trigger this scenario, though I could probably make it
>>>> happen by modifying ftree-loop-im to work in one case (the load of the
>>>> value
>>>> of p) but not the other (the *p load and store).
>>>>
>>>>> I think avoiding a NULL access_fns is ok but it should be done
>>>>> unconditionally, not only for the DECL_P case.
>>>>
>>>> Ok, I'll retest and commit this patch.
>>>
>>> Please add a comment as well.
>>
>> Patch updated with comment.
>>
>> During testing however, I ran into two testsuite regressions:
>>
>> 1.
>>
>> -PASS: gfortran.dg/graphite/pr39516.f   -O  (test for excess errors)
>> +FAIL: gfortran.dg/graphite/pr39516.f   -O  (internal compiler error)
>> +FAIL: gfortran.dg/graphite/pr39516.f   -O  (test for excess errors)
>>
>> AFAIU, this is a duplicate of PR68976.
>>
>> Should I wait with committing the patch until PR68976 is fixed?
>
> Yes - we shouldn't introduce new testsuite regressions willingly at this
> point.
>

After r232659 (the fix for pr68692), the ICE no longer occurs.

>> 2.
>>
>> -XFAIL: gcc.dg/graphite/scop-pr66980.c scan-tree-dump-times graphite "number
>> of SCoPs: 1" 1
>> +XPASS: gcc.dg/graphite/scop-pr66980.c scan-tree-dump-times graphite "number
>> of SCoPs: 1" 1
>>
>> AFAIU, this is not a real regression, but the testcase needs to be updated.
>> I'm not sure how. Sebastian, perhaps you have an idea there?
>
> It looks like simply removing the xfail might be ok.  But the comment in
> the testcase doesn't suggest its dependency analysis fault that the
> situation is not handled so I'd like Sebastian to chime in (who also
> should know the dependence code very well).
>

Sebastian,

Ping on the xfail -> xpass issue mentioned above.

I'd like to commit this ( 
https://gcc.gnu.org/ml/gcc-patches/2016-01/msg00762.html  ) patch. I'm 
currently retesting using r232712 as baseline.

Thanks,
- Tom

Re: [PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[Tom de Vries]

On 23/01/16 18:39, Sebastian Pop wrote:
> diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
> index a40f40d..7ff5db7 100644
> --- a/gcc/tree-data-ref.c
> +++ b/gcc/tree-data-ref.c
> @@ -1023,6 +1023,10 @@ dr_analyze_indices (struct data_reference *dr,
> loop_p nest, loop_p loop)
>       build_int_cst (reference_alias_ptr_type (ref), 0));
>       }
>
> +  /* Ensure that DR_NUM_DIMENSIONS (dr) != 0.  */
> +  if (access_fns == vNULL)
> +    access_fns.safe_push (integer_zero_node);
> +
>     DR_BASE_OBJECT (dr) = ref;
>     DR_ACCESS_FNS (dr) = access_fns;
>   }
>
> This code adds a data reference with an access function 0 for all data
> references
> that cannot be analyzed by the data reference analysis.  Let's move
> this check under
> the check for DECL_P (ref) and this fixes the check in graphite:
>
> diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
> index a40f40d..862589b 100644
> --- a/gcc/tree-data-ref.c
> +++ b/gcc/tree-data-ref.c
> @@ -1018,12 +1018,15 @@ dr_analyze_indices (struct data_reference *dr,
> loop_p nest, loop_p loop)
>     else if (DECL_P (ref))
>       {
>         /* Canonicalize DR_BASE_OBJECT to MEM_REF form.  */
>         ref = build2 (MEM_REF, TREE_TYPE (ref),
>                      build_fold_addr_expr (ref),
>                      build_int_cst (reference_alias_ptr_type (ref), 0));
> +
> +      if (access_fns == vNULL)
> +       access_fns.safe_push (integer_zero_node);
>       }
>
>     DR_BASE_OBJECT (dr) = ref;
>     DR_ACCESS_FNS (dr) = access_fns;
>   }
>
> Ok with this change.
>

Hi Sebastian,

That was my original patch, and Richard commented: 'I think avoiding a 
NULL access_fns is ok but it should be done unconditionally, not only 
for the DECL_P case'. In order words, he asked me to do the exact 
opposite of the change you now propose.

Thanks,
- Tom

Re: [PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[Sebastian Pop]

On Sat, Jan 23, 2016 at 12:28 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> That was my original patch, and Richard commented: 'I think avoiding a NULL
> access_fns is ok but it should be done unconditionally, not only for the
> DECL_P case'. In order words, he asked me to do the exact opposite of the
> change you now propose.
>

In the case of a DECL_P it is correct to say that it has an access
function of 0.
In the graphite testcase it is not correct to say that the access
function for a given data reference is zero:
we only initialize access_fns in the case of a polynomial chrec:

  if (TREE_CODE (ref) == MEM_REF)
    {
      op = TREE_OPERAND (ref, 0);
      access_fn = analyze_scalar_evolution (loop, op);
      access_fn = instantiate_scev (before_loop, loop, access_fn);
      if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
        {
[...]
           access_fns.safe_push (access_fn);
        }
    }

In all other cases we may not have a representation of the access functions.
It is incorrect to initialize to "A[0]" all those data references that
cannot be analyzed.
If needed, instead of returning vNULL, one could initialize the vector to empty:

if (access_fns == vNULL)
  access_fns.create (0);

and that would be correct, though it would not teach the dependence analysis
how to deal with the global variable access function in pr69110.
I think the fix is to add the zero subscript only for DECL_P (ref).

Sebastian

Re: [PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[Richard Biener]

On January 23, 2016 7:44:23 PM GMT+01:00, Sebastian Pop <sebpop@gmail.com> wrote:
>On Sat, Jan 23, 2016 at 12:28 PM, Tom de Vries <Tom_deVries@mentor.com>
>wrote:
>> That was my original patch, and Richard commented: 'I think avoiding
>a NULL
>> access_fns is ok but it should be done unconditionally, not only for
>the
>> DECL_P case'. In order words, he asked me to do the exact opposite of
>the
>> change you now propose.
>>
>
>In the case of a DECL_P it is correct to say that it has an access
>function of 0.
>In the graphite testcase it is not correct to say that the access
>function for a given data reference is zero:
>we only initialize access_fns in the case of a polynomial chrec:
>
>  if (TREE_CODE (ref) == MEM_REF)
>    {
>      op = TREE_OPERAND (ref, 0);
>      access_fn = analyze_scalar_evolution (loop, op);
>      access_fn = instantiate_scev (before_loop, loop, access_fn);
>      if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
>        {
>[...]
>           access_fns.safe_push (access_fn);
>        }
>    }
>
>In all other cases we may not have a representation of the access
>functions.
>It is incorrect to initialize to "A[0]" all those data references that
>cannot be analyzed.

But does it matter as the base will not be equal with one that can be analyzed?

>If needed, instead of returning vNULL, one could initialize the vector
>to empty:
>
>if (access_fns == vNULL)
>  access_fns.create (0);
>
>and that would be correct, though it would not teach the dependence
>analysis
>how to deal with the global variable access function in pr69110.
>I think the fix is to add the zero subscript only for DECL_P (ref).
>
>Sebastian

Re: [PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 2469 bytes --]

On 24/01/16 09:04, Richard Biener wrote:
> On January 23, 2016 7:44:23 PM GMT+01:00, Sebastian Pop <sebpop@gmail.com> wrote:
>> On Sat, Jan 23, 2016 at 12:28 PM, Tom de Vries <Tom_deVries@mentor.com>
>> wrote:
>>> That was my original patch, and Richard commented: 'I think avoiding
>> a NULL
>>> access_fns is ok but it should be done unconditionally, not only for
>> the
>>> DECL_P case'. In order words, he asked me to do the exact opposite of
>> the
>>> change you now propose.
>>>
>>
>> In the case of a DECL_P it is correct to say that it has an access
>> function of 0.
>> In the graphite testcase it is not correct to say that the access
>> function for a given data reference is zero:
>> we only initialize access_fns in the case of a polynomial chrec:
>>
>>   if (TREE_CODE (ref) == MEM_REF)
>>     {
>>       op = TREE_OPERAND (ref, 0);
>>       access_fn = analyze_scalar_evolution (loop, op);
>>       access_fn = instantiate_scev (before_loop, loop, access_fn);
>>       if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
>>         {
>> [...]
>>            access_fns.safe_push (access_fn);
>>         }
>>     }
>>
>> In all other cases we may not have a representation of the access
>> functions.
>> It is incorrect to initialize to "A[0]" all those data references that
>> cannot be analyzed.
>
> But does it matter as the base will not be equal with one that can be analyzed?
>

I'd like to propose a different fix.

I think the root cause of the problem is as follows:

The semantics of DDR_ARE_DEPENDENT is:
...
when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
relation between A and B, and the description of this relation
is given in the SUBSCRIPTS array
...

When A and B have DR_NUM_DIMENSIONS == 0, 
initialize_data_dependence_relation can create a ddr with 
DDR_NUM_SUBSCRIPTS == 0, and in the case of our test-case, it does.

I think this is the root cause: initialize_data_dependence_relation 
creates a ddr with DDR_ARE_DEPENDENT (ddr) == NULL_TREE and 
DDR_NUM_SUBSCRIPTS (ddr) == 0, which violates the semantics of 
DDR_ARE_DEPENDENT (ddr) == NULL_TREE.

[ There is the case of non-loop dependence analysis (tested for by 
loop_nest.exists ()), where DR_NUM_DIMENSIONS == 0 for all data 
references, that seems to be an exception. ]

The patch fixes the root cause of the problem by handling 
DR_NUM_DIMENSIONS == 0 in initialize_data_dependence_relation.

OK for trunk, 5.0, 4.9, if bootstrap/reg-test succeeds?

Thanks,
- Tom



[-- Attachment #2: 0001-Handle-DR_NUM_DIMENSIONS-0-in-initialize_data_dependence_relation.patch --]
[-- Type: text/x-patch, Size: 2988 bytes --]

Handle DR_NUM_DIMENSIONS == 0 in initialize_data_dependence_relation

2016-01-12  Tom de Vries  <tom@codesourcery.com>

	* tree-data-ref.c (initialize_data_dependence_relation): Handle
	DR_NUM_DIMENSIONS == 0.

	* gcc.dg/autopar/pr69110.c: New test.

	* testsuite/libgomp.c/pr69110.c: New test.

---
 gcc/testsuite/gcc.dg/autopar/pr69110.c | 17 +++++++++++++++++
 gcc/tree-data-ref.c                    | 10 ++++++----
 libgomp/testsuite/libgomp.c/pr69110.c  | 26 ++++++++++++++++++++++++++
 3 files changed, 49 insertions(+), 4 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/autopar/pr69110.c b/gcc/testsuite/gcc.dg/autopar/pr69110.c
new file mode 100644
index 0000000..27cdae5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/autopar/pr69110.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -ftree-parallelize-loops=2 -fno-tree-loop-im -fdump-tree-parloops2-details" } */
+
+#define N 1000
+
+unsigned int i = 0;
+
+void
+foo (void)
+{
+  unsigned int z;
+  for (z = 0; z < N; ++z)
+    ++i;
+}
+
+/* { dg-final { scan-tree-dump-times "SUCCESS: may be parallelized" 0 "parloops2" } } */
+/* { dg-final { scan-tree-dump-times "FAILED: data dependencies exist across iterations" 1 "parloops2" } } */
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index a40f40d..4c29fc2 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1510,8 +1510,9 @@ initialize_data_dependence_relation (struct data_reference *a,
   if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
     {
      if (loop_nest.exists ()
-        && !object_address_invariant_in_loop_p (loop_nest[0],
-       					        DR_BASE_OBJECT (a)))
+	 && (!object_address_invariant_in_loop_p (loop_nest[0],
+						  DR_BASE_OBJECT (a))
+	     || DR_NUM_DIMENSIONS (a) == 0))
       {
         DDR_ARE_DEPENDENT (res) = chrec_dont_know;
         return res;
@@ -1548,8 +1549,9 @@ initialize_data_dependence_relation (struct data_reference *a,
      analyze it.  TODO -- in fact, it would suffice to record that there may
      be arbitrary dependences in the loops where the base object varies.  */
   if (loop_nest.exists ()
-      && !object_address_invariant_in_loop_p (loop_nest[0],
-     					      DR_BASE_OBJECT (a)))
+      && (!object_address_invariant_in_loop_p (loop_nest[0],
+					       DR_BASE_OBJECT (a))
+	  || DR_NUM_DIMENSIONS (a) == 0))
     {
       DDR_ARE_DEPENDENT (res) = chrec_dont_know;
       return res;
diff --git a/libgomp/testsuite/libgomp.c/pr69110.c b/libgomp/testsuite/libgomp.c/pr69110.c
new file mode 100644
index 0000000..0d9e5ca
--- /dev/null
+++ b/libgomp/testsuite/libgomp.c/pr69110.c
@@ -0,0 +1,26 @@
+/* { dg-do run } */
+/* { dg-options "-ftree-parallelize-loops=2 -O1 -fno-tree-loop-im" } */
+
+#define N 1000
+
+unsigned int i = 0;
+
+static void __attribute__((noinline, noclone))
+foo (void)
+{
+  unsigned int z;
+  for (z = 0; z < N; ++z)
+    ++i;
+}
+
+extern void abort (void);
+
+int
+main (void)
+{
+  foo ();
+  if (i != N)
+    abort ();
+
+  return 0;
+}

Re: [PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[Sebastian Pop]

Tom de Vries wrote:
> diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
> index a40f40d..4c29fc2 100644
> --- a/gcc/tree-data-ref.c
> +++ b/gcc/tree-data-ref.c
> @@ -1510,8 +1510,9 @@ initialize_data_dependence_relation (struct data_reference *a,
>    if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
>      {
>       if (loop_nest.exists ()
> -        && !object_address_invariant_in_loop_p (loop_nest[0],
> -       					        DR_BASE_OBJECT (a)))
> +	 && (!object_address_invariant_in_loop_p (loop_nest[0],
> +						  DR_BASE_OBJECT (a))
> +	     || DR_NUM_DIMENSIONS (a) == 0))

Also please fix the indentation of all this if stmt.

>        {
>          DDR_ARE_DEPENDENT (res) = chrec_dont_know;
>          return res;
> @@ -1548,8 +1549,9 @@ initialize_data_dependence_relation (struct data_reference *a,
>       analyze it.  TODO -- in fact, it would suffice to record that there may
>       be arbitrary dependences in the loops where the base object varies.  */
>    if (loop_nest.exists ()
> -      && !object_address_invariant_in_loop_p (loop_nest[0],
> -     					      DR_BASE_OBJECT (a)))
> +      && (!object_address_invariant_in_loop_p (loop_nest[0],
> +					       DR_BASE_OBJECT (a))
> +	  || DR_NUM_DIMENSIONS (a) == 0))
>      {
>        DDR_ARE_DEPENDENT (res) = chrec_dont_know;
>        return res;

Let's check for DR_NUM_DIMENSIONS (a) == 0 independently of loop_nest.exists ().
We check for the loop_nest because we need to access the outer loop loop_nest[0]
to analyze the base object of a.

Otherwise the change looks good to me.

Thanks,
Sebastian

Re: [PATCH, PR69110] Don't return NULL access_fns in dr_analyze_indices

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 1836 bytes --]

On 26/01/16 17:59, Sebastian Pop wrote:
> Tom de Vries wrote:
>> diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
>> index a40f40d..4c29fc2 100644
>> --- a/gcc/tree-data-ref.c
>> +++ b/gcc/tree-data-ref.c
>> @@ -1510,8 +1510,9 @@ initialize_data_dependence_relation (struct data_reference *a,
>>     if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
>>       {
>>        if (loop_nest.exists ()
>> -        && !object_address_invariant_in_loop_p (loop_nest[0],
>> -       					        DR_BASE_OBJECT (a)))
>> +	 && (!object_address_invariant_in_loop_p (loop_nest[0],
>> +						  DR_BASE_OBJECT (a))
>> +	     || DR_NUM_DIMENSIONS (a) == 0))
>
> Also please fix the indentation of all this if stmt.
>

Done.

>>         {
>>           DDR_ARE_DEPENDENT (res) = chrec_dont_know;
>>           return res;
>> @@ -1548,8 +1549,9 @@ initialize_data_dependence_relation (struct data_reference *a,
>>        analyze it.  TODO -- in fact, it would suffice to record that there may
>>        be arbitrary dependences in the loops where the base object varies.  */
>>     if (loop_nest.exists ()
>> -      && !object_address_invariant_in_loop_p (loop_nest[0],
>> -     					      DR_BASE_OBJECT (a)))
>> +      && (!object_address_invariant_in_loop_p (loop_nest[0],
>> +					       DR_BASE_OBJECT (a))
>> +	  || DR_NUM_DIMENSIONS (a) == 0))
>>       {
>>         DDR_ARE_DEPENDENT (res) = chrec_dont_know;
>>         return res;
>
> Let's check for DR_NUM_DIMENSIONS (a) == 0 independently of loop_nest.exists ().

Done.

> We check for the loop_nest because we need to access the outer loop loop_nest[0]
> to analyze the base object of a.
>
> Otherwise the change looks good to me.
>

Bootstrapped and reg-tested on x86_64.

Committed as attached to trunk, 5.0 and 4.9 (And fixed up pass number in 
testcases in 5.0 and 4.9).

Thanks,
- Tom

[-- Attachment #2: 0001-Handle-DR_NUM_DIMENSIONS-0-in-initialize_data_dependence_relation.patch --]
[-- Type: text/x-patch, Size: 3436 bytes --]

Handle DR_NUM_DIMENSIONS == 0 in initialize_data_dependence_relation

2016-01-12  Tom de Vries  <tom@codesourcery.com>

	PR tree-optimization/69110
	* tree-data-ref.c (initialize_data_dependence_relation): Handle
	DR_NUM_DIMENSIONS == 0.

	* gcc.dg/autopar/pr69110.c: New test.

	* testsuite/libgomp.c/pr69110.c: New test.

---
 gcc/testsuite/gcc.dg/autopar/pr69110.c | 17 +++++++++++++++++
 gcc/tree-data-ref.c                    | 21 +++++++++++----------
 libgomp/testsuite/libgomp.c/pr69110.c  | 26 ++++++++++++++++++++++++++
 3 files changed, 54 insertions(+), 10 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/autopar/pr69110.c b/gcc/testsuite/gcc.dg/autopar/pr69110.c
new file mode 100644
index 0000000..27cdae5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/autopar/pr69110.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -ftree-parallelize-loops=2 -fno-tree-loop-im -fdump-tree-parloops2-details" } */
+
+#define N 1000
+
+unsigned int i = 0;
+
+void
+foo (void)
+{
+  unsigned int z;
+  for (z = 0; z < N; ++z)
+    ++i;
+}
+
+/* { dg-final { scan-tree-dump-times "SUCCESS: may be parallelized" 0 "parloops2" } } */
+/* { dg-final { scan-tree-dump-times "FAILED: data dependencies exist across iterations" 1 "parloops2" } } */
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index a40f40d..d6d9ffc 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1509,13 +1509,14 @@ initialize_data_dependence_relation (struct data_reference *a,
   /* The case where the references are exactly the same.  */
   if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
     {
-     if (loop_nest.exists ()
-        && !object_address_invariant_in_loop_p (loop_nest[0],
-       					        DR_BASE_OBJECT (a)))
-      {
-        DDR_ARE_DEPENDENT (res) = chrec_dont_know;
-        return res;
-      }
+      if ((loop_nest.exists ()
+	   && !object_address_invariant_in_loop_p (loop_nest[0],
+						   DR_BASE_OBJECT (a)))
+	  || DR_NUM_DIMENSIONS (a) == 0)
+	{
+	  DDR_ARE_DEPENDENT (res) = chrec_dont_know;
+	  return res;
+	}
       DDR_AFFINE_P (res) = true;
       DDR_ARE_DEPENDENT (res) = NULL_TREE;
       DDR_SUBSCRIPTS (res).create (DR_NUM_DIMENSIONS (a));
@@ -1547,9 +1548,9 @@ initialize_data_dependence_relation (struct data_reference *a,
   /* If the base of the object is not invariant in the loop nest, we cannot
      analyze it.  TODO -- in fact, it would suffice to record that there may
      be arbitrary dependences in the loops where the base object varies.  */
-  if (loop_nest.exists ()
-      && !object_address_invariant_in_loop_p (loop_nest[0],
-     					      DR_BASE_OBJECT (a)))
+  if ((loop_nest.exists ()
+       && !object_address_invariant_in_loop_p (loop_nest[0], DR_BASE_OBJECT (a)))
+      || DR_NUM_DIMENSIONS (a) == 0)
     {
       DDR_ARE_DEPENDENT (res) = chrec_dont_know;
       return res;
diff --git a/libgomp/testsuite/libgomp.c/pr69110.c b/libgomp/testsuite/libgomp.c/pr69110.c
new file mode 100644
index 0000000..0d9e5ca
--- /dev/null
+++ b/libgomp/testsuite/libgomp.c/pr69110.c
@@ -0,0 +1,26 @@
+/* { dg-do run } */
+/* { dg-options "-ftree-parallelize-loops=2 -O1 -fno-tree-loop-im" } */
+
+#define N 1000
+
+unsigned int i = 0;
+
+static void __attribute__((noinline, noclone))
+foo (void)
+{
+  unsigned int z;
+  for (z = 0; z < N; ++z)
+    ++i;
+}
+
+extern void abort (void);
+
+int
+main (void)
+{
+  foo ();
+  if (i != N)
+    abort ();
+
+  return 0;
+}