PR/7344 - O(n^2) algorithm?

[tm]

I looked at PR/7344 which is entitled

"performance regression on huge case statements"

The problem appears to be bad O-complexity scalability in        
process_note_prediction. It contains this loop:

  /* Now find the edge that leads to our branch and aply the
prediction.  */

  if (y == last_basic_block)
    return;
  for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
    if (e->dest->index >= 0
        && dominated_by_p (post_dominators, e->dest, bb))
      predict_edge_def (e, pred, taken);

This algorithm appears to be O(n^2) for our testcase.
There seem to be 10,000 basic blocks dominated by each other,
so predict_edge_def() would be called 100 million times.

Is there an alternate solution for this problem?

Toshi