predict.c (find_qualified_ssa_name): New

2012-05-08  Dehao Chen  <dehao@google.com>
gcc/
	* predict.c (find_qualified_ssa_name): New
	(find_ssa_name_in_expr): New
	(find_ssa_name_in_assign_stmt): New
	(is_comparison_with_loop_invariant_p): New
	(is_bound_expr_similar): New
	(predict_iv_comparison): New
	(predict_loops): Add heuristic for loop-nested branches that compare an
	induction variable to a loop bound variable.
	* predict.def (PRED_LOOP_IV_COMPARE): New macro
testsuite/
	* gcc.dg/predict-1.c: Check if LOOP_IV_COMPARE static predict
	heuristic is working properly.
	* gcc.dg/predict-2.c: Likewise.
	* gcc/dg/predict-3.c: Likewise.
	* gcc/dg/predict-4.c: Likewise.
	* gcc/dg/predict-5.c: Likewise.
	* gcc/dg/predict-6.c: Likewise.

From-SVN: r187277

10 files changed, 706 insertions, 0 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 8a84a90..733e854 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,15 @@
+2012-05-08  Dehao Chen  <dehao@google.com>
+
+	* predict.c (find_qualified_ssa_name): New
+	(find_ssa_name_in_expr): New
+	(find_ssa_name_in_assign_stmt): New
+	(is_comparison_with_loop_invariant_p): New
+	(is_bound_expr_similar): New
+	(predict_iv_comparison): New
+	(predict_loops): Add heuristic for loop-nested branches that compare an
+	induction variable to a loop bound variable.
+	* predict.def (PRED_LOOP_IV_COMPARE): New macro
+
 2012-05-08  Uros Bizjak  <ubizjak@gmail.com>
 
 	* config/i386/i386.c (has_dispatch): Use TARGET_BDVER1 and
diff --git a/gcc/predict.c b/gcc/predict.c
index 8ed2e83..c93586b 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -946,6 +946,355 @@ combine_predictions_for_bb (basic_block bb)
     }
 }
 
