All Flashcards
What are static links used for
They are used to implement local variables when nested functions are allowed in a language (stack based machine)
How are static links implemented
We add a pointer s to a functions stack frame which points to the stack frame of the definer. This allows us to access non-local values that can be found elsewhere in the stack
When can static linking fail? What’s the solution?
When a function is returned as a value as we can lose the “environment” of its free variables from the stack. Instead we need to use closures
Why do we need calling conventions for registers?
Otherwise we may overwrite registers or use values from the wrong registers - caller and callee code may use overlapping sets of registers
Caller saved register
When a caller saves a register value for later before making a call
Callee saved register
The caller can be assured that the callee will leave the register intact
When do we use register spilling?
When all the registers are in use
What is register spilling?
- Move some register values to the stack
- Use registers for computation
- Restore registers to their original value
Register pros/cons
Pro: fast execution
Con: explicit argument location so instructions are longer
Stack pros/cons
Pro: implicit argument locations so shorter instructions
Con: slower execution
What is inline expansion?
Replace a function call site with the body of the function
Inline expansion pros/cons
Pros:
- avoid building activation records at runtime
- may allow further optimisations (constant propagation)
Cons:
- may lead to code bloat
- need to be careful with variable scope
What is constant propagation/folding?
Propagate constants (i.e. if int y = 2; replace y with 2 where it appears in the code) and evaluate simple expressions AT COMPILE TIME
What is peephole optimisation?
Sweep a window over the code sequence looking for instances of simple code patterns that can be rewritten to better code e.g. eliminate useless combinations (push0; pop), improve control flow goto L1 … L1: goto L2 => goto L2 … L1: goto L2
Explain how “e handle f” and “raise e” work
“e handle f”
If e evaluates to a value v “normally” then v is the result of the entire expression
Otherwise if the value v’ is “raised” during evaluation of e the result of the expression is f v’
“raise e”
evaluate expression e to value v then raise v as an exceptional value which can only be “handled”
What does the stack look like when we encounter “e handle f” and later “raise v”
- push a special frame for the handler
- execute code
- current frame contains “raise v”
- “unwind” call stack and replace handle frame with frame for f on top of v
What is the root set?
Collection of registers and stack currently in use by program
What is reference counting?
Keep track of the number of pointers to each object. When the object is created set the count to 1. Every time a new pointer to the object is created, increment the count. Every time an existing pointer to the object is destroyed, decrement the count. When the reference count goes to 0 the object is unreachable garbage.
What is the idea behind tracing and what schemes are tracing schemes?
Find all objects reachable from root set e.g. mark and sweep; copying collection; generational garbage collection.
Reference counting pros/cons
Pros: incremental - no long pauses to collect
Cons:
can’t detect cycle => memory leaks
space/time overhead to maintain count
What is mark and sweep?
Mark phase: depth first traversal of object graph from root to mark live data
Sweep phase: iterate over entire heap adding unmarked data back onto the free list
What is copying collection?
Use two heaps: one used by program, the other unused until GC time
At GC:
- start at the roots and traverse the reachable data
- copy reachable data from the active heap to the other heap
- dead objects are left behind
- heaps switch roles
Copying collection pros/cons
Pros:
simple and collects cycles
run-time proportional to number of live objects
automatic compaction eliminates fragmentation
Cons:
twice as much memory used as program requires
long GC pauses - bad for real-time apps
What is generational copy collection?
First we observe that most new objects “die” very quickly.
Therefore we introduce heaps for different generations of objects:
Old generations are collected less frequently than newer ones.
