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

[Daniel Berlin <dberlin at dberlin dot org>]

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.

--Dan