Access to Non-local data on the Stack in Compiler Design

Nested Procedures

In a programming language that allows for nested procedures (i.e., functions or subroutines defined within other functions), a new activation record gets created for that procedure's variables. It returns an address each time we call a nested procedure.

The activation records for nested procedures are organized in a stack-like data structure, where each stack frame is linked to the activation record of the calling function, forming a chain of activation records.

Accessing Non-Local Data

When a language allows nested procedures, access becomes difficult. For example, in the figure below, p is inside q, so at compile time, it is impossible to determine the position of each activation record. If either of p and q or both are recursive, then there will be a series of activation records.

For p to access a variable or any kind of data declared in q, it requires the activation’s run-time information. Two strategies for accessing non-local data on the stack in Compiler Design are - Access Links and Displays. Let us look at each one of them.

Access Link

Access Links in one activation record are links that are used to refer to the non-local data in other activation records and provide access to it. A chain of access links is formed on the top of the stack and represents the program's scope or static structure.

The chain is a sequence of function activations with progressively lowering depths. The function currently being executed is at the end of the chain and has access to data and procedures of all the activations present in the chain.

The above picture depicts how the stack looks with the activation records of 4 functions and how the access links are connected for various functions depending on their depths and positions.

f1()
{
	f2()
	f3()
	{
		f4()
	}
}

In this, f1() is the function calling all other functions that's why all other function’s access links point to its access link. Then f4() is called in f3().

The cost of lookup and maintenance is variable for access links.

Example

Code in C

int global_var = 5;

void foo()
{
    int x = 1;
    int y = global_var;
    bar();
}

void bar()
{
    int z = 3;
    z=y+z;// How can I access the global variable from here?
}

global_var: A global variable that is defined outside the functions foo() and bar().

x,y: local variables of the function foo()

z: local variable of the function bar()

When we call bar(), a new activation record is created for it which has variables x and y which were declared in it.

When foo() calls bar(), it wants to use y, a non-local bar variable. y is stored in the activation record of foo(). So, we use the chain of activation records to follow the chain until we reach the value of y.

Displays

One of the issues of the access links is that if there are many nested calls of functions, there will be a very long chain of access links that we must follow to reach the non-local data we need. To solve this, we make the use of displays.

Displays are auxiliary arrays that contain a pointer for every nesting depth. At any point, d[i] is the pointer to the activation record which is the highest in the stack for a procedure which is at depth i.

In the above figure, we assume that each function f1(),f2(), f3(), and f4() lies at different depths. d[1] holds the pointer to the activation record for f1(), the only one for that depth. Similarly, there are pointers for each depth.

Now if a procedure requires access to data from another procedure, let's say f2() wants to access some data from f1(), then runtime only searches in activations from d[i] where i is the nesting depth of f1() and follow the pointer.

The cost of lookup and maintenance is constant for displays.

Also see, Cross Compiler

Frequently Asked Questions

How does a compiler handle access to non-local data on the stack?

The compiler generates code to set up an access link in the current stack frame, pointing to the calling function's stack frame or subroutine. This allows nested functions or subroutines to access non-local variables by following the chain of stack frames using access links.

What is the role of access links in accessing non-local data on the stack?

Access links are pointers that follow the chain of stack frames to locate non-local variables. They point to the stack frame of the calling function or subroutine, allowing nested functions or subroutines to access variables in the calling function's stack frame and variables in the stack frames of any other calling functions up the chain.

How does the depth of nesting affect access to non-local data on the stack? 

The depth of nesting refers to the number of levels of nested functions or subroutines. Each level of nesting requires an additional link in the chain of stack frames, which must be followed to access non-local data on the stack. Therefore, deeper levels of nesting can lead to longer chains of stack frames and potentially slower access times.

Conclusion

In summary, access links are used in nested procedures to allow for access to non-local variables. The access link is a special pointer that points to the stack frame of the calling function, and it is used to follow the chain of stack frames to locate the variable's memory location. The depth of nesting refers to the number of levels of nested procedures, and it affects the length of the stack frame chain that must be followed to access non-local variables.

Check out the following blogs:

• Stack Allocation
   
•  cousins of compiler
   
• Phases of Compiler
   
• Application of Stack
   

You can also consider our Mern Stack Course to give your career an edge over others.
Happy Learning!!