Propagate constant values or parametric expressions outside the scop region.

2010-07-22  Sebastian Pop  <sebastian.pop@amd.com>

	* graphite-sese-to-poly.c (propagate_expr_outside_region): New.
	(rewrite_close_phi_out_of_ssa): Propagate constant values or
	parametric expressions outside the scop region.
	(rewrite_cross_bb_scalar_deps): Same.
	* sese.c (rename_uses): Use NULL_TREE instead of NULL for trees.

	* gcc.dg/graphite/run-id-5.c: New.
	* gcc.dg/graphite/run-id-6.c: New.
	* gfortran.dg/graphite/id-21.f: New.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@163157 138bc75d-0d04-0410-961f-82ee72b054a4

8 files changed, 231 insertions, 11 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 15b5acf22b5..aa87d604ef3 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,13 @@
 2010-08-02  Sebastian Pop  <sebastian.pop@amd.com>
 
+	* graphite-sese-to-poly.c (propagate_expr_outside_region): New.
+	(rewrite_close_phi_out_of_ssa): Propagate constant values or
+	parametric expressions outside the scop region.
+	(rewrite_cross_bb_scalar_deps): Same.
+	* sese.c (rename_uses): Use NULL_TREE instead of NULL for trees.
+
+2010-08-02  Sebastian Pop  <sebastian.pop@amd.com>
+
 	* graphite-sese-to-poly.c (rewrite_phi_out_of_ssa): Use
 	SSA_NAME_DEF_STMT only on SSA_NAMEs.
 
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 1ae2bf2163b..0ed18ef8a53 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,17 @@
 2010-07-22  Sebastian Pop  <sebastian.pop@amd.com>
 
+	* graphite-sese-to-poly.c (propagate_expr_outside_region): New.
+	(rewrite_close_phi_out_of_ssa): Propagate constant values or
+	parametric expressions outside the scop region.
+	(rewrite_cross_bb_scalar_deps): Same.
+	* sese.c (rename_uses): Use NULL_TREE instead of NULL for trees.
+
+	* gcc.dg/graphite/run-id-5.c: New.
+	* gcc.dg/graphite/run-id-6.c: New.
+	* gfortran.dg/graphite/id-21.f: New.
+
+2010-07-22  Sebastian Pop  <sebastian.pop@amd.com>
+
 	* graphite-sese-to-poly.c (rewrite_phi_out_of_ssa): Use
 	SSA_NAME_DEF_STMT only on SSA_NAMEs.
 
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 084dd31cf52..574a25b2213 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -2182,6 +2182,45 @@ scalar_close_phi_node_p (gimple phi)
   return (gimple_phi_num_args (phi) == 1);
 }
 
+/* For a definition DEF in REGION, propagates the expression EXPR in
+   all the uses of DEF outside REGION.  */
+
+static void
+propagate_expr_outside_region (tree def, tree expr, sese region)
+{
+  imm_use_iterator imm_iter;
+  gimple use_stmt;
+  gimple_seq stmts;
+  bool replaced_once = false;
+
+  gcc_assert (TREE_CODE (def) == SSA_NAME
+	      && bb_in_sese_p (gimple_bb (SSA_NAME_DEF_STMT (def)), region));
+
+  expr = force_gimple_operand (unshare_expr (expr), &stmts, true,
+			       NULL_TREE);
+
+  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
+    if (!is_gimple_debug (use_stmt)
+	&& !bb_in_sese_p (gimple_bb (use_stmt), region))
+      {
+	ssa_op_iter iter;
+	use_operand_p use_p;
+
+	FOR_EACH_PHI_OR_STMT_USE (use_p, use_stmt, iter, SSA_OP_ALL_USES)
+	  if (operand_equal_p (def, USE_FROM_PTR (use_p), 0)
+	      && (replaced_once = true))
+	    replace_exp (use_p, expr);
+
+	update_stmt (use_stmt);
+      }
+
+  if (replaced_once)
+    {
+      gsi_insert_seq_on_edge (SESE_ENTRY (region), stmts);
+      gsi_commit_edge_inserts ();
+    }
+}
+
 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
    dimension array for it.  */
 
