re PR tree-optimization/29581 (Latent bug in 4.1/4.2/4.3 lambda-code.c)

	PR tree-optimization/29581
	* lambda-code.c (replace_uses_equiv_to_x_with_y): Add YINIT,
	REPLACEMENTS, FIRSTBSI arguments.  If initial condition or
	type is different between Y and USE, create a temporary
	variable, initialize it at the beginning of the body bb
	and use it as replacement instead of Y.

	* gcc.dg/pr29581-1.c: New test.
	* gcc.dg/pr29581-2.c: New test.
	* gcc.dg/pr29581-3.c: New test.
	* gcc.dg/pr29581-4.c: New test.
	* gfortran.dg/pr29581.f90: New test.

From-SVN: r118848

8 files changed, 323 insertions, 14 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index ff482fb..1675c70 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,12 @@
+2006-11-15  Jakub Jelinek  <jakub@redhat.com>
+
+	PR tree-optimization/29581
+	* lambda-code.c (replace_uses_equiv_to_x_with_y): Add YINIT,
+	REPLACEMENTS, FIRSTBSI arguments.  If initial condition or
+	type is different between Y and USE, create a temporary
+	variable, initialize it at the beginning of the body bb
+	and use it as replacement instead of Y.
+
 2006-11-15  Paolo Bonzini  <bonzini@gnu.org>
 
 	PR middle-end/29753
diff --git a/gcc/lambda-code.c b/gcc/lambda-code.c
index 3dfad91..14a1ba3 100644
--- a/gcc/lambda-code.c
+++ b/gcc/lambda-code.c
@@ -2104,11 +2104,17 @@ perfect_nest_p (struct loop *loop)
   return true;
 }
 
