whose 8051 cc overlays static inline stack frames

>
> Pat LaVarre <ppaatt@aol.com> schrieb in im Newsbeitrag:
> 2695edf1.0401120902.534a010@posting.google.com...
> > > From: Jan Homuth ...
> > > ...
> > > If it were an LJMP how would a return be
> > > possible ?  LCALL stores the return address on
> > > the 8051' stack.  If you use LJMP there is no
> > > way to "know" where to return to.
> >
> > Somehow we're speaking past each other out of context.
> >
> > I'm saying:
> >
> > LCALL p
> > ...
> > p: LCALL q
> > RET
> > q:
> > ...
> > RET
> >
> > often may equivalently be written:
> >
> > LCALL p
> > ...
> > p: LJMP q
> > ...
> > q:
> > ...
> > RET
> >
> > Am I yet more clear than mud?  The second expression of this same idea
> > requires only enough stack to fit one return address.  The first, more
> > naive, expression, wastefully requires enough stack to fit two return
> > addresses.
> >
> > For the example of:
> >
> > #define tbd /* ... */
> > extern void x(char chx);
> > static inline void c(char chc) { tbd; x(chc); tbd; }
> > static inline void b(char chb) { tbd; c(chb); tbd; }
> > void a(char cha) { tbd; b(cha); tbd; }
> >
> > what I call reasonable is:
> >
> > a: ljmp x
> >
> > I think we saw the tasking.com/ compile instead produce:
> >
> > a: lcall x
> > ret
> >
> > Situations where an 8051 processor behaves better when asked to lcall,
> > ret rather than ljmp are rare.
> >
> > > return ... as a goto ...
> >
> > I use that if a subroutine called only once has some good reason to be
> > stored elsewhere, rather than inline.
> >
> > > Aaaw.. c'mon. Did you also ... abvious ...
> >
> > Sorry I misunderstood, not on purpose, honestly, I did and I do
> > customarily review all the text of this thread, and my own drafts of
> > my own text, repeatedly before posting.
> >
> > Pat LaVarre


(-- top-posting corrected, TV --)

"Jan Homuth" <jandothomuth@altium.com> wrote in message
news:bu0uff$caga0$1@ID-139563.news.uni-berlin.de...
> Pat,
> A simple matter:
>
> The compiler cannot execute optimization on a call to an external routine
of
> a different translation unit. (C source module)
>
> This would mean having a feature like 'global call optimization'.
> That is a good idea.
> Thanks for the inspiration.
>
> Since the compiler does not have a feature x() must be CALL'ed.
> (Please do not forget that x() has a parameter that is to be passed. The
> compiler has calling conventions that must be used consistently)
>
> I am aware that there is potential for improvement.
>
> Let me ask you a question.
> For the code snippet presented, what is the result of the tools available
to
> you ?
>

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

> 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.

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:

---
http://groups.google.com/groups?threadm=2695edf1.0401121022.33c95ecd%40posting.google.com
Newsgroups: comp.lang.forth
Subject: gcc misunderstands Forth next less violently now
Date: 2004-01-09 10:33:48 PST 
...
hardcopy ...
ff.29
February 2004
C/C++ Users Journal
Andreas Bauer and Markus Pizka
Tackling C++ Tail Calls
...
... GCC has introduced ... "sibcalls" (short for "sibling calls"). 
Basically, a sibcall is an optimized tail call, but restricted to
functions that share a similar signature ... the same structural
equivalence of return types, as well as matching space requirements of
their arguments.

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);
...

---

> 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.

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

> The compiler cannot execute optimization on a call to an external routine of
> a different translation unit. (C source module)

Aye, the linker can, and self-modifying code can, but the compiler
cannot.

> The compiler has calling conventions that must be used consistently)

Only between separately compiled modules.

> Let me ask you a question.
> For the code snippet presented, what is the result of the tools available to
> you ?

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
http://members.aol.com/ppaatt/losslessc/

Tauno Voipio wrote:
> 
... snip ...
> 
> 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.

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.
   <http://cbfalconer.home.att.net>  USE worldnet address!

"Pat LaVarre" <ppaatt@aol.com> wrote in message
news:2695edf1.0401131249.2d63ff81@posting.google.com...
> 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:

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

Pat LaVarre wrote:
> 
... snip ...
> 
> 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

How can you compare translations of invalid source?

-- 
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!

> > 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:
>
> From: Kelly Hall (hall@priest.com)
> ...
> That's crap.  I checked for and found that GCC
> handled tail recursive calls properly in 1996.

1) How do you define "handled ... properly"?

2) Not all tail calls are recursive.  Did you check only tail
recursive calls?

comp.lang.forth more specifically said:

---

[M. Anton] Ertl ...

http://www.complang.tuwien.ac.at/forth/threaded-code.html

... 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.

---

> 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...

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

"Pat LaVarre" <ppaatt@aol.com> wrote in message
news:2695edf1.0401141049.460eae94@posting.google.com...
> 1) How do you define "handled ... properly"?
>
> 2) Not all tail calls are recursive.  Did you check only tail
> recursive calls?

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

> From: Kelly Hall ...
> ...
> I was checking ... GCC ... -O3 and -O4 ...
> only ... tail recursive calls. 

Clear now, thank you.

> After spending the better part of a decade using GCC, using the usual
> compilers for 8-bit embedded chips has been a let down.

Do you have any concrete examples?  I ask because I know the feeling,
but I did not retain my examples.

Pat LaVarre

"Pat LaVarre" <ppaatt@aol.com> wrote in message
news:2695edf1.0401150800.4896af80@posting.google.com...
> Do you have any concrete examples?  I ask because I know the feeling,
> but I did not retain my examples.

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