Variable-Length Data on the Stack
Introduction: The run-time memory-management system must deal frequently with the allocation of space for objects the sizes of which are not known at compile time, but which are local to a procedure and thus may be allocated on the stack. In modern languages, objects whose size cannot be determined at compile time are allocated space in the heap.
However, it is also possible to allocate objects, arrays, or other structures of unknown size on the stack, and we discuss here how to do so. The reason to prefer placing objects on the stack if possible is that we avoid the expense of garbage collecting their space. Note that the stack can be used only for an object if it is local to a procedure and becomes inaccessible when the procedure returns.
A common strategy for allocating variable-length arrays (i.e., arrays whose size depends on the value of one or more parameters of the called procedure) is shown in Fig. 7.8. The same scheme works for objects of any type if they are local to the procedure called and have a size that depends on the parameters of the call.
In Fig. 7.8, procedure p has three local arrays, whose sizes we suppose cannot be determined at compile time. The storage for these arrays is not part of the activation record for p, although it does appear on the stack. Only a pointer to the beginning of each array appears in the activation record itself. Thus, when p is executing, these pointers are at known offsets from the top-of-stack pointer, so the target code can access array elements through these pointers.
Also shown in Fig. 7.8 is the activation record for a procedure q, called by p. The activation record for q begins after the arrays of p, and any variable-length arrays of q are located beyond that.
Access to the data on the stack is through two pointers, top and topsp. nHere, top marks the actual top of stack; it points to the position at which the next activation record will begin. The second, topsp is used to find local, fixed-length fields of the top activation record. For consistency with Fig. 7.7, we shall suppose that topsp points to the end of the machine-status field. In Fig. 7.8, topsp points to the end of this field in the activation record for q. From there, we can find the control-link field for q, which leads us to the place in the activation record for p where topsp pointed when p was on top. The code to reposition top and topsp can be generated at compile time, in terms of sizes that will become known at run time. When q returns, topsp can be restored from the saved control link in the activation record for q. The new value of top is (the old unrestored value of) topsp minus the length of the machine-status, control and access link, return-value, and parameter fields (as in Fig. 7.5) in q's activation record. This length is known at compile time to the caller, although it may depend on the caller, if the number of parameters can vary across calls to q.