2012-02-15 Tobias Grosser <grosser@fim.uni-passau.de>

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

diff --git a/gcc/predict.c b/gcc/predict.c
index 29e0e2f..c12b45f 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.


@@ -43,7 +43,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "output.h"
 #include "function.h"
 #include "except.h"
 #include "output.h"
 #include "function.h"
 #include "except.h"

-#include "toplev.h"
+#include "diagnostic-core.h"

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


@@ -77,7 +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 choose_function_section (void);
+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;
 }


@@ -168,6 +168,9 @@ cgraph_maybe_hot_edge_p (struct cgraph_edge *edge)
   if (edge->caller->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED
       || edge->callee->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
     return false;
   if (edge->caller->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED
       || edge->callee->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
     return false;

+  if (edge->caller->frequency > NODE_FREQUENCY_UNLIKELY_EXECUTED
+      && edge->callee->frequency <= NODE_FREQUENCY_EXECUTED_ONCE)
+    return false;

   if (optimize_size)
     return false;
   if (edge->caller->frequency == NODE_FREQUENCY_HOT)
   if (optimize_size)
     return false;
   if (edge->caller->frequency == NODE_FREQUENCY_HOT)


@@ -193,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.  */


@@ -385,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.  */
 


@@ -938,7 +967,7 @@ predict_loops (void)
       exits = get_loop_exit_edges (loop);
       n_exits = VEC_length (edge, exits);
 
       exits = get_loop_exit_edges (loop);
       n_exits = VEC_length (edge, exits);
 

-      for (j = 0; VEC_iterate (edge, exits, j, ex); j++)
+      FOR_EACH_VEC_ELT (edge, exits, j, ex)

        {
          tree niter = NULL;
          HOST_WIDE_INT nitercst;
        {
          tree niter = NULL;
          HOST_WIDE_INT nitercst;


@@ -965,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)


@@ -1161,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;
 


@@ -1176,9 +1206,8 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code, tree op1, bitma
       def = SSA_NAME_DEF_STMT (op0);
 
       /* If we were already here, break the infinite cycle.  */
       def = SSA_NAME_DEF_STMT (op0);
 
       /* If we were already here, break the infinite cycle.  */

-      if (bitmap_bit_p (visited, SSA_NAME_VERSION (op0)))
+      if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))

        return NULL;
        return NULL;

-      bitmap_set_bit (visited, SSA_NAME_VERSION (op0));

 
       if (gimple_code (def) == GIMPLE_PHI)
        {
 
       if (gimple_code (def) == GIMPLE_PHI)
        {


@@ -1227,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;

            }
        }
 
            }
        }
 


@@ -1326,9 +1374,17 @@ strip_predict_hints (void)
                  && gimple_call_num_args (stmt) == 2)
                {
                  var = gimple_call_lhs (stmt);
                  && gimple_call_num_args (stmt) == 2)
                {
                  var = gimple_call_lhs (stmt);

-                 ass_stmt = gimple_build_assign (var, gimple_call_arg (stmt, 0));
-
-                 gsi_replace (&bi, ass_stmt, true);
+                 if (var)
+                   {
+                     ass_stmt
+                       = gimple_build_assign (var, gimple_call_arg (stmt, 0));
+                     gsi_replace (&bi, ass_stmt, true);
+                   }
+                 else
+                   {
+                     gsi_remove (&bi, true);
+                     continue;
+                   }

                }
            }
          gsi_next (&bi);
                }
            }
          gsi_next (&bi);


@@ -1540,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);

       }
 }
 
       }
 }
 