+/* Check if T1 and T2 satisfy the IV_COMPARE condition.
+   Return the SSA_NAME if the condition satisfies, NULL otherwise.
+
+   T1 and T2 should be one of the following cases:
+     1. T1 is SSA_NAME, T2 is NULL
+     2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
+     3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4]  */
+
+static tree
+strips_small_constant (tree t1, tree t2)
+{
+  tree ret = NULL;
+  int value = 0;
+
+  if (!t1)
+    return NULL;
+  else if (TREE_CODE (t1) == SSA_NAME)
+    ret = t1;
+  else if (host_integerp (t1, 0))
+    value = tree_low_cst (t1, 0);
+  else
+    return NULL;
+
+  if (!t2)
+    return ret;
+  else if (host_integerp (t2, 0))
+    value = tree_low_cst (t2, 0);
+  else if (TREE_CODE (t2) == SSA_NAME)
+    {
+      if (ret)
+        return NULL;
+      else
+        ret = t2;
+    }
+
+  if (value <= 4 && value >= -4)
+    return ret;
+  else
+    return NULL;
+}
+
+/* Return the SSA_NAME in T or T's operands.
+   Return NULL if SSA_NAME cannot be found.  */
+
+static tree
+get_base_value (tree t)
+{
+  if (TREE_CODE (t) == SSA_NAME)
+    return t;
+
+  if (!BINARY_CLASS_P (t))
+    return NULL;
+
+  switch (TREE_OPERAND_LENGTH (t))
+    {
+    case 1:
+      return strips_small_constant (TREE_OPERAND (t, 0), NULL);
+    case 2:
+      return strips_small_constant (TREE_OPERAND (t, 0),
+				    TREE_OPERAND (t, 1));
+    default:
+      return NULL;
+    }
+}
+
+/* Check the compare STMT in LOOP. If it compares an induction
+   variable to a loop invariant, return true, and save
+   LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
+   Otherwise return false and set LOOP_INVAIANT to NULL.  */
+
+static bool
+is_comparison_with_loop_invariant_p (gimple stmt, struct loop *loop,
+				     tree *loop_invariant,
+				     enum tree_code *compare_code,
+				     int *loop_step,
+				     tree *loop_iv_base)
+{
+  tree op0, op1, bound, base;
+  affine_iv iv0, iv1;
+  enum tree_code code;
+  int step;
+
+  code = gimple_cond_code (stmt);
+  *loop_invariant = NULL;
+
+  switch (code)
+    {
+    case GT_EXPR:
+    case GE_EXPR:
+    case NE_EXPR:
+    case LT_EXPR:
+    case LE_EXPR:
+    case EQ_EXPR:
+      break;
+
+    default:
+      return false;
+    }
+
+  op0 = gimple_cond_lhs (stmt);
+  op1 = gimple_cond_rhs (stmt);
+
+  if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST) 
+       || (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST))
+    return false;
+  if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
+    return false;
+  if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
+    return false;
+  if (TREE_CODE (iv0.step) != INTEGER_CST
+      || TREE_CODE (iv1.step) != INTEGER_CST)
+    return false;
+  if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
+      || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
+    return false;
+
+  if (integer_zerop (iv0.step))
+    {
+      if (code != NE_EXPR && code != EQ_EXPR)
+	code = invert_tree_comparison (code, false);
+      bound = iv0.base;
+      base = iv1.base;
+      if (host_integerp (iv1.step, 0))
+	step = tree_low_cst (iv1.step, 0);
+      else
+	return false;
+    }
+  else
+    {
+      bound = iv1.base;
+      base = iv0.base;
+      if (host_integerp (iv0.step, 0))
+	step = tree_low_cst (iv0.step, 0);  
+      else
+	return false;
+    }
+
+  if (TREE_CODE (bound) != INTEGER_CST)
+    bound = get_base_value (bound);
+  if (!bound)
+    return false;
+  if (TREE_CODE (base) != INTEGER_CST)
+    base = get_base_value (base);
+  if (!base)
+    return false;
+
+  *loop_invariant = bound;
+  *compare_code = code;
+  *loop_step = step;
+  *loop_iv_base = base;
+  return true;
+}
+
+/* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent.  */
+
+static bool
+expr_coherent_p (tree t1, tree t2)
+{
+  gimple stmt;
+  tree ssa_name_1 = NULL;
+  tree ssa_name_2 = NULL;
+
+  gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST);
+  gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST);
+
+  if (t1 == t2)
+    return true;
+
+  if (TREE_CODE (t1) == INTEGER_CST && TREE_CODE (t2) == INTEGER_CST)
+    return true;
+  if (TREE_CODE (t1) == INTEGER_CST || TREE_CODE (t2) == INTEGER_CST)
+    return false;
+
+  /* Check to see if t1 is expressed/defined with t2.  */
+  stmt = SSA_NAME_DEF_STMT (t1);
+  gcc_assert (stmt != NULL);
+  if (is_gimple_assign (stmt))
+    {
+      ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
+      if (ssa_name_1 && ssa_name_1 == t2)
+	return true;
+    }
+
+  /* Check to see if t2 is expressed/defined with t1.  */
+  stmt = SSA_NAME_DEF_STMT (t2);
+  gcc_assert (stmt != NULL);
+  if (is_gimple_assign (stmt))
+    {
+      ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
+      if (ssa_name_2 && ssa_name_2 == t1)
+	return true;
+    }
+
+  /* Compare if t1 and t2's def_stmts are identical.  */
+  if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2)
+    return true;
+  else
+    return false;
+}
+
+/* Predict branch probability of BB when BB contains a branch that compares
+   an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
+   loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
+
+   E.g.
+     for (int i = 0; i < bound; i++) {
+       if (i < bound - 2)
+	 computation_1();
+       else
+	 computation_2();
+     }
+
+  In this loop, we will predict the branch inside the loop to be taken.  */
+
+static void
+predict_iv_comparison (struct loop *loop, basic_block bb,
+		       tree loop_bound_var,
+		       tree loop_iv_base_var,
+		       enum tree_code loop_bound_code,
+		       int loop_bound_step)
+{
+  gimple stmt;
+  tree compare_var, compare_base;
+  enum tree_code compare_code;
+  int compare_step;
+  edge then_edge;
+  edge_iterator ei;
+
+  if (predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
+      || predicted_by_p (bb, PRED_LOOP_ITERATIONS)
+      || predicted_by_p (bb, PRED_LOOP_EXIT))
+    return;
+
+  stmt = last_stmt (bb);
+  if (!stmt || gimple_code (stmt) != GIMPLE_COND)
+    return;
+  if (!is_comparison_with_loop_invariant_p (stmt, loop, &compare_var,
+					    &compare_code,
+					    &compare_step,
+					    &compare_base))
+    return;
+
+  /* Find the taken edge.  */
+  FOR_EACH_EDGE (then_edge, ei, bb->succs)
+    if (then_edge->flags & EDGE_TRUE_VALUE)
+      break;
+
+  /* When comparing an IV to a loop invariant, NE is more likely to be
+     taken while EQ is more likely to be not-taken.  */
+  if (compare_code == NE_EXPR)
+    {
+      predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
+      return;
+    }
+  else if (compare_code == EQ_EXPR)
+    {
+      predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
+      return;
+    }
+
+  if (!expr_coherent_p (loop_iv_base_var, compare_base))
+    return;
+
+  /* If loop bound, base and compare bound are all constants, we can
+     calculate the probability directly.  */
+  if (host_integerp (loop_bound_var, 0)
+      && host_integerp (compare_var, 0)
+      && host_integerp (compare_base, 0))
+    {
+      int probability;
+      HOST_WIDE_INT compare_count;
+      HOST_WIDE_INT loop_bound = tree_low_cst (loop_bound_var, 0);
+      HOST_WIDE_INT compare_bound = tree_low_cst (compare_var, 0);
+      HOST_WIDE_INT base = tree_low_cst (compare_base, 0);
+      HOST_WIDE_INT loop_count = (loop_bound - base) / compare_step;
+
+      if ((compare_step > 0)
+          ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
+	compare_count = (loop_bound - compare_bound) / compare_step;
+      else
+	compare_count = (compare_bound - base) / compare_step;
+
+      if (compare_code == LE_EXPR || compare_code == GE_EXPR)
+	compare_count ++;
+      if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
+	loop_count ++;
+      if (compare_count < 0)
+	compare_count = 0;
+      if (loop_count < 0)
+	loop_count = 0;
+
+      if (loop_count == 0)
+	probability = 0;
+      else if (compare_count > loop_count)
+	probability = REG_BR_PROB_BASE;
+      else
+	probability = (double) REG_BR_PROB_BASE * compare_count / loop_count;
+      predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
+      return;
+    }
+
+  if (expr_coherent_p (loop_bound_var, compare_var))
+    {
+      if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
+	  && (compare_code == LT_EXPR || compare_code == LE_EXPR))
+	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
+      else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
+	       && (compare_code == GT_EXPR || compare_code == GE_EXPR))
+	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
+      else if (loop_bound_code == NE_EXPR)
+	{
+	  /* If the loop backedge condition is "(i != bound)", we do
+	     the comparison based on the step of IV:
+	     * step < 0 : backedge condition is like (i > bound)
+	     * step > 0 : backedge condition is like (i < bound)  */
+	  gcc_assert (loop_bound_step != 0);
+	  if (loop_bound_step > 0
+	      && (compare_code == LT_EXPR
+		  || compare_code == LE_EXPR))
+	    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
+	  else if (loop_bound_step < 0
+		   && (compare_code == GT_EXPR
+		       || compare_code == GE_EXPR))
+	    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
+	  else
+	    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
+	}
+      else
+	/* The branch is predicted not-taken if loop_bound_code is
+	   opposite with compare_code.  */
+	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
+    }
+  else if (expr_coherent_p (loop_iv_base_var, compare_var))
+    {
+      /* For cases like:
+	   for (i = s; i < h; i++)
+	     if (i > s + 2) ....
+	 The branch should be predicted taken.  */
+      if (loop_bound_step > 0
+	  && (compare_code == GT_EXPR || compare_code == GE_EXPR))
+	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
+      else if (loop_bound_step < 0
+	       && (compare_code == LT_EXPR || compare_code == LE_EXPR))
+	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
+      else
+	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
+    }
+}
+ 
 /* Predict edge probabilities by exploiting loop structure.  */
 
 static void
