Code Optimization Questions and Answers

Answer: C

Correct answer: may miss an optimisation but never enables an unsafe one

Every data flow analysis errs deliberately, and the direction of the error is chosen so that uncertainty costs performance rather than correctness. Being told a variable might be live when it is not merely wastes a register; being told it is dead when it is not corrupts the program.

Answer: D

Dominance is what identifies loop headers and is the basis for finding natural loops. The entry node dominates every node, and every node dominates itself. The relation is computed once and used repeatedly by later passes.

Answer: A

Correct answer: from a node to one of its dominators

A dominator of a node is a node through which every path to it must pass, so an edge back to a dominator closes a cycle in which the target is guaranteed to precede the source. This is what identifies a natural loop, and finding back edges is therefore the first step in every loop transformation.

Answer: B

The definition captures exactly the region controlled by the header. Natural loops are either disjoint or nested, which is what makes them convenient to optimise. Irreducible graphs can produce loops that overlap without nesting.

Answer: C

Back edges in the flow graph reveal the loops whatever construct produced them. A loop built from conditional jumps is optimised exactly as one written with a while statement. The optimiser works from the graph and never sees the source syntax at all.

Answer: D

Programs written with structured control constructs produce reducible graphs. Reducibility makes many analyses simpler and faster, which is one argument against unrestricted jumps. Irreducible graphs can still be analysed, at greater cost.

Answer: A

Such chains are built directly from reaching definitions. A use with exactly one reaching definition that assigns a constant is immediately a candidate for constant propagation. Definition use chains run the other way and support dead code elimination.

Answer: B

Renaming makes the reaching definition immediate rather than something to be computed. Phi functions at join points name the versions arriving along each incoming edge. Converting back out of the form inserts copies that later passes clean up.

Answer: C

Correct answer: removing a computation redundant on some but not all paths

Common subexpression elimination requires the expression to be available on every path, which fails if one branch computes it and another does not. Partial redundancy elimination inserts the computation on the paths lacking it, making it fully redundant at the join, and then removes it - and it subsumes loop invariant code motion as a special case.

Answer: D

A division that would have been skipped must not be executed early if it might trap. Compilers therefore restrict speculative motion to operations that cannot fault. Hardware support for speculation relaxes the restriction on some machines.