Function Call Stack
A function call stack is a data structure that stores information about the active subroutines of a computer
program.
When a function is called, a new stack frame is created and pushed onto the call stack, which contains the
function's parameters, local variables, and return address.
Upon returning from a function, the stack frame is popped off the stack, and control returns to the previous
function using the return address stored in the stack frame.
Each stack frame corresponds to a single function call, and the call stack grows and shrinks as functions are called
and return.
The call stack is essential for managing function calls, including passing arguments and storing return information.
Activation Records
An activation record is a data structure that contains information about a single execution of a function or
procedure. Each time a function is called, a new activation record is created, which stores the context needed to
execute that function. This context includes the function’s local variables, parameters, return address, and other
information necessary for the function’s execution. Once the function completes, the activation record is removed
from memory.
Activation records are fundamental to the concept of recursive functions, where the same function can be called
multiple times within its execution. Each call to the function must maintain its own separate context, which is
facilitated by the use of activation records.
Structure of an Activation Record
The exact structure of an activation record can vary between programming languages and compilers, but it
typically contains the following components:
Return Address
When a function is called, the program needs to know where to continue execution after the function completes.
The return address is stored in the activation record to keep track of this information. This address is usually the
instruction that follows the function call in the program.
Parameters
Parameters are the values passed to the function when it is called. The activation record includes space to store
these parameters, which can be accessed by the function during its execution.
Local Variables
Local variables are variables that are defined within the function. Each activation record allocates space for these
variables so that they can be used by the function. Local variables are created when the function is called and
destroyed when it exits.
Optional Control Link
The control link points to the activation record of the calling function. This link allows the program to return to the
previous function’s activation record when the current function completes, enabling a proper flow of control through
nested function calls.
Optional Access Link
The access link is used in languages that support nested functions or closures. It provides access to the activation
records of enclosing functions, allowing inner functions to reference variables defined in their parent functions.
Saved Registers
When a function is called, it may need to use CPU registers to store temporary values. However, the values in these
registers before the function call must be preserved. The saved registers section of the activation record holds the
values of registers that need to be restored when the function completes.
1: #include <stdio.h>
2:
3: int modify(int a, int b){
4: int tmp = a*4 - b / 3;
5: return tmp;
6: }
7: double truly_half(int x){
8: double tmp = x / 2.0;
9: return tmp;
10: }
11: int main(){
12: int a = 7, y = 17;
13: int mog = modify(a,y);
14: printf("Done with modify\n");
15:
16: double x = truly_half(y);
17: printf("Done with truly_half\n");
18:
19: a = modify(x,mog);
20:
21: printf("Results: %d %lf\n",mog,x);
22: return 0;
23: }
Call Stack behavior
main() called
Method Line Var Value Addr Notes
main() 12 a ? 1024
y ? 1028
mog ? 1032
x ? 1036
One line of main() executed
Method Line Var Value Addr Notes
main() 13 a 7 1024
y 17 1028
mog ? 1032
x ? 1036
modify() called
Method Line Var Value Addr Notes
main() 13 a 7 1024
y 17 1028
mog ? 1032
x ? 1036 double variable
modify() 4 a 7 1044
b 17 1048
tmp ? 1052
modify() first line executed
Method Line Var Value Addr Notes
main() 13 a 7 1024
y 17 1028
mog ? 1032
x ? 1036 double variable
modify() 5 a 7 1044
b 17 1048
tmp 23 1052
modify() second line (return) executed
Method Line Var Value Addr Notes
main() 13 a 7 1024
y 17 1028
mog 23 1032
x ? 1036 double variable
Method Line Var Value Addr Notes
main() 14 a 7 1024
y 17 1028
mog 23 1032
x ? 1036 double variable
printf() fmt ?? 1044 4-byte pointer
Method Line Var Value Addr Notes
main() 16 a 7 1024
y 17 1028
mog 23 1032
x ? 1036 double variable
truly_half() 8 x 17 1044
tmp ? 1048 double variable
Method Line Var Value Addr Notes
main() 16 a 7 1024
y 17 1028
mog 23 1032
x ? 1036 double variable
truly_half() 9 x 17 1044
tmp 8.5 1048 double variable
Method Line Var Value Addr Notes
main() 17 a 7 1024
y 17 1028
mog 23 1032
x 8.5 1036 double variable
Method Line Var Value Addr Notes
main() 19 a 7 1024
y 17 1028
mog 23 1032
x 8.5 1036 double variable
modify() 4 a 8 1044 caste to int
b 23 1048
tmp ? 1052
Method Line Var Value Addr Notes
main() 19 a 7 1024
y 17 1028
mog 23 1032
x 8.5 1036 double variable
modify() 5 a 8 1044 caste to int
b 23 1048
tmp 25 1052
Method Line Var Value Addr Notes
main() 19 a 25 1024
y 17 1028
mog 23 1032
x 8.5 1036 double variable
Advantages of Using Activation Records
Activation records provide several advantages in compiler design and program execution:
Simplified Function Calls
By encapsulating all the necessary information about a function call in a single structure, activation records simplify
the management of function calls and returns. The program can easily retrieve the return address and local variables
from the activation record.
Support for Recursion
Activation records are essential for handling recursive function calls. Each invocation creates a new activation record,
allowing the program to maintain separate contexts for each call. This enables functions to call themselves without
conflict.
Improved Memory Management
Using activation records allows for efficient memory allocation and deallocation on the stack.
Construct a Call Stack for this 1: #include <stdio.h>
program: 2:
3: double f1(double x){
4: return x+1.0; // (f1_1)
5: }
6:
7: double f2(double x){
8: double tmp = f1(x); // (f2_1)
9: double z = f1(x+1); // (f2_2)
10: return (z+ tmp) / 2; // (f2_3)
11: }
12:
13: double f3(double x, double y){
14: double z = f1(1); // (f3_1)
15: double tmp1 = x*z; // (f3_2)
16: double tmp2 = f2(y); // (f3_3)
17: return tmp1+tmp2; // (f3_4)
18: }
19:
20: int main(){
21: double x = 2; // (main_1)
22: double y = f3(x, x+3); // (main_2)
23: printf("%.3lf\n",y); // (main_3)
24: return 0; // (main_4)
25: }