Chapter 9: Error Handling

8.4 STACK ALLOCATION

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.

8.4.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 8.3 shows the format of a typical activation record. Here, the contents of the activation record are accessed using the CEP pointer.

Figure 8.3: The CEP pointer is used to access the contents of the activation record.

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 8.3, 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 (  T   1  ) /*  T   1  is holding the first argument push (  T   2  ) /*  T   2  is holding the second argument . . . push (  T  n   ) /*  T  n   is holding the  n  th 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 8.4.

Call sequence

Object code of the callee

Return sequence

Figure 8.4: Typical callee code segment.

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 

8.4.2 Access to Nonlocal Names

The way that the nonlocals are accessed depends on the scope rules of the language (see Chapter 7). 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 P ₁ such that:

1. The enclosing procedure P ₁ has a declaration of x , and

2. P ₁ 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 P ₁ , and the compiler is required to provision getting the value of x at run time from the most-recent activation record of P ₁ 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 8.5.

Figure 8.5: An activation record that deals with nonlocal name references.

The modified call and return sequence, required for setting up the activation record shown in Figure 8.5, is:

 push ( ) /* for return value push (  T   1  ) /*  T   1  is holding the first argument push (  T   2  ) /*  T   2  is holding the second argument . . . push (  T  n   ) /*  T  n   is holding the  n  th 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 8.6.

Call sequence

Object code of the callee

Return sequence

Figure 8.6: A typical callee segment.

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 

8.4.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 B 1 begin and B 1 end, then B 2 begin and B 2 end ”or they can be nested ”like B 1 begin and B 2 begin, then B 2 end and B 1 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:

1. The scope of a declaration in a block B includes B .

2. 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:

   1. B ² has a declaration of X , and

   2. 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 8.7. 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); } 

a

b

c,d

Figure 8.7: Storage for declared names.