From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: fac41,9a0ff0bffdf63657
X-Google-Attributes: gidfac41,public
X-Google-Thread: 1108a1,9a0ff0bffdf63657
X-Google-Attributes: gid1108a1,public
X-Google-Thread: 103376,4b06f8f15f01a568
X-Google-Attributes: gid103376,public
X-Google-Thread: f43e6,9a0ff0bffdf63657
X-Google-Attributes: gidf43e6,public
From: Samuel Tardieu <sam@ada.eu.org>
Subject: Re: Why C++ is successful
Date: 1998/08/18
Message-ID: <m3ww86e0y7.fsf@zaphod.enst.fr>#1/1
X-Deja-AN: 382321763
References: <dewar.902415458@merv> <6qfhri$gs7$1@nnrp1.dejanews.com>
 <Pine.BSF.3.96.980807124210.21259B-100000@shell5.ba.best.com>
 <35cb8058.645630787@news.ne.mediaone.net> <dewar.902578088@merv>
 <slrn6sopmg.4fg.jdege@jdege.visi.com> <rfzpddz3s2.fsf@bnp-eng.remcomp.com>
 <902934874.2099.0.nnrp-10.c246a717@news.demon.co.uk> <dewar.903074236@merv>
 <vUQA1.451$_P3.515571824@newsreader.digex.net>
 <EACHUS.98Aug17143342@spectre.mitre.org>
 <bg%B1.20607$MV.14907802@news.teleport.com>
Mail-Copies-To: sam@ada.eu.org
Content-Type: text/plain; charset=US-ASCII
Organization: TELECOM Paris
Mime-Version: 1.0 (generated by tm-edit 7.108)
Newsgroups: comp.lang.eiffel,comp.object,comp.software-eng,comp.lang.ada
Date: 1998-08-18T00:00:00+00:00
List-Id: <comp.lang.ada>

Robert> How about to avoid procedure call stack winding and unwinding
Robert> in time critical code?

Patrick> Another approach is to use a compiler that can eliminate tail
Patrick> recursive stack growth. If function A returns the result of
Patrick> function B, then there is no need to increase the stack only
Patrick> to pop it when the call is done. The result is a procedure
Patrick> call can be compiled as efficiently as a GOTO. Scheme is
Patrick> defined this way. All iterations can be defined in terms of
Patrick> procedures.

GNAT also makes this optimization for tail recursive functions.

For example, the following code:

   function Even (N : Natural) return Boolean is
   begin
      if N = 0 then
         return True;
      elsif N = 1 then
         return False;
      else
         return Even (N - 2);
      end if;
   end Even;

will be compiled as (flags used: -O3 -gnatp -fomit-frame-pointer) on a 
pentium:

_ada_even:
	movl 4(%esp),%eax
.L5:
	testl %eax,%eax
	jne .L2
	movb $1,%al
	ret
	.align 4
.L2:
	cmpl $1,%eax
	je .L4
	addl $-2,%eax
	jmp .L5
	.align 4
.L4:
	xorl %eax,%eax
	ret

Note that there is no subprogram call to Even from whithin Even, which
means that the stack will not grow as recursive calls are made.

In fact, GCC's back end transform the program flow to look like:

   function Even (N : Natural) return Boolean is
      C : Natural := N;
   begin
    << Even_Begin >>
      if C = 0 then
         return True;
      elsif C = 1 then
         return False;
      else
         C := C - 2;
         goto Even_Begin;
      end if;
   end Even;

  Sam
-- 
Samuel Tardieu -- sam@ada.eu.org