CSCE 434 Lecture 28

« previous | Wednesday, October 30, 2013 | next »

Lecture Slides

Procedure Abstraction

Linkage Convention

Caller and callee share same run space, so certain conventions must be followed in order for everything to work correctly.

• entry: establish function environment
• call: preserve function environment
• exit: tear down function environment
• between, addressability and lifetimes

Procedure P:
prolog
...
pre-call

    Procedure Q:
    prolog
    ...
    epilog

post-call
...
eiplog

Activation Records

Also called stack frame

Stack elements in order from bottom to top: (recall that stack grows downward)

1. parameters
2. return value
3. return address
4. access link
5. (current frame pointer points here)
6. caller frame pointer
7. locals

Random notes:

• Call function assembly instruction: jump and link
• stack is fast, but not random access (only accessible via pop operations)
• heap can be slow, but is random access

Responsibilities

Caller

Call Sequence

1. allocate basic frame
2. evaluate and store params
3. store return address
4. store frame pointer
5. set frame pointer for child
6. jump to child

Return Sequence:

1. copy return value from callee
2. deallocate basic frame
3. restore parameters

Callee

Prolog code

1. save registers and state (prepare for itself because caller doesn't know what registers it is going to use)
2. extend basic frame for local data
3. find static data area
4. initialize locals
5. fall through to code.

Epilog code

1. store and return value
2. restore caller state
3. unextend basic frame
4. restore parent's frame pointer
5. jump to return address

Run-Time Storage

code

fixed size

statically allocated

data

fixed size; may be statically allocated

variable-sized data must be dynamically allocated

some data may use malloc in code to dynamically allocate

control stack

dynamic slice of activation tree

return addresses

usually implemented in hardware

Memory Layout: (from low to high)

Code

Static

Heap →

( Free )

← Stack

If stack and heap ever overlap, the world will end.

Organization

downward exposure

called procedures can reference caller's variables

e.g. dynamic scoping

upward exposure

called procedures return reference to its own variables

functinos that return functions

Only downward exposure can be used with frames on run-time stack.

Storage Classes

Addresses computed at compile-time:

Static variables:

• Addresses compiled into code (offsets)
• Usually allocated in program code
• Limited to fixed-size objects
• Control access with naming scheme

Global variables:

• almost identical to static

Linkage editor handles duplicate definitions

Local variables:

• on stack if fixed size, limited lifetime, and unpreserved values

Dynamically Allocated Variables:

• call-by-reference, pointers, non-local lifetimes
• usually explicit allocation
• explicit (free) or implicit (out of scope) deallocation

Nonlocal, global data:

• Should be available everywhere
• naming convention gives address

Lexical nesting

• variables viewed as (level, offset) tuples at compile-time
• store chain of non-local access links
• more exnsive to find at runtime

Access Links

Accessing Non-Local Data Variables are viewed as (lexical level, offset) pairs at compile time.

Variables can chain-link to definition in higher scopes (if they exist)

Traversal of these links is expensive at runtime

1. How do we map name into (level, offset) pair?
   • use 'block structure symbol table' (get most recent declaration)
2. Given (level, offset) pair, what is the address?
   • access links and displays (later)

To find value specified by (level,offset), we need current procedure level $k$

• If ${\mbox{level}}=k$, it is a local variable
• If $k>{\mbox{level}}$, we must find ${\mbox{level}}$'s activation record
• $k<{\mbox{level}}$ can never occur

Displays

Improve runtime access costs

• Table of links for lower levels
• Lookup is index from known offset
• Takes small setup time
• Single display (bad idea) or one per frame
• For a level $k$ procedure, we need $k-1$ slots

Allocated on current frame every time new scope is entered

• previous display entries are copied