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.
