[patch] Fix PR tree-optimization/49960 ,Fix self data dependence

[patch] Fix PR tree-optimization/49960 ,Fix self data dependence

[Razya Ladelsky]

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

This patch fixes the failures described in 
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49960
It also fixes bzips when run with autopar enabled.

In both cases the self dependences are not handled correctly.
In the first case, a non affine access is analyzed:
in the second, the distance vector is not calculated correctly (the 
distance vector considered for for self dependences is always (0,0,...))

As  a result, the loops get wrongfully parallelized.

The patch avoids the special handling of  self dependences, and analyzes 
all dependences in the same way. Specific adjustments
and support for the self dependence cases were made.

Bootstrap and testsuite pass successfully for ppc64-redhat-linux.

OK for trunk?
Thank you,
Razya


ChangeLog:

        PR tree-optimization/49960
        * tree-data-ref.c (compute_self_dependence): Remove.
             (initialize_data_dependence_relation): Add intializations. 
Remove compute_self_dependence.
             (add_other_self_distances): Add support for two dimensions if 
the second is zero.
             (compute_affine_dependence): Remove the !DDR_SELF_REFERENCE 
condition.
             (compute_all_dependences): Remove call to 
compute_self_dependence. Add call to compute_affine_dependence

testsuite/ChangeLog:

        PR tree-optimization/49660
        * gcc.dg/autopar/pr49660.c: New test.
           * gcc.dg/autopar/pr49660-1.c: New test.













 


[-- Attachment #2: pr49960_fix.txt --]
[-- Type: text/plain, Size: 4300 bytes --]

Index: tree-data-ref.c
===================================================================
--- tree-data-ref.c	(revision 179799)
+++ tree-data-ref.c	(working copy)
@@ -1346,7 +1346,6 @@ dr_may_alias_p (const struct data_reference *a, co
   return refs_may_alias_p (addr_a, addr_b);
 }
 
-static void compute_self_dependence (struct data_dependence_relation *);
 
 /* Initialize a data dependence relation between data accesses A and
    B.  NB_LOOPS is the number of loops surrounding the references: the
@@ -1386,13 +1385,30 @@ initialize_data_dependence_relation (struct data_r
      the data dependence tests, just initialize the ddr and return.  */
   if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
     {
+      if (loop_nest
+	  && !object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
+						  DR_BASE_OBJECT (a)))
+	{
+	  DDR_ARE_DEPENDENT (res) = chrec_dont_know;
+	  return res;
+	}
       DDR_AFFINE_P (res) = true;
       DDR_ARE_DEPENDENT (res) = NULL_TREE;
       DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
       DDR_LOOP_NEST (res) = loop_nest;
       DDR_INNER_LOOP (res) = 0;
       DDR_SELF_REFERENCE (res) = true;
-      compute_self_dependence (res);
+      for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
+	{
+	  struct subscript *subscript;
+	  
+	  subscript = XNEW (struct subscript);
+	  SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
+	  SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
+	  SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
+	  SUB_DISTANCE (subscript) = chrec_dont_know;
+	  VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
+	}
       return res;
     }
 
