Re: needless deep recursion in gt-c-decl.h

[Geoff Keating <geoffk at geoffk dot org>]

Mike Stump <mrs@apple.com> writes:

> and the other is the idea that we can count how long the insn chain is
> (PREV_INSN and NEXT_INSN as long as the nodes are unmarked), allocate
> the many slots, move them in, mark just those nodes all iteratively,
> unmark the first, then really mark it, loop.  This way, all the long
> insn chains will be in the vec, very storage efficient.

Thank you!  That helped me think of a much better idea.  The new code
looks like:

  for (xlimit = (struct rtx_def *)x_p;
       ggc_test_and_set_mark (xlimit);
       xlimit = RTL_NEXT (xlimit))
    ;

  x = (struct rtx_def *)x_p;
  if (x != xlimit)
    { 
      struct rtx_def * xprev = x;
      for (;;)
        { 
          xprev = RTL_PREV (xprev);
          if (xprev == NULL)
            break;
          x = xprev;
          ggc_set_mark (x);
        }
    }

  for (; x != xlimit; x = RTL_NEXT (x))
     // mark fields of x

The neat part is the middle loop.  What it does is move to the head of
the doubly-linked list, marking as we go.  We know those elements
haven't been marked because if they'd been marked, the rest of the
list would also have been marked.  Then the final loop marks the whole
list.  No memory allocation is necessary.  The 'xlimit' variable is
still there so to handle EXPR_LISTs and the like.

Of course, it's not _quite_ that simple.  For instance, we have to
check that the thing we're marking is really part of the doubly-linked
list, it turns out this is not always the case.

This takes us down to a maximum nesting depth of 894, and this time
it's trees not RTL.  Much better!  Now, to implement it.

-- 
- Geoffrey Keating <geoffk@geoffk.org> <geoffk@redhat.com>