[PATCH] Fix PR46834: when removing a phi node also remove the dead code using its LHS.

[PATCH] Fix PR46834: when removing a phi node also remove the dead code using its LHS.

[Sebastian Pop]

Hi,

after this patch http://gcc.gnu.org/ml/gcc-cvs/2010-11/msg01074.html

2010-11-26  Michael Matz  <matz@suse.de>

	* tree-ssa-copy.c (fini_copy_prop): Don't DCE when we have loops.

	* passes.c (init_optimization_passes): Remove superfluous
	copy-prop pass.

the code passed to Graphite contains dead code.  This patch removes
the useless assign copies.  This fixes the testcase and all the
testcases that are listed in the description of the bug, that contain
the same pattern.

I am regstraping this on amd64-linux.  Ok for trunk?

Thanks,
Sebastian

2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>

	PR tree-optimization/46834
	* graphite-sese-to-poly.c (remove_phi): When removing a phi node
	also remove the dead code using its LHS.

	* gcc.dg/graphite/id-pr46834.c: New.
---
 gcc/ChangeLog                              |    6 ++++++
 gcc/graphite-sese-to-poly.c                |   17 ++++++++++++-----
 gcc/testsuite/ChangeLog                    |    5 +++++
 gcc/testsuite/gcc.dg/graphite/id-pr46834.c |   12 ++++++++++++
 4 files changed, 35 insertions(+), 5 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/graphite/id-pr46834.c

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index d2dca11..d607ec3 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,11 @@
 2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
 
