[net.lang.c] Tail recursion

greg@utcsri.UUCP (Gregory Smith) (04/16/86)

In article <708@bentley.UUCP> kwh@bentley.UUCP (KW Heuer) writes:
>In article <2516@utcsri.UUCP> utcsri!greg (Gregory Smith) writes:
>>What it should do next is .., call itself recursively to sort the shortest
>>list.  It should then *loop back* to sort the longest list (if it is more
>>than one item).  Thus a stack frame is saved while sorting the longer one.
>
>A good optimizer should compile tail-recursion into a jump anyway.  (But
>there are few good optimizers by that standard.)

This intrigues me... I would not have expected an optimizer to catch this
sort of thing, and would be interested in hearing details of any that do.

The salient parts of my code were:

func(a,b){
	do{
		foo bar;
		a = aa; b = bb;
	}while( cond );
}

The 'recursive version' is:
func( a,b ){
	foo bar;
	if( cond ) func(aa,bb);
}

The following is equivalent, and *might* be easier to catch, but shouldn't
be if proper control-flow analysis is done:

func(a,b){
	foo bar;
	if(!cond) return;
	func(aa,bb);
}
/* any comments? */
Does anybody end up with the do-while jump after compiling ( and optimizing )
one of the recursive ones? I tried a few variations and it didn't happen.
( 4.2 BSD vax 11/780 ).

This reminds me of one of the commonest 'tricks' in assembler - instead
of CALL X/RET, you write JMP X and then hopefully apologize in the comments.
Of course X must not be expecting any stack context. One of the DEC libraries
I was using to write pdp11 code had a macro CALLR X which was just JMP X !
I once wrote a CRT driver in Z80 code - if I hadn't used this trick, it
would have used about 10 levels of stack - with this trick, the maximum
was 2 ( This was significant - there was ..very.. little RAM available :-) ).

-- 
"If you aren't making any mistakes, you aren't doing anything".
----------------------------------------------------------------------
Greg Smith     University of Toronto      UUCP: ..utzoo!utcsri!greg

cg@myrias.UUCP (Chris Gray) (04/16/86)

When I was playing around with a compiler (not a C compiler) for CP/M-80
I included the following peephole optimization:

	call	x	=>	jmp	x
	ret

Of course it was only done if the call wasn't preceded by a PUSH.
Unfortunately, some of the built-in constructs which required run-time
support had arguments that were pushed onto the stack at some indeterminate
time in the past. I put in some kludges to handle them (flushing the peephole
after the call), but there were still problems. In the end the amount of
kludging to get it right outweighed the benefits, so I just ripped out the
optimization.

This is a much simpler case than recognizing tail recursion, but it does
illustrate some of the things compiler writers will try to do.

			Chris Gray (ihnp4!alberta!myrias!cg)