Code Generation Questions and Answers

Answer: A

A value with no next use in the block need not be kept in a register past its last use. Computing next use by scanning the block backwards is the standard method. The same information also tells the generator when a register may be freed.

Answer: B

Correct answer: backwards from the last instruction to the first

Next use is a statement about the future, so it can only be computed by working backwards from the end of the block. Scanning in reverse, each instruction records what it needs and then updates the information for the instruction before it - the same technique liveness analysis uses.

Answer: C

Together with the address descriptor, which records where each value can be found, it lets the generator avoid reloading a value that is already in a register. Those two tables are the whole state the simple algorithm maintains.

Answer: D

A value may live in a register, in memory, or in both at once. Knowing this lets the generator decide whether a store is needed before a register is reused. Keeping the two descriptors accurate is what makes the simple algorithm correct.

Answer: A

Correct answer: 2 - 4 - 1 - 3

A location for the result is chosen first, since it may determine which register the addition targets. The first operand is then brought into a register, the add is emitted with the second operand wherever it lies, and the descriptors are updated last so that they record where x now is.

Answer: B

Correct answer: chooses a register for a result, spilling one if necessary

When every register is occupied, getreg must decide which value to evict - preferring one already in memory, or one with no next use in the block - and emit a store if the value would otherwise be lost. That decision is the heart of a simple code generator’s register management.

Answer: C

The next block may be reached from elsewhere and cannot assume the contents of registers. Storing live values at the boundary is what makes the per block generation safe. A global allocator avoids much of that traffic by reasoning across blocks.

Answer: D

Both are true and the reason gives the mechanism, and it also explains why global allocation does better. An allocator working over the whole flow graph can keep a value in a register across blocks and avoid the traffic entirely.

Answer: A

Correct answer: the minimum number of registers needed to evaluate that subtree

The label of a node follows from its children: equal labels need one more register than either, unequal labels need the larger of the two. Evaluating the more demanding subtree first then minimises the registers required, which is what the numbering is for.

Answer: B

When the two labels are equal the node is labelled one more than either, so two and two give three. When they differ the node takes the larger of the two labels unchanged. Working a small tree by hand is the quickest way to fix the rule in mind.