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

login
register
mail settings
Submitter Razya Ladelsky
Date Nov. 15, 2011, 10:31 a.m.
Message ID <OFE59B30C0.27072E7A-ONC2257949.0035FEEA-C2257949.0039D985@il.ibm.com>
Download mbox | patch
Permalink /patch/125722/
State New
Headers show

Comments

Razya Ladelsky - Nov. 15, 2011, 10:31 a.m.
> > 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
=
Richard Guenther - Nov. 15, 2011, 5:25 p.m.
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
>
>
Jakub Jelinek - Nov. 21, 2011, 12:57 p.m.
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
Razya Ladelsky - Nov. 21, 2011, 1:50 p.m.
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
>
Jakub Jelinek - Nov. 21, 2011, 1:59 p.m.
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
Razya Ladelsky - Nov. 21, 2011, 2:54 p.m.
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
>
Jakub Jelinek - Nov. 21, 2011, 3:07 p.m.
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
Razya Ladelsky - Nov. 21, 2011, 4:56 p.m.
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
Jakub Jelinek - Nov. 21, 2011, 5:25 p.m.
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

Patch

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