This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: forcing tail/sibling call optimization


On 27-Nov-2000, Mark Mitchell <mark@codesourcery.com> wrote:
> The issue, I take it, is that if there are addressed locals in the
> caller, then the compiler might be afraid to do a tail call that would
> clobber them?

Right.

> Since we're accepting the point of view that the
> programmer is going to have to do something anyhow, it's worth
> pointing out that the programmer can already make that clear to the
> compiler: make the call after the addressed locals have gone out of
> scope.  In other words, instead of:
> 
>   {   
>     int i;
>     f(&i);
>     g(); /* I hope this will be a tail call! */ 
>   }
> 
> do:
>  
>   {
>     {
>       int i;
>       f(&i);
>     }
>     g();
>   }
> 
> Yes, that's harder in some cases -- but it can always be done with a
> goto to the call site, which can go in the outermost block of the
> function.

A goto to the call site is not sufficient, in general.
You also need to create copies of all of the parameters
to the tail call which are local variables.

You also need to make sure that you don't take the address of any of
the caller's function parameters; instead, if that would be required,
you must copy the function parameters into locals and take the address
of the locals.

For example, suppose that in your example above, instead of `g();' it
was `g(i);'.  And suppose this tail call is nested inside other code:

   void foo(int p)
   {   
     int j;
     f2(&p, &j);
     if (j > 0)
       {
	 int i;
	 f(&i);
	 g(i); /* I hope this will be a tail call! */ 
       }
     else
       {
         f3(j); /* Likewise here */
       }
   }

To give the C compiler a decent hint, we have to turn it
into something like this:

   void foo(int p)
   {   
     int outer_i;
     int outer_j;
     {
       int inner_p;
       int j;

       inner_p = p;
       f2(&inner_p, &j);
       if (j > 0)
         {
	   int i;
	   f(&i);
	   outer_i = i;
	   goto g_tailcall;
         }
       else
         {
           outer_j = j;
           goto f3_tailcall;
         }
     }
     return;

   g_tailcall:
     g(outer_i); /* Now I _really_ hope this will be a tail call! */
     return;

   f3_tailcall:
     f3(outer_j); /* Likewise here */
     return;
   }

This is a _lot_ uglier that just adding a simple tail call annotation 
at the point of the call.  And it would probably result in less efficient
code in some cases (e.g. if the parameters that need to be copied were
structs).  So I would still much rather have the annotation.
C-- and Microsoft's IL both provide much more direct support for this
than GNU C.

However, since this is automatically generated code, I suppose we
could grudgingly make do with that, if it worked.

The bad news is that gcc doesn't yet do tail recursion optimization
for code like the code above.  I think that is because of this code in
sibcall.c:

 |         /* We must be careful with stack slots which are live at
 |            potential optimization sites.
 |
 |            ?!? This test is overly conservative and will be replaced.  */
 |         if (frame_offset)
 |           goto failure;

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]