Code Optimization Questions and Answers

Answer: A

Correct answer: reordering the basic blocks of the whole procedure

Peephole optimisation looks through a sliding window of a few adjacent instructions and knows nothing beyond it. Reordering blocks requires a view of the whole flow graph, so it is a global transformation. The other three - redundant load elimination, jump chaining and unreachable instruction removal - are all decidable within a small window.

Answer: B

Correct answer: facts about the values or expressions holding at each program point

Data flow analysis propagates sets of facts round the flow graph until they stabilise, answering questions such as which definitions reach here, which variables are live, and which expressions are available. Everything a global optimiser does rests on those answers.

Answer: C

Correct answer: there is a path from the definition to the point with no redefinition

Reaching definitions is a forward analysis, and the definition of the property is a path property: some path exists along which the assignment is not overwritten. Note the word some - the analysis is a may analysis, so a definition reaches if it might, which is what makes the result conservative and therefore safe.

Answer: D

Correct answer: its current value may be used along some path from that point

Liveness is a backward analysis and again a may property: the variable is live if any path from here reads it before writing it. Its principal use is register allocation, since two variables that are never live at the same time can share a register, and dead code elimination, since an assignment to a dead variable can be deleted.

Answer: A

Available expressions is a forward analysis with intersection as its meet, because the value must be valid along every path. It is what justifies common subexpression elimination. An expression available on only some paths is a case for partial redundancy elimination.

Answer: B

Direction says whether information flows with or against control, and the meet says whether a fact must hold on all paths or on some. Together they classify every classical problem. A new analysis is usually described by naming its place in the same scheme.

Answer: C

Intersection means all paths must agree, which is what availability and very busy expressions require. Union answers the weaker question of whether any path establishes the fact. Choosing the wrong meet operation produces an analysis that is simply unsound.

Answer: D

Correct answer: iterating until no set changes any further

The equations are recursive round loops, so they are solved by initialising the sets and applying the transfer and meet functions repeatedly until nothing changes. Termination is guaranteed because the sets form a finite lattice and each iteration moves monotonically in one direction, so the process cannot cycle.

Answer: A

Both are true and the reason gives the mechanism, and it is the standard termination argument. Monotone transfer functions over a finite lattice cannot cycle, so the iteration must reach a fixed point in a bounded number of rounds.

Answer: B

Correct answer: the ideal answer, which the iterative solution may only approximate

The meet-over-all-paths solution takes the meet of the facts along every path reaching a point, which is what one would ideally like to know. The iterative algorithm computes the maximum fixed point instead, and the two coincide when the transfer functions distribute over the meet - which they do for many, but not all, analyses.