CSCE 434 Lecture 28
« previous | Wednesday, October 30, 2013 | next »
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
- return value
- return address
- access link
- (current frame pointer points here)
- caller frame pointer
- 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
- allocate basic frame
- evaluate and store params
- store return address
- store frame pointer
- set frame pointer for child
- jump to child
Return Sequence:
- copy return value from callee
- deallocate basic frame
- restore parameters
Callee
Prolog code
- save registers and state (prepare for itself because caller doesn't know what registers it is going to use)
- extend basic frame for local data
- find static data area
- initialize locals
- fall through to code.
Epilog code
- store and return value
- restore caller state
- unextend basic frame
- restore parent's frame pointer
- 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
- How do we map name into (level, offset) pair?
- use 'block structure symbol table' (get most recent declaration)
- 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k}
- If , it is a local variable
- If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k > \mbox{level}} , we must find Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mbox{level}} 's activation record
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} procedure, we need Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k-1} slots
Allocated on current frame every time new scope is entered
- previous display entries are copied
Footnotes
- ↑ The whole "stack growing down" thing has always confused me!