+	PR tree-optimization/46834
+	* graphite-sese-to-poly.c (remove_phi): When removing a phi node
+	also remove the dead code using its LHS.
+
+2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
+
 	PR tree-optimization/46194
 	* tree-data-ref.c (analyze_miv_subscript): Remove comment.
 	(build_classic_dist_vector_1): Do not represent classic distance
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 11a73b3..323d793 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -2970,24 +2970,31 @@ translate_scalar_reduction_to_array_for_stmt (scop_p scop, tree red,
 static void
 remove_phi (gimple phi)
 {
-  imm_use_iterator imm_iter;
+  imm_use_iterator imm_iter, ii;
   tree def;
-  use_operand_p use_p;
   gimple_stmt_iterator gsi;
   VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
   unsigned int i;
   gimple stmt;
 
   def = PHI_RESULT (phi);
-  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
+  FOR_EACH_IMM_USE_STMT (stmt, imm_iter, def)
     {
-      stmt = USE_STMT (use_p);
-
       if (is_gimple_debug (stmt))
 	{
 	  gimple_debug_bind_reset_value (stmt);
 	  VEC_safe_push (gimple, heap, update, stmt);
 	}
+
+      /* Remove dead code using DEF.  */
+      else if (gimple_assign_ssa_name_copy_p (stmt)
+	       && !first_imm_use_stmt (&ii, gimple_assign_lhs (stmt)))
+	{
+	  mark_virtual_ops_for_renaming (stmt);
+	  gsi = gsi_for_stmt (stmt);
+	  gsi_remove (&gsi, true);
+	  release_defs (stmt);
+	}
     }
 
   FOR_EACH_VEC_ELT (gimple, update, i, stmt)
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index de7301e..1bd4d46 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,10 @@
 2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
 
+	PR tree-optimization/46834
+	* gcc.dg/graphite/id-pr46834.c: New.
+
+2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
+
 	PR tree-optimization/46194
 	* gcc.dg/autopar/pr46194.c: New.
 
diff --git a/gcc/testsuite/gcc.dg/graphite/id-pr46834.c b/gcc/testsuite/gcc.dg/graphite/id-pr46834.c
new file mode 100644
index 0000000..8d89b8e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/id-pr46834.c
@@ -0,0 +1,12 @@
+/* { dg-options "-O -fgraphite-identity -ffast-math -fno-tree-dce" } */
+
+void foo ()
+{
+  int M0[4][4], M3[4] = {};
+  int i=-1;
+  int ii, jj;
+  for (; i; i++)
+      for (jj = 0; jj < 4; jj++)
+	for (ii = 0; ii < 4; ii++)
+	    M3[1] += __builtin_abs (M0[ii][0]);
+}
-- 
1.7.1

[PATCH] Fix PRs 46834, 46994, and 46995: when removing a phi node also remove the dead code using its LHS.

[Sebastian Pop]

Hi,

In fact this patch solves 3 PRs.  Same patch as before, with the other
testcases attached.  Regstrap on amd64-linux in progress.

Sebastian

2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>

	PR tree-optimization/46834
	PR tree-optimization/46994
	PR tree-optimization/46995
	* graphite-sese-to-poly.c (remove_phi): When removing a phi node
	also remove the dead code using its LHS.

	* gcc.dg/graphite/id-pr46834.c: New.
	* gfortran.dg/graphite/id-pr46994.f90: New.
	* gfortran.dg/graphite/id-pr46995.f90: New.
---
 gcc/ChangeLog                                     |    8 ++++++++
 gcc/graphite-sese-to-poly.c                       |   17 ++++++++++++-----
 gcc/testsuite/ChangeLog                           |    9 +++++++++
 gcc/testsuite/gcc.dg/graphite/id-pr46834.c        |   12 ++++++++++++
 gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90 |   14 ++++++++++++++
 gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90 |   16 ++++++++++++++++
 6 files changed, 71 insertions(+), 5 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/graphite/id-pr46834.c
 create mode 100644 gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90
 create mode 100644 gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index d2dca11..ce621d0 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,13 @@
 2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
 
+	PR tree-optimization/46834
+	PR tree-optimization/46994
+	PR tree-optimization/46995
+	* graphite-sese-to-poly.c (remove_phi): When removing a phi node
+	also remove the dead code using its LHS.
+
+2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
+
 	PR tree-optimization/46194
 	* tree-data-ref.c (analyze_miv_subscript): Remove comment.
 	(build_classic_dist_vector_1): Do not represent classic distance
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 11a73b3..323d793 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -2970,24 +2970,31 @@ translate_scalar_reduction_to_array_for_stmt (scop_p scop, tree red,
 static void
 remove_phi (gimple phi)
 {
-  imm_use_iterator imm_iter;
+  imm_use_iterator imm_iter, ii;
   tree def;
-  use_operand_p use_p;
   gimple_stmt_iterator gsi;
   VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
   unsigned int i;
   gimple stmt;
 
   def = PHI_RESULT (phi);
-  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
+  FOR_EACH_IMM_USE_STMT (stmt, imm_iter, def)
     {
-      stmt = USE_STMT (use_p);
-
       if (is_gimple_debug (stmt))
 	{
 	  gimple_debug_bind_reset_value (stmt);
 	  VEC_safe_push (gimple, heap, update, stmt);
 	}
+
+      /* Remove dead code using DEF.  */
+      else if (gimple_assign_ssa_name_copy_p (stmt)
+	       && !first_imm_use_stmt (&ii, gimple_assign_lhs (stmt)))
+	{
+	  mark_virtual_ops_for_renaming (stmt);
+	  gsi = gsi_for_stmt (stmt);
+	  gsi_remove (&gsi, true);
+	  release_defs (stmt);
+	}
     }
 
   FOR_EACH_VEC_ELT (gimple, update, i, stmt)
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index de7301e..086eb3d 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,14 @@
 2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
 
+	PR tree-optimization/46834
+	PR tree-optimization/46994
+	PR tree-optimization/46995
+	* gcc.dg/graphite/id-pr46834.c: New.
+	* gfortran.dg/graphite/id-pr46994.f90: New.
+	* gfortran.dg/graphite/id-pr46995.f90: New.
+
+2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
+
 	PR tree-optimization/46194
 	* gcc.dg/autopar/pr46194.c: New.
 
diff --git a/gcc/testsuite/gcc.dg/graphite/id-pr46834.c b/gcc/testsuite/gcc.dg/graphite/id-pr46834.c
new file mode 100644
index 0000000..8d89b8e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/id-pr46834.c
@@ -0,0 +1,12 @@
+/* { dg-options "-O -fgraphite-identity -ffast-math -fno-tree-dce" } */
+
+void foo ()
+{
+  int M0[4][4], M3[4] = {};
+  int i=-1;
+  int ii, jj;
+  for (; i; i++)
+      for (jj = 0; jj < 4; jj++)
+	for (ii = 0; ii < 4; ii++)
+	    M3[1] += __builtin_abs (M0[ii][0]);
+}
diff --git a/gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90 b/gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90
new file mode 100644
index 0000000..3228b02
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90
@@ -0,0 +1,14 @@
+! { dg-options "-O -ffast-math -fgraphite-identity -fno-tree-dce" }
+
+subroutine foo (m)
+  integer :: m, i, j, k
+  real :: s
+  s = 0
+  do i = 1, 9
+    do j = 1, 2*m
+      do k = 1, 2*m
+        s = s + 1
+      end do 
+    end do 
+  end do 
+end subroutine foo
diff --git a/gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90 b/gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90
new file mode 100644
index 0000000..06cbfd3
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90
@@ -0,0 +1,16 @@
+! { dg-options "-O -ffast-math -fgraphite-identity -fno-tree-dce" }
+
+subroutine foo (m, l, zw)
+  integer :: m, i, j, k
+  real, dimension(1:9) :: zw
+  real :: l, s
+  s = 0
+  do i = 1, 9
+    do j = 1, 2*m
+      do k = 1, 2*m
+        s = s + 1
+      end do
+    end do
+    l = l + zw(i)*s
+  end do
+end subroutine foo
-- 
1.7.1

Re: [PATCH] Fix PR46834: when removing a phi node also remove the dead code using its LHS.

[Richard Guenther]

On Fri, Feb 4, 2011 at 8:12 AM, Sebastian Pop <sebpop@gmail.com> wrote:
> Hi,
>
> after this patch http://gcc.gnu.org/ml/gcc-cvs/2010-11/msg01074.html
>
> 2010-11-26  Michael Matz  <matz@suse.de>
>
>        * tree-ssa-copy.c (fini_copy_prop): Don't DCE when we have loops.
>
>        * passes.c (init_optimization_passes): Remove superfluous
>        copy-prop pass.
>
> the code passed to Graphite contains dead code.  This patch removes
> the useless assign copies.  This fixes the testcase and all the
> testcases that are listed in the description of the bug, that contain
> the same pattern.
>
> I am regstraping this on amd64-linux.  Ok for trunk?
>
> Thanks,
> Sebastian
>
> 2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
>
>        PR tree-optimization/46834
>        * graphite-sese-to-poly.c (remove_phi): When removing a phi node
>        also remove the dead code using its LHS.
>
>        * gcc.dg/graphite/id-pr46834.c: New.
> ---
>  gcc/ChangeLog                              |    6 ++++++
>  gcc/graphite-sese-to-poly.c                |   17 ++++++++++++-----
>  gcc/testsuite/ChangeLog                    |    5 +++++
>  gcc/testsuite/gcc.dg/graphite/id-pr46834.c |   12 ++++++++++++
>  4 files changed, 35 insertions(+), 5 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/graphite/id-pr46834.c
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index d2dca11..d607ec3 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,5 +1,11 @@
>  2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
>
> +       PR tree-optimization/46834
> +       * graphite-sese-to-poly.c (remove_phi): When removing a phi node
> +       also remove the dead code using its LHS.
> +
> +2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
> +
>        PR tree-optimization/46194
>        * tree-data-ref.c (analyze_miv_subscript): Remove comment.
>        (build_classic_dist_vector_1): Do not represent classic distance
> diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
> index 11a73b3..323d793 100644
> --- a/gcc/graphite-sese-to-poly.c
> +++ b/gcc/graphite-sese-to-poly.c
> @@ -2970,24 +2970,31 @@ translate_scalar_reduction_to_array_for_stmt (scop_p scop, tree red,
>  static void
>  remove_phi (gimple phi)
>  {
> -  imm_use_iterator imm_iter;
> +  imm_use_iterator imm_iter, ii;
>   tree def;
> -  use_operand_p use_p;
>   gimple_stmt_iterator gsi;
>   VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
>   unsigned int i;
>   gimple stmt;
>
>   def = PHI_RESULT (phi);
> -  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
> +  FOR_EACH_IMM_USE_STMT (stmt, imm_iter, def)
>     {
> -      stmt = USE_STMT (use_p);
> -
>       if (is_gimple_debug (stmt))
>        {
>          gimple_debug_bind_reset_value (stmt);
>          VEC_safe_push (gimple, heap, update, stmt);
>        }
> +
> +      /* Remove dead code using DEF.  */
> +      else if (gimple_assign_ssa_name_copy_p (stmt)
> +              && !first_imm_use_stmt (&ii, gimple_assign_lhs (stmt)))
> +       {
> +         mark_virtual_ops_for_renaming (stmt);
> +         gsi = gsi_for_stmt (stmt);
> +         gsi_remove (&gsi, true);
> +         release_defs (stmt);

That's a strange piece of code.  And it just shifts the problem to the
stmts that use the defs you just removed.  Thus, why do we call
remove_phi at all when the PHI clearly isn't tivially dead?

Richard.

> +       }
>     }
>
>   FOR_EACH_VEC_ELT (gimple, update, i, stmt)
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index de7301e..1bd4d46 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,5 +1,10 @@
>  2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
>
> +       PR tree-optimization/46834
> +       * gcc.dg/graphite/id-pr46834.c: New.
> +
> +2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
> +
>        PR tree-optimization/46194
>        * gcc.dg/autopar/pr46194.c: New.
>
> diff --git a/gcc/testsuite/gcc.dg/graphite/id-pr46834.c b/gcc/testsuite/gcc.dg/graphite/id-pr46834.c
> new file mode 100644
> index 0000000..8d89b8e
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/graphite/id-pr46834.c
> @@ -0,0 +1,12 @@
> +/* { dg-options "-O -fgraphite-identity -ffast-math -fno-tree-dce" } */
> +
> +void foo ()
> +{
> +  int M0[4][4], M3[4] = {};
> +  int i=-1;
> +  int ii, jj;
> +  for (; i; i++)
> +      for (jj = 0; jj < 4; jj++)
> +       for (ii = 0; ii < 4; ii++)
> +           M3[1] += __builtin_abs (M0[ii][0]);
> +}
> --
> 1.7.1
>
>

Re: [PATCH] Fix PR46834: when removing a phi node also remove the dead code using its LHS.

[Sebastian Pop]

On Fri, Feb 4, 2011 at 17:19, Richard Guenther
<richard.guenther@gmail.com> wrote:
>> +
>> +      /* Remove dead code using DEF.  */
>> +      else if (gimple_assign_ssa_name_copy_p (stmt)
>> +              && !first_imm_use_stmt (&ii, gimple_assign_lhs (stmt)))
>> +       {
>> +         mark_virtual_ops_for_renaming (stmt);
>> +         gsi = gsi_for_stmt (stmt);
>> +         gsi_remove (&gsi, true);
>> +         release_defs (stmt);
>
> That's a strange piece of code.  And it just shifts the problem to the
> stmts that use the defs you just removed.

This call ensures that there are no other uses of the LHS of stmt:
>> +              && !first_imm_use_stmt (&ii, gimple_assign_lhs (stmt)))

> Thus, why do we call
> remove_phi at all when the PHI clearly isn't tivially dead?

We remove all the phi nodes that are in a reduction chain, for
example we rewrite this loop nest:

sum_0 = 0
loop_1
  sum_1 = phi (sum_0, sum_4)
  loop_2
    sum_2 = phi (sum_1, sum_3)
    sum_3 = sum_2 + x
  end_2
  sum_4 = phi (sum_3)
end_1
sum_5 = phi (sum_4)

into the following one:

A[0] = 0
loop_1
  loop_2
    A[0] = A[0] + x
  end_2
end_1

The detection of the reduction ensures that there are no computations
on the chain other than the reduction statement: sum_3 = sum_2 + x.

Sebastian

Re: [PATCH] Fix PR46834: when removing a phi node also remove the dead code using its LHS.

[Richard Guenther]

On Sat, Feb 5, 2011 at 3:12 AM, Sebastian Pop <sebpop@gmail.com> wrote:
> On Fri, Feb 4, 2011 at 17:19, Richard Guenther
> <richard.guenther@gmail.com> wrote:
>>> +
>>> +      /* Remove dead code using DEF.  */
>>> +      else if (gimple_assign_ssa_name_copy_p (stmt)
>>> +              && !first_imm_use_stmt (&ii, gimple_assign_lhs (stmt)))
>>> +       {
>>> +         mark_virtual_ops_for_renaming (stmt);
>>> +         gsi = gsi_for_stmt (stmt);
>>> +         gsi_remove (&gsi, true);
>>> +         release_defs (stmt);
>>
>> That's a strange piece of code.  And it just shifts the problem to the
>> stmts that use the defs you just removed.
>
> This call ensures that there are no other uses of the LHS of stmt:
>>> +              && !first_imm_use_stmt (&ii, gimple_assign_lhs (stmt)))

There is has_zero_uses ().  What about non-ssa-name-copy stmts?

Instead of mark_virtual_ops_for_renaming you should use unlink_stmt_vdef().

>> Thus, why do we call
>> remove_phi at all when the PHI clearly isn't tivially dead?
>
> We remove all the phi nodes that are in a reduction chain, for
> example we rewrite this loop nest:
>
> sum_0 = 0
> loop_1
>  sum_1 = phi (sum_0, sum_4)
>  loop_2
>    sum_2 = phi (sum_1, sum_3)
>    sum_3 = sum_2 + x
>  end_2
>  sum_4 = phi (sum_3)
> end_1
> sum_5 = phi (sum_4)
>
> into the following one:
>
> A[0] = 0
> loop_1
>  loop_2
>    A[0] = A[0] + x
>  end_2
> end_1
>
> The detection of the reduction ensures that there are no computations
> on the chain other than the reduction statement: sum_3 = sum_2 + x.

It "assumes"?  It should verify that, and fail.  Why do we not simply fail
to handle this reduction with -fno-tree-dce?  I see no particular reason
that graphite can assume the IL is in perfect "assumable" state.  The
analysis should be conservative about the assumptions it makes instead
(and yes, people can expect optimizations to no longer do their job
if they specify flags like -fno-tree-dce).

Richard.

>
> Sebastian
>

Re: [PATCH] Fix PR46834: when removing a phi node also remove the dead code using its LHS.

[Michael Matz]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1076 bytes --]

Hi,

On Sun, 6 Feb 2011, Richard Guenther wrote:

> >>> +      else if (gimple_assign_ssa_name_copy_p (stmt)
> >>> +              && !first_imm_use_stmt (&ii, gimple_assign_lhs (stmt)))
> >>> +       {
> >>> +         mark_virtual_ops_for_renaming (stmt);
> >>> +         gsi = gsi_for_stmt (stmt);
> >>> +         gsi_remove (&gsi, true);
> >>> +         release_defs (stmt);
> >>
> >> That's a strange piece of code.  And it just shifts the problem to the
> >> stmts that use the defs you just removed.
> >
> > This call ensures that there are no other uses of the LHS of stmt:
> >>> +              && !first_imm_use_stmt (&ii, gimple_assign_lhs (stmt)))
> 
> There is has_zero_uses ().  What about non-ssa-name-copy stmts?
> 
> Instead of mark_virtual_ops_for_renaming you should use unlink_stmt_vdef().

Just for completeness: a SSA_NAME copy never has vops.  Not that this 
makes the need for removing dead code for correctness less worrysome.


Ciao,
Michael.

[PATCH] Fix PRs 46834, 46994, and 46995: only rewrite reductions not containing other computations.

[Sebastian Pop]

Hi Richi,

This patch detects when a reduction cycle contains other computations
than the reduction and stops the translation out of SSA for these
reductions.  The patch passed regstrap on amd64-linux.  Ok for trunk?

Thanks,
Sebastian

2011-02-08  Sebastian Pop  <sebastian.pop@amd.com>

	PR tree-optimization/46834
	PR tree-optimization/46994
	PR tree-optimization/46995
	* graphite-sese-to-poly.c (used_outside_reduction): New.
	(detect_commutative_reduction): Call used_outside_reduction.
	(rewrite_commutative_reductions_out_of_ssa_close_phi): Call
	translate_scalar_reduction_to_array only when at least one
	loop-phi/close-phi tuple has been detected.

	* gcc.dg/graphite/id-pr46834.c: New.
	* gfortran.dg/graphite/id-pr46994.f90: New.
	* gfortran.dg/graphite/id-pr46995.f90: New.
---
 gcc/ChangeLog                                     |   11 ++++
 gcc/graphite-sese-to-poly.c                       |   56 ++++++++++++++------
 gcc/testsuite/ChangeLog                           |    9 +++
 gcc/testsuite/gcc.dg/graphite/id-pr46834.c        |   12 +++++
 gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90 |   14 +++++
 gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90 |   16 ++++++
 6 files changed, 101 insertions(+), 17 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/graphite/id-pr46834.c
 create mode 100644 gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90
 create mode 100644 gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 39baf06..6c2f652 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,14 @@
+2011-02-08  Sebastian Pop  <sebastian.pop@amd.com>
+
+	PR tree-optimization/46834
+	PR tree-optimization/46994
+	PR tree-optimization/46995
+	* graphite-sese-to-poly.c (used_outside_reduction): New.
+	(detect_commutative_reduction): Call used_outside_reduction.
+	(rewrite_commutative_reductions_out_of_ssa_close_phi): Call
+	translate_scalar_reduction_to_array only when at least one
+	loop-phi/close-phi tuple has been detected.
+
 2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
 
 	PR tree-optimization/46194
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 11a73b3..064ded3 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -2898,6 +2898,30 @@ initial_value_for_loop_phi (gimple phi)
   return NULL_TREE;
 }
 
+/* Returns true when DEF is used outside the reduction cycle of
+   LOOP_PHI.  */
+
+static bool
+used_outside_reduction (tree def, gimple loop_phi)
+{
+  use_operand_p use_p;
+  imm_use_iterator imm_iter;
+  loop_p loop = loop_containing_stmt (loop_phi);
+
+  /* In LOOP, DEF should be used only in LOOP_PHI.  */
+  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
+    {
+      gimple stmt = USE_STMT (use_p);
+
+      if (stmt != loop_phi
+	  && !is_gimple_debug (stmt)
+	  && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
+	return true;
+    }
+
+  return false;
+}
+
 /* Detect commutative and associative scalar reductions belonging to
    the SCOP starting at the loop closed phi node STMT.  Return the phi
    node of the reduction cycle, or NULL.  */
@@ -2908,8 +2932,8 @@ detect_commutative_reduction (scop_p scop, gimple stmt, VEC (gimple, heap) **in,
 {
   if (scalar_close_phi_node_p (stmt))
     {
-      tree arg = gimple_phi_arg_def (stmt, 0);
-      gimple def, loop_phi;
+      gimple def, loop_phi, phi, close_phi = stmt;
+      tree init, lhs, arg = gimple_phi_arg_def (close_phi, 0);
 
       if (TREE_CODE (arg) != SSA_NAME)
 	return NULL;
@@ -2917,26 +2941,24 @@ detect_commutative_reduction (scop_p scop, gimple stmt, VEC (gimple, heap) **in,
       /* Note that loop close phi nodes should have a single argument
 	 because we translated the representation into a canonical form
 	 before Graphite: see canonicalize_loop_closed_ssa_form.  */
-      gcc_assert (gimple_phi_num_args (stmt) == 1);
+      gcc_assert (gimple_phi_num_args (close_phi) == 1);
 
       def = SSA_NAME_DEF_STMT (arg);
-      if (!stmt_in_sese_p (def, SCOP_REGION (scop)))
+      if (!stmt_in_sese_p (def, SCOP_REGION (scop))
+	  || !(loop_phi = detect_commutative_reduction (scop, def, in, out)))
 	return NULL;
 
-      loop_phi = detect_commutative_reduction (scop, def, in, out);
+      lhs = gimple_phi_result (close_phi);
+      init = initial_value_for_loop_phi (loop_phi);
+      phi = follow_inital_value_to_phi (init, lhs);
 
-      if (loop_phi)
-	{
-	  tree lhs = gimple_phi_result (stmt);
-	  tree init = initial_value_for_loop_phi (loop_phi);
-	  gimple phi = follow_inital_value_to_phi (init, lhs);
-
-	  VEC_safe_push (gimple, heap, *in, loop_phi);
-	  VEC_safe_push (gimple, heap, *out, stmt);
-	  return phi;
-	}
-      else
+      if (phi && (used_outside_reduction (lhs, phi)
+		  || !has_single_use (gimple_phi_result (phi))))
 	return NULL;
+
+      VEC_safe_push (gimple, heap, *in, loop_phi);
+      VEC_safe_push (gimple, heap, *out, close_phi);
+      return phi;
     }
 
   if (gimple_code (stmt) == GIMPLE_ASSIGN)
@@ -3139,7 +3161,7 @@ rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop,
   VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
 
   detect_commutative_reduction (scop, close_phi, &in, &out);
-  res = VEC_length (gimple, in) > 0;
+  res = VEC_length (gimple, in) > 1;
   if (res)
     translate_scalar_reduction_to_array (scop, in, out);
 
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 226fa60..3b6df36 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,12 @@
+2011-02-08  Sebastian Pop  <sebastian.pop@amd.com>
+
+	PR tree-optimization/46834
+	PR tree-optimization/46994
+	PR tree-optimization/46995
+	* gcc.dg/graphite/id-pr46834.c: New.
+	* gfortran.dg/graphite/id-pr46994.f90: New.
+	* gfortran.dg/graphite/id-pr46995.f90: New.
+
 2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
 
 	PR tree-optimization/46194
diff --git a/gcc/testsuite/gcc.dg/graphite/id-pr46834.c b/gcc/testsuite/gcc.dg/graphite/id-pr46834.c
new file mode 100644
index 0000000..8d89b8e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/id-pr46834.c
@@ -0,0 +1,12 @@
+/* { dg-options "-O -fgraphite-identity -ffast-math -fno-tree-dce" } */
+
+void foo ()
+{
+  int M0[4][4], M3[4] = {};
+  int i=-1;
+  int ii, jj;
+  for (; i; i++)
+      for (jj = 0; jj < 4; jj++)
+	for (ii = 0; ii < 4; ii++)
+	    M3[1] += __builtin_abs (M0[ii][0]);
+}
diff --git a/gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90 b/gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90
new file mode 100644
index 0000000..93eff45
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90
@@ -0,0 +1,14 @@
+! { dg-options "-O -ffast-math -fgraphite-identity -fno-tree-dce" }
+
+subroutine foo (m)
+  integer :: m, i, j, k
+  real :: s
+  s = 0
+  do i = 1, 9
+    do j = 1, 2*m
+      do k = 1, 2*m
+        s = s + 1
+      end do
+    end do
+  end do
+end subroutine foo
diff --git a/gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90 b/gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90
new file mode 100644
index 0000000..06cbfd3
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90
@@ -0,0 +1,16 @@
+! { dg-options "-O -ffast-math -fgraphite-identity -fno-tree-dce" }
+
+subroutine foo (m, l, zw)
+  integer :: m, i, j, k
+  real, dimension(1:9) :: zw
+  real :: l, s
+  s = 0
+  do i = 1, 9
+    do j = 1, 2*m
+      do k = 1, 2*m
+        s = s + 1
+      end do
+    end do
+    l = l + zw(i)*s
+  end do
+end subroutine foo
-- 
1.7.1

Re: [PATCH] Fix PRs 46834, 46994, and 46995: only rewrite reductions not containing other computations.

[Richard Guenther]

On Mon, 7 Feb 2011, Sebastian Pop wrote:

> Hi Richi,
> 
> This patch detects when a reduction cycle contains other computations
> than the reduction and stops the translation out of SSA for these
> reductions.  The patch passed regstrap on amd64-linux.  Ok for trunk?

Ok.

Thanks,
Richard.

> Thanks,
> Sebastian
> 
> 2011-02-08  Sebastian Pop  <sebastian.pop@amd.com>
> 
> 	PR tree-optimization/46834
> 	PR tree-optimization/46994
> 	PR tree-optimization/46995
> 	* graphite-sese-to-poly.c (used_outside_reduction): New.
> 	(detect_commutative_reduction): Call used_outside_reduction.
> 	(rewrite_commutative_reductions_out_of_ssa_close_phi): Call
> 	translate_scalar_reduction_to_array only when at least one
> 	loop-phi/close-phi tuple has been detected.
> 
> 	* gcc.dg/graphite/id-pr46834.c: New.
> 	* gfortran.dg/graphite/id-pr46994.f90: New.
> 	* gfortran.dg/graphite/id-pr46995.f90: New.
> ---
>  gcc/ChangeLog                                     |   11 ++++
>  gcc/graphite-sese-to-poly.c                       |   56 ++++++++++++++------
>  gcc/testsuite/ChangeLog                           |    9 +++
>  gcc/testsuite/gcc.dg/graphite/id-pr46834.c        |   12 +++++
>  gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90 |   14 +++++
>  gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90 |   16 ++++++
>  6 files changed, 101 insertions(+), 17 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/graphite/id-pr46834.c
>  create mode 100644 gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90
>  create mode 100644 gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90
> 
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 39baf06..6c2f652 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,14 @@
> +2011-02-08  Sebastian Pop  <sebastian.pop@amd.com>
> +
> +	PR tree-optimization/46834
> +	PR tree-optimization/46994
> +	PR tree-optimization/46995
> +	* graphite-sese-to-poly.c (used_outside_reduction): New.
> +	(detect_commutative_reduction): Call used_outside_reduction.
> +	(rewrite_commutative_reductions_out_of_ssa_close_phi): Call
> +	translate_scalar_reduction_to_array only when at least one
> +	loop-phi/close-phi tuple has been detected.
> +
>  2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
>  
>  	PR tree-optimization/46194
> diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
> index 11a73b3..064ded3 100644
> --- a/gcc/graphite-sese-to-poly.c
> +++ b/gcc/graphite-sese-to-poly.c
> @@ -2898,6 +2898,30 @@ initial_value_for_loop_phi (gimple phi)
>    return NULL_TREE;
>  }
>  
> +/* Returns true when DEF is used outside the reduction cycle of
> +   LOOP_PHI.  */
> +
> +static bool
> +used_outside_reduction (tree def, gimple loop_phi)
> +{
> +  use_operand_p use_p;
> +  imm_use_iterator imm_iter;
> +  loop_p loop = loop_containing_stmt (loop_phi);
> +
> +  /* In LOOP, DEF should be used only in LOOP_PHI.  */
> +  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
> +    {
> +      gimple stmt = USE_STMT (use_p);
> +
> +      if (stmt != loop_phi
> +	  && !is_gimple_debug (stmt)
> +	  && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
> +	return true;
> +    }
> +
> +  return false;
> +}
> +
>  /* Detect commutative and associative scalar reductions belonging to
>     the SCOP starting at the loop closed phi node STMT.  Return the phi
>     node of the reduction cycle, or NULL.  */
> @@ -2908,8 +2932,8 @@ detect_commutative_reduction (scop_p scop, gimple stmt, VEC (gimple, heap) **in,
>  {
>    if (scalar_close_phi_node_p (stmt))
>      {
> -      tree arg = gimple_phi_arg_def (stmt, 0);
> -      gimple def, loop_phi;
> +      gimple def, loop_phi, phi, close_phi = stmt;
> +      tree init, lhs, arg = gimple_phi_arg_def (close_phi, 0);
>  
>        if (TREE_CODE (arg) != SSA_NAME)
>  	return NULL;
> @@ -2917,26 +2941,24 @@ detect_commutative_reduction (scop_p scop, gimple stmt, VEC (gimple, heap) **in,
>        /* Note that loop close phi nodes should have a single argument
>  	 because we translated the representation into a canonical form
>  	 before Graphite: see canonicalize_loop_closed_ssa_form.  */
> -      gcc_assert (gimple_phi_num_args (stmt) == 1);
> +      gcc_assert (gimple_phi_num_args (close_phi) == 1);
>  
>        def = SSA_NAME_DEF_STMT (arg);
> -      if (!stmt_in_sese_p (def, SCOP_REGION (scop)))
> +      if (!stmt_in_sese_p (def, SCOP_REGION (scop))
> +	  || !(loop_phi = detect_commutative_reduction (scop, def, in, out)))
>  	return NULL;
>  
> -      loop_phi = detect_commutative_reduction (scop, def, in, out);
> +      lhs = gimple_phi_result (close_phi);
> +      init = initial_value_for_loop_phi (loop_phi);
> +      phi = follow_inital_value_to_phi (init, lhs);
>  
> -      if (loop_phi)
> -	{
> -	  tree lhs = gimple_phi_result (stmt);
> -	  tree init = initial_value_for_loop_phi (loop_phi);
> -	  gimple phi = follow_inital_value_to_phi (init, lhs);
> -
> -	  VEC_safe_push (gimple, heap, *in, loop_phi);
> -	  VEC_safe_push (gimple, heap, *out, stmt);
> -	  return phi;
> -	}
> -      else
> +      if (phi && (used_outside_reduction (lhs, phi)
> +		  || !has_single_use (gimple_phi_result (phi))))
>  	return NULL;
> +
> +      VEC_safe_push (gimple, heap, *in, loop_phi);
> +      VEC_safe_push (gimple, heap, *out, close_phi);
> +      return phi;
>      }
>  
>    if (gimple_code (stmt) == GIMPLE_ASSIGN)
> @@ -3139,7 +3161,7 @@ rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop,
>    VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
>  
>    detect_commutative_reduction (scop, close_phi, &in, &out);
> -  res = VEC_length (gimple, in) > 0;
> +  res = VEC_length (gimple, in) > 1;
>    if (res)
>      translate_scalar_reduction_to_array (scop, in, out);
>  
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index 226fa60..3b6df36 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,12 @@
> +2011-02-08  Sebastian Pop  <sebastian.pop@amd.com>
> +
> +	PR tree-optimization/46834
> +	PR tree-optimization/46994
> +	PR tree-optimization/46995
> +	* gcc.dg/graphite/id-pr46834.c: New.
> +	* gfortran.dg/graphite/id-pr46994.f90: New.
> +	* gfortran.dg/graphite/id-pr46995.f90: New.
> +
>  2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
>  
>  	PR tree-optimization/46194
> diff --git a/gcc/testsuite/gcc.dg/graphite/id-pr46834.c b/gcc/testsuite/gcc.dg/graphite/id-pr46834.c
> new file mode 100644
> index 0000000..8d89b8e
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/graphite/id-pr46834.c
> @@ -0,0 +1,12 @@
> +/* { dg-options "-O -fgraphite-identity -ffast-math -fno-tree-dce" } */
> +
> +void foo ()
> +{
> +  int M0[4][4], M3[4] = {};
> +  int i=-1;
> +  int ii, jj;
> +  for (; i; i++)
> +      for (jj = 0; jj < 4; jj++)
> +	for (ii = 0; ii < 4; ii++)
> +	    M3[1] += __builtin_abs (M0[ii][0]);
> +}
> diff --git a/gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90 b/gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90
> new file mode 100644
> index 0000000..93eff45
> --- /dev/null
> +++ b/gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90
> @@ -0,0 +1,14 @@
> +! { dg-options "-O -ffast-math -fgraphite-identity -fno-tree-dce" }
> +
> +subroutine foo (m)
> +  integer :: m, i, j, k
> +  real :: s
> +  s = 0
> +  do i = 1, 9
> +    do j = 1, 2*m
> +      do k = 1, 2*m
> +        s = s + 1
> +      end do
> +    end do
> +  end do
> +end subroutine foo
> diff --git a/gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90 b/gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90
> new file mode 100644
> index 0000000..06cbfd3
> --- /dev/null
> +++ b/gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90
> @@ -0,0 +1,16 @@
> +! { dg-options "-O -ffast-math -fgraphite-identity -fno-tree-dce" }
> +
> +subroutine foo (m, l, zw)
> +  integer :: m, i, j, k
> +  real, dimension(1:9) :: zw
> +  real :: l, s
> +  s = 0
> +  do i = 1, 9
> +    do j = 1, 2*m
> +      do k = 1, 2*m
> +        s = s + 1
> +      end do
> +    end do
> +    l = l + zw(i)*s
> +  end do
> +end subroutine foo
> 

-- 
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex