Patchwork : Add static branch predict heuristic of comparing IV to loop_bound variable

login
register
mail settings
Submitter Dehao Chen
Date Jan. 9, 2012, 8:54 a.m.
Message ID <CAO2gOZVFy1FyL-ufU=XK2FcTzWE5Y9kuU8ZsPLxO-bQPmHgPEQ@mail.gmail.com>
Download mbox | patch
Permalink /patch/134974/
State New
Headers show

Comments

Dehao Chen - Jan. 9, 2012, 8:54 a.m.
Hello,

Attached is the updated version of the patch.

Passed the bootstrap and gcc testsuite.

Thanks,
Dehao


On Fri, Dec 30, 2011 at 11:22 AM, Dehao Chen <dehao@google.com> wrote:
> Hello,
>
> This patch add a static branch predict heuristic for the following cases:
>
> for (int i = 0; i < bound; i++) {
>  if (i < bound - 2)
>    computation_1();
>  else
>    computation_2();
> }
>
> In this case, we would predict the branch to be taken because it's
> comparing loop induction variable to loop bound variable.
>
> Tested with bootstrap, and no regression in the gcc testsuite.
>
> Is it ok for mainline?
>
> Thanks,
> Dehao
>
> http://codereview.appspot.com/5504086
>
> gcc/ChangeLog
>
> 2011-12-30  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
>
> gcc/testsuite/ChangeLog
>
> 2011-12-30  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.
>
> Index: gcc/testsuite/gcc.dg/predict-3.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/predict-3.c    (revision 0)
> +++ gcc/testsuite/gcc.dg/predict-3.c    (revision 0)
> @@ -0,0 +1,19 @@
> +/* { 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);
> +    }
> +}
> +
> +/* { dg-final { scan-tree-dump "loop iv compare heuristics"
> "profile_estimate"} } */
> +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
> Index: gcc/testsuite/gcc.dg/predict-1.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/predict-1.c    (revision 0)
> +++ gcc/testsuite/gcc.dg/predict-1.c    (revision 0)
> @@ -0,0 +1,19 @@
> +/* { 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);
> +    }
> +}
> +
> +/* { dg-final { scan-tree-dump "loop iv compare heuristics"
> "profile_estimate"} } */
> +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
> Index: gcc/testsuite/gcc.dg/predict-2.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/predict-2.c    (revision 0)
> +++ gcc/testsuite/gcc.dg/predict-2.c    (revision 0)
> @@ -0,0 +1,19 @@
> +/* { 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 * bound )
> +       global += bar (i);
> +    }
> +}
> +
> +/* { dg-final { scan-tree-dump-not "loop iv compare heuristics"
> "profile_estimate"} } */
> +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
> Index: gcc/predict.c
> ===================================================================
> --- gcc/predict.c       (revision 182738)
> +++ gcc/predict.c       (working copy)
> @@ -946,6 +946,292 @@
>     }
>  }
>
> +/* 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
> +find_qualified_ssa_name (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 (TREE_CODE (t1) == INTEGER_CST)
> +    value = TREE_INT_CST_LOW (t1);
> +  else
> +    return NULL;
> +
> +  if (!t2)
> +    return ret;
> +  else if (TREE_CODE (t2) == INTEGER_CST)
> +    value = TREE_INT_CST_LOW (t2);
> +  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 T does not satisfy IV_COMPARE condition.  */
> +
> +static tree
> +find_ssa_name_in_expr (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 find_qualified_ssa_name (TREE_OPERAND (t, 0), NULL);
> +    case 2:
> +      return find_qualified_ssa_name (TREE_OPERAND (t, 0),
> +                                     TREE_OPERAND (t, 1));
> +    default:
> +      return NULL;
> +    }
> +}
> +
> +/* Return the SSA_NAME in the rhs of assignment STMT.
> +   Return NULL if STMT does not satisfy IV_COMPARE condition.  */
> +
> +static tree
> +find_ssa_name_in_assign_stmt (gimple stmt)
> +{
> +  gcc_assert (is_gimple_assign (stmt));
> +
> +  if (gimple_assign_rhs3 (stmt) != NULL)
> +    return NULL;
> +
> +  return find_qualified_ssa_name (gimple_assign_rhs1 (stmt),
> +                                 gimple_assign_rhs2 (stmt));
> +}
> +
> +/* 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 op0, op1, bound;
> +  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 (op1) != SSA_NAME)
> +    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;
> +      step = TREE_INT_CST_LOW (iv1.step);
> +    }
> +  else
> +    {
> +      bound = iv1.base;
> +      step = TREE_INT_CST_LOW (iv0.step);
> +    }
> +
> +  bound = find_ssa_name_in_expr (bound);
> +  if (!bound)
> +    return false;
> +
> +  *loop_invariant = bound;
> +  *compare_code = code;
> +  *loop_step = step;
> +  return true;
> +}
> +
> +/* Compare two SSA_NAMEs: returns TRUE if T1 and T2 reference
> +   a similar variable.  */
> +
> +static bool
> +is_bound_expr_similar (tree t1, tree t2)
> +{
> +  gimple stmt;
> +  tree ssa_name_1 = NULL;
> +  tree ssa_name_2 = NULL;
> +
> +  gcc_assert (TREE_CODE (t1) == SSA_NAME);
> +  gcc_assert (TREE_CODE (t2) == SSA_NAME);
> +
> +  if (t1 == t2)
> +    return true;
> +
> +  /* 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 = find_ssa_name_in_assign_stmt (stmt);
> +      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 = find_ssa_name_in_assign_stmt (stmt);
> +      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 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,
> +                      enum tree_code loop_bound_code,
> +                      int loop_bound_step)
> +{
> +  gimple stmt;
> +  tree compare_var;
> +  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))
> +    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, TAKEN);
> +      return;
> +    }
> +  else if (compare_code == EQ_EXPR)
> +    {
> +      predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
> +      return;
> +    }
> +
> +  if (!is_bound_expr_similar (loop_bound_var, compare_var))
> +    return;
> +
> +  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, 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, 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, TAKEN);
> +      else if (loop_bound_step < 0
> +              && (compare_code == GT_EXPR
> +                  || compare_code == GE_EXPR))
> +       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
> +      else
> +       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, 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, NOT_TAKEN);
> +}
> +
>  /* Predict edge probabilities by exploiting loop structure.  */
>
>  static void
> @@ -963,6 +1249,11 @@
>       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;
> +      gimple stmt = NULL;
>
>       exits = get_loop_exit_edges (loop);
>       n_exits = VEC_length (edge, exits);
> @@ -1010,6 +1301,24 @@
>        }
>       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);
> +
>       bbs = get_loop_body (loop);
>
>       for (j = 0; j < loop->num_nodes; j++)
> @@ -1071,6 +1380,10 @@
>                    || !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_bound_code,
> +                                  loop_bound_step);
>        }
>
>       /* Free basic blocks from get_loop_body.  */
> Index: gcc/predict.def
> ===================================================================
> --- gcc/predict.def     (revision 182738)
> +++ gcc/predict.def     (working copy)
> @@ -116,3 +116,7 @@
>
>  /* 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, "loop iv compare", PROB_VERY_LIKELY, 0)
Index: gcc/testsuite/gcc.dg/predict-3.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-3.c	(revision 0)
+++ gcc/testsuite/gcc.dg/predict-3.c	(revision 0)
@@ -0,0 +1,19 @@
+/* { 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);
+    }
+}
+
+/* { dg-final { scan-tree-dump "loop iv compare heuristics" "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: gcc/testsuite/gcc.dg/predict-4.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-4.c	(revision 0)
+++ gcc/testsuite/gcc.dg/predict-4.c	(revision 0)
@@ -0,0 +1,19 @@
+/* { 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" "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: gcc/testsuite/gcc.dg/predict-1.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-1.c	(revision 0)
+++ gcc/testsuite/gcc.dg/predict-1.c	(revision 0)
@@ -0,0 +1,19 @@
+/* { 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);
+    }
+}
+
+/* { dg-final { scan-tree-dump "loop iv compare heuristics" "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: gcc/testsuite/gcc.dg/predict-2.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-2.c	(revision 0)
+++ gcc/testsuite/gcc.dg/predict-2.c	(revision 0)
@@ -0,0 +1,19 @@
+/* { 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 * bound )
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-not "loop iv compare heuristics" "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: gcc/predict.c
===================================================================
--- gcc/predict.c	(revision 182738)
+++ gcc/predict.c	(working copy)
@@ -946,6 +946,332 @@
     }
 }
 
+/* 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
+find_qualified_ssa_name (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 (TREE_CODE (t1) == INTEGER_CST && host_integerp (t1, 0))
+    value = tree_low_cst (t1, 0);
+  else
+    return NULL;
+
+  if (!t2)
+    return ret;
+  else if (TREE_CODE (t2) == INTEGER_CST && 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 T does not satisfy IV_COMPARE condition.  */
+
+static tree
+find_ssa_name_in_expr (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 find_qualified_ssa_name (TREE_OPERAND (t, 0), NULL);
+    case 2:
+      return find_qualified_ssa_name (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 = find_ssa_name_in_expr (bound);
+  if (!bound)
+    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 reference
+   a similar variable.  */
+
+static bool
+is_bound_expr_similar (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 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,
+		       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, TAKEN);
+      return;
+    }
+  else if (compare_code == EQ_EXPR)
+    {
+      predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
+      return;
+    }
+
+  if (!is_bound_expr_similar (loop_bound_var, compare_var))
+    return;
+
+  /* If loop bound, base and compare bound are all constents, we can
+     calculate the probability directly.  */
+  if (TREE_CODE (loop_bound_var) == INTEGER_CST
+      && TREE_CODE (compare_var) == INTEGER_CST
+      && TREE_CODE (compare_base) == INTEGER_CST
+      && 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 (loop_count == 0)
+	probability = 0;
+      else if (compare_count > loop_count)
+	probability = 1;
+      else
+	probability = REG_BR_PROB_BASE * compare_count / loop_count;
+      predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
+      return;
+    }
+
+  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, 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, 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, TAKEN);
+      else if (loop_bound_step < 0
+	       && (compare_code == GT_EXPR
+		   || compare_code == GE_EXPR))
+	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
+      else
+	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, 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, NOT_TAKEN);
+}
+ 
 /* Predict edge probabilities by exploiting loop structure.  */
 
 static void
