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

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

[rguenth at gcc dot gnu.org]

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

             Bug #: 54493
           Summary: -fguess-branch-probability takes ages
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: rguenth@gcc.gnu.org


For the testcase in PR54492 -fguess-branch-probability (default on at -O1)
takes
ages.

[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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-09-12
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-09-12 14:19:23 UTC ---
Because we accumulate gazillion predictors per BB and do linear scans over
them:

bool
gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
{
  struct edge_prediction *i;
  void **preds = pointer_map_contains (bb_predictions, bb);

  if (!preds)
    return false;

  for (i = (struct edge_prediction *) *preds; i; i = i->ep_next)
    if (i->ep_predictor == predictor)
      return true;
  return false;
}

Instrumenting gimple_predict_edge shows

Adding 22 to edge 2->100003
Adding 22 to edge 2->3
Adding 22 to edge 2->4
Adding 22 to edge 2->5
Adding 22 to edge 2->6
Adding 22 to edge 2->7
Adding 22 to edge 2->8
Adding 22 to edge 2->9
Adding 22 to edge 2->10
Adding 22 to edge 2->11
Adding 22 to edge 2->12
Adding 22 to edge 2->13
Adding 22 to edge 2->14
Adding 22 to edge 2->15
Adding 22 to edge 2->16
Adding 22 to edge 2->17
Adding 22 to edge 2->18
Adding 22 to edge 2->19
Adding 22 to edge 2->20
Adding 22 to edge 2->21
Adding 22 to edge 2->22
...
Adding 22 to edge 2->17332
Adding 22 to edge 2->17333
Adding

(and continuing).  22 is the br_predictor (PRED_TREE_EARLY_RETURN).

It seems to me that we should have at most one predictor of each kind per
basic-block, no?

Testcase repeated:

int foo (int a, int b, int c)
{
  int d;
  switch (a)
    {
#define X(N) \
    case N ## 0: d = a + b; break; \
    case N ## 1: d = a + b; break; \
    case N ## 2: d = a + b; break; \
    case N ## 3: d = a + b; break; \
    case N ## 4: d = a + b; break; \
    case N ## 5: d = a + b; break; \
    case N ## 6: d = a + b; break; \
    case N ## 7: d = a + b; break; \
    case N ## 8: d = a + b; break; \
    case N ## 9: d = a + b; break;
#define XX(N) \
    X(N ## 0) X(N ## 1) X(N ## 2) X(N ## 3) X(N ## 4) X(N ## 5) X(N ## 6) X(N
## 7) X(N ## 8) X(N ## 9)
#define XXX(N) \
    XX(N ## 0) XX(N ## 1) XX(N ## 2) XX(N ## 3) XX(N ## 4) XX(N ## 5) XX(N ##
6) XX(N ## 7) XX(N ## 8) XX(N ## 9)
#define XXXX(N) \
    XXX(N ## 0) XXX(N ## 1) XXX(N ## 2) XXX(N ## 3) XXX(N ## 4) XXX(N ## 5)
XXX(N ## 6) XXX(N ## 7) XXX(N ## 8) XXX(N ## 9)
#define XXXXX(N) \
    XXXX(N ## 0) XXXX(N ## 1) XXXX(N ## 2) XXXX(N ## 3) XXXX(N ## 4) XXXX(N ##
5) XXXX(N ## 6) XXXX(N ## 7) XXXX(N ## 8) XXXX(N ## 9)
    XXXXX(1)
#if 0
    XXXXX(2)
    XXXXX(3)
    XXXXX(4)
    XXXXX(5)
    XXXXX(6)
    XXXXX(7)
    XXXXX(8)
    XXXXX(9)
#endif
    }
  return d;
}

[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?