Function calls in Compiler Design

Functions are an important abstraction mechanism in many programming languages. In this article we discuss how functions are implemented in compilers.

Table of contents.

1. Introduction.
2. The call stack.
3. Activation records.
4. Prologues, epilogues and sequences.
5. Caller-save vs callee-saves.
6. Using registers and passing parameters.
7. Interaction with the register allocator.
8. Accessing non-local variables.
9. Static links.
10. Summary.
11. References.

Introduction.

Through out this article we assume that all variables are local to a procedure/function accessing them and parameters are call-by-value where the value of an argument expression is passed to the called function since this is the default parameter passing mechanism in most programming languages.

The call stack.

A procedure body uses a finite number of variables which we map to a set of registers.

A recursive program will have an unbounded number of variables because each recursive call will have its own set of variables.
Only variables local to the active function are kept in registers and the rest are spilled to memory since we cannot keep all in registers.

When a function is called, live variables of the calling function(caller) are stored in memory, therefore, the registers will be free for use by the called function(callee).

The stored variables are loaded back to registers when the callee returns.
A stack is used for this storing, loading and pushing register contents onto the stack to be saved and popping them back into registers for restoration for its convenience.

A stack is unbounded hence it works with unbounded recursion.

Other functions of the stack

• Storing addresses where execution must be resumed after a call returns.
• Storing variables in the scope of a function which are not declared locally.
• Storing parameters to function calls such that the callee can read therefrom.
• Storing variables that need to to spilled.
• Allocating local arrays and records allocated in a function.

Activation records.

An activation record/frame is a chunk of memory allocated for each function invoked to cater for the function needs for storing values on the stack.

The machine architecture is responsible for dictating the calling convention which will standardize the layout of activation records which will allow a program to call functions compiled with other compilers written in a different language.

A layout for an activation record assuming that all information such as parameters, return addresses and contents of registers are stored in memory will look like the following.

activation record 1

FP stands for Frame pointer and it points to the first word of the activation record.

The first word holds the return address and above it incoming parameters are stored.
The function moves parameters to registers(except spilled parameters) before executing the body.

The space for incoming parameters is used for storing the return value of the function call.

Above incoming parameters, a space for storing other local variables(for spilling or preserving across later calls) is kept.

Prologues, epilogues and sequences.

A prologue is the code in front of the code for the function body responsible for reading parameters from the activation record into variables.

prologue for the activation record 1

The epilogue is the code after the code of the function body responsible for storing the computed return value in the activation record by the caller.

epilogue for the activation record 1

M[] and GOTO are arguments
parameter1,...,parametern are names for the intermediate language variables used in the function body for n parameters.
The result is the intermediate language variable holding the result of the function after execution of function body.

Function call instructions are translated into a call-sequence of instructions that will save registers, place parameters in the activation record etc.

A call sequence for the activation record 1

The call sequence

All usable registers for holding variables(R0-Rk) are stored in the frame.
They are stored above the calling function's incoming m parameters.
The frame pointer is advanced to point to the new frame and the parameters and return address stored in the prescribed locations in this new frame.

A jump to the function is made.

When the function call returns, result is read from the frame into variable x.
FP(frame pointer) is restored to its former value and saved registers are read back from the old frame.

Caller-save vs callee-saves

Before a function is called the caller saves all registers that must be preserved(caller-saves).

Alternatively the called function saves its contents of the registers that need preservation and restores them immediately before the function returns.(callee-saves).

The difference between the two strategies is when registers are saved.
We can refine both strategies to callee-saves saving only registers that hold live variables and callee-saves saving only registers used by the function.

An activation record for callee-saves.

The prologue

The epilogue

The call-sequence for x := CALL f(a1,...,an)

We have unnecessary saves, in the caller-saves, we save a live variable in the frame even though the callee doesn't use the register holding this variable and in the callee-saves we save registers that don't hold live values.

These saves are unavoidable but we can reduce unnecessary saving by using a mixed caller-saves, callee-saves strategy.