@@ -2201,20 +2240,36 @@ rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi, sese region)
      before Graphite: see canonicalize_loop_closed_ssa_form.  */
   gcc_assert (gimple_phi_num_args (phi) == 1);
 
-  /* If res is scev analyzable, it is safe to ignore the close phi
-     node: it will be code generated in the out of Graphite pass.  */
-  if (scev_analyzable_p (res, region))
-    {
-      gsi_next (psi);
-      return;
-    }
-
   /* The phi node can be a non close phi node, when its argument is
      invariant, or when it is defined in the same loop as the phi node.  */
   if (is_gimple_min_invariant (arg)
       || SSA_NAME_IS_DEFAULT_DEF (arg)
       || gimple_bb (SSA_NAME_DEF_STMT (arg))->loop_father == bb->loop_father)
     stmt = gimple_build_assign (res, arg);
+
+  /* If res is scev analyzable and is not a scalar value, it is safe
+     to ignore the close phi node: it will be code generated in the
+     out of Graphite pass.  */
+  else if (scev_analyzable_p (res, region))
+    {
+      loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (res));
+      tree scev;
+
+      if (!loop_in_sese_p (loop, region))
+	{
+	  loop = loop_containing_stmt (SSA_NAME_DEF_STMT (arg));
+	  scev = scalar_evolution_in_region (region, loop, arg);
+	  scev = compute_overall_effect_of_inner_loop (loop, scev);
+	}
+      else
+	  scev = scalar_evolution_in_region (region, loop, res);
+
+      if (tree_does_not_contain_chrecs (scev))
+	propagate_expr_outside_region (res, scev, region);
+
+      gsi_next (psi);
+      return;
+    }
   else
     {
       tree zero_dim_array = create_zero_dim_array (var, "Close_Phi");
@@ -2428,10 +2483,20 @@ rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi)
       return;
     }
 
-  if (!is_gimple_reg (def)
-      || scev_analyzable_p (def, region))
+  if (!is_gimple_reg (def))
     return;
 
+  if (scev_analyzable_p (def, region))
+    {
+      loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
+      tree scev = scalar_evolution_in_region (region, loop, def);
+
+      if (tree_does_not_contain_chrecs (scev))
+	propagate_expr_outside_region (def, scev, region);
+
+      return;
+    }
+
   def_bb = gimple_bb (stmt);
 
   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
diff --git a/gcc/sese.c b/gcc/sese.c
index 5ac7a2fc5b9..651b8fbc9da 100644
--- a/gcc/sese.c
+++ b/gcc/sese.c
@@ -544,7 +544,7 @@ rename_uses (gimple copy, htab_t rename_map, gimple_stmt_iterator *gsi_tgt,
 
       /* Replace the old_name with the new_expr.  */
       new_expr = force_gimple_operand (unshare_expr (new_expr), &stmts,
-				       true, NULL);
+				       true, NULL_TREE);
       gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
       replace_exp (use_p, new_expr);
       set_rename (rename_map, old_name, new_expr);
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index fe463045de7..d1c803610e1 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,11 @@
 2010-08-02  Sebastian Pop  <sebastian.pop@amd.com>
 
+	* gcc.dg/graphite/run-id-5.c: New.
+	* gcc.dg/graphite/run-id-6.c: New.
+	* gfortran.dg/graphite/id-21.f: New.
+
+2010-08-02  Sebastian Pop  <sebastian.pop@amd.com>
+
 	* gcc.dg/graphite/id-24.c: New.
 
 2010-08-02  Sebastian Pop  <sebastian.pop@amd.com>
