Call and Return Implementation, Tail Recursion

Call and Return

• Temporary storage, like small arrays in the program.  You just "sub esp, N" to allocate N bytes starting at esp; as long as you be sure to "add esp,N" to give those bytes back before your function returns.  One nice part about the stack is that once you move the stack pointer over an area, those bytes are YOURS until you give them back, unlike registers, which almost always get overwritten when you call another function.
• Saving preserved registers.
  

call make_beef
mov eax,0xC0FFEE
ret

make_beef:
	mov eax,0xBEEF
	ret

int make_beef(void);
int foo(void) {
	make_beef();
	return 0xC0FFEE;
}

int make_beef(void) {
	return 0xBEEF;
}

jmp make_beef
mov eax,0xC0FFEE
ret

make_beef:
	mov eax,0xBEEF
	ret

int foo(void) {
	goto make_beef;
	return 0xC0FFEE;
make_beef:
	return 0xBEEF;
}

jmp make_beef
come_back:
mov eax,0xC0FFEE
ret

make_beef:
	mov eax,0xBEEF
	jmp come_back

(Try this in NetRun now!)

push come_back ; - simulated "call" -
jmp make_beef  ; -   continued  -
come_back:     ; - end of simulated "call" -

mov eax,0xC0FFEE
ret

make_beef:
	mov eax,0xBEEF
	pop rcx   ; - simulated "ret" -
	jmp rcx   ; - end of simulated "ret" -

(Try this in NetRun now!)

Optimization: Tail Recursion

Because calling functions takes some overhead (push return address, call function, do work, pop return address, return there), recursion is slower than iteration.  For example:

int sum(int i) {
	if (i==0) return 0;
	else return sum(i-1)+i;
}
int foo(void)
{
	return sum(10000000);
}

mov rdi,10000000
call sum
ret

; sum function: computes sum of numbers from 0...i
; one parameter: i, in rdi: number of recursions left
sum:
cmp   rdi,0 ; check if we're done
jle    base_case
push rdi
sub  rdi,0x1; i-1
call sum ; recursion step
pop rdi
add rax,rdi ; partial + i
ret

base_case: ; no more iterations--return zero
mov   rax,0
ret

Folks who love recursion have found an interesting optimization called "tail recursion", where you arrange for there to be *nothing* for the function to do after recursing, so there's no point in your children returning to you--you just "jmp" to them, not "call", because you don't want them to ever come back to you.  The base case is the only "ret".  Here's an example:

int sum(int i,int partial) {
	if (i==0) return partial;
	else return sum(i-1,partial+i);
}
int foo(void)
{
	return sum(10000000,0);
}

mov edi,1000000000 ; sum first argument
mov esi,0 ; partial result
call sum
ret

sum:
mov    eax,esi
cmp   edi,0
je    base_case
lea    esi,[rax+rdi*1]
sub    edi,0x1
jmp sum ; tail recursion step!

base_case:
ret

Tail recursion eliminates both the memory used on the stack for the return addresses, and the time taken for the call and return.  It can make recursion exactly as fast as iteration.  (Curiously, you can always transform an iteration into a recursion, and vice versa, although the code may get nasty.)

Sadly, my version of the gcc compiler doesn't seem to do the tail recursion optimization anymore on 64-bit machines, although it used to do them on 32-bit machines.

Why you care #1: Stack Space Usage

int silly_recursive(int i) {
	if (i==0) return 0;
	else return i+silly_recursive(i-1);
}

int foo(void) {
	std::cout<<"Returns: "<<silly_recursive(read_input());
	return 2;
}

(Try this in NetRun now!)

int silly_iterative(int n) {
	int sum=0;
	for (int i=0;i<=n;i++) sum+=i;
	return sum;
}

int foo(void) {
	std::cout<<"Returns: "<<silly_iterative(read_input());
	return 2;
}

(Try this in NetRun now!)

Why you care #2: Buffer Overflow Attack

int happy_innocent_code(void) {
	char str[8];
	cin>>str;
	cout<<"I just read a string: "<<str<<"!  I'm a big boy!\n";
	return 0;
}

void evil_bad_code(void) {
	cout<<"Mwa ha ha ha...\n";
	cout<<"...er, I can't return.  Crashing.\n";
}

int foo(void) {
	//void *p=(void *)evil_bad_code; /* address of the bad code */
	//printf("evil code is at: '%4s'\n",(char *)&p);
	happy_innocent_code();
	cout<<"How nice!\n";
	return 0;

}

(Try this in NetRun now!)