Chapter 6
Activation Records

OVERVIEW

Procedure data typically includes parameters, local, instance (field) and global variables; this represents the set of data accessible to the procedure. The physical location of the data, whether in memory or registers, is maintained at run-time in an activation record. This record structure is normally defined at compile time.

Many language such as C and Java place activation records in a LIFO (stack) in the order of function calls:

• The activation record is constructed (allocated and filled in with data) at run-time, some parts by the caller and other by the callee function.
• The callee accesses the data.
• On return the activation record is deallocated.

Functions in languages such as ML are treated as general data, can be bound to a variable, passed as parameters, and returned as a function result. ML, supports function nesting, where one function can be nested within the scope or another, for example:

fun f( x ) =     let         fun g( y ) = x + 2;     in         g    end;

fun f x  =     let fun g y = x + y;     in         g    end; g 4;       Error, g not visible in current scope f 3;        Returns a function: fn y => 3+y; (f 3) 4;   Returns 7

• g 4; function g is defined within f and cannot be called from outside f as illustrated by the Error case.
• f 3; returns what g is bound to, a function definition.
• (f 3) 4; returns the function g is bound to in the environment of f, then binds 4->y and returns the result 7.

The following presents general issues of generating activation record definitions and details for the Java Virtual Machine (JVM).

6.1 STACK FRAMES

Problem - Memory accesses during a program execution are costly. A key compiler goal is to reduce the number of memory accesses.

Although a stack matches the LIFO allocation and deallocation of activation records, a strict stack using push and pop is not practical as data in the activation record is often accessed repeatedly and randomly at locations other than the top of stack (TOS). Pushing and popping to access data not at TOS would cause excessive memory accesses.