@@ -1771,7 +1827,8 @@ tree_estimate_probability_driver (void)
 static void
 predict_paths_for_bb (basic_block cur, basic_block bb,
                      enum br_predictor pred,
 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;
 {
   edge e;
   edge_iterator ei;


@@ -1783,13 +1840,42 @@ predict_paths_for_bb (basic_block cur, basic_block bb,
     if (e->src->index >= NUM_FIXED_BLOCKS
        && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
     {
     if (e->src->index >= NUM_FIXED_BLOCKS
        && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
     {

+      edge e2;
+      edge_iterator ei2;
+      bool found = false;
+
+      /* 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));
       gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));

-      predict_edge_def (e, pred, taken);
+
+      /* 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))
+           && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb))
+         {
+           found = true;
+           break;
+         }
+
+      /* If there is non-abnormal path leaving e->src, predict edge
+        using predictor.  Otherwise we need to look for paths
+        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 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))
     }
   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
 }
 
 /* Sets branch probabilities according to PREDiction and


@@ -1799,7 +1885,38 @@ static void
 predict_paths_leading_to (basic_block bb, enum br_predictor pred,
                          enum prediction taken)
 {
 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
 }
 \f
 /* This is used to carry information about basic blocks.  It is


@@ -1852,9 +1969,6 @@ propagate_freq (basic_block head, bitmap tovisit)
       edge_iterator ei;
       int count = 0;
 
       edge_iterator ei;
       int count = 0;
 

-       /* The outermost "loop" includes the exit block, which we can not
-         look up via BASIC_BLOCK.  Detect this and use EXIT_BLOCK_PTR
-         directly.  Do the same for the entry block.  */

       bb = BASIC_BLOCK (i);
 
       FOR_EACH_EDGE (e, ei, bb->preds)
       bb = BASIC_BLOCK (i);
 
       FOR_EACH_EDGE (e, ei, bb->preds)


@@ -1869,6 +1983,9 @@ propagate_freq (basic_block head, bitmap tovisit)
                     e->src->index, bb->index);
        }
       BLOCK_INFO (bb)->npredecessors = count;
                     e->src->index, bb->index);
        }
       BLOCK_INFO (bb)->npredecessors = count;

+      /* When function never returns, we will never process exit block.  */
+      if (!count && bb == EXIT_BLOCK_PTR)
+       bb->count = bb->frequency = 0;

     }
 
   memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
     }
 
   memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));


@@ -2149,8 +2266,6 @@ estimate_bb_frequencies (void)
       free_aux_for_edges ();
     }
   compute_function_frequency ();
       free_aux_for_edges ();
     }
   compute_function_frequency ();

-  if (flag_reorder_functions)
-    choose_function_section ();

 }
 
 /* Decide whether function is hot, cold or unlikely executed.  */
 }
 
 /* Decide whether function is hot, cold or unlikely executed.  */


@@ -2158,7 +2273,12 @@ 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_DESTRUCTOR (current_function_decl))
+    node->only_called_at_exit = true;

 
   if (!profile_info || !flag_branch_probabilities)
     {
 
   if (!profile_info || !flag_branch_probabilities)
     {


@@ -2191,35 +2311,6 @@ compute_function_frequency (void)
     }
 }
 
     }
 }
 

-/* Choose appropriate section for the function.  */
-static void
-choose_function_section (void)
-{
-  struct cgraph_node *node = cgraph_node (current_function_decl);
-  if (DECL_SECTION_NAME (current_function_decl)
-      || !targetm.have_named_sections
-      /* Theoretically we can split the gnu.linkonce text section too,
-        but this requires more work as the frequency needs to match
-        for all generated objects so we need to merge the frequency
-        of all instances.  For now just never set frequency for these.  */
-      || DECL_ONE_ONLY (current_function_decl))
-    return;
-
-  /* If we are doing the partitioning optimization, let the optimization
-     choose the correct section into which to put things.  */
-
-  if (flag_reorder_blocks_and_partition)
-    return;
-
-  if (node->frequency == NODE_FREQUENCY_HOT)
-    DECL_SECTION_NAME (current_function_decl) =
-      build_string (strlen (HOT_TEXT_SECTION_NAME), HOT_TEXT_SECTION_NAME);
-  if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
-    DECL_SECTION_NAME (current_function_decl) =
-      build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME),
-                   UNLIKELY_EXECUTED_TEXT_SECTION_NAME);
-}
-

 static bool
 gate_estimate_probability (void)
 {
 static bool
 gate_estimate_probability (void)
 {


@@ -2231,7 +2322,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;
 }


@@ -2246,7 +2337,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 */


@@ -2279,3 +2370,29 @@ struct gimple_opt_pass pass_strip_predict_hints =
   TODO_ggc_collect | TODO_verify_ssa                   /* todo_flags_finish */
  }
 };
   TODO_ggc_collect | TODO_verify_ssa                   /* todo_flags_finish */
  }
 };

+
+/* Rebuild function frequencies.  Passes are in general expected to
+   maintain profile by hand, however in some cases this is not possible:
+   for example when inlining several functions with loops freuqencies might run
+   out of scale and thus needs to be recomputed.  */
+
+void
+rebuild_frequencies (void)
+{
+  timevar_push (TV_REBUILD_FREQUENCIES);
+  if (profile_status == PROFILE_GUESSED)
+    {
+      loop_optimizer_init (0);
+      add_noreturn_fake_exit_edges ();
+      mark_irreducible_loops ();
+      connect_infinite_loops_to_exit ();
+      estimate_bb_frequencies ();
+      remove_fake_exit_edges ();
+      loop_optimizer_finalize ();
+    }
+  else if (profile_status == PROFILE_READ)
+    counts_to_freqs ();
+  else
+    gcc_unreachable ();
+  timevar_pop (TV_REBUILD_FREQUENCIES);
+}