How function calls work

[Michael]

Guys,
I'm interested in how the compiler implements function calls, can anyone
correct my understanding/point me towards some good articles.

When a function is called, is the stack pointer incremented by the size of
the variables declared in the called function, and then the function will
know where these are in memory relative to the current stack pointer
position. ALso how are variables returned, is that by a set position in the
stack??


ie,

void func1()
{
int a;
}

void func2()
{
int a,b;
char c;
}

will these both execute at exactly the same speed??
Thanks

Mike

[red floyd]

Re: How function calls work

Michael wrote:[color=blue]
> Guys,
> I'm interested in how the compiler implements function calls, can anyone
> correct my understanding/point me towards some good articles.
>
> When a function is called, is the stack pointer incremented by the size of
> the variables declared in the called function, and then the function will
> know where these are in memory relative to the current stack pointer
> position. ALso how are variables returned, is that by a set position in the
> stack??
>
>
> ie,
>
> void func1()
> {
> int a;
> }
>
> void func2()
> {
> int a,b;
> char c;
> }
>
> will these both execute at exactly the same speed??
> Thanks
>
> Mike
>
>[/color]

It's all compiler dependent. Some machines don't even have a stack.

As for return, it also depends. I've seen both register and stack based
return types, and for register based return types, it depends on the
type of data being returned.

Example: Green Hills C-68K. Returned integer types in D0, pointer
types in A0, and float/double in FP0.

Whitesmith's Z80 C compiler: returned in either HL, BC/HL, or the stack,
depending.

It's compiler and chip architecture dependent.

[Ian]

Re: How function calls work

Michael wrote:[color=blue]
> Guys,
> I'm interested in how the compiler implements function calls, can anyone
> correct my understanding/point me towards some good articles.
>
> When a function is called, is the stack pointer incremented by the size of
> the variables declared in the called function, and then the function will
> know where these are in memory relative to the current stack pointer
> position. ALso how are variables returned, is that by a set position in the
> stack??
>
>[/color]
In the general case (machines with a stack!), you are correct. The
compiler may optimise the local variable to registers, both the examples
you quote are likely to be done this way.

As said before, return method is very compiler and chip specific. It's
typical to return things that fit in a register or register pair by
register and large objects by reserving space on the stack.

Some machines (Sparc for example) have register sets reserved for 'in'
and 'out' variables for function calls.

Ian
[color=blue]
> ie,
>
> void func1()
> {
> int a;
> }
>
> void func2()
> {
> int a,b;
> char c;
> }
>
> will these both execute at exactly the same speed??
> Thanks
>
> Mike
>
>[/color]

[Leor Zolman]

Re: How function calls work

On Thu, 13 May 2004 23:00:19 +0000 (UTC), "Michael"
<slick_mick_00@ hotmail.com> wrote:
[color=blue]
>Guys,
>I'm interested in how the compiler implements function calls, can anyone
>correct my understanding/point me towards some good articles.
>
>When a function is called, is the stack pointer incremented by the size of
>the variables declared in the called function, and then the function will
>know where these are in memory relative to the current stack pointer
>position. ALso how are variables returned, is that by a set position in the
>stack??[/color]

As red says, it depends. But here's a rough checklist of actual or "as if"
tasks that need to happen somehow or another, or their equivalents, during
a function call sequence (disclaimer: this is based on 25-year-old
hand-coded 8-bit compiler implementation experience, so take that with a
grain of salt):

1. caller saves registers it wants saved (unless it knows function plans to
save ones it will alter...)

2. caller evaluates arguments, pushes them on the stack (typically in
reverse order, so the first one is in a "fixed" location, for the benefit
of variadic calls)

3. caller "calls" function