To do this, we designate caller-saves and callee-saves to registers.
If live variables are held in caller-saves registers, the callees must save these in its frame otherwise if a function uses callee-saves registers in the body, it saves these before using them.

Therefore only callee-saves registers used in the body will need to be saved.

Using registers and passing parameters.

In the call sequences shown in the previous images, parameters are stored in the frame and in both prologues most of them are immediately loaded back into registers.
We can reduce memory traffic by passing parameters in registers instead of memory.
To do this we can use registers 4 to 8 for passing the first function parameters and pass the remaining parameters onto the stack.

Functions have a short parameter list, therefore most likely they will fit in registers.

Possible division of register for the 16-register architecture

Register	Saved by	Use
0	caller	parameter 1 / result / local variable
1-3	caller	parameters 2 to 4 / local variables
4-12	callee	local variables
13	caller	temporary storage
14	callee	Frame pointer
15	callee	Return address

The return address is passed in a register.
RISC architectures have jump-and-link instructions which leave the return address in a register.

If a function call is made inside the body, this register is overwritten that is why we save the activation record before a call.
Callee-saves mark the return address register.

The activation record for the register division

Prologue for the register division*

Epilogue for the register division*

R15 holds the return address and is like any other a callee-saves register saved in the prologue and restores in the epilogue if used inside the body.
Its offset is 0 because the return address is stored at offset 0 in the frame.

The call sequence for x := CALL f(a1,...,an) for the register division

The instructions
R15 := returnaddress
GOTO f
LABEL return address
can be implemented using jump-and-link instruction in RISC processors.

Interaction with the register allocator.

A register allocator can provide information about which registers need to be saved, return information about registers being used by a function body and tell live variables after a function call and hence overally optimize function calls.

When a mixed strategy(caller-saves, calle-saves) is used variables living across a function call should be allocated to callee-saves registers and in this way the caller will not have to save them and with luck don't have to be saved by the callee either(i.e if the callee doesn't use these registers in its body).

If variables living across function calls interfere with caller-saves register, the register allocator avoids allocating them in caller-saves registers and the desired effect is achieved.

If no callee registers are available, the variable is spilled and therefore is saved across the function call and hence the call sequence wont worry about saving caller-saves registers as it is done by the register allocator.

Spilling is costly than local save/restore around a function call and thus it is a good idea to have alot of callee-saves registers for holding variables living across function calls.

Parameters that are not spilled should be loaded into registers contrary to the prologues images in previous sections.

Register-passed parameters that need spilling should be transferred to a stack location instead of a symbolic register.

From the prologues and epilogues notice that we have moved register-passed parameters from the numbered registers or stack locations to named registers to which the register allocator assigns numbers, this means that these parts must be included in the body when the register allocator is called.

This automatically handles the issue of spilled parameters because spilled-code is inserted immediately after the parameters are temporarily transferred to registers.
However, this causes extra memory transfers when a spilled stack-passed parameter is first loaded into a register and then stored back again however this can be handled by optimizations.

As discussed, we move register-passed parameters to named registers instead of leaving them in the registers they are passed in.
These registers may be needed for other function calls and this will give rise to problems if a parameter allocated to one of these needs to be preserved across the call.
Moving parameters to named registers frees the register allocator to allocate these callee-saves registers if needed.
Otherwise if this is not needed the register allocator might allocate the named variable to the same register.

In summary given a good register allocator, the compiler will do the following.

1. Generate code for the body of the function using symbol names for variables.
2. Add code for moving parameters from numbered registers and stack locations to named variables used for accessing the parameters in the body of the function and moving function-result from a named register to register used for function results.
3. Call the register allocator with the extended function body which should be aware of the register division and allocate variables that lives across function calls, to callee-saves registers and the set of spilled variables.
4. Add code for saving and restoring callee-saves registers that the register allocator sees as used in the extended function body and code for updating the frame pointer with the size of the frame to the register-allocated code
5. Add a function label at the beginning of the code and a return jump at the end.

