9.5 Procedures and Function Calls

Functions are an important and widespread abstraction mechanism in many different programming languages. A function is a first step to reusable code. A function name carries its returned value. A procedure is a function that does not return any useful value via its name, and it is used for its side effects only. We now discuss the implementation of functions and the kind of data structures we require to implement them.

There are a wide range of different design choices:

• What are the types of arguments that can be passed as parameters or returned as results?
• Do we allow variable number of arguments?
• Do we allow recursion in functions?
• Do we allow nested functions?
• Can functions have side effects?

Various languages like FORTRAN, C, C++, Java, Python, Perl and Haskell would have different answers to the questions above.

There are several issues in actual implementations of functions:

• How does the function determine the correct return address on its exit?
• How are call parameters passed to functions?
• How are function results returned?
• Where are the values of local variables stored?
• What happens to local variables when the function returns?

The answers to these questions determine the calling conventions for a particular implementation.

Suppose we start with a naïve calling conventions and assign fixed variables for function parameters, locals and results. That will have many limitations.

Return address: A function may be called from many different points in a single program that is in fact the idea behind a function. The code for the function must be able to find the appropriate point in the program to return to after a function call is complete. Also if there are nested calls to a number of functions, the last one called should be the first to return. This indicates a LIFO or stack structure. Thus using call and ret instructions in the instruction set of a typical processor should be used. This also allows nested and recursive calls.

Return value: It is awkward and inefficient to access the return value of a function through a global variable. It is much better to use a register. However, the return value may not fit within a register, for example eax is 32-bits, and cannot return a double. Also, we have to take care that return value from repeated calls do not overwrite the register.

Finding parameters: If we use fixed variables to pass function parameters, we will get strange results if there are recursive function calls or several calls to the same function. Consider factorial(n) written recursively. There, intuitively, we expect a new, but temporary, variable n each time we enter the function. Parameters can be passed to a function by pushing values onto the stack, because then the LIFO behaviour will automatically be achieved. For example, a call f(x, y, z) may be implemented by

pushl    x
pushl    y
pushl    z            // give parameters
call     f            // call function
addl     $12, %esp    // discard parameters

Note that we remove and discard the pushed values on return from the function. The general principle here is: the calling routine pushed the parameters, so it must remove them. It also means that the called function should not disturb them on the stack.

Accessing parameters: We have to access the values of function call parameters within the body of the function, without disturbing them on the stack. We should use indexed addressing, relative to the stack pointer, as shown in Fig. 9.5. For example, GAS code 4(%esp) refers to the contents of the memory at address esp + 4. We replace uses of the parameter name x with 12(%esp), etc. However, this mapping has a problem. It can change during evaluation within the function, as the stack pointer moves due to other activity within the function. For example, we may spill some register value on the stack (see Section 9.8.1), while saving some intermediate value.

 

Fig. 9.5 Call parameters’ access

Most of the modern processors provide a special register, called a frame pointer, fp, or a base pointer, bp, to establish the lower limit or the base of the stack-frame used by a function. On entry to a function, this register is set from the stack pointer, but once set, does not change for the duration of the function invocation.

The standard calling convention on the x86 processors uses the base pointer register, ebp, and it is used to access the call parameters. For each function or procedure call, we set up an Activation Record (AR) or stack-frame, as shown in Fig. 9.6. The arrangement now can be summarized as:

 

Fig. 9.6 A standard x86 stack-frame. Call parameters are accessible 8(%ebp) onwards. Local variables are stored and accessible –4(%ebp) downwards

Call parameters: x, y and z are the function's call arguments. We can refer to z as 8(%ebp), y as 12(%ebp), etc.

Return address: It is at 4(%ebp), but it will be automatically used when the ret instruction is executed at the exit of the function.

Old base pointer: It is the base pointer for the calling function. This will provide a link to calling functions’ stack-frame, in case it is also statically (lexically) enclosing.

Local variables: a, b are the local variables of the function. They are accessible, for example a as –4(%ebp), b as –8(%ebp).

Stack-frame: The caller starts by pushing the arguments, then it executes a call instruction, which pushes the return address. The called function saves the old base pointer, and sets a new value equal to current stack pointer; this establishes the base of the stack-frame. Then the function decreases the stack pointer to reserve space for the local variables.

9.5.1 Function Prologue and Epilogue

The code that builds the part of the stack-frame for which it is responsible, at the beginning of a function, is called the prologue. On the entry to a function, the call parameters and return address have already been pushed onto the stack by the caller. The function needs to:

pushl %ebp         // save old base pointer
movl  %esp, %ebp   // and set current value

If there are local variables which require N bytes of storage, then the function needs to reserve space for them:

subl  $N, %esp     // allocate space for locals

That ends the function prologue.

When the function terminates, we must dismantle the stack-frame and return the machine to the state it was in just before the call to this function. The code to do this is called the function epilogue, which is basically running the previous procedure in reverse:

movl  %ebp,%esp    // discard locals and temps
popl  %ebp         // recover original base ptr
ret                // return

On an x86 processor, the first two instructions can be replaced by the more efficient, but otherwise equivalent special instruction leave.

Once the called function returns to the caller, the result of the function is possibly in eax, but the parameters are still on the stack. They need to be removed. We restore the stack pointer to its original value by adding on the number of bytes, say M, used by the parameters:

addl $M, %esp

If no parameters were passed, then this step can be omitted.

9.5.2 Saving Registers

Consider what happens when a routine calls a function in the middle of an expression when there are values in registers that it needs to preserve. Unless the routine was written with this in mind, the called function might overwrite those registers with values needed. Some part of the code has to take responsibility for preserving register contents, for example by saving them on the stack. There can be two approaches:

The caller: Knows which registers have values that must be preserved, but does not know which the callee will actually use.

The callee: The same situation as for the caller, but reversed.

Neither one has enough information to guarantee that it can do a good job. Inter-procedural register allocation can solve these problems if the caller and callee are in the same compilation unit.

9.5.3 A Test for C Linkage

We are planning to use the standard C linkage in our implementation of the code generator for miniC language discussed in Chapter 12. Also, as mentioned in Section 9.6, we do not plan to use standard C library for system services. It is required that we check that our plan for the stack-frame layout works with a C program. We wrote the following programs – first a function in assembly language as per suggested function calling conventions, and second a C program to invoke that function. Test function myfunc1 in assembly:

.section .text
.globl    myfunc1
         .type myfunc1, @function
myfunc1:
         pushl %ebp
         movl  %esp, %ebp
         movl  8(%ebp), %eax
         addl  $100, %eax
         movl  %ebp, %esp
         popl  %ebp
         ret

Test program testclinkc.c in C:

extern int myfunc1(int i);
int main(){
  int i = 5;
  printf(“%d %d
”, i, myfunc1(i));
}

The C program was compiled with gcc, the assembly program was assembled with as and the two objects were linked. When testclinkc was executed, we got the correct answer “5 105”. We used this compatibility to test all the code generated by the miniC compiler.

We saw that a wide variety of design decisions are involved in the implementation of a function calling mechanism, with varying degrees of flexibility. Return addresses, function call parameters and local variables can be allocated storage on the hardware run-time stack. The most important data structure here is the Activation Record, also called a Stack Frame. Function parameters and local variables can be accessed from the current AR using either the stack pointer (unreliable) or a base pointer (preferred).