@@ -963,6 +1289,12 @@
       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 +1342,25 @@
 	}
       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 +1422,10 @@
 		    || !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_bound_code,
+				   loop_bound_step);
 	}
 
       /* Free basic blocks from get_loop_body.  */
Index: gcc/predict.def
===================================================================
--- gcc/predict.def	(revision 182738)
+++ gcc/predict.def	(working copy)
@@ -116,3 +116,7 @@
 
 /* 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, "loop iv compare", PROB_VERY_LIKELY, 0)

Patch

Index: gcc/testsuite/gcc.dg/predict-3.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-3.c	(revision 0)
+++ gcc/testsuite/gcc.dg/predict-3.c	(revision 0)
@@ -0,0 +1,19 @@ 
+/* { 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);
+    }
+}
+
+/* { dg-final { scan-tree-dump "loop iv compare heuristics"
"profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: gcc/testsuite/gcc.dg/predict-4.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-4.c	(revision 0)
+++ gcc/testsuite/gcc.dg/predict-4.c	(revision 0)
@@ -0,0 +1,19 @@ 
+/* { 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"
"profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: gcc/testsuite/gcc.dg/predict-1.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-1.c	(revision 0)
+++ gcc/testsuite/gcc.dg/predict-1.c	(revision 0)
@@ -0,0 +1,19 @@ 
+/* { 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);
+    }
+}
+
+/* { dg-final { scan-tree-dump "loop iv compare heuristics"
"profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: gcc/testsuite/gcc.dg/predict-2.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-2.c	(revision 0)
+++ gcc/testsuite/gcc.dg/predict-2.c	(revision 0)
@@ -0,0 +1,19 @@ 
+/* { 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 * bound )
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-not "loop iv compare heuristics"
"profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: gcc/predict.c
===================================================================
--- gcc/predict.c	(revision 182738)
+++ gcc/predict.c	(working copy)
@@ -946,6 +946,332 @@ 
     }
 }

+/* 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
+find_qualified_ssa_name (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 (TREE_CODE (t1) == INTEGER_CST && host_integerp (t1, 0))
+    value = tree_low_cst (t1, 0);
+  else
+    return NULL;
+
+  if (!t2)
+    return ret;
+  else if (TREE_CODE (t2) == INTEGER_CST && 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 T does not satisfy IV_COMPARE condition.  */
+
+static tree
+find_ssa_name_in_expr (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 find_qualified_ssa_name (TREE_OPERAND (t, 0), NULL);
+    case 2:
+      return find_qualified_ssa_name (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 = find_ssa_name_in_expr (bound);
+  if (!bound)
+    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 reference
+   a similar variable.  */
+
+static bool
+is_bound_expr_similar (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 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,
+		       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, TAKEN);
+      return;
+    }
+  else if (compare_code == EQ_EXPR)
+    {
+      predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
+      return;
+    }
+
+  if (!is_bound_expr_similar (loop_bound_var, compare_var))
+    return;
+
+  /* If loop bound, base and compare bound are all constents, we can
+     calculate the probability directly.  */
+  if (TREE_CODE (loop_bound_var) == INTEGER_CST
+      && TREE_CODE (compare_var) == INTEGER_CST
+      && TREE_CODE (compare_base) == INTEGER_CST
+      && 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 (loop_count == 0)
+	probability = 0;
+      else if (compare_count > loop_count)
+	probability = 1;
+      else
+	probability = REG_BR_PROB_BASE * compare_count / loop_count;
+      predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
+      return;
+    }
+
+  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, 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, 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, TAKEN);
+      else if (loop_bound_step < 0
+	       && (compare_code == GT_EXPR
+		   || compare_code == GE_EXPR))
+	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
+      else
+	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, 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, NOT_TAKEN);
+}
+
 /* Predict edge probabilities by exploiting loop structure.  */

 static void
@@ -963,6 +1289,12 @@ 
       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 +1342,25 @@ 
 	}
       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 +1422,10 @@ 
 		    || !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_bound_code,
+				   loop_bound_step);
 	}

       /* Free basic blocks from get_loop_body.  */
Index: gcc/predict.def
===================================================================
--- gcc/predict.def	(revision 182738)
+++ gcc/predict.def	(working copy)
@@ -116,3 +116,7 @@ 

 /* 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, "loop iv compare", PROB_VERY_LIKELY, 0)