@@ -963,6 +1312,12 @@ predict_loops (void)
       VEC (edge, heap) *exits;
       struct tree_niter_desc niter_desc;
       edge ex;
+      struct nb_iter_bound *nb_iter;
+      enum tree_code loop_bound_code = ERROR_MARK;
+      int loop_bound_step = 0;
+      tree loop_bound_var = NULL;
+      tree loop_iv_base = NULL;
+      gimple stmt = NULL;
 
       exits = get_loop_exit_edges (loop);
       n_exits = VEC_length (edge, exits);
@@ -1010,6 +1365,25 @@ predict_loops (void)
 	}
       VEC_free (edge, heap, exits);
 
+      /* Find information about loop bound variables.  */
+      for (nb_iter = loop->bounds; nb_iter;
+	   nb_iter = nb_iter->next)
+	if (nb_iter->stmt
+	    && gimple_code (nb_iter->stmt) == GIMPLE_COND)
+	  {
+	    stmt = nb_iter->stmt;
+	    break;
+	  }
+      if (!stmt && last_stmt (loop->header)
+	  && gimple_code (last_stmt (loop->header)) == GIMPLE_COND)
+	stmt = last_stmt (loop->header);
+      if (stmt)
+	is_comparison_with_loop_invariant_p (stmt, loop,
+					     &loop_bound_var,
+					     &loop_bound_code,
+					     &loop_bound_step,
+					     &loop_iv_base);
+
       bbs = get_loop_body (loop);
 
       for (j = 0; j < loop->num_nodes; j++)
