tree-ssa-loop-ivopts.c (extract_cond_operands): Split from find_interesting_uses_cond.

	* tree-ssa-loop-ivopts.c (extract_cond_operands): Split from
	find_interesting_uses_cond.
	(find_interesting_uses_cond): Use extract_cond_operands.
	(rewrite_use_compare): Use extract_cond_operands and
	force_gimple_operand_bsi.  Do not call update_stmt.
	(determine_use_iv_cost_condition): Use extract_cond_operands.
	Return cheaper of using original bound and changing the exit bound.

	* gcc.dg/tree-ssa/loop-22.c: New test.

From-SVN: r120697

4 files changed, 149 insertions, 90 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 205e33b..5c4277d 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,15 @@
 2007-01-11  Zdenek Dvorak <dvorakz@suse.cz>
 
+	* tree-ssa-loop-ivopts.c (extract_cond_operands): Split from
+	find_interesting_uses_cond.
+	(find_interesting_uses_cond): Use extract_cond_operands.
+	(rewrite_use_compare): Use extract_cond_operands and
+	force_gimple_operand_bsi.  Do not call update_stmt.
+	(determine_use_iv_cost_condition): Use extract_cond_operands.
+	Return cheaper of using original bound and changing the exit bound.
+
+2007-01-11  Zdenek Dvorak <dvorakz@suse.cz>
+
 	PR tree-optimization/29516
 	* tree-ssa-address.c (tree_mem_ref_addr, add_to_parts,
 	most_expensive_mult_to_index, addr_to_parts,
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 58164ce..1ad561d 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,9 @@
 2007-01-11  Zdenek Dvorak <dvorakz@suse.cz>
 
+	* gcc.dg/tree-ssa/loop-22.c: New test.
+
+2007-01-11  Zdenek Dvorak <dvorakz@suse.cz>
+
 	PR tree-optimization/29516
 	* gcc.dg/tree-ssa/loop-20.c: New test.
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-22.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-22.c
new file mode 100644
index 0000000..be8cdcc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-22.c
@@ -0,0 +1,17 @@
+/* { dg-options "-O2 -fdump-tree-final_cleanup" } */
+
+int a[100];
+
+void test (int n)
+{
+  int i;
+
+  for (i = 0; i < n; i += 3)
+    a[i] = i;
+}
+
+/* We used to replace the exit test "i < n" by "i != ((n-1)/3) * 3 + 1".  Although
+   correct, this transformation is obviously harmful.  */
+
+/* { dg-final { scan-tree-dump-times "/" 0 "final_cleanup" } } */
+/* { dg-final { cleanup-tree-dump "final_cleanup" } } */
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index b727ef4..65f1b84 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -1183,67 +1183,96 @@ find_interesting_uses_op (struct ivopts_data *data, tree op)
   return use;
 }
 