diff --git a/gcc/testsuite/gcc.dg/graphite/run-id-5.c b/gcc/testsuite/gcc.dg/graphite/run-id-5.c
new file mode 100644
index 00000000000..9005c43fd47
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/run-id-5.c
@@ -0,0 +1,54 @@
+/* { dg-options "-O2 -ftree-vectorize -fno-vect-cost-model -fno-tree-scev-cprop -fgraphite-identity" } */
+/* { dg-require-effective-target vect_int } */
+
+/* gcc.dg/vect/no-scevccp-outer-22.c was miscompiled by Graphite.
+   Adding it here to always test it with Graphite.  */
+
+#include <stdarg.h>
+
+extern void abort ();
+#define N 40
+
+int a[N];
+
+__attribute__ ((noinline)) int
+foo (int n){
+  int i,j;
+  int sum;
+
+  if (n<=0)
+    return 0;
+
+  /* inner-loop index j used after the inner-loop */
+  for (i = 0; i < N; i++) {
+    sum = 0;
+    for (j = 0; j < n; j+=2) {
+      sum += j;
+    }
+    a[i] = sum + j;
+  }
+}
+
+int main (void)
+{
+  int i,j;
+  int sum;
+
+  for (i=0; i<N; i++)
+    a[i] = i;
+
+  foo (N);
+
+  /* check results:  */
+  for (i=0; i<N; i++)
+    {
+      sum = 0;
+      for (j = 0; j < N; j+=2)
+        sum += j;
+      if (a[i] != sum + j)
+        abort();
+    }
+
+  return 0;
+}
+
diff --git a/gcc/testsuite/gcc.dg/graphite/run-id-6.c b/gcc/testsuite/gcc.dg/graphite/run-id-6.c
new file mode 100644
index 00000000000..dafa7f8bec7
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/run-id-6.c
@@ -0,0 +1,55 @@
+/* { dg-options "-O2 -ftree-vectorize -fno-vect-cost-model -fno-tree-scev-cprop -fgraphite-identity" } */
+/* { dg-require-effective-target vect_int } */
+
+/* gcc.dg/vect/no-scevccp-outer-4.c was miscompiled by Graphite.
+   Adding it here to always test it with Graphite.  */
+
+#include <stdarg.h>
+
+extern void abort ();
+#define N 40
+
+int a[N];
+
+/* induction variable k advances through inner and outer loops.  */
+
+__attribute__ ((noinline)) int
+foo (int n){
+  int i,j,k=0;
+  int sum;
+
+  if (n<=0)
+    return 0;
+
+  for (i = 0; i < N; i++) {
+    sum = 0;
+    for (j = 0; j < n; j+=2) {
+      sum += k++;
+    }
+    a[i] = sum + j;
+  }
+}
+
+int main (void)
+{
+  int i,j,k=0;
+  int sum;
+
+  for (i=0; i<N; i++)
+    a[i] = i;
+
+  foo (N);
+
+    /* check results:  */
+  for (i=0; i<N; i++)
+    {
+      sum = 0;
+      for (j = 0; j < N; j+=2)
+        sum += k++;
+      if (a[i] != sum + j)
+	abort();
+    }
+
+  return 0;
+}
+
diff --git a/gcc/testsuite/gfortran.dg/graphite/id-21.f b/gcc/testsuite/gfortran.dg/graphite/id-21.f
new file mode 100644
index 00000000000..4fa047ed6f2
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/graphite/id-21.f
@@ -0,0 +1,20 @@
+      MODULE LES3D_DATA
+      DOUBLE PRECISION,ALLOCATABLE,DIMENSION(:,:,:) ::
+     >             P, T, H
+      DOUBLE PRECISION,ALLOCATABLE,DIMENSION(:,:,:,:) ::
+     >             HF
+      DOUBLE PRECISION,ALLOCATABLE,DIMENSION(:,:,:,:,:) ::
+     >             Q
+      END MODULE LES3D_DATA
+      USE LES3D_DATA
+      DO K = 1, KMAX - 1
+         DO J = 1, JMAX - 1
+            DO I = 1, I2
+               T(I,J,K) = (EI - HF(I,J,K,1)) / HF(I,J,K,3)
+            ENDDO
+            P(1:I2,J,K) = Q(1:I2,J,K,1,M) * HF(1:I2,J,K,4) * T(1:I2,J,K)
+            IF(ISGSK .EQ. 1) H(1:I2,J,K) =
+     >                   (Q(1:I2,J,K,5,M) + P(1:I2,J,K))
+         END DO
+      ENDDO
+      END