@@ -3119,8 +3135,11 @@ add_other_self_distances (struct data_dependence_r
 	    {
 	      if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
 		{
-		  DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
-		  return;
+		  if (DDR_NUM_SUBSCRIPTS (ddr) != 2 || !integer_zerop (DR_ACCESS_FN (DDR_A (ddr), 1)))
+		    {
+		      DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
+		      return;
+		    }
 		}
 
 	      access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
@@ -4037,8 +4056,7 @@ compute_affine_dependence (struct data_dependence_
     }
 
   /* Analyze only when the dependence relation is not yet known.  */
-  if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
-      && !DDR_SELF_REFERENCE (ddr))
+  if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
     {
       dependence_stats.num_dependence_tests++;
 
@@ -4113,39 +4131,6 @@ compute_affine_dependence (struct data_dependence_
     fprintf (dump_file, ")\n");
 }
 
-/* This computes the dependence relation for the same data
-   reference into DDR.  */
-
-static void
-compute_self_dependence (struct data_dependence_relation *ddr)
-{
-  unsigned int i;
-  struct subscript *subscript;
-
-  if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
-    return;
-
-  for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
-       i++)
-    {
-      if (SUB_CONFLICTS_IN_A (subscript))
-	free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
-      if (SUB_CONFLICTS_IN_B (subscript))
-	free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
-
-      /* The accessed index overlaps for each iteration.  */
-      SUB_CONFLICTS_IN_A (subscript)
-	= conflict_fn (1, affine_fn_cst (integer_zero_node));
-      SUB_CONFLICTS_IN_B (subscript)
-	= conflict_fn (1, affine_fn_cst (integer_zero_node));
-      SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
-    }
-
-  /* The distance vector is the zero vector.  */
-  save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
-  save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
-}
-
 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
    the data references in DATAREFS, in the LOOP_NEST.  When
    COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
@@ -4176,7 +4161,8 @@ compute_all_dependences (VEC (data_reference_p, he
       {
 	ddr = initialize_data_dependence_relation (a, a, loop_nest);
 	VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
-	compute_self_dependence (ddr);
+	if (loop_nest)
+	  compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
       }
 }
 
=

[-- Attachment #3: pr49660-1.c --]
[-- Type: application/octet-stream, Size: 984 bytes --]

/* { dg-do compile } */
/* { dg-options "-O2 -ftree-parallelize-loops=4 -fdump-tree-parloops-details -fdump-tree-optimized" } */

#include <stdlib.h>
#include <stdio.h>

int main() 
{
  unsigned int x, y, idx, H = 1024, W = 1024;
  
  int * tmps = (int *)malloc(H*W*sizeof(int));
  
  /* This loop gets parallelized even though output dependences exist 
     between writes to 'tmps' that prevent parallelization. 
     For example: tmps[1] = 1, ..., tmps[1] = 17.  */
  
  for(x = 1; x < H; x++) 
    {
      for(y = 1; y < W; y++) 
	{
	  idx = x*W+y;
	  tmps[idx % 4096] = idx;	  
	}
    }
  
  for(x = 1; x < 8; x++)
    printf("tmps[%d]=%d\n", x, tmps[x]);
  
  return 0;
}
/* Check that no loop gets parallelized.  */

/* { dg-final { scan-tree-dump-times "SUCCESS: may be parallelized" 0 "parloops" } } */
/* { dg-final { scan-tree-dump-times "loopfn" 0 "optimized" } } */
/* { dg-final { cleanup-tree-dump "parloops" } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */

[-- Attachment #4: pr49960.c --]
[-- Type: application/octet-stream, Size: 1276 bytes --]

/* { dg-do compile } */
/* { dg-options "-O2 -ftree-parallelize-loops=4 -fdump-tree-parloops-details -fdump-tree-optimized" } */

#include <stdio.h>
#define MB 100
#define NA 450
#define MA 400

int T[MA][MB],A[MA][NA],B[MB][NA];
void MRTRBR(int MA_1, int NA_1, int MB_1)
{
  int i,j, t,k;

  /* The outer most loop is not parallel because for different k's there
     is write-write dependency for T[i][j].  */
  
  /* The two inner loops don't get parallelized due to low number of 
     iterations.  */

  for (k = 3; k < NA_1; k++)
    for (i = 3; i < MA_1; i++)
      for (j = 3; j < MB_1; j++)
	{
	  t = T[i][j];
	  T[i][j] = t+2+A[i][k]*B[j][k];
	}
}
void main ()
{
  int j,i;
  
  for (i = 3; i < MA; i++)
    for (j = 3; j < MB; j++)
      T[i][j] = (i>j?i:j);
  
  MRTRBR (MA,NA,MB);
  
  for (i = MA-1; i < MA; i++)
    for (j = MB-10; j < MB; j++)
      printf ("i %d j %d T[i][j] = %d\n",i,j,T[i][j]);
}


/* Check that the outer most loop doesn't get parallelized (thus no loop gets parallelized)  */

/* { dg-final { scan-tree-dump-times "SUCCESS: may be parallelized" 0 "parloops" } } */
/* { dg-final { scan-tree-dump-times "loopfn" 0 "optimized" } } */
/* { dg-final { cleanup-tree-dump "parloops" } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */

Re: [patch] Fix PR tree-optimization/49960 ,Fix self data dependence

[Richard Guenther]

On Mon, Oct 17, 2011 at 8:23 AM, Razya Ladelsky <RAZYA@il.ibm.com> wrote:
> This patch fixes the failures described in
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49960
> It also fixes bzips when run with autopar enabled.
>
> In both cases the self dependences are not handled correctly.
> In the first case, a non affine access is analyzed:
> in the second, the distance vector is not calculated correctly (the
> distance vector considered for for self dependences is always (0,0,...))
>
> As  a result, the loops get wrongfully parallelized.
>
> The patch avoids the special handling of  self dependences, and analyzes
> all dependences in the same way. Specific adjustments
> and support for the self dependence cases were made.

Can you elaborate on

@@ -3119,8 +3135,11 @@ add_other_self_distances (struct data_dependence_r
 	    {
 	      if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
 		{
-		  DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
-		  return;
+		  if (DDR_NUM_SUBSCRIPTS (ddr) != 2 || !integer_zerop (DR_ACCESS_FN
(DDR_A (ddr), 1)))
+		    {
+		      DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
+		      return;
+		    }
 		}

 	      access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);

?  It needed a comment before, and now so even more.

The rest of the patch is ok, I suppose the above hunk is to enhance
something, not
to fix the bug?

Thanks,
Richard.

> Bootstrap and testsuite pass successfully for ppc64-redhat-linux.
>
> OK for trunk?
> Thank you,
> Razya
>
>
> ChangeLog:
>
>        PR tree-optimization/49960
>        * tree-data-ref.c (compute_self_dependence): Remove.
>             (initialize_data_dependence_relation): Add intializations.
> Remove compute_self_dependence.
>             (add_other_self_distances): Add support for two dimensions if
> the second is zero.
>             (compute_affine_dependence): Remove the !DDR_SELF_REFERENCE
> condition.
>             (compute_all_dependences): Remove call to
> compute_self_dependence. Add call to compute_affine_dependence
>
> testsuite/ChangeLog:
>
>        PR tree-optimization/49660
>        * gcc.dg/autopar/pr49660.c: New test.
>           * gcc.dg/autopar/pr49660-1.c: New test.
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

Fwd: [patch] Fix PR tree-optimization/49960 ,Fix self data dependence

[Richard Guenther]

Forwarded to the list, gcc.gnu.org doesn't like gmail anymore.

---------- Forwarded message ----------
From: Richard Guenther <richard.guenther@gmail.com>
Date: Fri, Oct 21, 2011 at 11:03 AM
Subject: Re: [patch] Fix PR tree-optimization/49960 ,Fix self data dependence
To: Razya Ladelsky <RAZYA@il.ibm.com>
Cc: gcc-patches@gcc.gnu.org, gcc-patches-owner@gcc.gnu.org, Sebastian
Pop <spop@gcc.gnu.org>


On Wed, Oct 19, 2011 at 5:42 PM, Razya Ladelsky <RAZYA@il.ibm.com> wrote:
> gcc-patches-owner@gcc.gnu.org wrote on 17/10/2011 09:03:59 AM:
>
>> From: Richard Guenther <richard.guenther@gmail.com>
>> To: Razya Ladelsky/Haifa/IBM@IBMIL
>> Cc: gcc-patches@gcc.gnu.org, Sebastian Pop <spop@gcc.gnu.org>
>> Date: 17/10/2011 09:04 AM
>> Subject: Re: [patch] Fix PR tree-optimization/49960 ,Fix self data
> dependence
>> Sent by: gcc-patches-owner@gcc.gnu.org
>>
>> On Mon, Oct 17, 2011 at 8:23 AM, Razya Ladelsky <RAZYA@il.ibm.com>
> wrote:
>> > This patch fixes the failures described in
>> > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49960
>> > It also fixes bzips when run with autopar enabled.
>> >
>> > In both cases the self dependences are not handled correctly.
>> > In the first case, a non affine access is analyzed:
>> > in the second, the distance vector is not calculated correctly (the
>> > distance vector considered for for self dependences is always
> (0,0,...))
>> >
>> > As  a result, the loops get wrongfully parallelized.
>> >
>> > The patch avoids the special handling of  self dependences, and
> analyzes
>> > all dependences in the same way. Specific adjustments
>> > and support for the self dependence cases were made.
>>
>> Can you elaborate on
>>
>> @@ -3119,8 +3135,11 @@ add_other_self_distances (struct
> data_dependence_r
>>         {
>>           if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
>>        {
>> -        DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
>> -        return;
>> +        if (DDR_NUM_SUBSCRIPTS (ddr) != 2 || !integer_zerop
> (DR_ACCESS_FN
>> (DDR_A (ddr), 1)))
>> +          {
>> +            DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
>> +            return;
>> +          }
>>        }
>>
>>           access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
>>
>> ?  It needed a comment before, and now so even more.
>>
>> The rest of the patch is ok, I suppose the above hunk is to enhance
>> something, not
>> to fix the bug?
>
> For fortran code like:
>
>      DO 140 J=1,MB
>         DO 130 K=1,NA
>            BKJ=B(K,J)
>            IF(BKJ.EQ.ZERO) GO TO 130
>               DO 120 I=1,MA
>                  C(I,J)=C(I,J)+A(K,I)*BKJ
>  120          CONTINUE
>  130    CONTINUE
>  140 CONTINUE
>      RETURN
>
>
> The access functions for the C(i j) self dependence are:
>
> (Data Dep:
> #(Data Ref:
> #  bb: 9
> #  stmt: D.1427_79 = *c_78(D)[D.1426_77];
> #  ref: *c_78(D)[D.1426_77];
> #  base_object: *c_78(D);
> #  Access function 0: {{(stride.12_25 + 1) + offset.13_36, +,
> stride.12_25}_1, +, 1}_3
> #  Access function 1: 0B
> #)
> #(Data Ref:
> #  bb: 9
> #  stmt: *c_78(D)[D.1426_77] = D.1433_88;
> #  ref: *c_78(D)[D.1426_77];
> #  base_object: *c_78(D);
> #  Access function 0: {{(stride.12_25 + 1) + offset.13_36, +,
> stride.12_25}_1, +, 1}_3
> #  Access function 1: 0B
> #)
>
>
> Two dimesions are created to describe C(i j) although there's no need for
> access function 1 which is just 0B.
>
>
> If this was a C code, we would have these two access functions for
> C[i][j]:
>
> (Data Dep:
> #(Data Ref:
> #  bb: 5
> #  stmt: t_10 = C[i_33][j_37];
> #  ref: C[i_33][j_37];
> #  base_object: C
> #  Access function 0: {3, +, 1}_3
> #  Access function 1: {3, +, 1}_2
> #)
> #(Data Ref:
> #  bb: 5
> #  stmt: C[i_33][j_37] = D.3852_15;
> #  ref: C[i_33][j_37];
> #  base_object: C
> #  Access function 0: {3, +, 1}_3
> #  Access function 1: {3, +, 1}_2
> #)
>
>
> In order to handle the Fortran data accesses, even for simple cases as
> above,
> I would need to handle multivariate accesses.
> The data dependence analysis doesn't know how to handle such dependences
> if there's more than one subscript.
> The above Frotran code doesn't actually have two subscripts, but one, and
> thus should be handled.
>
> The reason this issue came up only with the changes of this patch is that
> now
> add_other_self_distances is called from build_classic_dist_vector, which
> is called also for self dependences.
> Before the patch, the distance vector for self dependences was always
> determined as a vector of 0's, and build_classic_dist_vector
> was not called.
>
> I hope it's clearer now, I will add a comment to the code, and submit it
> before committing it.

No, it's not clearer, because it is not clear why you need to add the hack
instead of avoiding the 2nd access function. And iff you add the hack it
needs a comment why zero should be special (any other constant would
be the same I suppose).

Btw, your fortran example does not compile and I don't believe the issue
is still present after my last changes to dr_analyze_indices.  So, did
you verify this on trunk?

Richard.

> Thanks,
> Razya
>
>
>>
>> Thanks,
>> Richard.
>>
>> > Bootstrap and testsuite pass successfully for ppc64-redhat-linux.
>> >
>> > OK for trunk?
>> > Thank you,
>> > Razya
>> >
>> >
>> > ChangeLog:
>> >
>> >        PR tree-optimization/49960
>> >        * tree-data-ref.c (compute_self_dependence): Remove.
>> >             (initialize_data_dependence_relation): Add intializations.
>> > Remove compute_self_dependence.
>> >             (add_other_self_distances): Add support for two dimensions
> if
>> > the second is zero.
>> >             (compute_affine_dependence): Remove the
> !DDR_SELF_REFERENCE
>> > condition.
>> >             (compute_all_dependences): Remove call to
>> > compute_self_dependence. Add call to compute_affine_dependence
>>
>> > testsuite/ChangeLog:
>> >
>> >        PR tree-optimization/49660
>> >        * gcc.dg/autopar/pr49660.c: New test.
>> >           * gcc.dg/autopar/pr49660-1.c: New test.
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>
>

[PATCH, take 2] Fix PR tree-optimization/49960 ,Fix self data dependence

[Razya Ladelsky]

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

> > I hope it's clearer now, I will add a comment to the code, and submit 
it
> > before committing it.
> 
> No, it's not clearer, because it is not clear why you need to add the 
hack
> instead of avoiding the 2nd access function. And iff you add the hack it
> needs a comment why zero should be special (any other constant would
> be the same I suppose).
> 
> Btw, your fortran example does not compile and I don't believe the issue
> is still present after my last changes to dr_analyze_indices.  So, did
> you verify this on trunk?
> 
> Richard.

This patch fixes the failures described in 
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49960
It also fixes bzips when run with autopar enabled.

In both cases the self dependences are not handled correctly.
In the first case, a non affine access is analyzed:
in the second, the distance vector is not calculated correctly (the 
distance vector considered for for self dependences is always (0,0,...))
As  a result, the loops get wrongfully parallelized.

I modified the previous patch according to the last changes in the trunk,
which indeed do not requite special handling for the 2nd access function 
(as mentioned by Richard).
Another change is that the previous version of the patch eliminated 
compute_self_dependences function
as the calls to it were redundant, while this version considers the new 
call to compute_self_dependences from the vect code for gather (inserted 
lately by Jakub).

ChangeLog:
        PR tree-optimization/49960

        * tree-data-ref.c (initialize_data_dependence_relation): Add 
initializations. 
        Remove call to compute_self_dependence.
        (compute_affine_dependence): Remove the !DDR_SELF_REFERENCE 
condition.
        (compute_self_dependence): Remove old code. Add call to 
compute_affine_dependence.
        (compute_all_dependences): Remove call to compute_self_dependence. 

        Add call to compute_affine_dependence.
 
        testsuite/ChangeLog:
        PR tree-optimization/49960

        * gcc.dg/autopar/pr49960.c: New test.
        * gcc.dg/autopar/pr49960-1.c: New test.







Bootstrap and testsuite pass successfully for ppc64-redhat-linux.

OK for trunk?
Thank you,
Razya


[-- Attachment #2: pr49960.c --]
[-- Type: application/octet-stream, Size: 1276 bytes --]

/* { dg-do compile } */
/* { dg-options "-O2 -ftree-parallelize-loops=4 -fdump-tree-parloops-details -fdump-tree-optimized" } */

#include <stdio.h>
#define MB 100
#define NA 450
#define MA 400

int T[MA][MB],A[MA][NA],B[MB][NA];
void MRTRBR(int MA_1, int NA_1, int MB_1)
{
  int i,j, t,k;

  /* The outer most loop is not parallel because for different k's there
     is write-write dependency for T[i][j].  */
  
  /* The two inner loops don't get parallelized due to low number of 
     iterations.  */

  for (k = 3; k < NA_1; k++)
    for (i = 3; i < MA_1; i++)
      for (j = 3; j < MB_1; j++)
	{
	  t = T[i][j];
	  T[i][j] = t+2+A[i][k]*B[j][k];
	}
}
void main ()
{
  int j,i;
  
  for (i = 3; i < MA; i++)
    for (j = 3; j < MB; j++)
      T[i][j] = (i>j?i:j);
  
  MRTRBR (MA,NA,MB);
  
  for (i = MA-1; i < MA; i++)
    for (j = MB-10; j < MB; j++)
      printf ("i %d j %d T[i][j] = %d\n",i,j,T[i][j]);
}


/* Check that the outer most loop doesn't get parallelized (thus no loop gets parallelized)  */

/* { dg-final { scan-tree-dump-times "SUCCESS: may be parallelized" 0 "parloops" } } */
/* { dg-final { scan-tree-dump-times "loopfn" 0 "optimized" } } */
/* { dg-final { cleanup-tree-dump "parloops" } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */

[-- Attachment #3: pr49960-1.c --]
[-- Type: application/octet-stream, Size: 984 bytes --]

/* { dg-do compile } */
/* { dg-options "-O2 -ftree-parallelize-loops=4 -fdump-tree-parloops-details -fdump-tree-optimized" } */

#include <stdlib.h>
#include <stdio.h>

int main() 
{
  unsigned int x, y, idx, H = 1024, W = 1024;
  
  int * tmps = (int *)malloc(H*W*sizeof(int));
  
  /* This loop gets parallelized even though output dependences exist 
     between writes to 'tmps' that prevent parallelization. 
     For example: tmps[1] = 1, ..., tmps[1] = 17.  */
  
  for(x = 1; x < H; x++) 
    {
      for(y = 1; y < W; y++) 
	{
	  idx = x*W+y;
	  tmps[idx % 4096] = idx;	  
	}
    }
  
  for(x = 1; x < 8; x++)
    printf("tmps[%d]=%d\n", x, tmps[x]);
  
  return 0;
}
/* Check that no loop gets parallelized.  */

/* { dg-final { scan-tree-dump-times "SUCCESS: may be parallelized" 0 "parloops" } } */
/* { dg-final { scan-tree-dump-times "loopfn" 0 "optimized" } } */
/* { dg-final { cleanup-tree-dump "parloops" } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */

[-- Attachment #4: self_dependence_patch.txt --]
[-- Type: text/plain, Size: 3461 bytes --]

Index: gcc/tree-data-ref.c
===================================================================
--- gcc/tree-data-ref.c	(revision 181168)
+++ gcc/tree-data-ref.c	(working copy)
@@ -1389,13 +1389,30 @@ initialize_data_dependence_relation (struct data_r
      the data dependence tests, just initialize the ddr and return.  */
   if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
     {
+     if (loop_nest
+        && !object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
+       					        DR_BASE_OBJECT (a)))
+      {
+        DDR_ARE_DEPENDENT (res) = chrec_dont_know;
+        return res;
+      }
       DDR_AFFINE_P (res) = true;
       DDR_ARE_DEPENDENT (res) = NULL_TREE;
       DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
       DDR_LOOP_NEST (res) = loop_nest;
       DDR_INNER_LOOP (res) = 0;
       DDR_SELF_REFERENCE (res) = true;
-      compute_self_dependence (res);
+      for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
+       {
+         struct subscript *subscript;
+
+         subscript = XNEW (struct subscript);
+         SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
+         SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
+         SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
+         SUB_DISTANCE (subscript) = chrec_dont_know;
+         VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
+       }
       return res;
     }
 
@@ -4040,8 +4057,7 @@ compute_affine_dependence (struct data_dependence_
     }
 
   /* Analyze only when the dependence relation is not yet known.  */
-  if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
-      && !DDR_SELF_REFERENCE (ddr))
+  if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
     {
       dependence_stats.num_dependence_tests++;
 
@@ -4122,31 +4138,11 @@ compute_affine_dependence (struct data_dependence_
 void
 compute_self_dependence (struct data_dependence_relation *ddr)
 {
-  unsigned int i;
-  struct subscript *subscript;
-
   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
     return;
 
-  for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
-       i++)
-    {
-      if (SUB_CONFLICTS_IN_A (subscript))
-	free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
-      if (SUB_CONFLICTS_IN_B (subscript))
-	free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
-
-      /* The accessed index overlaps for each iteration.  */
-      SUB_CONFLICTS_IN_A (subscript)
-	= conflict_fn (1, affine_fn_cst (integer_zero_node));
-      SUB_CONFLICTS_IN_B (subscript)
-	= conflict_fn (1, affine_fn_cst (integer_zero_node));
-      SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
-    }
-
-  /* The distance vector is the zero vector.  */
-  save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
-  save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
+  if (DDR_LOOP_NEST (ddr))
+    compute_affine_dependence (ddr, VEC_index (loop_p, DDR_LOOP_NEST (ddr), 0));
 }
 
 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
@@ -4179,7 +4175,8 @@ compute_all_dependences (VEC (data_reference_p, he
       {
 	ddr = initialize_data_dependence_relation (a, a, loop_nest);
 	VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
-	compute_self_dependence (ddr);
+        if (loop_nest)
+   	  compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
       }
 }
 
=

Re: [PATCH, take 2] Fix PR tree-optimization/49960 ,Fix self data dependence

[Richard Guenther]

On Tue, Nov 15, 2011 at 11:31 AM, Razya Ladelsky <RAZYA@il.ibm.com> wrote:
>> > I hope it's clearer now, I will add a comment to the code, and submit
> it
>> > before committing it.
>>
>> No, it's not clearer, because it is not clear why you need to add the
> hack
>> instead of avoiding the 2nd access function. And iff you add the hack it
>> needs a comment why zero should be special (any other constant would
>> be the same I suppose).
>>
>> Btw, your fortran example does not compile and I don't believe the issue
>> is still present after my last changes to dr_analyze_indices.  So, did
>> you verify this on trunk?
>>
>> Richard.
>
> This patch fixes the failures described in
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49960
> It also fixes bzips when run with autopar enabled.
>
> In both cases the self dependences are not handled correctly.
> In the first case, a non affine access is analyzed:
> in the second, the distance vector is not calculated correctly (the
> distance vector considered for for self dependences is always (0,0,...))
> As  a result, the loops get wrongfully parallelized.
>
> I modified the previous patch according to the last changes in the trunk,
> which indeed do not requite special handling for the 2nd access function
> (as mentioned by Richard).
> Another change is that the previous version of the patch eliminated
> compute_self_dependences function
> as the calls to it were redundant, while this version considers the new
> call to compute_self_dependences from the vect code for gather (inserted
> lately by Jakub).
> ChangeLog:
>        PR tree-optimization/49960
>
>        * tree-data-ref.c (initialize_data_dependence_relation): Add
> initializations.
>        Remove call to compute_self_dependence.
>        (compute_affine_dependence): Remove the !DDR_SELF_REFERENCE
> condition.
>        (compute_self_dependence): Remove old code. Add call to
> compute_affine_dependence.
>        (compute_all_dependences): Remove call to compute_self_dependence.
>
>        Add call to compute_affine_dependence.
>
>        testsuite/ChangeLog:
>        PR tree-optimization/49960
>
>        * gcc.dg/autopar/pr49960.c: New test.
>        * gcc.dg/autopar/pr49960-1.c: New test.
>
>
>
>
>
>
>
> Bootstrap and testsuite pass successfully for ppc64-redhat-linux.
>
> OK for trunk?

Ok.

Thanks,
Richard.

> Thank you,
> Razya
>
>

Re: [PATCH, take 2] Fix PR tree-optimization/49960 ,Fix self data dependence

[Jakub Jelinek]

On Tue, Nov 15, 2011 at 12:31:39PM +0200, Razya Ladelsky wrote:
> This patch fixes the failures described in 
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49960
> It also fixes bzips when run with autopar enabled.

Sorry, I've been away and couldn't react to this earlier, but the patch
looks wrong to me.  The reason why I've been calling compute_self_dependence
from the gather handling code is to do there what we did for normal data
references in compute_all_dependences, except for the affine stuff.
So, when compute_all_dependences no longer calls it, neither should
vect_analyze_data_refs.

	Jakub

Re: [PATCH, take 2] Fix PR tree-optimization/49960 ,Fix self data dependence

[Razya Ladelsky]

gcc-patches-owner@gcc.gnu.org wrote on 21/11/2011 02:57:07 PM:

> From: Jakub Jelinek <jakub@redhat.com>
> To: Razya Ladelsky/Haifa/IBM@IBMIL
> Cc: Richard Guenther <richard.guenther@gmail.com>, GCC Patches <gcc-
> patches@gcc.gnu.org>
> Date: 21/11/2011 02:57 PM
> Subject: Re: [PATCH, take 2] Fix PR tree-optimization/49960 ,Fix 
> self data dependence
> Sent by: gcc-patches-owner@gcc.gnu.org
> 
> On Tue, Nov 15, 2011 at 12:31:39PM +0200, Razya Ladelsky wrote:
> > This patch fixes the failures described in 
> > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49960
> > It also fixes bzips when run with autopar enabled.
> 
> Sorry, I've been away and couldn't react to this earlier, but the patch
> looks wrong to me.  The reason why I've been calling 
compute_self_dependence
> from the gather handling code is to do there what we did for normal data
> references in compute_all_dependences, except for the affine stuff.

Hi Jakub,
what do you mean by 'except for the affine stuff'?


Before having this patch, compute_self_depepndence just marked the 
distance zero 
and returned, while now it calls compute_affine_dependence.
So I think you do get the right outcome now.

> So, when compute_all_dependences no longer calls it, neither should
> vect_analyze_data_refs.

So do you want to replace it with the call to compute_affine_dependence?

Thanks,
Razya

> 
>    Jakub
> 

Re: [PATCH, take 2] Fix PR tree-optimization/49960 ,Fix self data dependence

[Jakub Jelinek]

On Mon, Nov 21, 2011 at 03:50:10PM +0200, Razya Ladelsky wrote:
> what do you mean by 'except for the affine stuff'?

I mean that compute_affine_dependence must never be called on gather
data refs, that function can't do anything meaningful for them, they are
gather data refs exactly because dr_analyze_innermost failed on them
otherwise, as base and/or offset aren't simple IVs.

> > So, when compute_all_dependences no longer calls it, neither should
> > vect_analyze_data_refs.
> 
> So do you want to replace it with the call to compute_affine_dependence?

No.  With nothing at all.

	Jakub

Re: [PATCH, take 2] Fix PR tree-optimization/49960 ,Fix self data dependence

[Razya Ladelsky]

Jakub Jelinek <jakub@redhat.com> wrote on 21/11/2011 03:59:15 PM:

> From: Jakub Jelinek <jakub@redhat.com>
> To: Razya Ladelsky/Haifa/IBM@IBMIL
> Cc: GCC Patches <gcc-patches@gcc.gnu.org>, Richard Guenther 
> <richard.guenther@gmail.com>
> Date: 21/11/2011 03:59 PM
> Subject: Re: [PATCH, take 2] Fix PR tree-optimization/49960 ,Fix 
> self data dependence
> 
> On Mon, Nov 21, 2011 at 03:50:10PM +0200, Razya Ladelsky wrote:
> > what do you mean by 'except for the affine stuff'?
> 
> I mean that compute_affine_dependence must never be called on gather
> data refs, that function can't do anything meaningful for them, they are
> gather data refs exactly because dr_analyze_innermost failed on them
> otherwise, as base and/or offset aren't simple IVs.
> 

I understand.
I tried to follow the same paths that data refs (affine or not) go through 
in compute_all_depepndences.

According to compute_all_depepndences(), the path for computing any data 
dependence is:
call initialize_data_depepndence_relation(), and call 
compute_affine_dependence() if there's a loop nest.
I tried to keep the same semantics for self dependences.

Although compute_affine_dependence() can't do anything meaningful for the 
gather data refs,
it may still be assigning values to the dependence relation structure, if 
you need to use them. 
Therefore I did not skip the call to compute_self_dependence(), which 
indeed calls
compute_affine_depepndence().


If you think it's redundant, we can remove it.
Thanks,
Razya
 

> > > So, when compute_all_dependences no longer calls it, neither should
> > > vect_analyze_data_refs.
> > 
> > So do you want to replace it with the call to 
compute_affine_dependence?
> 
> No.  With nothing at all.
> 
>    Jakub
> 

Re: [PATCH, take 2] Fix PR tree-optimization/49960 ,Fix self data dependence

[Jakub Jelinek]

On Mon, Nov 21, 2011 at 04:54:09PM +0200, Razya Ladelsky wrote:
> Although compute_affine_dependence() can't do anything meaningful for the 
> gather data refs,
> it may still be assigning values to the dependence relation structure, if 
> you need to use them. 
> Therefore I did not skip the call to compute_self_dependence(), which 
> indeed calls
> compute_affine_depepndence().
> 
> 
> If you think it's redundant, we can remove it.

It is not just redundant, but harmful.  compute_affine_dependence assumes
that base and offset are simple IVs, that is not true for gather deps.
So please do remove it.

	Jakub

Re: [PATCH, take 2] Fix PR tree-optimization/49960 ,Fix self data dependence

[Razya Ladelsky]

Jakub Jelinek <jakub@redhat.com> wrote on 21/11/2011 05:07:54 PM:

> From: Jakub Jelinek <jakub@redhat.com>
> To: Razya Ladelsky/Haifa/IBM@IBMIL
> Cc: GCC Patches <gcc-patches@gcc.gnu.org>, Richard Guenther 
> <richard.guenther@gmail.com>
> Date: 21/11/2011 05:08 PM
> Subject: Re: [PATCH, take 2] Fix PR tree-optimization/49960 ,Fix 
> self data dependence
> 
> On Mon, Nov 21, 2011 at 04:54:09PM +0200, Razya Ladelsky wrote:
> > Although compute_affine_dependence() can't do anything meaningful for 
the 
> > gather data refs,
> > it may still be assigning values to the dependence relation structure, 
if 
> > you need to use them. 
> > Therefore I did not skip the call to compute_self_dependence(), which 
> > indeed calls
> > compute_affine_depepndence().
> > 
> > 
> > If you think it's redundant, we can remove it.
> 
> It is not just redundant, but harmful.  compute_affine_dependence 
assumes
> that base and offset are simple IVs, that is not true for gather deps.
> So please do remove it.
> 
>    Jakub
> 

Jakub,

I have some non-affine cases for which compute_affine_dependence is called 
(as it is called for 
ALL dependences from compte_all_depepndences()), and no harm is done.
I looked a little bit closer into the code, and this is what happens for 
non affine accesses:

initialize_data_dependence_relation() assigns 
DDR_ARE_DEPENDENT (res) = chrec_dont_know for the dr.

Then, compute_affine_depepndence()
tests if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE), and does nothing 
otherwise.
Since the dr was initialized with chrec_dont_know, no harm is done.

Anyway, since it is useless for your gather case, I'll just remove it, 
along with compute_self_dependence().

OK?

Thanks,
Razya

Re: [PATCH, take 2] Fix PR tree-optimization/49960 ,Fix self data dependence

[Jakub Jelinek]

On Mon, Nov 21, 2011 at 06:56:55PM +0200, Razya Ladelsky wrote:
> I have some non-affine cases for which compute_affine_dependence is called 
> (as it is called for 
> ALL dependences from compte_all_depepndences()), and no harm is done.
> I looked a little bit closer into the code, and this is what happens for 
> non affine accesses:
> 
> initialize_data_dependence_relation() assigns 
> DDR_ARE_DEPENDENT (res) = chrec_dont_know for the dr.

It can be chrec_known too (that's actually the only interesting case for us
unless it is a read-read ddr), but you're right that likely
object_address_invariant_in_loop_p should be false.

> Then, compute_affine_depepndence()
> tests if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE), and does nothing 
> otherwise.
> Since the dr was initialized with chrec_dont_know, no harm is done.
> 
> Anyway, since it is useless for your gather case, I'll just remove it, 
> along with compute_self_dependence().
> 
> OK?

Yes, patch preapproved.

	Jakub

Re: [PATCH, take 2] Fix PR tree-optimization/49960 ,Fix self data dependence

[Razya Ladelsky]

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

Jakub Jelinek <jakub@redhat.com> wrote on 21/11/2011 07:25:10 PM:

> From: Jakub Jelinek <jakub@redhat.com>
> To: Razya Ladelsky/Haifa/IBM@IBMIL
> Cc: GCC Patches <gcc-patches@gcc.gnu.org>, Richard Guenther 
> <richard.guenther@gmail.com>
> Date: 21/11/2011 07:25 PM
> Subject: Re: [PATCH, take 2] Fix PR tree-optimization/49960 ,Fix 
> self data dependence
> 
> On Mon, Nov 21, 2011 at 06:56:55PM +0200, Razya Ladelsky wrote:
> > I have some non-affine cases for which compute_affine_dependence is 
called 
> > (as it is called for 
> > ALL dependences from compte_all_depepndences()), and no harm is done.
> > I looked a little bit closer into the code, and this is what happens 
for 
> > non affine accesses:
> > 
> > initialize_data_dependence_relation() assigns 
> > DDR_ARE_DEPENDENT (res) = chrec_dont_know for the dr.
> 
> It can be chrec_known too (that's actually the only interesting case for 
us
> unless it is a read-read ddr), but you're right that likely
> object_address_invariant_in_loop_p should be false.
> 
> > Then, compute_affine_depepndence()
> > tests if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE), and does nothing 
> > otherwise.
> > Since the dr was initialized with chrec_dont_know, no harm is done.
> > 
> > Anyway, since it is useless for your gather case, I'll just remove it, 

> > along with compute_self_dependence().
> > 
> > OK?
> 
> Yes, patch preapproved.
> 
>    Jakub
> 

Hi,

Going to commit this patch today.
I bootstrapped and regtested on  ppc64-suse-linux.

ChangeLog:
 
        * tree-data-ref.c (initialize_data_dependence_relation): Update 
comment for the 
        self dependence case.
        (compute_self_dependence): Remove.
        * tree-vect-data-refs.c (vect_analyze_data_refs): Remove call to 
        compute_self_dependenc. 


Thanks,
Razya


[-- Attachment #2: self_dependence_2.txt --]
[-- Type: text/plain, Size: 1834 bytes --]

Index: tree-data-ref.c
===================================================================
--- tree-data-ref.c	(revision 181675)
+++ tree-data-ref.c	(working copy)
@@ -1385,8 +1385,7 @@ initialize_data_dependence_relation (struct data_r
       return res;
     }
 
-  /* When the references are exactly the same, don't spend time doing
-     the data dependence tests, just initialize the ddr and return.  */
+  /* The case where the references are exactly the same.  */
   if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
     {
      if (loop_nest
@@ -4132,19 +4131,6 @@ compute_affine_dependence (struct data_dependence_
     fprintf (dump_file, ")\n");
 }
 
-/* This computes the dependence relation for the same data
-   reference into DDR.  */
-
-void
-compute_self_dependence (struct data_dependence_relation *ddr)
-{
-  if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
-    return;
-
-  if (DDR_LOOP_NEST (ddr))
-    compute_affine_dependence (ddr, VEC_index (loop_p, DDR_LOOP_NEST (ddr), 0));
-}
-
 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
    the data references in DATAREFS, in the LOOP_NEST.  When
    COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
Index: tree-vect-data-refs.c
===================================================================
--- tree-vect-data-refs.c	(revision 181675)
+++ tree-vect-data-refs.c	(working copy)
@@ -3122,7 +3122,6 @@ vect_analyze_data_refs (loop_vec_info loop_vinfo,
 	  ddr = VEC_index (ddr_p, ddrs, k);
 	  gcc_assert (DDR_A (ddr) == olddr && DDR_B (ddr) == olddr);
 	  newddr = initialize_data_dependence_relation (dr, dr, nest);
-	  compute_self_dependence (newddr);
 	  VEC_replace (ddr_p, ddrs, k, newddr);
 	  free_dependence_relation (ddr);
 	  VEC_replace (data_reference_p, datarefs, i, dr);
=