Code Generation Questions and Answers

Answer: C

Correct answer: free one more register for allocation to values

The frame pointer occupies a register solely to make the frame layout easy to follow, and where the frame size is known at compile time the stack pointer alone will serve. Omitting it recovers a register, which on a machine with few of them is worth having - at the cost of making stack traces harder to reconstruct.

Answer: D

Machines with a scaled index addressing mode can perform the computation as part of the access. Where such a mode is absent the generator must emit explicit arithmetic. Strength reduction can often replace the multiplication with an addition.

Answer: A

One instruction then performs the multiplication, the addition and the access. Exploiting such modes is a large part of what makes instruction selection worth doing carefully. A generator that ignores them emits three instructions where one would serve.

Answer: B

Correct answer: False

The machine has whatever registers it has, and running out is the central difficulty of the back end. An intermediate representation may assume unlimited virtual registers, but the code generator must map them onto the real set and spill to memory where it cannot - which is exactly what register allocation is.

Answer: C

Generating code against an unlimited set separates selection from allocation. The allocator afterwards maps them onto the real set, spilling wherever the mapping does not fit. Separating the two concerns makes each of them considerably simpler to write.

Answer: D

The comparison sets condition codes or produces a boolean, and the jump acts on it. Which form is used depends on how the target machine expresses comparisons. Some machines produce a boolean in a register instead of setting flags.

Answer: A

If the flags already reflect the value, the comparison is redundant. Tracking the state of the condition codes is a small but worthwhile part of a good back end. The saving is one instruction per comparison, which adds up inside a loop.

Answer: B

Correct answer: keeping the loop control variable in a register

The control variable is read and written on every iteration, so it is the value that most repays a register. Storing it to memory each time round would add two memory references per iteration, and recomputing the bound would add more - both being work the loop multiplies.

Answer: C

Correct answer: Both A and R are true, and R is the correct explanation of A

Both are true and the reason gives the mechanism. A use inside a loop costs whatever it costs multiplied by the trip count, so the allocator weights it accordingly - commonly by ten per level of nesting. That weighting is what makes the allocator spill the outer values and keep the inner ones.

Answer: D

Two levels of nesting give ten times ten, that is one hundred. The heuristic is crude but reflects the fact that inner loop code dominates execution time in most programs. Profile data replaces the heuristic with a measurement when it is available.