Stack pointer - References memory relative to the last push or pop instruction (on Intel, the eSp, and similar CPU's CALL, INT and other instructions also affect).

Frame pointer - A frame pointer is typically a register that references memory, Intel CPU's have the eBp register. The frame pointer is typically unaffected by push and pop instructions so as to remain fixed during a function execution.

General Rules for C++ Functions

Using functions requires following specific rules or protocol by both the caller and the callee. For MicroSoft C++ on the Intel processor, the rules can be summarized by the following:
 

Caller	Callee
Save any necessary registers and flags. Push parameters on the stack in right to left order. Call the function. Remove parameters from stack by adding to eSp number bytes pushed. Restore saved registers and flags.	Save eBp and any segment registers. Point eBp to parameters on stack. Access the parameters on the stack. Modify Al, Ax, eAx or eDx:eAx to return a result. Restore eBp and any segment registers. Return.

Call-by-Value versus Call-by-Reference

• Call-by-value - The value of the caller's parameter is passed to the function parameter. Since this is a copy of the caller's parameter, any changes made to the function parameter are isolated. In the following diagram on left side, the value 3 of B is passed to Q.
   
• Call-by-reference - The reference (offset location) of the caller's parameter is passed to the function parameter. The reference to the caller's parameter location allows changes by the function. In the following diagram on right side, the reference 0108 to B is passed to Q.

The following figure illustrates the difference between value (left figure) and reference (right figure) passing in the program examples that follow later. In value passing the function does not have access to the original parameter, in reference passing the reference allows indirect access to the caller's parameters.
 

Call by Value                    Call by Reference

Value int X, B, C; int Max (int Q, int R)  {    if (Q > R)       return Q;    else return R;  } void main(void) {    B=3; C=8;    X = Max( B, C );         } Reference int X, B, C; int Max (int &Q, int &R)  { if (Q > R) return Q; else return R;  } void main(void) { B=3; C=8; X = Max( B, C );          }

Call-by-value and reference Assembly

.data 000000000 X dd ? 000000004 C dd 8 000000008 B dd 3 .code Main Proc Near ;; Push B ;; Highest=Max(B,C) Push offset C Call Max Add eSp, 8 ;; Remove B and C Mov X, eAx Push 0 ;; Stop Call ExitProcess Main Endp

Max Proc Near ; int Max( int Q, int &R) { ;; ___________ Assuming that the call was ;; | | Max( B, C ); the stack ;; |___________| appears at left after the ;; Q | B = 3 | <- eBp+12 instruction sequence: ;; |___________| ;; R |&C=00000004| <- eBp+8 Push eBp ;; |___________| Mov eBp, eSp ;; |Return Addr| <- eBp+4 ;; |___________| ;; | Old eBp | <- eBp = eSp ;; |___________| Push eBp ;; Save Caller's Frame Ptr Mov eBp, eSp ;; New Frame Ptr for Max Mov eAx, [eBp+12] Ifa: Mov eBx, [eBp+8] Cmp [eBx], eAx ;; if (Q > R) Jg Thena Jmp Elsea Thena: Mov eAx, [eBx] ;; eAx = Q; Jmp EndIfa Elsea: Mov eAx, [eBp+12];; else eAx = R; EndIfa: Pop eBp ;; Restore Frame Pointer Ret ;; Return maximum in eAx Max Endp End Main

 

ACTIVATION RECORD OVERVIEW

• Parameter passing
• Static Activation records
• Dynamic Activation records
• Statically Nested Scope and Links

 

REGISTERS

• Shared by all routines
• Saving/restoring requires memory accesses
• Either caller or callee can save and restore or a mixed approach
  • MicroSoft C++ on Intel requires
    • caller to save any register for restore on return from CALL.
    • callee to save and restore frame pointer and segment registers
    • Makes sense as only caller knows which registers are in use at time of call.
• MIPS
  • Registers 16-23 are callee-saved
  • All others are caller-saved
• A local variable not needed after return should be placed in caller-save registers but not saved, reduces the number of memory accesses
• Careful choice of registers for variables can significantly reduce memory accesses and improve execution performance of compiled code.

 

PARAMETER PASSING

1970 - Machine design used stack for parameter passing (Intel)

• Dynamic - Can handle any number of parameters, even variable from one call to next
• Wasteful
  • Call by value requires at least 2 memory accesses:
    1. caller - copy value to stack memory
    2. callee - access stack memory value.
  • Call by reference requires at least 3 memory accesses
    1. caller - copy memory reference to stack
    2. callee - copy reference from stack memory to reference register (e.g. eSi)
    3. callee - dereference register to access memory
  • Most functions have 4 or less parameters
  • Almost none have more than 6.
  • The majority of the time, parameters could be passed in registers without any memory accesses
    
        f(p1, p2, p3, ..., p6) -> f(r1, r2, r3, ..., r6)

Problem - Passing parameters in registers still requires saving and restoring on calls, no savings over use of stack

• Leafs - most functions are leaf functions
  • do not call other functions
  • do not need to save registers
  • may not need frame (e.g. all locals held in registers)
• Assume on average most call 0-2 functions, can describe as a binary tree of calls

  Example: Fibonacci
   

  int Fib(int n) {     if (n == 1) return 1;     if (n == 2) return 1;     return Fib(n-1) + Fib(n-2); } void main(void) {     cout << Fib(5); }

  Tree of recursive calls for Fib(5)

   

• Analyze function calls to allocate registers to not conflict.
  • f(r₁) call h(r₂) where r₁ would not be changed by h
• If f is finished with parameter in r₁ by h(r₂), f does not need to save r₁
• Some architectures have register windows allowing new set of registers to be allocated for each function call without memory accesses.

RETURN ADDRESS

• Intel - CALL pushes return address onto stack, RETURN pops return address into IP; requires memory access for each and stack pointer to be correctly positioned.
• Modern architecture - Better to pass return in a designated register, a non-leaf function may need to save on stack but leaf function would not

FRAME-RESIDENT VARIABLES

Modern architectures support use of registers for parameters, return address and locals rather than frame in memory

Variables written to frame when:

• pass by reference since must have memory address in frame
• local variable accessed by inner function, although register allocation over function boundaries can sometimes keep in register
• value to big for a register but can use multiple registers
• array parameter which is in many languages (C++) a reference anyway. Pointer arithmetic used to access array components
• register conflict though can often copy to another to avoid saving to memory
• more locals and parameters than registers, some are spilled into frame memory

Escapes - variables escapes if passed by reference, address take (C & operator) or accessed from inner function - requires frame memory

• Ideally could assign location - either register or frame - at point variable declared
• Reality is generally not clear at declaration how variable is used - whether passed by reference later
• Solution is to provisionally assign locations to all formals and locals - decide later which can go in registers

6.2 FRAMES IN MiniJava

The target machine for our project will be the JVM, discussed separately from the more general discussion of the text.

• Attempt to implement frames independent of architecture but assume frame is on a stack
• Create abstraction of machine-independent Frame
• Architectural details implemented in extension of Frame specific to an architecture (e.g. Intel, Sparc, etc.)