[tree-ssa] Optimize tail calls not in the final block

[Zdenek Dvorak]

Hello,

> > this patch enables the tail recursion optimization to handle calls that
> > are not in a basic block that directly precedes exit, e. g.
> > 
> > void yyy(int a, int b)
> > {
> >   if (a < b)
> >     yyy (b, a);
> >   else
> >     foo (a, b);
> > }
> 
> We handle this example without this new patch.  I'm guessing 
> that you had something else in mind.

oops. But something like

void yyy(int a, int b)
{
  if (god_knows_what ())
    goto end;

  if (a < b)
    yyy (b, a);
  else
    foo (a, b);

  end: ;
}

could do.  Or something like

int yyy(int a, int b)
{
  if (a < b)
    ret = yyy (b, a);
  else
    ret = foo (a, b);

  return ret;
}

This is not optimized even with the patch, since the intermediate
variable is used between the yyy call and return (tracking of such
chains has also to be added), but this is what I was mainly aiming
for -- the case when return and the function call are not in the same
basic block.

> > 	* tree-cfg.c (first_real_stmt): New.
> > 	* tree-flow.h (first_real_stmt): Declare.
> > 	* tree-tailcall.c (bb_optimize_tail_calls, find_tail_call_p,
> > 	eliminate_tail_call): Optimize tail calls not in the exit predecessor.
> 
> I can't quite follow what you're trying to do here.  I see
> forward and backward searching all within the same function
> all within a single while loop.

It is just a standard algorithm for traversing the tree without
using stack (by having father pointers). I may rewrite it using the
stack, which should be a bit cleaner (although also a bit harder to
write).

> Does all of this become unnecessary given a good jump threader?
> If these paths really do lead to exit, why wouldn't they be
> direct ancestors of the exit block?

I am mostly aiming for case when the return and the function are not
in the same block.  Assuming working jump threading, we could probably
just try finding the function call in the blocks preceding exit blocks,
which would only fail in some really obscure cases.

Zdenek