-/* Replace the USES of X in STMT, or uses with the same step as X  with Y.  */
+/* Replace the USES of X in STMT, or uses with the same step as X with Y.
+   YINIT is the initial value of Y, REPLACEMENTS is a hash table to
+   avoid creating duplicate temporaries and FIRSTBSI is statement
+   iterator where new temporaries should be inserted at the beginning
+   of body basic block.  */
 
 static void
 replace_uses_equiv_to_x_with_y (struct loop *loop, tree stmt, tree x, 
-				int xstep, tree y)
+				int xstep, tree y, tree yinit,
+				htab_t replacements,
+				block_stmt_iterator *firstbsi)
 {
   ssa_op_iter iter;
   use_operand_p use_p;
@@ -2117,17 +2123,83 @@ replace_uses_equiv_to_x_with_y (struct loop *loop, tree stmt, tree x,
     {
       tree use = USE_FROM_PTR (use_p);
       tree step = NULL_TREE;
-      tree scev = instantiate_parameters (loop,
-					  analyze_scalar_evolution (loop, use));
+      tree scev, init, val, var, setstmt;
+      struct tree_map *h, in;
+      void **loc;
 
-      if (scev != NULL_TREE && scev != chrec_dont_know)
-	step = evolution_part_in_loop_num (scev, loop->num);
+      /* Replace uses of X with Y right away.  */
+      if (use == x)
+	{
+	  SET_USE (use_p, y);
+	  continue;
+	}
+
+      scev = instantiate_parameters (loop,
+				     analyze_scalar_evolution (loop, use));
+
+      if (scev == NULL || scev == chrec_dont_know)
+	continue;
+
+      step = evolution_part_in_loop_num (scev, loop->num);
+      if (step == NULL
+	  || step == chrec_dont_know
+	  || TREE_CODE (step) != INTEGER_CST
+	  || int_cst_value (step) != xstep)
+	continue;
+
+      /* Use REPLACEMENTS hash table to cache already created
+	 temporaries.  */
+      in.hash = htab_hash_pointer (use);
+      in.from = use;
+      h = htab_find_with_hash (replacements, &in, in.hash);
+      if (h != NULL)
+	{
+	  SET_USE (use_p, h->to);
+	  continue;
+	}
 
-      if ((step && step != chrec_dont_know 
-	   && TREE_CODE (step) == INTEGER_CST
-	   && int_cst_value (step) == xstep)
-	  || USE_FROM_PTR (use_p) == x)
-	SET_USE (use_p, y);
+      /* USE which has the same step as X should be replaced
+	 with a temporary set to Y + YINIT - INIT.  */
+      init = initial_condition_in_loop_num (scev, loop->num);
+      gcc_assert (init != NULL && init != chrec_dont_know);
+      if (TREE_TYPE (use) == TREE_TYPE (y))
+	{
+	  val = fold_build2 (MINUS_EXPR, TREE_TYPE (y), init, yinit);
+	  val = fold_build2 (PLUS_EXPR, TREE_TYPE (y), y, val);
+	  if (val == y)
+ 	    {
+	      /* If X has the same type as USE, the same step
+		 and same initial value, it can be replaced by Y.  */
+	      SET_USE (use_p, y);
+	      continue;
+	    }
+	}
+      else
+	{
+	  val = fold_build2 (MINUS_EXPR, TREE_TYPE (y), y, yinit);
+	  val = fold_convert (TREE_TYPE (use), val);
+	  val = fold_build2 (PLUS_EXPR, TREE_TYPE (use), val, init);
+	}
+
+      /* Create a temporary variable and insert it at the beginning
+	 of the loop body basic block, right after the PHI node
+	 which sets Y.  */
+      var = create_tmp_var (TREE_TYPE (use), "perfecttmp");
+      add_referenced_var (var);
+      val = force_gimple_operand_bsi (firstbsi, val, false, NULL);
+      setstmt = build2 (MODIFY_EXPR, void_type_node, var, val);
+      var = make_ssa_name (var, setstmt);
+      TREE_OPERAND (setstmt, 0) = var;
+      bsi_insert_before (firstbsi, setstmt, BSI_SAME_STMT);
+      update_stmt (setstmt);
+      SET_USE (use_p, var);
+      h = ggc_alloc (sizeof (struct tree_map));
+      h->hash = in.hash;
+      h->from = use;
+      h->to = var;
+      loc = htab_find_slot_with_hash (replacements, h, in.hash, INSERT);
+      gcc_assert ((*(struct tree_map **)loc) == NULL);
+      *(struct tree_map **) loc = h;
     }
 }
 
@@ -2379,7 +2451,7 @@ perfect_nestify (struct loops *loops,
   tree then_label, else_label, cond_stmt;
   basic_block preheaderbb, headerbb, bodybb, latchbb, olddest;
   int i;
-  block_stmt_iterator bsi;
+  block_stmt_iterator bsi, firstbsi;
   bool insert_after;
   edge e;
   struct loop *newloop;
@@ -2388,7 +2460,8 @@ perfect_nestify (struct loops *loops,
   tree stmt;
   tree oldivvar, ivvar, ivvarinced;
   VEC(tree,heap) *phis = NULL;
-  
+  htab_t replacements = NULL;
+
   /* Create the new loop.  */
   olddest = loop->single_exit->dest;
   preheaderbb = loop_split_edge_with (loop->single_exit, NULL);
@@ -2484,10 +2557,13 @@ perfect_nestify (struct loops *loops,
 					    uboundvar,
 					    ivvarinced);
   update_stmt (exit_condition);
+  replacements = htab_create_ggc (20, tree_map_hash,
+				  tree_map_eq, NULL);
   bbs = get_loop_body_in_dom_order (loop); 
   /* Now move the statements, and replace the induction variable in the moved
      statements with the correct loop induction variable.  */
   oldivvar = VEC_index (tree, loopivs, 0);
+  firstbsi = bsi_start (bodybb);
   for (i = loop->num_nodes - 1; i >= 0 ; i--)
     {
       block_stmt_iterator tobsi = bsi_last (bodybb);
@@ -2543,7 +2619,8 @@ perfect_nestify (struct loops *loops,
 		    }
 		  
 		  replace_uses_equiv_to_x_with_y 
-		    (loop, stmt, oldivvar, VEC_index (int, steps, 0), ivvar);
+		    (loop, stmt, oldivvar, VEC_index (int, steps, 0), ivvar,
+		     VEC_index (tree, lbounds, 0), replacements, &firstbsi);
 
 		  bsi_move_before (&bsi, &tobsi);
 		  
@@ -2559,6 +2636,7 @@ perfect_nestify (struct loops *loops,
     }
 
   free (bbs);
+  htab_delete (replacements);
   return perfect_nest_p (loop);
 }
 
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 73486b1..a53e25c 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,12 @@
+2006-11-15  Jakub Jelinek  <jakub@redhat.com>
+
+	PR tree-optimization/29581
+	* gcc.dg/pr29581-1.c: New test.
+	* gcc.dg/pr29581-2.c: New test.
+	* gcc.dg/pr29581-3.c: New test.
+	* gcc.dg/pr29581-4.c: New test.
+	* gfortran.dg/pr29581.f90: New test.
+
 2006-11-14  Brooks Moses  <brooks.moses@codesourcery.com>
 
 	PR fortran/29702
diff --git a/gcc/testsuite/gcc.dg/pr29581-1.c b/gcc/testsuite/gcc.dg/pr29581-1.c
new file mode 100644
index 0000000..e540073
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr29581-1.c
@@ -0,0 +1,44 @@
+/* PR tree-optimization/29581 */
+/* Origin: gcc.dg/vect/vect-85.c */
+/* { dg-do run } */
+/* { dg-options "-O2 -ftree-loop-linear" } */
+
+extern void abort (void);
+
+#define N 16
+
+int main1 (int *a)
+{
+  int i, j, k;
+  int b[N];
+
+  for (i = 0; i < N; i++)
+    {
+      for (j = 0; j < N; j++)
+	{
+	  k = i + N;
+	  a[j] = k;
+	}
+      b[i] = k;
+    }
+
+
+  for (j = 0; j < N; j++)
+    if (a[j] != i + N - 1)
+      abort();	
+
+  for (j = 0; j < N; j++)
+    if (b[j] != j + N)
+      abort();	
+
+  return 0;
+}
+
+int main (void)
+{
+  int a[N] __attribute__ ((__aligned__(16)));
+
+  main1 (a);
+
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/pr29581-2.c b/gcc/testsuite/gcc.dg/pr29581-2.c
new file mode 100644
index 0000000..c99d78c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr29581-2.c
@@ -0,0 +1,46 @@
+/* PR tree-optimization/29581 */
+/* Origin: gcc.dg/vect/vect-86.c */
+/* { dg-do run } */
+/* { dg-options "-O2 -ftree-loop-linear" } */
+
+extern void abort (void);
+
+#define N 16
+
+int main1 (int n)
+{
+  int i, j, k;
+  int a[N], b[N];
+
+  for (i = 0; i < n; i++)
+    {
+      for (j = 0; j < n; j++)
+	{
+	  k = i + n;
+	  a[j] = k;
+	}
+      b[i] = k;
+    }
+
+
+  for (j = 0; j < n; j++)
+    if (a[j] != i + n - 1)
+      abort();	
+
+  for (i = 0; i < n; i++)
+    if (b[i] != i + n)
+      abort();	
+
+  return 0;
+}
+
+int main (void)
+{
+  main1 (N);
+  main1 (0);
+  main1 (1);
+  main1 (2);
+  main1 (N-1);
+
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/pr29581-3.c b/gcc/testsuite/gcc.dg/pr29581-3.c
new file mode 100644
index 0000000..c9d72ce
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr29581-3.c
@@ -0,0 +1,48 @@
+/* PR tree-optimization/29581 */
+/* Origin: gcc.dg/vect/vect-87.c */
+/* { dg-do run } */
+/* { dg-options "-O2 -ftree-loop-linear" } */
+
+extern void abort (void);
+
+#define N 16
+
+int main1 (int n, int *a)
+{
+  int i, j, k;
+  int b[N];
+
+  for (i = 0; i < n; i++)
+    {
+      for (j = 0; j < n; j++)
+	{
+	  k = i + n;
+	  a[j] = k;
+	}
+      b[i] = k;
+    }
+
+
+  for (j = 0; j < n; j++)
+    if (a[j] != i + n - 1)
+      abort();	
+
+  for (j = 0; j < n; j++)
+    if (b[j] != j + n)
+      abort();	
+
+  return 0;
+}
+
+int main (void)
+{
+  int a[N] __attribute__ ((__aligned__(16)));
+
+  main1 (N, a);
+  main1 (0, a);
+  main1 (1, a);
+  main1 (2, a);
+  main1 (N-1, a);
+
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/pr29581-4.c b/gcc/testsuite/gcc.dg/pr29581-4.c
new file mode 100644
index 0000000..c2d894c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr29581-4.c
@@ -0,0 +1,48 @@
+/* PR tree-optimization/29581 */
+/* Origin: gcc.dg/vect/vect-88.c */
+/* { dg-do run } */
+/* { dg-options "-O2 -ftree-loop-linear" } */
+
+extern void abort (void);
+
+#define N 16
+
+int main1 (int n, int *a)
+{
+  int i, j, k;
+  int b[N];
+
+  for (i = 0; i < n; i++)
+    {
+      for (j = 0; j < n; j++)
+	{
+	  k = i + n;
+	  a[j] = k;
+	}
+      b[i] = k;
+    }
+
+
+  for (j = 0; j < n; j++)
+    if (a[j] != i + n - 1)
+      abort();	
+
+  for (j = 0; j < n; j++)
+    if (b[j] != j + n)
+      abort();	
+
+  return 0;
+}
+
+int main (void)
+{
+  int a[N+1] __attribute__ ((__aligned__(16)));
+
+  main1 (N, a+1);
+  main1 (0, a+1);
+  main1 (1, a+1);
+  main1 (2, a+1);
+  main1 (N-1, a+1);
+
+  return 0;
+}
diff --git a/gcc/testsuite/gfortran.dg/pr29581.f90 b/gcc/testsuite/gfortran.dg/pr29581.f90
new file mode 100644
index 0000000..3e4a39e
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/pr29581.f90
@@ -0,0 +1,27 @@
+! PR tree-optimization/29581
+! { dg-do run }
+! { dg-options "-O2 -ftree-loop-linear" }
+
+      SUBROUTINE FOO (K)
+      INTEGER I, J, K, A(5,5), B
+      COMMON A
+      A(1,1) = 1
+ 10   B = 0
+      DO 30 I = 1, K
+        DO 20 J = 1, K
+          B = B + A(I,J)
+ 20     CONTINUE
+        A(I,I) = A(I,I) * 2
+ 30   CONTINUE
+      IF (B.GE.3) RETURN
+      GO TO 10
+      END SUBROUTINE
+
+      PROGRAM BAR
+        INTEGER A(5,5)
+        COMMON A
+        CALL FOO (2)
+        IF (A(1,1).NE.8) CALL ABORT
+        A(1,1) = 0
+        IF (ANY(A.NE.0)) CALL ABORT
+      END