Re: PR rtl-optimization/28071 (domwalk recursion)

[Jeffrey Law <law at redhat dot com>]

On Fri, 2006-07-28 at 11:49 -0400, Daniel Berlin wrote:
> Jan Hubicka wrote:
> > Hi,
> > at -O3 the testcase builds huge CFG with depth of dominator tree about
> > 15000 blocks.  This makes GCC to run out of stack space when not built
> > with optimization and without checking even on Linux.
> > In RTL world we avoid recusion whose depth depends on CFG size, it is
> > probably good time to start re-inforcing this on trees.  This patch
> > avoids recusion on domwalk that is source of most of the stack space
> > consumption.  The patch does not make non-bootstrapped compiler to work
> > for me as tree-into-ssa contains one recursive walk of dominator tree
> > written by hand, but it still shave of few seconds out of the
> > compilation.
> > 
> > For GCC modules test I also get speedup of about 2 seconds out of 4
> > minutes.
> > 
> > If accepted, i will send patches for the other few recursive walks as
> > followups.
> > 
> > Except for fair amount of re-indenting the patch is rather easy. It is
> > simply using already existing stack walk_data->block_data_stack for the
> > stack of basic blocks too.
> > 
> 
> 
> This is some seriously convoluted logic to achieve not storing an
> explicit worklist of the blocks somewhere.
> IMHO, it would look much nicer in worklist form, like Steven B. changed
> PRE's compute_avail to do.
I don't have the code in front of me right now, but IIRC the only
remaining user of the block data stack is DSE which I think we all
hope will be replaced by something better.

I'd kindof rather see a separate worklist as well instead of adding
another user of a field we want to go away.

jeff