(-- top-posting corrected, TV --)
of
to
Before you devote a considerable amount of effort into this optimisation, check compiler writer's literature for 'tail recursion'. It's a well-known method.
If there are separate stack frames for the functions, the advantage of the tail recursion gets questionable due to the effort needed for stack maintenenace.
HTH
Tauno Voipio tauno voipio @ iki fi
However, Fortran folk often choose to annoy Lisp folk by not translating tail calls as a form of goto, no matter how academically well known the equivalence has been since the 1950's Fortran/ Lisp split.
What brought Me to c.a.e. was comp.lang.forth talk of a claim I inferred from cuj, specifically: gcc is only now (2004!!) learning to see tail calls as goto's:
---
For example, again assuming the ABI of ix86 Linux/UNIX, ... a tail call from ... foo to var would be a potential optimization candidate ...
int foo (long long a); int bar (short a, short b); ...
---
Possibly this English says something more/ different than "Fortran folk often choose to annoy Lisp folk by not translating tail calls as a form of goto".
An example I use to make the existence of C epilogues plain to newbies is to contrast `gcc -c -Wall -W` translations of:
int * echo(int * pi) { return pi; } int * blech(void) { int i = 0; return echo(&i); } // wrong by epilogue
int fetch(int * pi) { return *pi; } int zero(void) { int i = 0; return fetch(&i); } // reasonably legit
Pat LaVarre
Aye, the linker can, and self-modifying code can, but the compiler cannot.
Only between separately compiled modules.
Sorry I cannot know.
Back when I was paid to work 8051, I could not easily talk here: NDA, pre-assigned IP, etc. Now that I am not paid to work 8051, I no longer own any 8051 tools.
E-mail tells me Keil offers, gratis, unlimited evaluation time for compilation of code images up to 2 KiB. Also fun 8051 kits at something like US$60 each.
I'm unlikely to try that myself simply to keep the IP unentangled as I try to invent and write and simultaneously publish a new kind of compiler myself. Left to myself, I'll be targetting JVM, PPC, x86, ... I first started this hobby in about 1982, but I might release a usable version this time around, who knows.
Pat LaVarre
... snip ...
Hunh? One or more of us is confused. Optimizing tail recursion avoids creating further stack frames, which can be a heavy advantage. Example:
void treewalk(nodeptr tree) { char biglocalbuffer[SIZE];
if (tree) { treewalk(tree->left); extractdatafrom(tree, biglocalbuffer); puts(biglocalbuffer); treewalk(tree->right); } }
which may, especially with unbalanced trees, assign lots of space to biglocalbuffer(s). The tail recursion optimized version is:
void treewalk(nodeptr tree) { char biglocalbuffer[SIZE];
while (tree) { treewalk(tree->left); extractdatafrom(tree, biglocalbuffer); puts(biglocalbuffer); tree = tree->right; } }
avoiding all extra space assignments and stack markers while investigating the right branches. Only the last statement and the loop condition were changed. There are other ways of avoiding that extra space usage in this case, but that doesn't affect the general case.
I'm sure you know all this, so this may clear things for others.
--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
Available for consulting/temporary embedded and systems.
USE worldnet address!
That's crap. I checked for and found that GCC handled tail recursive calls properly in 1996. Likely it handled them correctly before then, but I never checked it them before them. x86 code generator, although it shouldn't make a difference...
Kelly
... snip ...
How can you compare translations of invalid source?
--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
Available for consulting/temporary embedded and systems.
USE worldnet address!
1) How do you define "handled ... properly"? 2) Not all tail calls are recursive. Did you check --- [M. Anton] Ertl ...
... proposes the following code as one possible way to implement a "next-function" for a threaded Forth virtual machine interpreter [comments omitted]:
typedef void (* Inst)();
void inst1(Inst *ip) { ... (*ip)(ip+1); }
... Indirect sibcalls, as they are implemented in GCC 3.4, however, support this notion ... perfectly ... at this writing ... only fully functional on ix86 ... Porting ... SPARC or PowerPC should ... targets such as ARM-based ... miss out because of restrictions imposed by their ABI definition.
---
I think you mean to say in 1996 you checked x86 code generation of tail recursive calls. Thanks for sharing from your personal history of pain.
Pat LaVarre
It's been a few years, but I believe my test function was:
int factHelper( int x, int acc ) { return factHelper( x-1, x*acc ); }
I was checking to make sure GCC correctly implemented the tail recursive call as a branch. It did so for -O3 and -O4.
I was only checking for proper handling of tail recursive calls. If you care about tail calls in general, your mileage may vary.
After spending the better part of a decade using GCC, using the usual compilers for 8-bit embedded chips has been a let down.
Kelly
Clear now, thank you.
Do you have any concrete examples? I ask because I know the feeling, but I did not retain my examples.
Pat LaVarre
I've been doing my recent work on a Rabbit using Dynamic C. There's no optimization beyond simple expressions as near as I can tell.
Kelly
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.