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

["rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.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;
}