Re: [f-cpu] calling conventions

[Michael Riepe <michael@stud.uni-hannover.de>]

On Sat, Jun 08, 2002 at 12:02:18PM +0200, Christophe wrote:
[...]
> For the case of "open", I need some info :
> 
> since there are two forms and in C they share the same name, there must be only
> one implementation. So "open" implementation has really three arguments. What
> happens when we call "open" with two arguments ? put a default value on the
> third argument ?

Unfortunately, open() is not part of the ISO C99 standard. It's a POSIX.1
function with a lot of historic background. The third argument is used
(and must be provided) if the O_CREATE flag is set in the second argument.

One can implement open() as a 3-argument function and simply ignore the
additional argument (in C, there is no run-time check for the number of
arguments anyway). But the prototype should specify a varargs function.

There are other functions that may be declared as having a variable
number of arguments:

	int fcntl (int fd, int cmd, ...);
	int ioctl (int fd, int cmd, ...);

These functions also take at most 3 arguments, but the third argument
may have different types. Sometimes it's an `int', sometimes an `int*',
a `struct flock*', `struct termios*' and so on.

> > > Recursive function calls require stack operations too. Other than inline
> > > macros to hint at function call parameters fixed arg functions still are
> > > better using off the stack in my view.
> >
> > Not really. First of all, a lot of recursive function calls can be
> > automatically translated to iterative code. A `tail-recursive' call like
> 
> First, the compiler must be able to handle recursive-to-iterative translation.
> Not a evidence for all compilers.

Since that can be done in the code generator (or machine-specific
optimizer), we just have to replace the tail-recursive calling sequence

	move first_arg, r1
	move second_arg, r2
	...
	move last_arg, r<n>
	<save return_reg>
	jmp <myaddr>, <return_reg>
	<restore return_reg>
	jmp <return_reg>

with

	move first_arg, r1
	move second_arg, r2
	...
	move last_arg, r<n>
	jmp <myaddr>

and we're done. Note that the second version doesn't even touch the stack.

> Second, there is really cases where compiler cannot translate but a programmer
> can (because programmer can use an explicit stack to save only necessary data
> during iteration).

If the compiler can't translate the call, it will have to use the
(implicit) stack. But toys^H^H^H^Hcompilers that don't detect and replace
tail-recursive calls aren't worth using them. It's one of the most simple
optimizations, and quite effective.

> So recursive function always requires stack operations but as the callee is in
> charge to save what must callee-saved, for n recursive calls, we just save n-1
> times callee-saved registers instead of n if caller-saved.

You can also save them once on entry and keep them throughout the
recursion, if that's convenient. But that depends on the code (and
the compiler).

> Anyway, for performance, one of two choices : having a great compiler able to
> translate recursive functions to iterative functions, or translate by ourselves
> recursive functions into iterative functions.

Try to always write *tail-recursive* functions and let the compiler do
the rest. That is, instead of

	int fak(int x) {
		return x < 2 ? 1 : x * fak(x - 1);
	}

use

	static int fak2(int x, int y) {
		return x < 2 ? y : fak2(x - 1, y * x);
	}
	int fak(int x) {
		return fak2(x, 1);
	}

and the compiler should substitute

	int fak(int x) {
		int y = 1;

		while (x >= 2) {
			y *= x;
			x -= 1;
		}
		return y;
	}

-- 
 Michael "Tired" Riepe <Michael.Riepe@stud.uni-hannover.de>
 "All I wanna do is have a little fun before I die"
*************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe f-cpu       in the body. http://f-cpu.seul.org/