Code Generation Questions and Answers

Answer: C

Unequal labels mean the larger subtree can be evaluated first and its result held in one register while the smaller is evaluated, so the maximum is unchanged at three. Reversing the order would have required a fourth register.

Answer: D

Holding one register while evaluating the smaller subtree costs less than the reverse order. The saving is exactly what makes the labelling worth computing at all. On a machine with few registers the difference can decide whether spilling occurs.

Answer: A

Sharing turns the tree into a graph and the optimality argument no longer holds. The method also assumes a uniform register set with no special purpose registers. Real machines often violate both assumptions, so the result is a useful guide rather than a rule.

Answer: B

Reading a value before it has been written gives the wrong answer, not a stall. Dependences are therefore hard constraints on the schedule, while latencies are merely costs the scheduler tries to hide by filling the gaps with independent work.

Answer: C

True dependences, where one reads what the other wrote, are the fundamental constraint. Anti and output dependences arise from reusing names and can often be removed by renaming. Only the true dependence reflects an actual flow of data.

Answer: D

Only the true dependence reflects real data flow. The other two arise from reusing a name and can often be removed by giving one of the instructions a fresh destination. Static single assignment form removes them all by construction.

Answer: A

Both are true and the reason gives the mechanism, and this is one of the attractions of static single assignment form. Giving each write its own name leaves only the true dependences, which the schedule genuinely must respect.

Answer: B

Correct answer: repeatedly issuing a ready instruction chosen by a priority rule

List scheduling maintains the set of instructions whose operands are available and picks one by a heuristic - usually the longest path to the end of the block. It is greedy and not optimal, but optimal scheduling is NP-hard and list scheduling comes close enough at a fraction of the cost.

Answer: C

A longer schedule keeps more values live at once and so needs more registers, which may force spilling. Doing allocation first instead constrains the schedule that can be produced. Some compilers interleave the two rather than choosing an order.

Answer: D

Correct answer: overlaps instructions from successive loop iterations

Software pipelining starts the next iteration before the current one has finished, so the long-latency operations of one iteration overlap the work of another. The result is a steady-state kernel with a prologue and epilogue, and it keeps a deep pipeline full where simple unrolling would not.