function calls

[Jim Giles]

>From article <1990Mar14.172152.25436 at utzoo.uucp>, by henry at utzoo.uucp (Henry Spencer):
> [... efficient procedure call interface ...]
> Many people can conceive of such ways, and a good many of them have been
> implemented, some quite successfully.  On the Mips machines, for example,
> a C function call to a "leaf" function (one which calls no others) is
> one instruction for the call and one for the return, total elapsed time
> a small fraction of a microsecond.  Non-leaf functions have to do a little
> bit more work at times.

Most machines implement call/return with single instructions.  However, this
tends to be the tip of the iceberg for procedure call overhead.  The interface
_MUST_ do the following:

1) Save/restore all register values that are still 'live' values for the
   caller.

2) Test the stack to make sure there is enough room for the callee's local
   variables (and call the memory manager for a new stack frame if there
   wasn't room).

3) Create (on the stack) a traceback entry so the debugger and/or the
   postmortem analyzer can find the current thread through the call tree.

A 'leaf' routine _might_ get away without doing number (3) by setting some
'leaf' flag.  A virtual memory machine might simplify number (2) to just a
test/fatal_error combination since stack overflow might be considered too
rare to justify much effort.  The problem is: _MOST_ of the procedure call
overhead is concentrated in number (1)!  And, this overhead applies to all
procedures - including 'leaf' routines.  Basically, 'leafness' has very
little to do with procedure call overhead.  Because modern machines tend
to have a _large_ number of registers, implementing (1) is usually quite
expensive - and it can't be made cheaper without interprocedural analysis
which in turn can't be done as long as separate compilation is possible.
Oh, well---

J. Giles