Stack Allocation of Space
Introduction: A function's prolog is responsible for allocating stack space for local variables, saved registers, stack parameters, and register parameters. All compilers for languages that use procedures, functions, or methods as units of user-defined actions manage at least part of their run-time memory as a stack. Each time a procedure1 is called, space for its local variables is pushed onto a stack, and when the procedure terminates, that space is popped off the stack. As we shall see, this arrangement not only allows space to be shared by procedure calls whose durations do not overlap in time, but it allows us to compile code for a procedure in such a way that the relative addresses of its nonlocal variables are always the same, regardless of the sequence of procedure calls.
Activation Trees: Stack allocation would not be feasible if procedure calls, or activations of procedures, did not nest in time. The following example illustrates nesting of procedure calls.
Example: Figure 7.2 contains a sketch of a program that reads nine integers into an array a and sorts them using the recursive quick sort algorithm. The main function has three tasks. It calls read Array, sets the sentinels, and then calls quicksort on the entire data array. Figure 7.3 suggests a sequence of calls that might result from an execution of the program. In this execution, the call to partition (l,9) returns 4, so a[l] through a hold elements less than its chosen separator value v, while the larger elements are in a  through a .
In this example, as is true in general, procedure activations are nested in time. If an activation of procedure p calls procedure q, then that activation of nq must end before the activation of p can end. There are three common cases:
- The activation of q terminates normally. Then in essentially any language, control resumes just after the point of p at which the call to q was made.
- The activation of q, or some procedure q called, either directly or indirectly, aborts; i.e., it becomes impossible for execution to continue. In that case, p ends simultaneously with q.
- The activation of q terminates because of an exception that q cannot handle. Procedure p may handle the exception, in which case the activation of q has terminated while the activation of p continues, although not necessarily from the point at which the call to q was made. If p cannot handle the exception, then this activation of p terminates at the same time as the activation of q, and presumably the exception will be handled by some other open activation of a procedure.
We therefore can represent the activations of procedures during the running of an entire program by a tree, called an activation tree. Each node corresponds to one activation, and the root is the activation of the "main" procedure that initiates execution of the program. At a node for an activation of procedure p, the children correspond to activations of the procedures called by this activation of p. We show these activations in the order that they are called, from left to right. Notice that one child must finish before the activation to its right can begin.
Example: One possible activation tree that completes the sequence of calls and returns suggested in Fig. 7.3 is shown in Fig. 7.4. Functions are represented by the first letters of their names. Remember that this tree is only
one possibility, since the arguments of subsequent calls, and also the number of calls along any branch is influenced by the values returned by partition.
The use of a run-time stack is enabled by several useful relationships between the activation tree and the behavior of the program:
The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
- The sequence of returns corresponds to a postorder traversal of the activation tree.
- Suppose that control lies within a particular activation of some procedure, corresponding to a node N of the activation tree. Then the activations that are currently open (live) are those that correspond to node N and its ancestors. The order in which these activations were called is the order in which they appear along the path to N, starting at the root, and they will return in the reverse of that order.