[metapost] recursion in MP/ MF [was: all intersections between two paths]

[Lars Engebretsen]

tis 2005-01-18 klockan 10:09 +0100 skrev Laurence Finston:
> On Tue, 18 Jan 2005, Lars Engebretsen wrote:
> 
> > It could depend on the backend. I'm not an expert in SPARC
> > assembler, but it seems that with that back end, the stack frame
> > for the current recursive call is removed during the delay slot
> > corresponding to the next recursive function call.
> >
> > I generated the assembler code with
> >
> > g++ -S -foptimize-sibling-calls testrcrs.cc
> >
> > using gcc 3.4.2.
> >
> 
> Thanks for your answer.  Please excuse my obtuseness, but I don't
> understand it.  Does this mean that the compiler is causing tail recursion
> to be performed?  If so, is this disabled when you use the `-g' option?
> Or does the problem lie with GDB?

In short, yes it means that the compiler is causing tail recursion.

Basically, each function call causes a "frame" to be allocated on the
runtime stack; this frame in principle contains local variables. When
functions are called recursively, frames corresponding to "currently
active" recursive calls remain on the stack. The SPARC backend for gcc
3.4.2, however, seems to remove the previous stack frame when performing
a tail recursive call. This implemented using a so called "delay
slot" (which means that after an assembler call instruction, the next
instruction in memory is also executed). So the the tail recursive call
is implemented with something like "call myself again" followed by
"destroy current stack frame".

And, yes, compiling with -g changes this behaviour, at least as far as I
could see by deciphering the assembler output.

    /Lars