Stack Allocation of Space
Stack Allocation of Space
Almost all compilers for languages that use procedure, functions, or methods manage their run-time memory as a stack. Whenever a procedure is called, the local variable's space is pushed into a stack and popped off from the stack when the procedure terminates.
Activation Trees
A program is a set of instruction with some operation associated with it. The sequence in which the procedure executes is known as activation. We also assume that a procedure executes in a sequential manner, and this sequence is easily represented by a tree known as the activation tree.
The following example illustrates the nesting of procedure calls:
Example
int a[11];
void readArray() {
int i;
...
}
int partition(int m, int n) {
....
}
void quicksort(int m, int n) {
int i;
if (n > m) {
i = partition(m, n);
quicksort(m, i-1);
quicksort(i+1, n);
}
}
main() {
readArray();
a[0] = -9999;
a[10] = 9999;
quicksort(1,9);
}
The above code shows that array ‘a’ reads nine integers and sorts them using the recursive quicksort algorithm.
The task of the main function is to invoke the function readArray, sets the sentinels, and then call the function quicksort on the entire data array.
The code below shows a set of calls that might result from the execution of a program.
enter main( ) enter readArray() leave readArray() enter quicksort(1, 9) enter partition(1, 9) leave partition(1, 9) enter quicksort(1, 3) .... leave quicksort(1, 3) enter quicksort(5, 9) .... leave quicksort(5, 9) leave quicksort(1, 9) leave main()
The figure below shows the possible activation tree for the given code.
Activation Records
A run-time stack known as a control stack manages the procedure calls and returns. The control stack stores the activation record of each live activation. The top of the stack will hold the latest activation record.
The content of the activation record is given below. This record may vary according to the implemented languages.
| Actual parameters |
| Returned values |
| Control link |
| Access link |
| Saved machine status |
| Local data |
| Temporaries |
Temporaries: The values which arise from the evaluation of expression will be held by temporaries.
Local data: The data belonging to the execution of the procedure is stored in local data.
Saved machine status: The status of the machine that might contain register, program counter before the call to the procedure is stored in saved machine status.
Access link: The data's information outside the local scope is stored in the access link.
Control link: The activation record of the caller is pointed by the control link.
Returned values: It represents the space for the return value of the called function if any.
Actual parameter: It represents the actual parameters used by the calling procedure.