Implementing Subprograms Notes

The General Semantics of Calls and Returns

  • Subprogram Linkage: This term refers to the combined operations of calling a subprogram and returning from it.

  • General Semantics of Subprogram Calls:     - Handling of parameter passing methods.     - Allocation of stack-dynamic local variables.     - Saving the execution status of the calling program unit.     - Management of the transfer of control and arrangement for the return.     - If subprogram nesting is supported, setup must be arranged for access to nonlocal variables.

  • General Semantics of Subprogram Returns:     - Parameters in in mode and inout mode must have their values returned (specifically inout and out result transfers).     - Deallocation of stack-dynamic local variables.     - Restoration of the execution status of the caller.     - Transfer of control back to the calling unit.

Implementing "Simple" Subprograms

  • Call Semantics:     - Save the execution status of the caller.     - Pass the parameters.     - Pass the return address to the called subprogram.     - Transfer control to the called subprogram.

  • Return Semantics:     - If pass-by-value-result or out mode parameters are utilized, the current values of those parameters must be moved to their corresponding actual parameters.     - If the subprogram is a function, the functional value must be moved to a location where the caller can access it.     - Restore the execution status of the caller.     - Transfer control back to the caller.

  • Required Storage Elements:     - Status information.     - Parameters.     - Return address.     - Functional values (for functions).

  • Structural Components:     - A subprogram consists of two separate parts: the actual code (static) and the non-code part (dynamic data such as local variables).     - Activation Record: The format or layout of the non-code part of an executing subprogram.     - Activation Record Instance (ARI): A concrete example of an activation record; the specific collection of data for a particular activation of a subprogram.

  • Activation Record Layout for "Simple" Subprograms:     - Local variables.     - Parameters.     - Return address.

  • Memory Layout during Execution:     - For a program with a MAIN unit and subprograms A and B, the memory contains the code for each and a dedicated static activation record for each containing local variables, parameters, and return addresses.

Implementing Subprograms with Stack-Dynamic Local Variables

  • Complexity: These require a more complex activation record because the compiler must generate code for implicit allocation and deallocation of local variables.

  • Recursion Support: Implementation must support recursion, which introduces the possibility of multiple simultaneous activations of the same subprogram.

  • Typical Activation Record Structure:     - Local variables.     - Parameters.     - Dynamic link: Points to the top of an instance of the activation record of the caller.     - Return address.

  • Core Characteristics:     - The activation record format is static, but the size of its instances may be dynamic.     - Activation record instances are dynamically created upon a subprogram call.     - Instances reside on the run-time stack.

  • Environment Pointer (EP):     - Must be maintained by the run-time system.     - It always points at the base of the activation record instance of the currently executing program unit.

Revised Semantic Call and Return Actions

  • Caller Actions:     1. Create an activation record instance.     2. Save the execution status of the current program unit.     3. Compute and pass the parameters.     4. Pass the return address to the called subprogram.     5. Transfer control to the called subprogram.

  • Prologue Actions of the Called Subprogram:     1. Save the old EP in the stack as the dynamic link and create the new value for EP.     2. Allocate space for local variables.

  • Epilogue Actions of the Called Subprogram:     1. If pass-by-value-result or out-mode parameters exist, move current values to corresponding actual parameters.     2. If it is a function, move the return value to a place accessible to the caller.     3. Restore the stack pointer (SPSP) by setting it to the value of the current EP−1EP - 1.     4. Set the EP to the value of the old dynamic link.     5. Restore the execution status of the caller.     6. Transfer control back to the caller.

Dynamic Chain and Variable Access

  • Dynamic Chain (Call Chain): The collection of dynamic links currently in the stack.

  • Local Offset: Local variables are accessed via their offset from the beginning of the activation record (the address in the EP).

  • Determining Offsets: The local_offset of a local variable can be determined by the compiler at compile time.

  • Recursive Example Analysis: In a factorial(3) call sequence:     - The main unit calls factorial(3). This creates the first ARI with n=3n = 3.     - This calls factorial(2), creating a second ARI with n=2n = 2.     - This calls factorial(1), creating a third ARI with n=1n = 1.     - As returns occur, the functional value (e.g., 1, then 2, then 6) is placed in the ARI before the record is popped from the stack.

Nested Subprograms and Static Scoping

  • Supported Languages: Fortran 95+, Ada, Python, JavaScript, Ruby, and Swift.

  • Non-local Access Process:     1. Find the correct activation record instance on the stack.     2. Determine the correct offset within that instance.

  • Static Chain: A chain of static links that connects activation record instances to their static ancestors.     - The static link in an ARI for subprogram A points to an ARI of A's static parent.

  • Static_depth: An integer associated with a static scope representing its depth of nesting.

  • Chain_offset (Nesting_depth): The difference between the static_depth of the reference and the static_depth of the scope where the variable is declared.

  • Reference Representation: A pair consisting of (chain_offset, local_offset).

  • Example Reference (JavaScript):     - main invokes bigsub (contains a, b, c).     - bigsub invokes sub2 (contains a, d).     - sub2 invokes sub3 (contains c, e).     - sub3 invokes sub1 (contains a, d).     - At Position 1 in sub1, a reference a = b + c is made.

  • Static Chain Maintenance:     - On a call, the ARI is built; the dynamic link is the old stack top pointer.     - The static link must point to the most recent ARI of the static parent.     - Methods: Searching the dynamic chain or treating subprogram calls/definitions like variable references.

  • Evaluation of Static Chains:     - Problem 1: Nonlocal references are slow if the nesting depth is large.     - Problem 2: Time-critical code is difficult because costs of nonlocal references are hard to determine, and code changes affecting nesting depth change the execution cost.

Implementing Blocks

  • Definition: Blocks are user-specified local scopes for variables (e.g., { int temp; ... } in C).

  • Lifetime: The lifetime of a variable inside a block (like temp) begins when control enters the block.

  • Implementation Methods:     1. As Subprograms: Treat blocks as parameter-less subprograms that are always called from the same location, each with its own ARI.     2. Static Allocation within ARI: Since maximum storage for a block is statically determinable, space can be allocated immediately after the local variables in the activation record of the containing subprogram.

Implementing Dynamic Scoping

  • Deep Access: Non-local references are found by searching the ARI instances on the dynamic chain.     - Requires variable names to be stored in the ARI.     - The length of the chain cannot be determined at compile time.

  • Shallow Access: Local variables are placed in a central location.     - Method 1: Maintain one stack for each variable name.     - Method 2: Maintain a central table with an entry for every variable name in the program.