Accessing non-local variables.

Global variables.

Global variables are stored in memory and the location of each variable is known at compile-time or link-time.

The global variable x generates the code
x := M[addressx]
instruction that uses x

The global variable will be loaded into a register-allocated temporary variable and this will be used in the place of the global variable in the instruction that needs the value of the global variable.

Assignment to a global variable x is implemented as such

x := the value to be stored in x
M[addressx] := x.

Global variables are treated as spilled variables.

Their values are loaded from memory to the register before any use and stored from a register into memory after assignment.

If a global variable is often used within a function, it is loaded into a local variable at the beginning of the function and stored back again when the function returns.

Consider the following:

• Global variables are read back from memory after a function call so changes will be registered in the local copy therefore it is best to allocate local copies of global variables in caller-saves registers.
• If a language allows call-by-reference parameters or pointers then there exist more than one way of accessing global variables, either through its name or using the call by reference parameter or pointer.
  It is important to note that use of global variables should be implemented sparingly as accessing local variables is much faster.

Call-by-reference parameters.

These parameters can be variables, array elements, fields in records etc.
Inside a function with call-by-reference parameter values can be assigned to the parameter and these assignments update the variable, array element or record passed such that the changes are visible to the caller.

Call-by-reference is implemented by passing the address of the given parameters therefore any access to the call-by-reference parameter is through this address.
In the C programming language we use the &(address-of) operator to explicitly pass pointers to variables, array-elements as parameters to a function.

When the value of the variable is used or updated, this pointer is explicitly followed by the * (de-referencing) operator.

A variable passed as a call-by-reference parameter or has its address passed using & operator resides in memory and must be spilled at the time of the call or allocated to the caller-saves register. It will be stored before the call and restored after the call.

Passing a result back to the caller using call-by-reference or pointer parameters can be slower than using function return value as the return value can be passed in a register.
Call-by-reference should also be used sparingly.

Nested scopes.

Some languages allow other functions to be declared locally within other functions. This local function will have access to variable declared within the parent function.

An example of nested scopes in pascal

procedure f (x : integer);
    var y : integer;
    function g(p : integer);
    var q : integer;
    begin
        if p<10 then y := g(p+y)
        else q := p+y;
        if (y<20) then f(y);
        g := q
    end;
    begin
        y := x+x;
        writeln(g(y),y)
        end;

From the above g has access to x and y as well as its own local variables p and q.

When g is called its local variables p and q are held in registers. Other variables x and y will reside in the activation records of the procedures/functions in which they are declared.

All variables that can be accessed in the inner scopes should be stored in memory when the function is called and this is handled by allocating such variables in caller-saves registers.

Static links.

Assuming there are more than two nested scopes, pointers to all outer scopes are passed as parameters to local functions.

An example; if g declares a local function h, h will need pointers of f's and g's activation records.
If there are many nested scopes, the list of parameters would be long and therefore a single parameter is selected to hold a linked list of the frame pointers for the outer scopes.

To implement the above, links are placed in the activation records.
Therefore the first field of the activation record will point to the activation record of the next outer scope.
This pointer to the next outer scope is referred to as a static link because scope nesting is static.

Summary.

Fixed-size activation records grow upwards in memory and frame pointers point to the first element of the frame however we may opt to change this using variants such as using a variable-sized frame, variable number of parameters, changing the direction of growth of the stack and repositioning the frame pointer, keeping frames in registers rather than on stacks, passing function addresses as parameters to other functions instead of using static links.

Function calls are a part of expressions and they generate cpde.
During compilation of a function, each parameter is checked to see if it matches the type corresponding to the formal parameter of the declaration.
The call-by-value is the default parameter passing mechanism in most programming languages.

References

1. "Basics of Compiler Design" by Torben Ægidius Mogensen.
2. Function calls slides by Viktor Leijon, Peter Jonsson, Johan Nordlander and Mark P. Jones from Lulea University of Technology in Lulea, Sweden.