Tail Recursion (Why it appears that Gnat 3.15p does support it)

Tail Recursion (Why it appears that Gnat 3.15p does support it)

[Chad R. Meiners]

I have noticed that Gnat 3.15p does not optimize the tail recursion in
the following program.

with Ada.Text_IO;
use  Ada.Text_IO;

procedure Tail is

type Int is mod 2**64;

procedure Fib(First, Second : Int) is
Next : constant Int := First + Second;
begin
Put(Int'Image(Next) & ", ");
Fib(Second,Next);
end Fib;

begin
Put("1, 1, ");
Fib(1,1);
end Tail;

Does anyone know why GNAT (or any other compiler) does not always reuse
stack frames for all subroutines that appear right before a return?  Is
there some requirement that prevents such naive optimizations?
Incidently, if anyone knows of a compiler that does optimize the tail
recursion for this program please let me know.
Thank you,
Chad R. Meiners

Re: Tail Recursion (Why it appears that Gnat 3.15p does support it)

[Duncan Sands]

Hi Chad, first I commented out the Put in Fib:

begin
--Put(Int'Image(Next) & ", ");
Fib(Second,Next);

then I compiled this with gcc from CVS as follows:

> gnatmake -O2 tail
gcc -c -O2 tail.adb
tail.adb:12:01: warning: possible infinite recursion
tail.adb:12:01: warning: Storage_Error may be raised at run time
gnatbind -x tail.ali
gnatlink tail.ali

The disassembly is then:

> objdump -r -d tail.o

tail.o:     file format elf32-i386

Disassembly of section .text:

00000000 <tail__fib.365>:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   eb fe                   jmp    3 <tail__fib.365+0x3>
   5:   8d 74 26 00             lea    0x0(%esi),%esi
   9:   8d bc 27 00 00 00 00    lea    0x0(%edi),%edi

00000010 <_ada_tail>:
  10:   55                      push   %ebp
  11:   b8 08 00 00 00          mov    $0x8,%eax
                        12: R_386_32    .rodata
  16:   89 e5                   mov    %esp,%ebp
  18:   ba 00 00 00 00          mov    $0x0,%edx
                        19: R_386_32    .rodata
  1d:   83 ec 08                sub    $0x8,%esp
  20:   89 04 24                mov    %eax,(%esp)
  23:   89 54 24 04             mov    %edx,0x4(%esp)
  27:   e8 fc ff ff ff          call   28 <_ada_tail+0x18>
                        28: R_386_PC32  ada__text_io__put__4
  2c:   31 c0                   xor    %eax,%eax
  2e:   89 e9                   mov    %ebp,%ecx
  30:   89 44 24 04             mov    %eax,0x4(%esp)
  34:   31 d2                   xor    %edx,%edx
  36:   b8 01 00 00 00          mov    $0x1,%eax
  3b:   c7 04 24 01 00 00 00    movl   $0x1,(%esp)
  42:   e8 b9 ff ff ff          call   0 <tail__fib.365>
  47:   c9                      leave
  48:   c3                      ret


which is a bit too optimised!

Comments:
(1) I commented out the Put because I expected the "&" (string concatenation) to cause
trouble, since it uses the secondary stack.
(2) Maybe the fact that Fib is a local procedure causes problems for older gcc.

All the best,

Duncan.

Re: Tail Recursion (Why it appears that Gnat 3.15p does support it)

[Jacob Sparre Andersen]

Chad  R. Meiners wrote:

> I have noticed that Gnat 3.15p does not optimize the tail recursion
> in the following program.
> 
> with Ada.Text_IO;
> use  Ada.Text_IO;
> 
> procedure Tail is
> 
> type Int is mod 2**64;
> 
> procedure Fib(First, Second : Int) is
> Next : constant Int := First + Second;
> begin
> Put(Int'Image(Next) & ", ");
> Fib(Second,Next);
> end Fib;
> 
> begin
> Put("1, 1, ");
> Fib(1,1);
> end Tail;
> 
> Does anyone know why GNAT (or any other compiler) does not always
> reuse stack frames for all subroutines that appear right before a
> return?

Could it be related to the parameter passing rules in Ada?  And would
it really be faster?

If the arguments for Fib are not copied in the order you have written
them in the procedure specification and a single stack frame is
reused, the program will not behave correctly.  But alternating
between two stack frames should be safe enough.

Jacob
-- 
�By becoming continuous, war has fundamentally changed its character.
 In past ages, a war, almost by definition, was something that sooner
 or later came to an end, usually in unmistakable victory or defeat.�
                               -- Nineteen Eighty-Four, George Orwell
�I don't think you can win [the war on terror].�    -- George W. Bush

Re: Tail Recursion (Why it appears that Gnat 3.15p does support it)

[wojtek]

GNAT does not optimize tail calls, because, AFAIK, the underlying GCC
does not.

Regards,
Wojtek

Re: Tail Recursion (Why it appears that Gnat 3.15p does support it)

[Brian May]

>>>>> "wojtek" == wojtek  <wojtek@power.com.pl> writes:

    wojtek> GNAT does not optimize tail calls, because, AFAIK, the
    wojtek> underlying GCC does not.

My copy of the *man* page (which may be wrong) has:

       -mtail-call
       -mno-tail-call
           Do (or do not) make additional attempts (beyond those of the
           machine-independent portions of the compiler) to optimize tail-
           recursive calls into branches.  You may not want to do this because
           the detection of cases where this is not valid is not totally com-
           plete.  The default is -mno-tail-call.

So, to the original poster, try -mtail-call, that might help.

The implication is that this might be buggy, but this documentation
might be wrong too. I don't have the info documentation currently
installed.
-- 
Brian May <bam@snoopy.apana.org.au>

Re: Tail Recursion (Why it appears that Gnat 3.15p does support it)

[Chad R. Meiners]

Thank you everyone for the data points.

-CRM