All

Question 1

What are static links used for

Answer 1

They are used to implement local variables when nested functions are allowed in a language (stack based machine)

Question 2

How are static links implemented

Answer 2

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

Question 3

When can static linking fail? What’s the solution?

Answer 3

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

Question 4

Why do we need calling conventions for registers?

Answer 4

Otherwise we may overwrite registers or use values from the wrong registers - caller and callee code may use overlapping sets of registers

Question 5

Caller saved register

Answer 5

When a caller saves a register value for later before making a call

Question 6

Callee saved register

Answer 6

The caller can be assured that the callee will leave the register intact

Question 7

When do we use register spilling?

Answer 7

When all the registers are in use

Question 8

What is register spilling?

Answer 8

1. Move some register values to the stack
2. Use registers for computation
3. Restore registers to their original value

Question 9

Register pros/cons

Answer 9

Pro: fast execution
Con: explicit argument location so instructions are longer

Question 10

Stack pros/cons

Answer 10

Pro: implicit argument locations so shorter instructions
Con: slower execution

Question 11

What is inline expansion?

Answer 11

Replace a function call site with the body of the function

Question 12

Inline expansion pros/cons

Answer 12

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

Question 13

What is constant propagation/folding?

Answer 13

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

Question 14

What is peephole optimisation?

Answer 14

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

Question 15

Explain how “e handle f” and “raise e” work

Answer 15

“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”

Question 16

What does the stack look like when we encounter “e handle f” and later “raise v”

Answer 16

1. push a special frame for the handler
2. execute code
3. current frame contains “raise v”
4. “unwind” call stack and replace handle frame with frame for f on top of v

Question 17

What is the root set?

Answer 17

Collection of registers and stack currently in use by program

Question 18

What is reference counting?

Answer 18

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.

Question 19

What is the idea behind tracing and what schemes are tracing schemes?

Answer 19

Find all objects reachable from root set e.g. mark and sweep; copying collection; generational garbage collection.

Question 20

Reference counting pros/cons

Answer 20

Pros: incremental - no long pauses to collect
Cons:
can’t detect cycle => memory leaks
space/time overhead to maintain count

Question 21

What is mark and sweep?

Answer 21

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

Question 22

What is copying collection?

Answer 22

Use two heaps: one used by program, the other unused until GC time

At GC:

1. start at the roots and traverse the reachable data
2. copy reachable data from the active heap to the other heap
3. dead objects are left behind
4. heaps switch roles

Question 23

Copying collection pros/cons

Answer 23

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

Question 24

What is generational copy collection?

Answer 24

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.