http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56113
--- Comment #25 from rguenther at suse dot de <rguenther at suse dot de> 2013-02-01 08:48:32 UTC --- On Thu, 31 Jan 2013, steven at gcc dot gnu.org wrote: > > 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; > } Yeah, I thought about such scheme but found the proposed patch much better ;) > (*) can go away if CFG modifications are forbidden during a domwalk, > but that's for GCC 4.9 earliest. But it seems the patch passed bootstrap & regtest ok ... I wonder how CFG modifications would survive the current scheme - after all we're using a visited sbitmap, too. So it at least can't be allowed to add basic-blocks during the domwalk. Changing dominator relationship with the proposed patch would only make the sorting bogus (thus, back to "random", as it were before the issue was introduced to domwalk which was rev. 159100). So, I'm going to propose the patch nevertheless - did you spot code that does CFG manipulations? asan/tsan do not use domwalk as far as I can see. Richard.
