Avoid infinite recursion on flattening

[Jan Hubicka]

> On 1/21/07, Jan Hubicka <jh@suse.cz> wrote:
> >Hi,
> >this patch avoid infinite recursion on flattening.  I somehow assumed we
> >are safe with recursive_inlining_p but it tests only self recursion
> >(this has changed from early implementations of inliner)
> >
> >This problem caused C++ benchmarks to fail today, I am testing the patch
> >and will commit it tomorrow if it passes to not disturb them once again.
> 
> Didn't I implement the cgraph_find_cycles thing to avoid exactly this
> during cgraph_flatten_node?  In the loop

Yes, you did.  I just somehow managed to convince myself that it is not
needed here because we arleady check recurisve inlining.
> 
> +             /* Veify that we are not inlining function into itself to 
> prevent
> +                infinite loop.  */
> +             for (n = node; n->global.inlined_to ; n = 
> node->callers->caller)
> +               if (n->decl == e->callee->decl)
> +                 break;
> 
> 'global' suggests that whenever this would happen in one part of the
> cgraph you prevent inlining in another part that doesn't suffer from the
> problem?  If not, isn't fixing cgraph_recursive_inlining_p the better
> fix (and marking the edge as non-inlinable to avoid re-computing it
> again)?

No, global just suggests that the value is computed by global analysis
of the unit.

What happens is that if you have a->b->c->a callgraph, inlining a->b->c
is non-recursive, inlining a again is recursive and will be hanlded by
special algorithm.
However with a->b->c->b... callgraph, inlining a->b->c->b is not
recursive in this sense (the special algorithm won't deal with it nor
would tail recursion) and it makes sense to do such decisions with
profile feedback available. Perhaps the predicate can be renamed to
"self_recursive"

The in patch code simply looks at the inline chain and when it is trying
to inline function A into function B, it looks backward where A is
inlined into up to uninlined function and if B is contained there,
inlining is not done.

Your code first statically marks at least one edge within each cycle as
backward edge.  Les say that a->b is marked as backward.  Now if the a
in second testcase was marked flattened, we would never inline a->b,
while with my code we always inline a->b->c and stop on second inlining,
that I think is more consistent behaviour.

The problem is that code is linear in depth of inline graph (ie it
always looks back to see if given node isn't already in the chain
but I hope it won't be limiting problem in practice (as at the time we
hit it, we would be exploding in RAM anyway)
Otherwise we can simply hold pointer set of visited nodes.

Honza
> 
> Richard.