4. (if #1 didn't happen) function saves registers it plans on blowing away

5. function allocates stack space for all its local data, all at once (a
common misconception is that block-scope data is allocated upon entry to
the block; that's not true. It "comes into scope" there, but has probably
already been allocated upon entry to the enclosing function. That saves an
awful lot of allocation/deallocation on the stack during execution of
functions.)

6. function does its thing

7. function de-allocates its local stack frame (un-doing #5)

8. function puts return value wherever

9. function restores registers it saved in #4, if any

10. function "returns" to caller

11. caller grabs return value from wherever, and puts it wherever, if
necessary

12. caller pops args off the stack (all at once, of course)

13. caller restores saved registers (if any)
[color=blue]
>
>
>ie,
>
>void func1()
>{
>int a;
>}
>
>void func2()
>{
>int a,b;
>char c;
>}
>
>will these both execute at exactly the same speed??[/color]

Who knows? Kinda depends on whether "cleaning up the stack" can be done as
fast by func2 as by func1. I'd guess that func1 could do it by a simple
"pop", while func2 may need a few more cycles to increment the stack
pointer by some arbitrary number (12 bytes?). But modern compilers can
pretty much be trusted to do things about as smartly as they can be done,
so I wouldn't worry about it too much.
-leor
P.S. Disclaimer #2: Again, all of this is just to give a rough idea of the
/kinds/ of things function calls entail, not to proclaim that there's all
this overhead that is always necessarily costing you megacycles of CPU
time. But it does make inlining of functions (whether explicitly or
automatically by the compiler as in Java) look like a really, really good
idea when the functions are short and sweet...


--
Leor Zolman --- BD Software --- www.bdsoft.com
On-Site Training in C/C++, Java, Perl and Unix
C++ users: download BD Software's free STL Error Message Decryptor at:

https://www.bdsoft.com/tools/stlfilt.html

[E. Robert Tisdale]

Re: How function calls work

Michael wrote:
[color=blue]
> I'm interested in how the compiler implements function calls.[/color]

Which compiler?
[color=blue]
> Can anyone correct my understanding
> and/or point me toward some good articles.
>
> When a function is called, is the stack pointer incremented
> by the size of the variables declared in the called function,
> and then the function will know where these are in memory
> relative to the current stack pointer position.
> Also, how are variables returned?
> Is that by a set position in the stack?[/color]
[color=blue]
> cat f.cc[/color]
int f(int a, int b) {
return a + b;
}
[color=blue]
> g++ -Wall -ansi -pedantic -S f.cc
> cat f.save[/color]
.file "f.cc"
.text
.align 2
.globl _Z1fii
.type _Z1fii,@functio n
_Z1fii:
.LFB1:
pushl %ebp // push frame pointer onto stack
.LCFI0:
movl %esp, %ebp // base pointer gets stack poi
.LCFI1:
movl 12(%ebp), %eax // eax = a
addl 8(%ebp), %eax // eax += b
leave // restore frame pointer
ret // return
.LFE1:
.Lfe1:
.size _Z1fii,.Lfe1-_Z1fii
.ident "GCC: (GNU) 3.2 20020903 \
(Red Hat Linux 8.0 3.2-7)"

This is a *typical* implementation.
The compiler pushes a and b onto the stack
then "calls" the function at _Z1fii which is the symbol
that the compiler generated to represent f(int, int).
One register (ebp in this case) holds a pointer
to the base of the current stack frame.
One of the first things that the function does
is to save the old stack frame base pointer and
one of the last things that the function does
is to restore the old stack frame base pointer.
The stack pointer (esp in this case) becomes
the new stack frame base pointer. Now

esp + 0 points to the old stack frame base pointer,
esp + 4 points to the return address,
esp + 8 points to b and
esp +12 points to a

The sum a + b is accumulated and returned in register eax.

More generally, what your compiler does depends upon
the machine architecture and the operating system.
You would be better off asking this question
in a forum specifically for *your* compiler.

[E. Robert Tisdale]

Re: How function calls work

red floyd wrote:
[color=blue]
> Some machines don't even have a stack.[/color]

Really!
Can you name these machines?
And which compiler developers have implemented
an ANSI/ISO C++ compliant compiler for these machines?

[Dave Vandervies]

Re: How function calls work

In article <c80um3$3bn$1@h ercules.btinter net.com>,
Michael <slick_mick_00@ hotmail.com> wrote:[color=blue]
>Guys,
>I'm interested in how the compiler implements function calls, can anyone
>correct my understanding/point me towards some good articles.[/color]

First of all, it depends on the compiler. The FAQ for comp.compilers
is probably a good place to start for information on how such things
are done in general.

What you can count on, as guaranteed by the C++ language:

When you call a function, the implementation arranges for the arguments
(if anything) to be made available to the code in the function.
(In the case of a compiler (as opposed to an interpreter, say) it does
this by generating code (at compile time) to do this (at run time).)
For reference arguments, what's made available to the function is
the information needed to find the object passed by reference; for
non-reference arguments, what's made available is a copy of the object.

Inside the function, local (automatic) variables are created in some
area referenced by some sort of invocation record. These invocation
records act stack-like (and are therefore implemented using a (probably
hardware-supported) stack on any platform that has reasonable support for
such a thing, which most do). When a function returns, the invocation
record for that function is popped off the stack, local variables for
that invocation record are deallocated appropriately, and control is
passed back to the caller of the function.

Return values are made available to the caller; as with function
arguments, reference returns are given the information needed to find
the object a reference to is returned, and non-reference returns are
given a copy of the object returned. (This is why returning a reference
(or pointer) to a local variable is a Bad Thing - the object that the
reference actually refers to no longer exists.)

Abnormal returns (f'rexample, by throwing an exception) are handled
similarly, except that the object thrown is what gets passed back,
and activation records keep getting removed from the call stack (and
deallocated appropriately - f'rexample, destructors for local objects
will be run) until it gets to an invocation record where that exception
is caught, and control is passed to the catch code rather than to the
point from which the function represented by the last activation record
was called.


Now that you have some idea what you *can* count on, on to more concrete
stuff that depends on the implementation.

Keep in mind that knowing how your compiler does this tells you
nothing useful about how the language requires it to work or how
another compiler (or even your compiler invoked with a different
configuration) works.
(Excuse me for a minute while I go have a chat with the sigmonster...
there, that's better.)
[color=blue]
>When a function is called, is the stack pointer incremented by the size of
>the variables declared in the called function, and then the function will
>know where these are in memory relative to the current stack pointer
>position.[/color]

Most hardware makes it more natural to use a downward-growing stack,
so you're more likely to see the stack pointer decremented on function
entry and incremented on exit (and not at all unlikely to see some or
all of your local variables put in registers and not appearing on the
stack at all), but otherwise this is the way things are normally done
on the types of hardware you're probably used to using.

Note that if any local objects have nontrivial constructors (or
destructors), the constructors are run at the point where the variable
is created (and the destructors are run on function exit), so there's
potentially more to this than just reserving space on the stack.

[color=blue]
> ALso how are variables returned, is that by a set position in the
>stack??[/color]

More likely in a CPU register, especially for things small enough to fit
there, but it's also possible for space on the stack to be reserved for
the return value.


If you really want to know how your compiler does this, most compilers
have an option to generate assembly code that you can look at to see.
Note (again; can't say it too many times) that this is only useful
if you're curious about how your compiler does things, and shouldn't
be relied on to provide information that's useful to you while you're
writing C++ code, since it could very well be different with the compiler
you'll be using next week or the next version of your current compiler.

[color=blue]
>ie,
>
>void func1()
>{
>int a;
>}
>
>void func2()
>{
>int a,b;
>char c;
>}
>
>will these both execute at exactly the same speed??[/color]

These functions as written will both be translated by any self-respecting
optimizing compiler into a single return (or, if you're lucky, inlined
into nothing at all).

More generally, if for one reason or another the compiler can't or
won't keep the values entirely in registers (there are a few reasons
why it might not, but, say, a loop counter that's not used anywhere but
the loop's control statement is probably going to exist entirely in a
register) and the variables don't get initialized (either explicitly or
by running a constructor), the space for all of them will be allocated
on the stack in a single operation. So creating seventeen local int
variables should take no longer than creating one.

But if anything gets initialized, then the compiler needs to generate
code both to allocate space for it and to initialize it. The allocation
will probably be combined with any other allocations, and therefore not
add anything, but the initialization will need to be done separately
for each object (and can potentially be expensive).



dave

--
Dave Vandervies dj3vande@csclub .uwaterloo.ca
But usually, if you need to know, you're either a compiler writer, or
consumed by insatiable curiosity, or asking the wrong question; whichever
works. --Chris Dollin in comp.lang.c

[David Harmon]

Re: How function calls work

On Thu, 13 May 2004 16:53:42 -0700 in comp.lang.c++, "E. Robert Tisdale"
<E.Robert.Tisda le@jpl.nasa.gov > wrote,[color=blue]
>red floyd wrote:
>[color=green]
>> Some machines don't even have a stack.[/color]
>
>Really!
>Can you name these machines?
>And which compiler developers have implemented
>an ANSI/ISO C++ compliant compiler for these machines?[/color]

In the event that the machine has no dedicated hardware stack, the
compiler developer must create one through more general software means.
Of course the C++ implementation has some kind of a call stack whether
the supporting machine does or not. That implementation may not look much
like "incrementi ng the stack pointer" as the O.P. described. It's really
not that much of a burden, Robert.

[E. Robert Tisdale]

Re: How function calls work

David Harmon wrote:
[color=blue]
> E. Robert Tisdale wrote:
>[color=green]
>>red floyd wrote:
>>[color=darkred]
>>>Some machines don't even have a stack.[/color]
>>
>>Really!
>>Can you name these machines?
>>And which compiler developers have implemented
>>an ANSI/ISO C++ compliant compiler for these machines?[/color]
>
> In the event that the machine has no dedicated hardware stack,[/color]

My Pentium has a "hardware stack" for floating-point numbers
but the "call stack" isn't really implemented in hardware.
There are some assembler instructions which automatically
increment or decrement the stack
when objects are push'd onto or pop'd off of the "call stack".
[color=blue]
> the compiler developer must create one
> through more general software means.
> Of course the C++ implementation has some kind of a call stack[/color]

I believe that this is true
but the language does *not* require a stack of any kind.
[color=blue]
> whether the supporting machine does or not.
> That implementation may not look much like
> "incrementi ng the stack pointer" as the O.P. described.
> It's really not that much of a burden, Robert.[/color]

[Jerry Coffin]

Re: How function calls work

"E. Robert Tisdale" <E.Robert.Tisda le@jpl.nasa.gov > wrote in message news:<40A40A86. 7090902@jpl.nas a.gov>...[color=blue]
> red floyd wrote:
>[color=green]
> > Some machines don't even have a stack.[/color]
>
> Really!
> Can you name these machines?[/color]

I believe current Crays have stacks, but the original Cray 1 did not.
Offhand I don't remember exactly when dedicated hardware to support a
stack was added.

Older IBM mainframes didn't have stacks either. It's a fair guess
that they've added dedicated hardware to support a stack as well, but
I honestly don't know for sure (and assuming they have, when it was
added).
[color=blue]
> And which compiler developers have implemented
> an ANSI/ISO C++ compliant compiler for these machines?[/color]

At the present time, that's basically isomorphic to "has Greg Comeau
gotten an order to port his compiler to one of these machines?"

The Comeau Computing web site doesn't list either of these as a
supported target for his compiler, so the answer is probably that
neither has a fully conforming compiler.

OTOH, that has a lot to do with the difficulty of supporting things
like export, 2-phase name lookup (admittedly, the two are closely
related) and so on, and little or nothing to do with having a stack --
both certainly support recursion and such, which are where the stack
normally comes into play. I believe their current compilers do enough
that if Greg had a good reason to do so, he could support either of
these as a target.
--
Later,
Jerry.

The universe is a figment of its own imagination.

[Greg Comeau]

Re: How function calls work

In article <b2e4b04.040515 0823.5f51a70d@p osting.google.c om>,
Jerry Coffin <jcoffin@taeus. com> wrote:[color=blue]
>"E. Robert Tisdale" <E.Robert.Tisda le@jpl.nasa.gov > wrote in message news:<40A40A86. 7090902@jpl.nas a.gov>...[color=green]
>> red floyd wrote:[color=darkred]
>> > Some machines don't even have a stack.[/color]
>>
>> Really!
>> Can you name these machines?[/color]
>
>I believe current Crays have stacks, but the original Cray 1 did not.
>Offhand I don't remember exactly when dedicated hardware to support a
>stack was added.
>
>Older IBM mainframes didn't have stacks either. It's a fair guess
>that they've added dedicated hardware to support a stack as well, but
>I honestly don't know for sure (and assuming they have, when it was
>added).[/color]

Sounds right.
[color=blue][color=green]
>> And which compiler developers have implemented
>> an ANSI/ISO C++ compliant compiler for these machines?[/color]
>
>At the present time, that's basically isomorphic to "has Greg Comeau
>gotten an order to port his compiler to one of these machines?"
>
>The Comeau Computing web site doesn't list either of these as a
>supported target for his compiler, so the answer is probably that
>neither has a fully conforming compiler.
>
>OTOH, that has a lot to do with the difficulty of supporting things
>like export, 2-phase name lookup (admittedly, the two are closely
>related) and so on, and little or nothing to do with having a stack --
>both certainly support recursion and such, which are where the stack
>normally comes into play. I believe their current compilers do enough
>that if Greg had a good reason to do so, he could support either of
>these as a target.[/color]

Sounds right again (note that we don't publicize all our ports BTW).
--
Greg Comeau / Comeau C++ 4.3.3, for C++03 core language support
Comeau C/C++ ONLINE ==> http://www.comeaucomputing.com/tryitout
World Class Compilers: Breathtaking C++, Amazing C99, Fabulous C90.
Comeau C/C++ with Dinkumware's Libraries... Have you tried it?