Copyright © 2004
Robert W. Hasker

Ch. 6

Activation Records

• issue: how to handle local variables, parameters, return addresses
  • also need to support recursion!
• activation record: all info needed for a function call
  • typically stored as a stack frame
• standard stack frame [see fig. 6.2]
  • static link: used to access local variables of "enclosing" function
  • temporaries: used for expression evaluation, loop limits, switch statements, etc.
  • return address: often before local variables
  • saved registers: restore context of caller when callee finished
• Frame pointer
  • used to simplify access to arguments, local variables, return address
  • VAX-11 & others: stack, frame pointer were both explicit
  • in most cases, can determine location of frame pointer by [stack pointer + offset]
  • RISC architectures: FP probably not explicit
• Registers
  • caller vs. callee save:
    • caller-save: caller saves and restores registers being used
    • callee-save: callee saves and restores registers
  • many machines/calling conventions support both
    • eg MIPS: regs 16-23 are preserved across calls (callee-save); all others are caller-save
• Parameter passing
  • old style: all parameters passed on stack
  • research: few functions > 4 args, very few > 6
    • usual mechanism today: first k args in registers, remainder passed on stack
    • I wonder if the issue has been revisited with OO style?
  • issue: calling another function means these registers have to be saved and restored anyways - is there a real efficiency gain?
    • most procedures are "leaf" procedures (don't call any other procedures)
      • leaf procedures may not need a frame at all!
    • can perform interprocedural register allocation
      • can use different, non-overlapping sets of registers for various calls
    • if parameter is "dead" by the time of the call, won't need to save its register
    • architectures may provide register windows
  • issue: if take address of argument, may need to store that argument in the temporary data section
  • typical solution: allocate space for all args on stack, write values only as needed
  • better solution: drop & operator in C and disallow "varargs"
• return address
  • often stored in register as well
  • call instruction for most modern architectures simply right current location to a register
  • leaf procedures can avoid writing the value to the stack
• local data
  • generally can avoid writing these to the stack
  • typical approach: allocate space for the data on the stack, but use space only if necessary
    • arrays
    • code takes local's address in some way
    • nested function accesses value
    • too much data for available list of registers; need to "spill" registers into frame to make room for some computations

Static Links

• issue: how to access data when functions are nested
  • C: no nesting
  • Pascal, ML: explicit nesting

            procedure a;
              var x: integer;
              procedure b;
                var y: integer;
                begin y := 10 * 10; x := y; end;
              begin b; end;
    

    See book for a more realistic example.
  • Java, C++: inner classes
    • see nested.java
    • had to declare base as final, so not a worst-case example
    • note: seems C++ has even tighter restrictions
• solutions
  • when call a function, pass frame pointer of (statically) enclosing function: static link
    • see book for implementation details
  • global array containing static links; calls and returns involve just a couple of updates, and accessing deeply nested data is cheaper
    • known as a display
  • pass such data as extra arguments to functions: lambda lifting
• which is best?
  • display important for languages in which deeply nested procedures are common
  • static link would work well for Java (but not even clear it's required!)

Frames in our MiniJava Compiler

• Issue: need to abstract frame management from specific architectures
• Textbook suggestion: abstract Frame with operations to
  • determine number of parameters, locals
  • specify whether parameter accessed as register or memory location
  • specify "view shift": how frame shifts when calling a procedure
• temporaries
  • good register allocation may remove most temporaries, but there will always be cases where temporary must be allocated actual space
  • labels
    • need labels for if statements, function entry points, global variables, etc.
    • generic name such as "L123" might be hard to deal with in debugger
    • better: scheme for unique names
      • example for method m in class C: label "C" + "$" + "m"
• static links
  • language-dependent issue: not needed for MiniJava
  • recommendation: treat as extra parameter to each function

Review

• activation records
  • incoming parameters
  • static links/displays: accessing data according to static scoping rules
  • return address
  • local variables
  • temporaries/saved registers
  • parameters for called procedures