-/* Checks whether the condition *COND_P in STMT is interesting
-   and if so, records it.  */
-
-static void
-find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
-{
-  tree *op0_p;
-  tree *op1_p;
-  struct iv *iv0 = NULL, *iv1 = NULL, *civ;
-  struct iv const_iv;
-  tree zero = integer_zero_node;
+/* Given a condition *COND_P, checks whether it is a compare of an induction
+   variable and an invariant.  If this is the case, CONTROL_VAR is set
+   to location of the iv, BOUND to the location of the invariant,
+   IV_VAR and IV_BOUND are set to the corresponding induction variable
+   descriptions, and true is returned.  If this is not the case,
+   CONTROL_VAR and BOUND are set to the arguments of the condition and
+   false is returned.  */
 
+static bool
+extract_cond_operands (struct ivopts_data *data, tree *cond_p,
+		       tree **control_var, tree **bound,
+		       struct iv **iv_var, struct iv **iv_bound)
+{
+  /* The nodes returned when COND has just one operand.  Note that you should
+     not modify anything in BOUND or IV_BOUND because of this.  */
+  static struct iv const_iv;
+  static tree zero;
+  tree cond = *cond_p;
+  tree *op0 = &zero, *op1 = &zero, *tmp_op;
+  struct iv *iv0 = &const_iv, *iv1 = &const_iv, *tmp_iv;
+  bool ret = false;
+
+  zero = integer_zero_node;
   const_iv.step = integer_zero_node;
 
-  if (TREE_CODE (*cond_p) != SSA_NAME
-      && !COMPARISON_CLASS_P (*cond_p))
-    return;
-
-  if (TREE_CODE (*cond_p) == SSA_NAME)
+  if (TREE_CODE (cond) == SSA_NAME)
     {
-      op0_p = cond_p;
-      op1_p = &zero;
+      op0 = cond_p;
+      iv0 = get_iv (data, cond);
+      ret = (iv0 && !integer_zerop (iv0->step));
+      goto end;
     }
-  else
+
+  if (!COMPARISON_CLASS_P (cond))
     {
-      op0_p = &TREE_OPERAND (*cond_p, 0);
-      op1_p = &TREE_OPERAND (*cond_p, 1);
+      op0 = cond_p;
+      goto end;
     }
 
-  if (TREE_CODE (*op0_p) == SSA_NAME)
-    iv0 = get_iv (data, *op0_p);
-  else
-    iv0 = &const_iv;
+  op0 = &TREE_OPERAND (cond, 0);
+  op1 = &TREE_OPERAND (cond, 1);
+  if (TREE_CODE (*op0) == SSA_NAME)
+    iv0 = get_iv (data, *op0);
+  if (TREE_CODE (*op1) == SSA_NAME)
+    iv1 = get_iv (data, *op1);
 
-  if (TREE_CODE (*op1_p) == SSA_NAME)
-    iv1 = get_iv (data, *op1_p);
-  else
-    iv1 = &const_iv;
-
-  if (/* When comparing with non-invariant value, we may not do any senseful
-	 induction variable elimination.  */
-      (!iv0 || !iv1)
-      /* Eliminating condition based on two ivs would be nontrivial.
-	 ??? TODO -- it is not really important to handle this case.  */
-      || (!integer_zerop (iv0->step)
-	  && !integer_zerop (iv1->step)))
-    {
-      find_interesting_uses_op (data, *op0_p);
-      find_interesting_uses_op (data, *op1_p);
-      return;
+  /* Exactly one of the compared values must be an iv, and the other one must
+     be an invariant.  */
+  if (!iv0 || !iv1)
+    goto end;
+
+  if (integer_zerop (iv0->step))
+    {
+      /* Control variable may be on the other side.  */
+      tmp_op = op0; op0 = op1; op1 = tmp_op;
+      tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
     }
+  ret = !integer_zerop (iv0->step) && integer_zerop (iv1->step);
+
+end:
+  if (control_var)
+    *control_var = op0;;
+  if (iv_var)
+    *iv_var = iv0;;
+  if (bound)
+    *bound = op1;
+  if (iv_bound)
+    *iv_bound = iv1;
+
+  return ret;
+}
+
+/* Checks whether the condition *COND_P in STMT is interesting
+   and if so, records it.  */
+
+static void
+find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
+{
+  tree *var_p, *bound_p;
+  struct iv *var_iv, *civ;
 
-  if (integer_zerop (iv0->step)
-      && integer_zerop (iv1->step))
+  if (!extract_cond_operands (data, cond_p, &var_p, &bound_p, &var_iv, NULL))
     {
-      /* If both are invariants, this is a work for unswitching.  */
+      find_interesting_uses_op (data, *var_p);
+      find_interesting_uses_op (data, *bound_p);
       return;
     }
 
   civ = XNEW (struct iv);
-  *civ = integer_zerop (iv0->step) ? *iv1: *iv0;
+  *civ = *var_iv;
   record_use (data, cond_p, civ, stmt, USE_COMPARE);
 }
 
@@ -3672,9 +3701,11 @@ static bool
 determine_use_iv_cost_condition (struct ivopts_data *data,
 				 struct iv_use *use, struct iv_cand *cand)
 {
-  tree bound = NULL_TREE, op, cond;
-  bitmap depends_on = NULL;
-  unsigned cost;
+  tree bound = NULL_TREE;
+  struct iv *cmp_iv;
+  bitmap depends_on_elim = NULL, depends_on_express = NULL, depends_on;
+  unsigned elim_cost, express_cost, cost;
+  bool ok;
 
   /* Only consider real candidates.  */
   if (!cand->iv)
@@ -3683,35 +3714,44 @@ determine_use_iv_cost_condition (struct ivopts_data *data,
       return false;
     }
 
+  /* Try iv elimination.  */
   if (may_eliminate_iv (data, use, cand, &bound))
-    {
-      cost = force_var_cost (data, bound, &depends_on);
+    elim_cost = force_var_cost (data, bound, &depends_on_elim);
+  else
+    elim_cost = INFTY;
 
-      set_use_iv_cost (data, use, cand, cost, depends_on, bound);
-      return cost != INFTY;
-    }
+  /* Try expressing the original giv.  If it is compared with an invariant,
+     note that we cannot get rid of it.  */
+  ok = extract_cond_operands (data, use->op_p, NULL, NULL, NULL, &cmp_iv);
+  gcc_assert (ok);
 
-  /* The induction variable elimination failed; just express the original
-     giv.  If it is compared with an invariant, note that we cannot get
-     rid of it.  */
-  cost = get_computation_cost (data, use, cand, false, &depends_on);
+  express_cost = get_computation_cost (data, use, cand, false,
+				       &depends_on_express);
+  fd_ivopts_data = data;
+  walk_tree (&cmp_iv->base, find_depends, &depends_on_express, NULL);
 
-  cond = *use->op_p;
-  if (TREE_CODE (cond) != SSA_NAME)
+  /* Choose the better approach.  */
+  if (elim_cost < express_cost)
     {
-      op = TREE_OPERAND (cond, 0);
-      if (TREE_CODE (op) == SSA_NAME
-	  && !integer_zerop (get_iv (data, op)->step))
-	op = TREE_OPERAND (cond, 1);
-      if (TREE_CODE (op) == SSA_NAME)
-	{
-	  op = get_iv (data, op)->base;
-	  fd_ivopts_data = data;
-	  walk_tree (&op, find_depends, &depends_on, NULL);
-	}
+      cost = elim_cost;
+      depends_on = depends_on_elim;
+      depends_on_elim = NULL;
+    }
+  else
+    {
+      cost = express_cost;
+      depends_on = depends_on_express;
+      depends_on_express = NULL;
+      bound = NULL_TREE;
     }
 
-  set_use_iv_cost (data, use, cand, cost, depends_on, NULL);
+  set_use_iv_cost (data, use, cand, cost, depends_on, bound);
+
+  if (depends_on_elim)
+    BITMAP_FREE (depends_on_elim);
+  if (depends_on_express)
+    BITMAP_FREE (depends_on_express);
+
   return cost != INFTY;
 }
 
@@ -5087,12 +5127,12 @@ static void
 rewrite_use_compare (struct ivopts_data *data,
 		     struct iv_use *use, struct iv_cand *cand)
 {
-  tree comp;
-  tree *op_p, cond, op, stmts, bound;
+  tree comp, *var_p, op, bound;
   block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
   enum tree_code compare;
   struct cost_pair *cp = get_use_iv_cost (data, use, cand);
-  
+  bool ok;
+
   bound = cp->value;
   if (bound)
     {
@@ -5100,15 +5140,10 @@ rewrite_use_compare (struct ivopts_data *data,
       tree var_type = TREE_TYPE (var);
 
       compare = iv_elimination_compare (data, use);
-      bound = fold_convert (var_type, bound);
-      op = force_gimple_operand (unshare_expr (bound), &stmts,
-				 true, NULL_TREE);
-
-      if (stmts)
-	bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
+      bound = unshare_expr (fold_convert (var_type, bound));
+      op = force_gimple_operand_bsi (&bsi, bound, true, NULL_TREE);
 
       *use->op_p = build2 (compare, boolean_type_node, var, op);
-      update_stmt (use->stmt);
       return;
     }
 
@@ -5117,17 +5152,10 @@ rewrite_use_compare (struct ivopts_data *data,
   comp = get_computation (data->current_loop, use, cand);
   gcc_assert (comp != NULL_TREE);
 
-  cond = *use->op_p;
-  op_p = &TREE_OPERAND (cond, 0);
-  if (TREE_CODE (*op_p) != SSA_NAME
-      || integer_zerop (get_iv (data, *op_p)->step))
-    op_p = &TREE_OPERAND (cond, 1);
-
-  op = force_gimple_operand (comp, &stmts, true, SSA_NAME_VAR (*op_p));
-  if (stmts)
-    bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
+  ok = extract_cond_operands (data, use->op_p, &var_p, NULL, NULL, NULL);
+  gcc_assert (ok);
 
-  *op_p = op;
+  *var_p = force_gimple_operand_bsi (&bsi, comp, true, SSA_NAME_VAR (*var_p));
 }
 
 /* Rewrites USE using candidate CAND.  */