Patchwork Fix PR tree-optimization/49960 ,Fix self data dependence

login
register
mail settings
Submitter Razya Ladelsky
Date Oct. 17, 2011, 6:23 a.m.
Message ID <OF662F6234.DE8C60EA-ONC2257926.0048D53A-C225792C.00231C15@il.ibm.com>
Download mbox | patch
Permalink /patch/120099/
State New
Headers show

Comments

Razya Ladelsky - Oct. 17, 2011, 6:23 a.m.
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.
=
Richard Guenther - Oct. 17, 2011, 7:03 a.m.
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.
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
Richard Guenther - Oct. 21, 2011, 9:06 a.m.
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

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));
       }
 }