* Re: Tail Recursion (Why it appears that Gnat 3.15p does support it)
2005-01-13 22:04 Tail Recursion (Why it appears that Gnat 3.15p does support it) Chad R. Meiners
@ 2005-01-14 8:32 ` Duncan Sands
2005-01-14 9:04 ` Jacob Sparre Andersen
` (2 subsequent siblings)
3 siblings, 0 replies; 6+ messages in thread
From: Duncan Sands @ 2005-01-14 8:32 UTC (permalink / raw)
To: comp.lang.ada; +Cc: Chad R. Meiners
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.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Tail Recursion (Why it appears that Gnat 3.15p does support it)
2005-01-13 22:04 Tail Recursion (Why it appears that Gnat 3.15p does support it) Chad R. Meiners
2005-01-14 8:32 ` Duncan Sands
@ 2005-01-14 9:04 ` Jacob Sparre Andersen
2005-01-14 16:06 ` wojtek
2005-01-18 20:59 ` Chad R. Meiners
3 siblings, 0 replies; 6+ messages in thread
From: Jacob Sparre Andersen @ 2005-01-14 9:04 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Tail Recursion (Why it appears that Gnat 3.15p does support it)
2005-01-13 22:04 Tail Recursion (Why it appears that Gnat 3.15p does support it) Chad R. Meiners
2005-01-14 8:32 ` Duncan Sands
2005-01-14 9:04 ` Jacob Sparre Andersen
@ 2005-01-14 16:06 ` wojtek
2005-01-15 5:08 ` Brian May
2005-01-18 20:59 ` Chad R. Meiners
3 siblings, 1 reply; 6+ messages in thread
From: wojtek @ 2005-01-14 16:06 UTC (permalink / raw)
GNAT does not optimize tail calls, because, AFAIK, the underlying GCC
does not.
Regards,
Wojtek
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Tail Recursion (Why it appears that Gnat 3.15p does support it)
2005-01-14 16:06 ` wojtek
@ 2005-01-15 5:08 ` Brian May
0 siblings, 0 replies; 6+ messages in thread
From: Brian May @ 2005-01-15 5:08 UTC (permalink / raw)
>>>>> "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>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Tail Recursion (Why it appears that Gnat 3.15p does support it)
2005-01-13 22:04 Tail Recursion (Why it appears that Gnat 3.15p does support it) Chad R. Meiners
` (2 preceding siblings ...)
2005-01-14 16:06 ` wojtek
@ 2005-01-18 20:59 ` Chad R. Meiners
3 siblings, 0 replies; 6+ messages in thread
From: Chad R. Meiners @ 2005-01-18 20:59 UTC (permalink / raw)
Thank you everyone for the data points.
-CRM
^ permalink raw reply [flat|nested] 6+ messages in thread