@@ -1071,6 +1445,10 @@ predict_loops (void)
 		    || !flow_bb_inside_loop_p (loop, e->dest))
 		  predict_edge (e, PRED_LOOP_EXIT, probability);
 	    }
+	  if (loop_bound_var)
+	    predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
+				   loop_bound_code,
+				   loop_bound_step);
 	}
 
       /* Free basic blocks from get_loop_body.  */
diff --git a/gcc/predict.def b/gcc/predict.def
index 4b3e87a..591bb1c 100644
--- a/gcc/predict.def
+++ b/gcc/predict.def
@@ -116,3 +116,13 @@ DEF_PREDICTOR (PRED_NULL_RETURN, "null return", HITRATE (90), 0)
 
 /* Branches to a mudflap bounds check are extremely unlikely.  */
 DEF_PREDICTOR (PRED_MUDFLAP, "mudflap check", PROB_VERY_LIKELY, 0)
+
+/* Branches to compare induction variable to a loop bound is
+   extremely likely.  */
+DEF_PREDICTOR (PRED_LOOP_IV_COMPARE_GUESS, "guess loop iv compare",
+	       PROB_VERY_LIKELY, 0)
+
+/* Use number of loop iterations determined by # of iterations analysis
+   to set probability of branches that compares IV to loop bound variable.  */
+DEF_PREDICTOR (PRED_LOOP_IV_COMPARE, "loop iv compare", PROB_VERY_LIKELY,
+	       PRED_FLAG_FIRST_MATCH)
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 323c652..f9ef02a8 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,13 @@
+2012-05-08  Dehao Chen  <dehao@google.com>
+
+	* gcc.dg/predict-1.c: Check if LOOP_IV_COMPARE static predict
+	heuristic is working properly.
+	* gcc.dg/predict-2.c: Likewise.
+	* gcc/dg/predict-3.c: Likewise.
+	* gcc/dg/predict-4.c: Likewise.
+	* gcc/dg/predict-5.c: Likewise.
+	* gcc/dg/predict-6.c: Likewise.
+
 2012-05-07  Jakub Jelinek  <jakub@redhat.com>
 
 	PR tree-optimization/53239
