gcc/:

[pf3gnuchains/gcc-fork.git] / gcc / predict.c

diff --git a/gcc/predict.c b/gcc/predict.c
index cb4edcd..9236531 100644 (file)
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -1,5 +1,5 @@
 /* Branch prediction routines for the GNU compiler.
 /* Branch prediction routines for the GNU compiler.

-   Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009
+   Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010

    Free Software Foundation, Inc.
 
 This file is part of GCC.
    Free Software Foundation, Inc.
 
 This file is part of GCC.


@@ -44,7 +44,6 @@ along with GCC; see the file COPYING3.  If not see
 #include "function.h"
 #include "except.h"
 #include "diagnostic-core.h"
 #include "function.h"
 #include "except.h"
 #include "diagnostic-core.h"

-#include "toplev.h"

 #include "recog.h"
 #include "expr.h"
 #include "predict.h"
 #include "recog.h"
 #include "expr.h"
 #include "predict.h"


@@ -78,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 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.
 static bool can_predict_insn_p (const_rtx);
 
 /* Information we hold about each branch predictor.


@@ -113,7 +113,7 @@ static const struct predictor_info predictor_info[]= {
 static inline bool
 maybe_hot_frequency_p (int freq)
 {
 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)
   if (!profile_info || !flag_branch_probabilities)
     {
       if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)


@@ -124,9 +124,9 @@ maybe_hot_frequency_p (int freq)
   if (profile_status == PROFILE_ABSENT)
     return true;
   if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
   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;
     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;
 }
     return false;
   return true;
 }


@@ -196,27 +196,44 @@ maybe_hot_edge_p (edge e)
   return maybe_hot_frequency_p (EDGE_FREQUENCY (e));
 }
 
   return maybe_hot_frequency_p (EDGE_FREQUENCY (e));
 }
 

+

 /* Return true in case BB is probably never executed.  */
 /* 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)
 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;
   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 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.  */
 }
 
 /* Return true when current function should always be optimized for speed.  */


@@ -388,6 +405,15 @@ rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
 
 static struct pointer_map_t *bb_predictions;
 
 
 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.  */
 
 /* Return true if the one of outgoing edges is already predicted by
    PREDICTOR.  */
 


@@ -968,7 +994,7 @@ predict_loops (void)
             the loop, use it to predict this exit.  */
          else if (n_exits == 1)
            {
             the loop, use it to predict this exit.  */
          else if (n_exits == 1)
            {

-             nitercst = estimated_loop_iterations_int (loop, false);
+             nitercst = max_stmt_executions_int (loop, false);

              if (nitercst < 0)
                continue;
              if (nitercst > max)
              if (nitercst < 0)
                continue;
              if (nitercst > max)


@@ -1164,7 +1190,8 @@ static tree expr_expected_value (tree, bitmap);
 /* Helper function for expr_expected_value.  */
 
 static tree
 /* 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;
 
 {
   gimple def;
 


@@ -1229,17 +1256,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;
          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;

            }
        }
 
            }
        }
 


@@ -1550,8 +1596,8 @@ apply_return_prediction (void)
       {
        pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
        if (pred != PRED_NO_PREDICTION)
       {
        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);

       }
 }
 
       }
 }
 


@@ -1797,8 +1843,8 @@ predict_paths_for_bb (basic_block cur, basic_block bb,
       edge_iterator ei2;
       bool found = false;
 
       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));
 
        continue;
       gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
 


@@ -1806,7 +1852,7 @@ predict_paths_for_bb (basic_block cur, basic_block bb,
         and does not lead to BB.  */
       FOR_EACH_EDGE (e2, ei2, e->src->succs)
        if (e2 != e
         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;
            && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb))
          {
            found = true;


@@ -1836,6 +1882,31 @@ predict_paths_leading_to (basic_block bb, enum br_predictor pred,
 {
   predict_paths_for_bb (bb, bb, pred, taken);
 }
 {
   predict_paths_for_bb (bb, bb, pred, taken);
 }

+
+/* 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)
+    predict_paths_for_bb (bb, bb, pred, taken);
+  else
+    predict_edge_def (e, pred, taken);
+}

 \f
 /* This is used to carry information about basic blocks.  It is
    attached to the AUX field of the standard CFG block.  */
 \f
 /* This is used to carry information about basic blocks.  It is
    attached to the AUX field of the standard CFG block.  */


@@ -2191,7 +2262,7 @@ void
 compute_function_frequency (void)
 {
   basic_block bb;
 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;
   if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
       || MAIN_NAME_P (DECL_NAME (current_function_decl)))
     node->only_called_at_startup = true;


@@ -2240,7 +2311,7 @@ tree
 build_predict_expr (enum br_predictor predictor, enum prediction taken)
 {
   tree t = build1 (PREDICT_EXPR, void_type_node,
 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;
 }
   SET_PREDICT_EXPR_OUTCOME (t, taken);
   return t;
 }


@@ -2255,7 +2326,7 @@ struct gimple_opt_pass pass_profile =
 {
  {
   GIMPLE_PASS,
 {
  {
   GIMPLE_PASS,

-  "profile",                           /* name */
+  "profile_estimate",                  /* name */

   gate_estimate_probability,           /* gate */
   tree_estimate_probability_driver,    /* execute */
   NULL,                                        /* sub */
   gate_estimate_probability,           /* gate */
   tree_estimate_probability_driver,    /* execute */
   NULL,                                        /* sub */