COMS W4115
Programming Languages and Translators
Lecture 20: Run-Time Storage Allocation
April 9, 2008

Lecture Outline

1. Review
2. Storage-allocation strategies
3. Activation trees and records
4. Parameter passing mechanisms
5. Calling sequences

1. Review

• Assignment statements
• Arrays
• Boolean expressions
• Flow-of-control statements

2. Storage-Allocation Strategies

• Static allocation
• Storage for all data objects laid out at compile time.
• Names are bound to storage as program is compiled.
• Used in early versions of Fortran.
• Recursion is restricted.
• Size of all data objects must be known at compile time.
• No dynamic data structures can be supported.
• Stack allocation
• Run-time storage is organized as a stack.
• Activation records (ARs) are pushed and popped as activations begin and end.
• Storage for the locals in each call is contained in the AR for that call.
• Used by C and Java.
• Heap allocation
• Allocates and deallocates storage as needed at run time from a data area called a heap.
• Necessary when a called activation outlives the caller.
• Also needed when the values of local names must be retained after an activation ends.

3. Activation Trees and Records

• Consider the quicksort program in Fig. 7.2, p. 431.
• The activation tree in Fig. 7.4 represents the calls made during an execution of quicksort.
• Note that:
  • The sequence of procedure calls corresponds to a preorder traversal of the tree.
  • The sequence of returns corresponds to a postorder travseral.
  • The path from the root to a node N shows the activations that are live at the time N is executing.
• Procedure calls and returns are managed by a control stack.
• On each procedure call, an activation record for that procedure is pushed on the stack. When the call returns, that activation record is popped from the stack.

4. Parameter Passing Mechanisms

• Programming languages differ in how procedures get their arguments.
• We use the term actual parameters to denote the parameters used in the call of a procedure.
• We use the term formal parameters to denote the parameters used in the definition of a procedure.
• Call by value
• Actual parameters are evaluated and their r-values are passed to the callee.
• Used by C.
• "swap" example from C
• Consider swap1(a, b):

      void swap1(int x, int y) {
        int temp;
        temp = x;
        x = y;
        y = temp;
      }
    

• Now consider swap2(&a, &b):

      void swap2(int *px, int *py) {
        int temp;
        temp = *px;
        *px = *py;
        *py = temp;
      }
    

• Call by reference
• Caller passes a pointer to the storage address of each actual parameter
• If parameter is a name or an expression having an l-value, that l-value itself is passed; otherwise, expression is evaluated in a new location and the address of that location is passed.
• Useful for passing large parameters to procedures.
• Used for "ref" parameters in C++.
• Call by name
• Body of procedure is substituted for the call in the caller, with the actual parameters substituted for the formal parameters, with renaming of local names to keep them distinct.

5. Calling Sequences

• Procedure calls are implemented by calling sequences, code that allocates an activation record on the control stack and enters information into its fields.
• A return sequence is code invoked after the call to restore the state of the machine so the calling procedure can continue its execution after the call.
• The code in a calling sequence is usually divided between the calling procedure (the "caller") and the procedure it calls (the "callee").
• Here is one example of how the caller and callee might cooperate in the calling sequence:
• The caller evaluates the actual parameters.
• The caller stores a return address and the old value of the top of the stack into the callee's AR. The caller then updates the value top-of-stack pointer.
• The callee saves the register values and other status information.
• The callee initializes its local data and begins execution.
• In the return sequence:
• The callee places the return value in a known location on the stack.
• The callee restores the value of the top-of-stack pointer to what it was before the call and then branches to the return address that the caller placed on the stack.
• The caller knows where the return value is relative to the current value of the top-of-stack pointer.

6. Reading

• ALSU, Sections 7.1, 7.2