diff --git a/gcc/testsuite/gcc.dg/predict-1.c b/gcc/testsuite/gcc.dg/predict-1.c
new file mode 100644
index 0000000..e7f4618
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-1.c
@@ -0,0 +1,54 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int bound)
+{
+  int i, ret = 0;
+  for (i = 0; i < bound; i++)
+    {
+      if (i > bound)
+	global += bar (i);
+      if (i >= bound + 2)
+	global += bar (i);
+      if (i > bound - 2)
+	global += bar (i);
+      if (i + 2 > bound)
+	global += bar (i);
+      if (i == 10)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 0.0%" 5 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int bound)
+{
+  int i, ret = 0;
+  for (i = 0; i < bound; i++)
+    {
+      if (i > bound)
+	global += bar (i);
+      if (i >= bound + 2)
+	global += bar (i);
+      if (i > bound - 2)
+	global += bar (i);
+      if (i + 2 > bound)
+	global += bar (i);
+      if (i == 10)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 0.0%" 5 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
diff --git a/gcc/testsuite/gcc.dg/predict-2.c b/gcc/testsuite/gcc.dg/predict-2.c
new file mode 100644
index 0000000..44895b7
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-2.c
@@ -0,0 +1,54 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int base, int bound)
+{
+  int i, ret = 0;
+  for (i = base; i < bound; i++)
+    {
+      if (i > bound * bound)
+	global += bar (i);
+      if (i > bound + 10)
+	global += bar (i);
+      if (i <= bound + 10)
+	global += bar (i);
+      if (i > base + 10)
+	global += bar (i);
+      if (i < base - 10)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-not "loop iv compare heuristics" "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int base, int bound)
+{
+  int i, ret = 0;
+  for (i = base; i < bound; i++)
+    {
+      if (i > bound * bound)
+	global += bar (i);
+      if (i > bound + 10)
+	global += bar (i);
+      if (i <= bound + 10)
+	global += bar (i);
+      if (i > base + 10)
+	global += bar (i);
+      if (i < base - 10)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-not "loop iv compare heuristics" "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
diff --git a/gcc/testsuite/gcc.dg/predict-3.c b/gcc/testsuite/gcc.dg/predict-3.c
new file mode 100644
index 0000000..afaf540
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-3.c
@@ -0,0 +1,50 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int bound)
+{
+  int i, ret = 0;
+  for (i = 0; i <= bound; i++)
+    {
+      if (i < bound - 2)
+	global += bar (i);
+      if (i <= bound)
+	global += bar (i);
+      if (i + 1 < bound)
+	global += bar (i);
+      if (i != bound)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 100.0%" 4 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int bound)
+{
+  int i, ret = 0;
+  for (i = 0; i <= bound; i++)
+    {
+      if (i < bound - 2)
+	global += bar (i);
+      if (i <= bound)
+	global += bar (i);
+      if (i + 1 < bound)
+	global += bar (i);
+      if (i != bound)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 100.0%" 4 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
diff --git a/gcc/testsuite/gcc.dg/predict-4.c b/gcc/testsuite/gcc.dg/predict-4.c
new file mode 100644
index 0000000..f575b98
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-4.c
@@ -0,0 +1,38 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int bound)
+{
+  int i, ret = 0;
+  for (i = 0; i < 10; i++)
+    {
+      if (i < 5)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump "loop iv compare heuristics: 50.0%" "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int bound)
+{
+  int i, ret = 0;
+  for (i = 0; i < 10; i++)
+    {
+      if (i < 5)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump "loop iv compare heuristics: 50.0%" "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
diff --git a/gcc/testsuite/gcc.dg/predict-5.c b/gcc/testsuite/gcc.dg/predict-5.c
new file mode 100644
index 0000000..f6e70d3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-5.c
@@ -0,0 +1,50 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar (int);
+
+void foo (int base, int bound)
+{
+  int i, ret = 0;
+  for (i = base; i <= bound; i++)
+    {
+      if (i > base)
+	global += bar (i);
+      if (i > base + 1)
+	global += bar (i);
+      if (i >= base + 3)
+	global += bar (i);
+      if (i - 2 >= base)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 100.0%" 4 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar (int);
+
+void foo (int base, int bound)
+{
+  int i, ret = 0;
+  for (i = base; i <= bound; i++)
+    {
+      if (i > base)
+	global += bar (i);
+      if (i > base + 1)
+	global += bar (i);
+      if (i >= base + 3)
+	global += bar (i);
+      if (i - 2 >= base)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 100.0%" 4 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
diff --git a/gcc/testsuite/gcc.dg/predict-6.c b/gcc/testsuite/gcc.dg/predict-6.c
new file mode 100644
index 0000000..552fd07
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-6.c
@@ -0,0 +1,50 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar (int);
+
+void foo (int base, int bound)
+{
+  int i, ret = 0;
+  for (i = base; i <= bound; i++)
+    {
+      if (i < base)
+	global += bar (i);
+      if (i < base + 1)
+	global += bar (i);
+      if (i <= base + 3)
+	global += bar (i);
+      if (i - 1 < base)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 0.0%" 4 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar (int);
+
+void foo (int base, int bound)
+{
+  int i, ret = 0;
+  for (i = base; i <= bound; i++)
+    {
+      if (i < base)
+	global += bar (i);
+      if (i < base + 1)
+	global += bar (i);
+      if (i <= base + 3)
+	global += bar (i);
+      if (i - 1 < base)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 0.0%" 4 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */