i386.c (legitimize_tls_address): Generate tls_initial_exec_64_sun only when !TARGET_X32.
[gcc.git] / gcc / predict.c
index dbef3595c45060d8902ad09e2c11289c5d07eef2..c93586bd50272ec0d8a0efdaa451118dcb8259eb 100644 (file)
@@ -77,6 +77,7 @@ static sreal real_zero, real_one, real_almost_one, real_br_prob_base,
 static void combine_predictions_for_insn (rtx, basic_block);
 static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
 static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction);
+static void predict_paths_leading_to_edge (edge, enum br_predictor, enum prediction);
 static bool can_predict_insn_p (const_rtx);
 
 /* Information we hold about each branch predictor.
@@ -112,7 +113,7 @@ static const struct predictor_info predictor_info[]= {
 static inline bool
 maybe_hot_frequency_p (int freq)
 {
-  struct cgraph_node *node = cgraph_node (current_function_decl);
+  struct cgraph_node *node = cgraph_get_node (current_function_decl);
   if (!profile_info || !flag_branch_probabilities)
     {
       if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
@@ -123,9 +124,9 @@ maybe_hot_frequency_p (int freq)
   if (profile_status == PROFILE_ABSENT)
     return true;
   if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
-      && freq <= (ENTRY_BLOCK_PTR->frequency * 2 / 3))
+      && freq < (ENTRY_BLOCK_PTR->frequency * 2 / 3))
     return false;
-  if (freq < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
+  if (freq < ENTRY_BLOCK_PTR->frequency / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
     return false;
   return true;
 }
@@ -195,27 +196,44 @@ maybe_hot_edge_p (edge e)
   return maybe_hot_frequency_p (EDGE_FREQUENCY (e));
 }
 
+
 /* Return true in case BB is probably never executed.  */
+
 bool
 probably_never_executed_bb_p (const_basic_block bb)
 {
   if (profile_info && flag_branch_probabilities)
     return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
   if ((!profile_info || !flag_branch_probabilities)
-      && cgraph_node (current_function_decl)->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
+      && (cgraph_get_node (current_function_decl)->frequency
+         == NODE_FREQUENCY_UNLIKELY_EXECUTED))
     return true;
   return false;
 }
 
+/* Return true if NODE should be optimized for size.  */
+
+bool
+cgraph_optimize_for_size_p (struct cgraph_node *node)
+{
+  if (optimize_size)
+    return true;
+  if (node && (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED))
+    return true;
+  else
+    return false;
+}
+
 /* Return true when current function should always be optimized for size.  */
 
 bool
 optimize_function_for_size_p (struct function *fun)
 {
-  return (optimize_size
-         || (fun && fun->decl
-             && (cgraph_node (fun->decl)->frequency
-                 == NODE_FREQUENCY_UNLIKELY_EXECUTED)));
+  if (optimize_size)
+    return true;
+  if (!fun || !fun->decl)
+    return false;
+  return cgraph_optimize_for_size_p (cgraph_get_node (fun->decl));
 }
 
 /* Return true when current function should always be optimized for speed.  */
@@ -387,6 +405,15 @@ rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
 
 static struct pointer_map_t *bb_predictions;
 
+/*  Structure representing predictions in tree level. */
+
+struct edge_prediction {
+    struct edge_prediction *ep_next;
+    edge ep_edge;
+    enum br_predictor ep_predictor;
+    int ep_probability;
+};
+
 /* Return true if the one of outgoing edges is already predicted by
    PREDICTOR.  */
 
@@ -919,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
@@ -936,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);
@@ -967,7 +1349,7 @@ predict_loops (void)
             the loop, use it to predict this exit.  */
          else if (n_exits == 1)
            {
-             nitercst = estimated_loop_iterations_int (loop, false);
+             nitercst = estimated_stmt_executions_int (loop);
              if (nitercst < 0)
                continue;
              if (nitercst > max)
@@ -983,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++)
@@ -1044,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.  */
@@ -1163,7 +1568,8 @@ static tree expr_expected_value (tree, bitmap);
 /* Helper function for expr_expected_value.  */
 
 static tree
-expr_expected_value_1 (tree type, tree op0, enum tree_code code, tree op1, bitmap visited)
+expr_expected_value_1 (tree type, tree op0, enum tree_code code,
+                      tree op1, bitmap visited)
 {
   gimple def;
 
@@ -1228,17 +1634,36 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code, tree op1, bitma
          tree decl = gimple_call_fndecl (def);
          if (!decl)
            return NULL;
-         if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL
-             && DECL_FUNCTION_CODE (decl) == BUILT_IN_EXPECT)
-           {
-             tree val;
+         if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
+           switch (DECL_FUNCTION_CODE (decl))
+             {
+             case BUILT_IN_EXPECT:
+               {
+                 tree val;
+                 if (gimple_call_num_args (def) != 2)
+                   return NULL;
+                 val = gimple_call_arg (def, 0);
+                 if (TREE_CONSTANT (val))
+                   return val;
+                 return gimple_call_arg (def, 1);
+               }
 
-             if (gimple_call_num_args (def) != 2)
-               return NULL;
-             val = gimple_call_arg (def, 0);
-             if (TREE_CONSTANT (val))
-               return val;
-             return gimple_call_arg (def, 1);
+             case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
+             case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
+             case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
+             case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
+             case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
+             case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
+             case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
+             case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
+             case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
+             case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
+             case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
+             case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
+             case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
+               /* Assume that any given atomic operation has low contention,
+                  and thus the compare-and-swap operation succeeds.  */
+               return boolean_true_node;
            }
        }
 
@@ -1549,8 +1974,8 @@ apply_return_prediction (void)
       {
        pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
        if (pred != PRED_NO_PREDICTION)
-         predict_paths_leading_to (gimple_phi_arg_edge (phi, i)->src, pred,
-                                   direction);
+         predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
+                                        direction);
       }
 }
 
@@ -1780,7 +2205,8 @@ tree_estimate_probability_driver (void)
 static void
 predict_paths_for_bb (basic_block cur, basic_block bb,
                      enum br_predictor pred,
-                     enum prediction taken)
+                     enum prediction taken,
+                     bitmap visited)
 {
   edge e;
   edge_iterator ei;
@@ -1796,16 +2222,16 @@ predict_paths_for_bb (basic_block cur, basic_block bb,
       edge_iterator ei2;
       bool found = false;
 
-      /* Ignore abnormals, we predict them as not taken anyway.  */
-      if (e->flags & (EDGE_EH | EDGE_FAKE | EDGE_ABNORMAL))
+      /* Ignore fake edges and eh, we predict them as not taken anyway.  */
+      if (e->flags & (EDGE_EH | EDGE_FAKE))
        continue;
       gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
 
-      /* See if there is how many edge from e->src that is not abnormal
+      /* See if there is an edge from e->src that is not abnormal
         and does not lead to BB.  */
       FOR_EACH_EDGE (e2, ei2, e->src->succs)
        if (e2 != e
-           && !(e2->flags & (EDGE_EH | EDGE_FAKE | EDGE_ABNORMAL))
+           && !(e2->flags & (EDGE_EH | EDGE_FAKE))
            && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb))
          {
            found = true;
@@ -1814,16 +2240,20 @@ predict_paths_for_bb (basic_block cur, basic_block bb,
 
       /* If there is non-abnormal path leaving e->src, predict edge
         using predictor.  Otherwise we need to look for paths
-        leading to e->src.  */
+        leading to e->src.
+
+        The second may lead to infinite loop in the case we are predicitng
+        regions that are only reachable by abnormal edges.  We simply
+        prevent visiting given BB twice.  */
       if (found)
         predict_edge_def (e, pred, taken);
-      else
-       predict_paths_for_bb (e->src, e->src, pred, taken);
+      else if (bitmap_set_bit (visited, e->src->index))
+       predict_paths_for_bb (e->src, e->src, pred, taken, visited);
     }
   for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
        son;
        son = next_dom_son (CDI_POST_DOMINATORS, son))
-    predict_paths_for_bb (son, bb, pred, taken);
+    predict_paths_for_bb (son, bb, pred, taken, visited);
 }
 
 /* Sets branch probabilities according to PREDiction and
@@ -1833,7 +2263,38 @@ static void
 predict_paths_leading_to (basic_block bb, enum br_predictor pred,
                          enum prediction taken)
 {
-  predict_paths_for_bb (bb, bb, pred, taken);
+  bitmap visited = BITMAP_ALLOC (NULL);
+  predict_paths_for_bb (bb, bb, pred, taken, visited);
+  BITMAP_FREE (visited);
+}
+
+/* Like predict_paths_leading_to but take edge instead of basic block.  */
+
+static void
+predict_paths_leading_to_edge (edge e, enum br_predictor pred,
+                              enum prediction taken)
+{
+  bool has_nonloop_edge = false;
+  edge_iterator ei;
+  edge e2;
+
+  basic_block bb = e->src;
+  FOR_EACH_EDGE (e2, ei, bb->succs)
+    if (e2->dest != e->src && e2->dest != e->dest
+       && !(e->flags & (EDGE_EH | EDGE_FAKE))
+       && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
+      {
+       has_nonloop_edge = true;
+       break;
+      }
+  if (!has_nonloop_edge)
+    {
+      bitmap visited = BITMAP_ALLOC (NULL);
+      predict_paths_for_bb (bb, bb, pred, taken, visited);
+      BITMAP_FREE (visited);
+    }
+  else
+    predict_edge_def (e, pred, taken);
 }
 \f
 /* This is used to carry information about basic blocks.  It is
@@ -2190,7 +2651,7 @@ void
 compute_function_frequency (void)
 {
   basic_block bb;
-  struct cgraph_node *node = cgraph_node (current_function_decl);
+  struct cgraph_node *node = cgraph_get_node (current_function_decl);
   if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
       || MAIN_NAME_P (DECL_NAME (current_function_decl)))
     node->only_called_at_startup = true;
@@ -2239,7 +2700,7 @@ tree
 build_predict_expr (enum br_predictor predictor, enum prediction taken)
 {
   tree t = build1 (PREDICT_EXPR, void_type_node,
-                  build_int_cst (NULL, predictor));
+                  build_int_cst (integer_type_node, predictor));
   SET_PREDICT_EXPR_OUTCOME (t, taken);
   return t;
 }
@@ -2254,7 +2715,7 @@ struct gimple_opt_pass pass_profile =
 {
  {
   GIMPLE_PASS,
-  "profile",                           /* name */
+  "profile_estimate",                  /* name */
   gate_estimate_probability,           /* gate */
   tree_estimate_probability_driver,    /* execute */
   NULL,                                        /* sub */