Functions in C - Part 2 of 5

We have seen that a C program is composed of a single main() function, which during execution may call different functions (sub-programs). The called functions, in turn, may call some other functions, and so on. This can go on to any depth. Some functions may even call themselves several times - this is referred as a recursive call, which we will discuss in the next article post.

The execution of each function is expected to terminate at some point when it returns control back to the function that called it. While a called function is being executed, execution of the calling function is temporarily suspended. When execution of the called function is over, the calling function resumes its execution at the instruction immediately following the function call.

Note that we are using the word instruction here instead of statement, because, the higher level statements that you write in the C language, will be translated into machine instructions by the compiler.

Before delving further on this topic, let us first develop a clear understanding of some of the terms that we will be frequently using. Consider a simple example whose code snippet is given below:

 main()
 {
	int max(int, int);
	int a=5, b=10, max_num;
	max_num = max(a, b);
	printf("Max = %d", max_num);
 }

 int max(int x, int y)
 {
	int max_val;
	if(x>y)
		max_val = x;
	else 
		max_val = y;
	return(max_val);
 }

In the above example, the function main() calls function max(). So, main() is the caller or calling function and max() is the called function. When calling max(), main() will pass parameters a & b. These parameters will be accepted in arguments x & y respectively of the called function. After executing fully, function max() will return max_val to main(). So max_val is the return value. These emphasized definitions must be clearly visualized in your mind before proceeding ahead.

In order to become a good programmer, it is necessary for us to understand how the C compiler organizes execution of the various functions so that proper sequencing of program execution is maintained. We will understand what kind of memory organization/layouts the C compiler does, to keep track of various function calls and return control back to calling functions. We will also understand how the parameters passed during functions calls are maintained in the memory and how return value of called functions are stored so that they can be accessed by the calling function.

We will discuss a simplified subprogram call and return statement structure used by a C compiler. All programming language compilers use a similar kind of organization and method to handle function calls and function execution.

In order to execute any program, the C compiler needs to first load the program itself in the main memory of the computer. Now, each function in C is essentially a sub-program. Hence, to execute a function, the compiler needs to first load the function code (which defines the function) in the memory. In a more technical language we say that the compiler needs to load the function definition in the main memory. The block of space where the function definitions are loaded is referred as code segment. More appropriately, we call it static code segment because it remains static in the memory and is only read.

Next, while executing the function code, the compiler needs another block of space where it can store all data related to the particular instance of function execution. This will be essentially space for storing all variables & results of intermediate computation (such as x, y, max_val in the above example). It also needs to store other information such as who called the function and where the function has to return after it completes its run. The block of space where all these information is stored is referred as the function's activation record.

Note that any constant definitions will be stored in the code segment and not in the activation record, as constants remain unchanged for multiple invocations of the same function.

At this point it is essential to understand that a program may entail several calls to the same function. In such a scenario, the C compiler does not maintain multiple copies of function definition in the memory. It only maintains a single copy of the code segment which acts as a template for multiple invocations of the function. However, for each invocation of the same function, the compiler needs to maintain separate activation record, one for each invocation/instance of the function execution. So, if a C program calls a function n times, the compiler will create 1 static code segment and n activation records in the memory.

The compiler also maintains external spaces for two pointers, viz. current instruction pointer (CIP) and current environment pointer (CEP). CIP stores the address of the instruction that the machine (computer) is currently executing, and CEP stores the address of the activation record that belongs to the current instruction. This tells the machine which line of instruction it is currently executing and what is it's referencing environment (for data).

To summarize...

1. The execution of function involves two parts, a static code segment containing the executable code and constants, and an activation record containing local data, parameters, and various other data items.
2. The code segment is invariant during execution. It is created by the compiler and stored as a static component in the memory. During function execution it is used but never modified no matter how many times the function is called. Every activation of the function uses the same code segment.
3. The activation record however is created anew each time the function is called, and it is destroyed when the function returns to the calling program. While the subprogram (i.e., the called function) is in execution, the contents of its activation record are constantly updated as assignments are made to local variables and other data objects.

Let us understand what we have learnt so far, with an example. Consider the following C program where main() calls f1(), and f1() calls f2(). Function main() will begin execution. When main calls f1(), the execution of main will temporarily stop and execution of f1() will begin. Next, when f1 calls f2(), execution of f1 will temporarily stop and execution of f2() will begin. After f2() returns, f1 will continue execution from where it stopped. Thereafter, when f1() returns, main will continue execution from where it stopped.

 main()
 {
    ...
    f1();
    ...
 }

 f1()
 {
    ...
    f2();
    ...
    return;
 }

 f2()
 {
    ...
    return;
 }
   

Program statements and expressions in the functions are translated into executable instructions and stored in the above static code segment. The numbers 10 - 21 are memory addresses where instructions are loaded/stored. The numbers 22 - 48 are memory addresses of activation records.

Also note the address values stored in CIP & CEP. At a particular stage of execution the machine fetches the instruction designated by the CIP, updates the CIP to point to the next instruction in sequence and then executes the instruction (which may itself change the CIP again to effect a jump to some other instruction). Since all activations of the same function use the same code segment but different activation record, a pointer to the activation record, i.e. the current referencing environment, is also stored as shown in CEP above.

With the help of CEP and CIP pointers one can readily track how a program is executed. To begin with, an activation record for the main program (function main) is created. The CIP is assigned a pointer to the first instruction in the code segment for the main program. The machine then begins fetching and execution of instructions as designated by the CIP.

When a function call, say call f1, instruction is reached, an activation record for the function f1 is created and a pointer to it (viz. the address of AR_f1) is assigned to the CEP. The CIP is assigned a pointer to the first instruction of the code segment of f1, execution of instructions of f1 now commences from this point. When the function f1 calls another function say f2, new assignments are made to set the CIP and CEP for the activation of f2.

In order to be able to return correctly from a function call, the values of the CIP and CEP must be saved somewhere by the function call instruction before the new values are assigned. When a return instruction is reached that terminates an activation of a function, the old values of the CIP and CEP that were saved when the subprogram was called must be retrieved and reinstated. This reinstatement of the old values is all that is necessary to return control to the correct activation of the calling function at the correct place so that execution of the calling function may resume. The associated pointer values (CIP & CEP) are stored in the activation record of the function being called. After the call instruction creates the activation record, it stores the old values of the CIP and CEP at a particular place referred as return point (addresses 42 & 43 in case of AR_f2), and assigns the new CIP and CEP, thus effecting the transfer of control to the called function. Execution of the return instruction in the called function would cause fetching the old CIP & CEP from the return point and reinstating them as the values of the CIP and CEP, thus effecting the return control to the calling function.

Thus the call and return instructions swap CIP & CEP values in and out to effect transfers of control back and forth to functions. If execution is to be halted at some point, one can easily determine which function was currently being executed (by looking at the CEP & CIP), and which function had called it (by looking at the return point of the function being executed), which function had called that function (by looking at that function's return point), and so on.

A convenient data structure for implementing such a mechanism is a stack (last in - first out organization). In a stack one can access only the topmost element and the data introduced last can be accessed first. This feature clearly suits the requirement of storing activation record, instruction pointer and environment pointer values of functions. Note that the activation record for the function most recently activated, will be on the top of the stack. Immediately below it will be the activation record of the function, which called it.

I hope the above would have given you some picture of how program execution and sequence control is organized by the C compiler so that the machine (computer) can execute the instructions as per the logic. In case you still have some ambiguity in mind, re-read this article carefully.