In stack allocation, storage is organized as a stack, and activation records are pushed and popped as the activation of procedures begin and end, respectively, thereby permitting recursive procedures. The storage for the locals in each procedure call is contained in the activation record for that call. Hence, the locals are bound to fresh storage in each activation, because a new activation record is pushed onto stack when a call is made. The storage values of locals are deleted when the activation ends.
1 The Call and Return Sequence
Procedure calls are implemented by generating what is called a "call sequence and return sequence" in the target code. The job of a call sequence is to set up an activation record. Setting up an activation record means entering the information into the fields of the activation record if the storage for the activation record is allocated statically. When the storage for the activation record is allocated dynamically, storage is allocated for it on the stack, and the information is entered in its fields.
On the other hand, the job of a return sequence is to restore the state of machine so that the machine's calling procedure can continue executing. This also involves destroying the activation record if it was allocated dynamically on the stack.
The code in a call sequence is often divided between the caller and the callee. But there is no exact division of run-time tasks between the caller and callee. It depends on the source language, the target machine, and the operating system. Hence, even when using a common language, the call sequence may differ from implementation to implementation. But it is desirable to put as much of the calling sequence into the callee as possible, because there may be several calls for a procedure. And even though that portion of the calling sequence is generated for each call by the various callers, this portion of the calling sequence is shared within the callee, so it is generated only once. Figure 1 shows the format of a typical activation record. Here, the contents of the activation record are accessed using the CEP pointer.
The stack is assumed to be growing from higher to lower addresses. A positive offset will be used to access the contents of the activation record when we want to go in a direction opposite to that of the growth of the stack (in Figure 1, the field pointed to by the CEP). A negative offset will be used to access the contents of the activation record when we want to go in the same direction as the growth of stack. A typical call sequence for caller code to evaluate parameters is as follows:
push ( ) /* for return value
push (T1) /* T1 is holding the first argument
push (T2) /* T2 is holding the second argument
.
.
.
push (Tn) /* Tn is holding the nth argument
push (n) /* n is the count of arguments
push (return address)
push (CEP)
goto start of code segment of callee
A typical callee code segment is shown in Figure 2.
A typical call sequence in the callee will be:
CEP = top /*
Code for pushing the local data of
the callee
And a typical return sequence is:
top = CEP + 1
1 = *top /* for retrieving return address
top = top + 1
CEP =*CEP / for resetting the CEP to point to the activation record of the caller
top = top+ *top +2 /*for resetting top to point to the top of the activation record of caller goto1
2 Access to Nonlocal Names
The way that the nonlocals are accessed depends on the scope rules of the language . There are two different types of scope rules: static scope rules and dynamic scope rules.
Static scope rules determine which declaration a name's reference will be associated with, depending upon the program's language, thereby determining from where the name's value will be obtained at run time. When static scope rules are used during compilation, the compiler knows how the declarations are bound to the name references, and hence, from where their values will be obtained at run time. What the compiler has to do is to provision the retrieval of the nonlocal name value when it is accessed at run time.
Whereas when dynamic scope rules are used, the values of nonlocal names are retrieved at run time by scanning down the stack, starting at the top-most activation record. The rule for associating a nonlocal reference to a declaration is simple when procedure nesting is not permitted. In the absence of nested procedures, the storage for all names declared outside any procedure can be allocated statically. The position of this storage is known at compile time, so if a name is nonlocal in some procedure's body, its statically determined address is used; whereas if a name is local, it is assessed via a CEP pointer using the suitable offset.
An important benefit of static allocation for nonlocals is that declared procedures can be freely passed as parameters and returned as results. For example, a function inCis passed by address; that is, a pointer is passed to it. When the procedures are nested, declarations are bound to name references according to the following rule: if a name x is not declared in a procedure P, then an occurrence of x in P is in the scope of a declaration of x in an enclosing procedure P1 such that:
-
The enclosing procedure P1 has a declaration of x, and
-
P1 is more closely nested around P than any other procedure with a declaration of x.
Therefore, a reference to a nonlocal name x is resolved by associating it with the declaration of x in P1, and the compiler is required to provision getting the value of x at run time from the most-recent activation record of P1 by generating a suitable call sequence.
One of the ways to implement this is to add a pointer, called an "access link," to each activation record. And if a procedure P is nested immediately within Q in the source text, then make the access link in the activation record P, pointing to the most-recent activation record of Q. This requires an activation record with a format like that shown in Figure 3.
The modified call and return sequence, required for setting up the activation record shown in Figure 3, is:
push ( ) /* for return value
push (T1) /* T1 is holding the first argument
push (T2) /* T2 is holding the second argument
.
.
.
push (Tn) /* Tn is holding the nth argument
push(n) /* n is the count of arguments
push (return address)
push (CEP)
code to set up access link
goto start of code segment of callee
A typical callee segment is shown in Figure 4.
A typical call sequence in the callee is:
CEP = top+1/* code for pushing the local data of the callee
A typical return sequence is:
top = CEP+1
1 = *top /* for retrieving return address
top = top+1
CEP = *CEP / for resetting the CEP to point to the activation record of caller
top = top + *top +2/* for resetting top to point to the top of the activation record of caller goto 1
3 Setting Up the Access Link
To generate the code for setting up the access link, a compiler makes use of the following information: the nesting depth of the caller procedure and the nesting depth of the callee procedure. A procedure's nesting depth is number that is obtained by starting with value of one for the main and adding one to it every time we go from an enclosing to an enclosed procedure. This number is basically a count of how many procedures are there in the referencing environment of the procedure.
Suppose that procedure p at a nesting depth Np calls a procedure at nesting depth Nq. Then the access link in the activation record of procedure q is set up as follows:
if (Nq > Np) then
The access link in the activation record of procedure q is set to point to the activation record of procedure p.
else
if (Nq =Np) then
Copy the access link in the activation record of procedure p into the activation record of procedure q.
else
if (Nq < Np) then
Follow (Np − Nq) links to reach to the activation record, and copy the access link of this activation record into the activation record of procedure q.
The Block Statement
A block is a statement that contains its own local data declarations. Blocks can either be independent—like B1 begin and B1 end, then B2 begin and B2 end—or they can be nested—like B1 begin and B2 begin, then B2 end and B1 end. This nesting property is sometimes called a "block structure". The scope of a declaration in a block-structured language is given by the most closely nested rule:
-
The scope of a declaration in a block B includes B.
-
If a name X is not declared in a block B, then an occurrence of X in B is in the scope of a declaration of X in an enclosing block B′, such that:
-
B′ has a declaration of X, and
-
B′ is more closely nested around B than any other block with a declaration of X.
Block structure can be implemented using stack allocation. Space is allocated for declared names. The block is entered by pushing an activation record, and it is de-allocated when control leaves the block and the activation record is destroyed. That is, a block is treated like a parameter-less procedure, called only at the entry to the block and returned upon exit from the block. An alternative is to allocate storage for a complete procedure body at one time. If there are blocks within the procedure, then an allowance is made for the storage needed by the declarations within the block, as shown in Figure 5. For example, consider the following program structure:
main ()
{
int a;
{
int b;
{
int c;
printf ("% d% d\n", b,c);
}
{
intd;
printf("% d% d\n", b, d);
}
}
printf("% d\n",a);
}
