Code Optimization Questions and Answers

Answer: A

The live variables at block exits are B1:{a, b, c, e, f}, B2:{d, e}, B3:{b, c, e, f}, B4:∅.

Liveness flows backwards: OUT(B) is the union of IN over B's successors, and IN(B) = USE(B) ∪ (OUT(B) - DEF(B)). The edges are B1 → B2, B1 → B3, B3 → B1 and B2 → B4.

• B4 (g = d + e) leads to EXIT, and g is never used: OUT(B4) = ∅, IN(B4) = {d, e}.
• B2 (d = a + e): OUT(B2) = IN(B4) = {d, e}; IN(B2) = {a, e}.
• B1 (a = b + c) and B3 (e = a + f) form a loop. Iterating to a fixed point: IN(B1) = {b, c, e, f} and IN(B3) = {a, b, c, f}.
• OUT(B1) = IN(B2) ∪ IN(B3) = {a, b, c, e, f}; OUT(B3) = IN(B1) = {b, c, e, f}.

The options with B1:∅ ignore that a is used in both successors of B1. The option with B3:{c, e, f} drops b, which is live because B1, reached from B3, uses it.

Answer: D

The live sets at block exits are B1: {a, i, j}, B2: {a, j}, B3: {a, j}, B4: {a, i, j}.

A variable is live at a point if some path from there uses it before redefining it. Work backwards from the uses, assuming nothing is live at EXIT:

• B2 uses i and j (i = i + 1, j = j - 1) before defining them, so both are live on entry to B2.
• B4 uses a, then redefines i. Its successors are B2 and EXIT, so live-out of B4 = live-in of B2.
• B3 defines a and uses nothing; B2 flows to B3 and B4.

Solving: live-in(B4) = {a} plus (live-out(B4) minus {i}) = {a, j}; live-in(B3) = {a, j} minus {a} = {j}; live-out(B2) = {j} plus {a, j} = {a, j}; live-in(B2) = {i, j} plus ({a, j} minus {i, j}) = {a, i, j}, which is live-out of both B1 and B4. B3's exit set is live-in(B4) = {a, j}.

The first two options drop i and j at B1's exit although B2 reads them at once. The third keeps i live after B2, but i is redefined in B4 before any use on that path.

Answer: B

The order in which statements are executed is the Control flow.

Control flow is the sequence in which a program's statements, instructions or function calls are executed, shaped by conditionals, loops, jumps and calls. Compilers represent it as a control flow graph.

Data flow concerns how values move between definitions and uses, register allocation assigns variables to registers, and instruction scheduling reorders machine instructions for the pipeline.

Answer: D

Loop unrolling aims at expanding the body of a loop to reduce overhead and improve parallelism.

Unrolling replicates the loop body several times and adjusts the loop counter, so the test, increment and branch are executed less often. The longer straight-line body also gives the scheduler more independent instructions to overlap.

It does not reduce the number of loops in the program, it does not remove conditionals inside the body, and it makes the loop larger, not smaller.

Answer: C

Constant folding means folding constant expressions during compilation.

When an expression's operands are all known at compile time, the compiler evaluates it once and replaces it with the result: x = 2 * 3 + 4 becomes x = 10. This saves the computation at run time.

Combining consecutive loads, eliminating dead code and unrolling loops are separate optimisations. Each removes or restructures code, but none computes constant expressions in advance.