[Bug middle-end/56113] out of memory when compiling a function with many goto labels (50k > )

["rguenther at suse dot de" <gcc-bugzilla@gcc.gnu.org>]

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.