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

[steven at gcc dot gnu.org]

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.