"Local Optimisation & Data Flow Analysis" — Practice

Question 1

Partition the code i = 0; L: t = i*4; if i >= n goto E; a[t] = 0; i = i+1; goto L; E: return into basic blocks and state how many blocks result.

Accepted Answer

Leaders are instruction 1 (first), the instruction labelled L (jump target), the instruction after the conditional jump, and the instruction labelled E (jump target and follows a jump). Four blocks result.

Question 2

Classify each of the four classical analyses by direction and meet operator.

Accepted Answer

Reaching definitions: forward, union. Available expressions: forward, intersection. Live variables: backward, union. Very busy expressions: backward, intersection.

Question 3

Optimise a = 3; b = a + 2; c = b * 1; d = c + 0 assuming only d is live at exit, naming each transformation.

Accepted Answer

Constant propagation and folding give b = 5. Algebraic simplification removes the multiply by one and add of zero, giving c = b and d = c. Copy propagation and folding give d = 5. Dead code elimination removes a, b and c, leaving d = 5.

Question 4

Explain why available expressions must use intersection while reaching definitions uses union.

Accepted Answer

Available expressions justifies replacing a computation with a reference to an earlier result, which is safe only if that result exists on every path, hence intersection. Reaching definitions must report any definition visible on some path, since ignoring one could lead to a wrong substitution, hence union.

Question 5

In the block x = a+b; y = a+b; a = 5; z = a+b, which occurrences of a+b are common subexpressions?

Accepted Answer

The second occurrence, assigned to y, reuses the first because neither a nor b changed. The third, assigned to z, cannot reuse either, because a was reassigned in between, killing the expression.

Question 6

A loop body contains q = x / y where neither x nor y is assigned inside the loop. Under what condition is hoisting q unsafe, and how is it fixed?

Accepted Answer

It is unsafe when the loop may execute zero times, because the original program would never perform the division but the hoisted version always does, so a divide-by-zero can be introduced. Fix by guarding the preheader with a test that the loop iterates at least once.

Question 7

Given a loop where i increases by 1 and t = 4*i + 8, rewrite t using strength reduction.

Accepted Answer

Initialise t = 8 in the preheader, since i starts at 0, and replace the multiplication in the body with t = t + 4, because i advances by 1 and the coefficient is 4.

Question 8

For the block p = a+b; q = p*2; p = c+d; r = p+q with only r live at exit, compute the live set before each instruction and identify any dead assignment.

Accepted Answer

Before instruction 4 the set is p and q; before 3 it is q, c, d; before 2 it is p, c, d; before 1 it is a, b, c, d. No assignment is dead, because each target is live immediately after its definition.

Question 9

A flow graph has entry E, and blocks B1, B2, B3 with edges E to B1, B1 to B2, B2 to B3, B3 to B1, and B2 to exit. Identify the back edge and the natural loop.

Accepted Answer

B1 dominates B3, since every path from E to B3 passes through B1, so B3 to B1 is a back edge. The natural loop is the set of nodes reaching B3 without passing through B1, together with B1 itself: B1, B2 and B3.

Question 10

Why does the iterative data-flow algorithm always terminate?

Accepted Answer

The facts form a finite lattice and every transfer and meet operation is monotone, so each iteration moves the solution in one direction only and cannot cycle. Since the lattice has finite height, a fixed point is reached in finitely many rounds.

Practice — "Local Optimisation & Data Flow Analysis"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities