COMPILER DESIGN AND SYSTEM SOFTWARE (18UCSC502) CTA ASSIGNMENT TOPIC: ACCESS TO NON-LOCAL DATA ON STACK MADE BY: RITESH S. KULKARNI 2SD19CS088

COMPILER DESIGN AND SYSTEM SOFTWARE (18UCSC502) CTA ASSIGNMENT TOPIC: ACCESS TO NON-LOCAL DATA ON STACK MADE BY: RITESH S. KULKARNI 2SD19CS088.

INTRODUCTION. It is very important to know that how procedures access their data, specially the mechanism for finding data used within a procedure p but that does not belong to p. Access becomes more complicated in languages where procedures can be declared inside other procedures. We therefore begin with the simple case of C functions, and then introduce a language, ML, that permits both nested function declarations and functions as "first-class objects" that is, functions can take functions as arguments and return functions as values. This capability can be supported by modifying the implementation of the runtime stack..

1. Data Access Without Nested Procedures. I n the C family of languages, all variables are defined either within a single function or outside any function ("globally"). Most importantly, it is impossible to declare one procedure whose scope is entirely within another procedure. Rather, a global variable v has a scope consisting of all the functions that follow the declaration of v, except where there is a local definition of the identifier v. Variables declared within a function have a scope consisting of that function only, or part of it, if the function has nested blocks..

Continued… For languages that do not allow nested procedure declarations, allocation of storage for variables and access to those variables is simple: Global variables are allocated static storage. The locations of these variables remain fixed and are known at compile time. So to access any variable that is not local to the currently executing procedure, we simply use the statically determined address. Any other name must be local to the activation at the top of the stack. We may access these variables through the topsp pointer of the stack..

2. Issues With Nested Procedures. Access becomes far more complicated when a language allows procedure declarations to be nested and also uses the normal static scoping rule; that is, a procedure can access variables of the procedures whose declarations surround its own declaration, following the nested scoping rule described for blocks in Section 1.6.3. The reason is that knowing at compile time that the declaration of p is immediately nested within q does not tell us the relative positions of their activation records at run time. In fact, since either p or q or both may be recursive, there may be several activation records of p and/or q on the stack. Finding the declaration that applies to a nonlocal name x in a nested procedure p is a static decision; it can be done by an extension of the static-scope rule for blocks. Suppose x is declared in the enclosing procedure q. Finding the relevant activation of q from an activation of p is a dynamic decision; it requires additional run-time information about activations. One possible solution to this problem is to use "access links,".

3. A Language With Nested Procedure Declarations.

Continued….. ML is a functional language, meaning that variables, once declared and initialized, are not changed. There are only a few exceptions, such as the array, whose elements can be changed by special function calls. Variables are defined, and have their unchangeable values initialized, by a statement of the form: v a l (name) = (expression) Functions are defined using the syntax: fun (name) ( (arguments) ) = (body).

4. Nesting Depth. Let us give nesting depth 1 to procedures that are not nested within any other procedure. For example, all C functions are at nesting depth 1. However, if a procedure p is defined immediately within a procedure at nesting depth i , then give p the nesting depth i +. Example: Figure 1 contains a sketch in ML of our running quicksort example. The only function at nesting depth 1 is the outermost function, sort, which reads an array of 9 integers and sorts them using the quicksort algorithm. Defined within sort, at line (2), is the array a itself. Notice the form of the ML declaration. The first argument of array says we want the array to have 11 elements; all ML arrays are indexed by integers starting with 0. The second argument of array says that initially, all elements of the array a hold the value 0. This choice of initial value lets the ML compiler deduce that a is an integer array, since 0 is an integer, so we never have to declare a type for a..

Continued…. Fig 1: A version of quicksorts , using ML.

Continued….. Lines (7) through (11) show some of the detail of quicksort. Local value v, the pivot for the partition, is declared at line (8). Function partition is defined at line (9). In line (10) we suggest that partition accesses both the array a and the pivot value v, and also calls the function exchange. Since partition is defined immediately within a function at nesting depth 2, it is at depth 3. Line (11) suggests that quicksort accesses variables a and v, the function partition, and itself recursively. Line (12) suggests that the outer function sort accesses a and calls the two procedures readArray and quicksort.

5. Access Links. A direct implementation of the normal static scope rule for nested functions is obtained by adding a pointer called the access link to each activation record. If procedure p is nested immediately within procedure q in the source code, then the access link in any activation of p points to the most recent activation of q. Note: nesting depth of q must be exactly one less than the nesting depth of p. Access links form a chain from the activation record at the top of the stack to a sequence of activations at progressively lower nesting depths. Along this chain are all the activations whose data and procedures are accessible to the currently executing procedure..

6. Manipulating Access Links. How are access links determined? The simple case occurs when a procedure call is to a particular procedure whose name is given explicitly in the procedure call. The harder case is when the call is to a procedure-parameter; in that case, the particular procedure being called is not known until run time, and the nesting depth of the called procedure may differ in different executions of the call. Thus, let us first consider what should happen when a procedure q calls procedure p, explicitly..

7. Access Links for Procedure Parameters. When a procedure p is passed to another procedure q as a parameter, and q then calls its parameter (and therefore calls p in this activation of q), it is possible that q does not know the context in which p appears in the program. If so, it is impossible for q to know how to set the access link for p. The solution to this problem is as follows: when procedures are used as parameters, the caller needs to pass, along with the name of the procedure-parameter, the proper access link for that parameter. The caller always knows the link, since if p is passed by procedure r as an actual parameter, then p must be a name accessible to r, and therefore, r can determine the access link for p exactly as if p were being called by r directly..

8. Displays. One problem with the access-link approach to nonlocal data is that if the nesting depth gets large, we may have to follow long chains of links to reach the data we need. A more efficient implementation uses an auxiliary array d, called the display, which consists of one pointer for each nesting depth. We arrange that, at all times, d[ i ] is a pointer to the highest activation record on the stack for any procedure at nesting depth i . The advantage of using a display is that if procedure p is executing, and it needs to access element x belonging to some procedure q, we need to look only in d[ i ], where i is the nesting depth of q; we follow the pointer d[ i ] to the activation record for q, wherein x is found at a known offset. The compiler knows what i is, so it can generate code to access x using d[ i ] and the offset of x from the top of the activation record for q. Thus, the code never needs to follow a long chain of access links..

Continued….. In order to maintain the display correctly, we need to save previous values of display entries in new activation records. If procedure p at depth n p is called, and its activation record is not the first on the stack for a procedure at depth n p , then the activation record for p needs to hold the previous value of d[n p ], while d[n p ] itself is set to point to this activation of p. When p returns, and its activation record is removed from the stack, we restore d[n p ] to have its value prior to the call of p..