[Bug middle-end/54493] -fguess-branch-probability takes ages

[rguenth at gcc dot gnu.org]

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

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-09-12 
14:37:51 UTC ---
Something like

Index: gcc/predict.c
===================================================================
--- gcc/predict.c       (revision 191222)
+++ gcc/predict.c       (working copy)
@@ -525,8 +525,9 @@ void
 gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
 {
   gcc_assert (profile_status != PROFILE_GUESSED);
-  if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1)
-      && flag_guess_branch_prob && optimize)
+  if (flag_guess_branch_prob && optimize
+      && (e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1)
+      && !gimple_predicted_by_p (e->src, predictor))
     {
       struct edge_prediction *i = XNEW (struct edge_prediction);
       void **preds = pointer_map_insert (bb_predictions, e->src);

of course that doesn't try to merge the predictors probability nor the
edge it is for.  Why are the predictors stored per block and not per edge?

Another approach would be to fix this special case:

          && gimple_code (last) == GIMPLE_RETURN)
        {
          edge e1;
          edge_iterator ei1;

          if (single_succ_p (bb))
            {
              FOR_EACH_EDGE (e1, ei1, bb->preds)
                if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
                    && !predicted_by_p (e1->src, PRED_CONST_RETURN)
                    && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
                  predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);

which ends up adding all those (bogus?!) predications to the entry block.

Simplified we have


foo (int a, int b, int c)
{
  int d;

  <bb 2>:
  switch (a_2(D)) <default: <L10>, case 10: <L0>, ...

<L0>:
  d_5 = a_2(D) + b_4(D);
  goto <bb 13> (<L10>);
...
<L9>:
  d_14 = a_2(D) + b_4(D);

  # d_1 = PHI <d_3(D)(2), d_5(3), d_6(4), d_7(5), d_8(6), d_9(7), d_10(8),
d_11(9), d_12(10), d_13(11), d_14(12)>
<L10>:
  return d_1;

and we are adding the loads of !PRED_TREE_EARLY_RETURN to bb 2.  Thus
as we are only adding PRED_TREE_EARLY_RETURN at this point we can also do

@@ -2113,13 +2113,15 @@ tree_estimate_probability_bb (basic_bloc
              FOR_EACH_EDGE (e1, ei1, bb->preds)
                if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
                    && !predicted_by_p (e1->src, PRED_CONST_RETURN)
-                   && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
+                   && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN)
+                   && !predicted_by_p (e1->src, PRED_TREE_EARLY_RETURN))
                  predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
            }
          else
            if (!predicted_by_p (e->src, PRED_NULL_RETURN)
                && !predicted_by_p (e->src, PRED_CONST_RETURN)
-               && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
+               && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN)
+               && !predicted_by_p (e->src, PRED_TREE_EARLY_RETURN))
              predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
        }


(those predicted_by_p sequences are also inefficient as they repeat the
linear walk ...)

Honza?