Re: [RFC] Massive recursion in tree_ssa_phiprop_1?

[Dave Korn <dave dot korn dot cygwin at googlemail dot com>]

Richard Guenther wrote:
> On Sat, Apr 18, 2009 at 7:01 PM, Dave Korn
> <dave.korn.cygwin@googlemail.com> wrote:

>>  With the default per-thread stack size of 2MB, it crashes in
>> tree_ssa_phiprop_1(), which by the time of the crash has recursed to a depth
>> that I can actually honestly describe as "OVER 9000"!  If I boost the stack to
>> 4MB, I find that the recursion does actually bottom out at some point, since
>> the compile completes, but I tested at 3MB and it crashed at a recursion depth
>> of 13924.
>>
>>  I know that boostrapping libjava is a tough job and pretty intensive on
>> memory demands, but is this level of nesting actually to be expected, or has
>> something gone astray?
> 
> Well, this is one of the usual ways of iterating over the CFG, so this
> is certainly not unexpected.  

  It appears to be the only pass that gets anywhere near this level of stack
usage, if I gate it off the compilation completes successfully.

> Maybe for some reason gsi is not scalarized and stack usage
> of that function is unusually high?

  Yes, I suspect it's as simple as that.  The function itself is
defineElements() in
libjava/classpath/gnu/javax/swing/text/html/parser/HTML_401F.java, and it's
got a huge long sequence of function calls to a function called defElement(),
each of which contain numerous constructors creating array arguments for the
call, e.g.

      defElement(SUB, 0, false, false, null,
      NONE
      ,
      new String[] {
        PCDATA, A, ABBR, ACRONYM,
        APPLET, B, BASEFONT, BDO, BIG,
        BR, BUTTON, CITE, CODE, DFN,
        EM, FONT, I, IFRAME, IMG,
        INPUT, KBD, LABEL, MAP, OBJECT,
        Q, S, SAMP, SCRIPT, SELECT,
        SMALL, SPAN, STRIKE, STRONG, SUB,
        SUP, TEXTAREA, TT, U, VAR
      }
    ,
      new AttributeList[] {
        attr(sID, null, null, ID, IMPLIED),
        attr(CLASS, null, null, 0, IMPLIED),
        attr(STYLE, null, null, 0, IMPLIED),
        attr(TITLE, null, null, 0, IMPLIED),
        attr(LANG, null, null, 0, IMPLIED),
        attr(DIR, null,  new String[] { LTR, RTL }, 0, IMPLIED),
        attr(ONCLICK, null, null, 0, IMPLIED),
        attr(ONDBLCLICK, null, null, 0, IMPLIED),
        attr(ONMOUSEDOWN, null, null, 0, IMPLIED),
        attr(ONMOUSEUP, null, null, 0, IMPLIED),
        attr(ONMOUSEOVER, null, null, 0, IMPLIED),
        attr(ONMOUSEMOVE, null, null, 0, IMPLIED),
        attr(ONMOUSEOUT, null, null, 0, IMPLIED),
        attr(ONKEYPRESS, null, null, 0, IMPLIED),
        attr(ONKEYDOWN, null, null, 0, IMPLIED),
        attr(ONKEYUP, null, null, 0, IMPLIED)
      }
    );

and that's one of the shorter examples, and this goes on for thousands of
lines, so I think I can believe that there really are that many BBs and that
level of dominator nesting.  Thanks for commenting; I'll just turn up my
per-thread stack allocation and not worry about it.

    cheers,
      DaveK