http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56113
--- Comment #24 from Steven Bosscher <steven at gcc dot gnu.org> 2013-01-31 23:22:43 UTC --- (In reply to comment #23) > (In reply to comment #19) > > Created attachment 29317 [details] > > kill dominator queries from domwalk > > > > This patch kills dominator queries from domwalk, removing a quadratic > > bottleneck > > I introduced there. Do so by sorting DOM children after DFS completion > > numbers. > > > > Which hopefully results in equivalent operation ;) Another alternative would be to set up a vector with the edge counts at the start of the dominator walk. When visiting a basic block bb, do FOR_EACH_EDGE (e, ei, bb->succs) if (e->dest->index < unvisited_preds_count.length () // * && (single_pred_p (e->dest) // common case, cheap test || dominated_by_p (CDI_DOMINATORS, e->dest, e->src)) --unvisited_preds_count[e->dest] and replace the expensive loop: FOR_EACH_EDGE (e, ei, bb->preds) { if (!dominated_by_p (CDI_DOMINATORS, e->src, e->dest) && !bitmap_bit_p (visited, e->src->index)) { found = false; break; } } with: if (e->dest->index < unvisited_preds_count.length () // * && unvisited_preds_count[e->dest->index] > 0) { found = false; break; } (*) can go away if CFG modifications are forbidden during a domwalk, but that's for GCC 4.9 earliest.