Code Optimization Questions and Answers

Answer: C

Independence between the iterations must first be established. Data dependences, unknown alignment and unclear trip counts are the usual obstacles to applying it. Programmers sometimes supply hints to remove those obstacles.

Answer: D

If one iteration needs a value produced by an earlier one, they cannot run together. Dependence analysis is what establishes whether such a relationship exists. A reduction such as a running sum is a dependence that can often be broken.

Answer: A

Correct answer: works across the whole procedure rather than one block

Local value numbering assigns a number to each distinct computed value within a block and reuses it where the same value recurs. The global version extends this across the whole procedure, which requires reasoning about values flowing along different control paths - commonly done over static single assignment form, though that is a convenience rather than a requirement.

Answer: B

Hoisting to a common dominator reduces code size by keeping one copy where several existed. It is chiefly a size optimisation rather than a speed one. The dominator relation is what identifies the safe place to put the single copy.

Answer: C

Writing the transformation once at that level pays off across every back end. This is one of the main practical arguments for having an intermediate representation at all. The alternative is reimplementing every transformation for each target.

Answer: D

Speed is worthless if the answer changes, so every pass carries with it the conditions under which it preserves meaning. Where the analysis cannot establish those conditions the transformation is simply not applied, which costs an opportunity rather than correctness.

Answer: A

The interactions between passes are numerous and hard to enumerate, so a fault may lie dormant until one particular sequence of transformations meets one particular shape of code. Randomised program generation and differential testing against other compilers are the usual responses, since a miscompilation that surfaces rarely can be extremely costly.

Answer: B

Correct answer: a combination of many modest transformations rather than any one

No single transformation dominates. The gains come from many modest ones applied together and reinforcing each other - inlining exposing constants, propagation exposing dead code, code motion exposing common subexpressions. This is also why the phase ordering problem matters so much and why any one optimisation pushed to an extreme tends to lose more than it gains.

Answer: B

Live variable analysis is used for Register assignment to variables.

A variable is live at a point if its current value may be used later. Two variables that are never live at the same time can share a register, so register allocation builds an interference graph from liveness information and colours it with the available registers. Liveness also tells the allocator when a register can be freed or a value need not be stored back.

Strength reduction replaces expensive operations such as multiplication by cheaper ones such as addition, usually in loops with induction variables. Constant folding evaluates constant expressions at compile time. Run-time function call management concerns activation records. None of these depends on liveness.

Answer: D

The redundant expressions are B4: { g * k } and B5: { }.

An expression is redundant in a block if it is available there: computed on every path into the block, with none of its operands changed afterwards.

• g * k is computed in both B2 and B3, the only predecessors of B4, and neither block changes g or k afterwards, so it is available in B4.
• b + i is computed in B1, but B3 then assigns b = c + m, so on the path through B3 the value is stale. It is not available in B4.
• c + m is computed only in B3. On the path B1, B2, B4, B5 it is never computed, so it is not available in B5.

The options listing b + i or c + m each ignore one of these paths.