[Bug middle-end/38074] [4.4 Regression] missed inlining on Core2 Duo due to apparent wrong branch prediction/profile

["hubicka at ucw dot cz" <gcc-bugzilla@gcc.gnu.org>]

------- Comment #11 from hubicka at ucw dot cz  2008-12-05 17:15 -------
Subject: Re:  [4.4 Regression] missed inlining on Core2 Duo due  to apparent
wrong branch prediction/profile

OK,
so the problem is that all the paths are leading to noreturn, so the
conditional deciding on what noreturn path will be taken is predictor by
same heuristic in both dirrections.
Our first math heuristic blindly picks the first one in row predicting
the "invalid command line parameters" path to be very likely and main
body to be very unlikely.

This patch fixes it in both ways: when all paths are leading to
noreturn, we disable the heuristics and when heuristics is taken
into consideration for first match we first check that it was not
confused and did not predict edge in both ways.

I also fixed nonsence in compute_call_stmt_bb_frequency noticed by
Jakub. To make frequencies at least little bit sane, I simply add 1 to
both values so we still get calls with higher frequency than 0 predicted
as more often.

Honza

        Jan Hubicka  <jh@suse.cz>
        Jakub Jelinek <jakub@redhat.com>
        * cgraphbuild.c (compute_call_stmt_bb_frequency): Fix handling of 0
        entry frequency.
        * predict.c (combine_predictions_for_bb): Ignore predictor predicting
        in both dirrection for first match heuristics.
        (tree_bb_level_predictions): Disable noreturn heuristic when there
        is no returning path.
Index: cgraphbuild.c
===================================================================
*** cgraphbuild.c       (revision 141929)
--- cgraphbuild.c       (working copy)
*************** int
*** 109,121 ****
  compute_call_stmt_bb_frequency (basic_block bb)
  {
    int entry_freq = ENTRY_BLOCK_PTR->frequency;
!   int freq;

    if (!entry_freq)
!     entry_freq = 1;

!   freq = (!bb->frequency && !entry_freq ? CGRAPH_FREQ_BASE
!             : bb->frequency * CGRAPH_FREQ_BASE / entry_freq);
    if (freq > CGRAPH_FREQ_MAX)
      freq = CGRAPH_FREQ_MAX;

--- 109,120 ----
  compute_call_stmt_bb_frequency (basic_block bb)
  {
    int entry_freq = ENTRY_BLOCK_PTR->frequency;
!   int freq = bb->frequency;

    if (!entry_freq)
!     entry_freq = 1, freq++;

!   freq = freq * CGRAPH_FREQ_BASE / entry_freq;
    if (freq > CGRAPH_FREQ_MAX)
      freq = CGRAPH_FREQ_MAX;

Index: predict.c
===================================================================
*** predict.c   (revision 141929)
--- predict.c   (working copy)
*************** combine_predictions_for_bb (basic_block 
*** 820,827 ****
            probability = REG_BR_PROB_BASE - probability;

          found = true;
          if (best_predictor > predictor)
!           best_probability = probability, best_predictor = predictor;

          d = (combined_probability * probability
               + (REG_BR_PROB_BASE - combined_probability)
--- 820,852 ----
            probability = REG_BR_PROB_BASE - probability;

          found = true;
+         /* First match heuristics would be widly confused if we predicted
+            both directions.  */
          if (best_predictor > predictor)
!           {
!               struct edge_prediction *pred2;
!             int prob = probability;
! 
!               for (pred2 = (struct edge_prediction *) *preds; pred2; pred2 =
pred2->ep_next)
!              if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
!                {
!                  int probability2 = pred->ep_probability;
! 
!                  if (pred2->ep_edge != first)
!                    probability2 = REG_BR_PROB_BASE - probability2;
! 
!                  if ((probability < REG_BR_PROB_BASE / 2) != 
!                      (probability2 < REG_BR_PROB_BASE / 2))
!                    break;
! 
!                  /* If the same predictor later gave better result, go for
it! */
!                  if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 >
probability))
!                      || (probability <= REG_BR_PROB_BASE / 2 && (probability2
< probability)))
!                    prob = probability2;
!                }
!             if (!pred2)
!               best_probability = prob, best_predictor = predictor;
!           }

          d = (combined_probability * probability
               + (REG_BR_PROB_BASE - combined_probability)
*************** static void
*** 1521,1526 ****
--- 1546,1561 ----
  tree_bb_level_predictions (void)
  {
    basic_block bb;
+   bool has_return_edges = false;
+   edge e;
+   edge_iterator ei;
+ 
+   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
+     if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH)))
+       {
+         has_return_edges = true;
+       break;
+       }

    apply_return_prediction ();

*************** tree_bb_level_predictions (void)
*** 1535,1541 ****

          if (is_gimple_call (stmt))
            {
!             if (gimple_call_flags (stmt) & ECF_NORETURN)
                predict_paths_leading_to (bb, PRED_NORETURN,
                                          NOT_TAKEN);
              decl = gimple_call_fndecl (stmt);
--- 1570,1577 ----

          if (is_gimple_call (stmt))
            {
!             if ((gimple_call_flags (stmt) & ECF_NORETURN)
!                 && has_return_edges)
                predict_paths_leading_to (bb, PRED_NORETURN,
                                          NOT_TAKEN);
              decl = gimple_call_fndecl (stmt);


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074