Implementation of Simple Stack Allocation Scheme

Stack Allocation scheme is the simplest Run-Time Storage Management Technique. The storage is allocated sequentially in the stack beginning at one end. Storage should be freed in the reverse order of allocation so that a block of storage being released is always at the top of the stack.

A program consists of data and procedures. On execution of each procedure, some amount of memory is occupied, which has information regarding the procedure, i.e., its actual parameters, number of arguments, return address, return values & local data, etc. That part of memory is the Activation Record of that procedure.

Activation Record

An Activation Record is a data structure that is activated/ created when a procedure/function is invoked, and it contains the following information about the function.

Activation Record in 'C' language consist of

• Actual Parameters
• Number of Arguments
• Return Address
• Return Value
• Old Stack Pointer (SP)
• Local Data in a function or procedure

Here, Old SP stores the value of stack pointer of Activation Record of procedure which has called this procedure which leads to the generation of this Activation Record, i.e., It is a pointer to the activation record of the caller.

Two pointers are required for Stack Allocation Scheme −

• top− It points to the top of the stack. top points to the top of the top activation record. In the figure, the top pointer will point to the top of the C Activation Record.
• Stack Pointer (SP)− It points to the activation record of the currently active procedure.

Actual Parameter− It is used by the calling procedure to supply parameters to the called procedure.

Return value− This field is used by the called procedure to return a value to the calling procedure. The size of each of the above fields is determined at the time when the procedure is called. The size of almost all the fields can be determined at compilation time.

Stack Allocation of Procedure Calls

It can analysis on how the memory is allocated at runtime when a procedure is called & when the value from the procedure is returned.

Consider a procedure P(x₁, x₂, x₃ … … x_n).Three address code statement for the call of this procedure will be

param x₁

param x₂

…………….

param x_n

call P, n

where ???? ?, ? → calls the procedure P with n number of arguments.

????? ? → refers to passing actual parameter x.

Execution of all the following statements related to the procedure will perform stack allocation at runtime.

• ????? ? ? Passing actual parameter x.
• ???? ?, ?− calling procedure P with n arguments.
• ?????????− The first statement of procedure
• ??????(?????)− When the value is returned.
• ???− Last statement of procedure.