Code Optimization in Compiler Design: Basic Blocks, Data Flow and Worked Examples

Constant folding, common subexpression elimination and liveness are clear on their own, then interfere once all three act on the same GATE-style basic block: folding makes a constant that propagation must carry, and propagation leaves a copy that only liveness can prove dead. One rule keeps them honest. An optimizer may change how a program computes its result, never the result an outside observer can see.

1. What code optimization may change, and what it must preserve

Code optimization preserves semantics while targeting time, size, memory traffic or energy. 3 * 4 -> 12 is safe. read_sensor(); return 0; cannot be deleted solely because its value is unused if the call has observable effects.

After lexical analysis in the compiler front end, an intermediate representation feeds middle-end work; the back end produces target instructions. These are roles, not necessarily three physical components.

Fewer statements need not mean faster target code. The cost model decides.

2. Basic blocks and the control-flow graph

A basic block is a maximal straight-line sequence with one entry and branches only at the end. Leaders are the first statement, jump targets and statements after jumps.

1  i = 0
2  L1: t1 = i * 4
3      t2 = A[t1]
4      t3 = i * 4
5      t4 = B[t3]
6      t5 = t2 + t4
7      t6 = i * 4
8      t7 = t5 + 0
9      C[t6] = t7
10     i = i + 1
11     if i < 3 goto L1
12     return

The leaders give B0 = {1}, B1 = {2..11}, B2 = {12}. The control-flow graph (CFG) edges are B0 -> B1, B1 -> B1 when i < 3, otherwise B1 -> B2. B0 is the preheader, B1 the loop header and body, its true self-edge the back edge.

Expression reuse requires that no path between the two computations redefines an operand. Hoisting a computation out of a loop requires two facts: it yields the same value on every iteration, and it still runs on every path where the original ran.

3. Core code-optimization transformations

For p = 3 * 4; q = p + 5; unused = q * 1; return 0, folding yields p = 12, propagation plus folding q = 17, then simplification unused = 17. Because the right-hand sides are side-effect free and the function returns 0, liveness deletes all three assignments. Passes may repeat until no profitable safe change remains.

Safe strength reduction replaces repeated i * 4 offsets with offset = offset + 4. Target-level peephole optimization removes a redundant move or jump-to-next-instruction only with known register and CFG facts. Not every compiler runs every pass.

4. Worked example: optimize a three-iteration array loop

Arrays A, B, C hold 4-byte integers; A = [2, 5, 7], B = [3, 4, 1]. Valid offsets are 0, 4, 8, with i = 0, 1, 2.

Thus C = [5, 9, 8]. Since i stays unchanged, common subexpression elimination replaces t3, t6 with t1. Simplification makes t7 = t5 + 0 a copy, then propagation removes t7. Strength reduction initializes offset in the preheader:

i = 0
offset = 0
L1: t2 = A[offset]
    t4 = B[offset]
    t5 = t2 + t4
    C[offset] = t5
    i = i + 1
    offset = offset + 4
    if i < 3 goto L1
    return

The trace still gives C = [5, 9, 8]. Three i * 4 operations across three iterations mean 9 multiplications; the new form has 0 loop multiplications, 3 offset additions. That count is at the intermediate-representation level. A target with scaled-index addressing folds the same multiply into the load itself, so fewer IR operations need not mean fewer machine cycles.

5. Data-flow analysis: liveness and dead assignments

Liveness asks backward whether a current value may be read before overwrite. For block B, OUT[B] is the union of successor IN[S] sets; IN[B] = USE[B] union (OUT[B] - DEF[B]). Recompute to a fixed point.

B1: x = 4; y = 7; if p goto B2 else B3
B2: z = x + y; x = 9; goto B4
B3: z = x - y; goto B4
B4: print(z)

Since x is not live after x = 9 in B2, it is dead. The true path prints 4 + 7 = 11; the false prints 4 - 7 = -3. Deletion preserves both. Liveness asks if a value is used; constant propagation asks which constant reaches a point. Equations differ.

6. Optimization traps and safety checks

Fixed-width overflow, floating-point rounding, signed zero, infinity or NaN can invalidate identities; 0.0 * x is not always 0.0. Language and compiler mode govern restrictions from volatile access, exceptions and concurrency.

A dead assignment executes but is unused; unreachable code has no entry path. A safe rewrite may lose on size, cache or registers. Unrolling a four-iteration loop by a factor of two cuts the loop-condition tests from four to two, at the cost of doubling the body.

7. How GATE and interviews test code optimization

The archived official GATE 2026 Computer Science and Information Technology syllabus names local optimization and data-flow analyses explicitly: constant propagation, liveness analysis and common subexpression elimination. A syllabus fixes the topic list, not the marks, and those follow from each year's paper. See how Compiler Design fits into the wider subject plan.

Practise by marking leaders and CFG edges; applying a pass while checking redefinitions; solving USE, DEF, IN, OUT to a fixed point; comparing dynamic operation counts without assuming fewer statements are faster. After a = 3; b = 4; t1 = a * b; b = b + 1; t2 = a * b, can t2 reuse t1? No. The second operand changed in between, so t1 is 12 and t2 is 15.

In interviews, state the proof obligation out loud: the behaviour preserved, the safety fact that licenses the rewrite, the cost improvement expected. The KnowledgeGate question bank carries more than 70 Code Optimization questions to practise on. Use timed subject-wise and mock practice once your hand-working is reliable.

8. The short version and next step

• Optimization must preserve observable behaviour.

• Basic blocks define local straight-line regions.

• CFGs expose paths and loops.

• Data-flow facts justify global rewrites.

• Cost models decide whether a safe rewrite is worthwhile.

In the worked loop, 9 loop multiplications became 3 offset additions, and C stayed [5, 9, 8].

Self-check for 8-byte elements: optimize k = 0; L: t1 = k * 8; t2 = k * 8; D[t2] = E[t1] + 0; k = k + 1; if k < 2 goto L. Set offset = 0, use D[offset] = E[offset], add 8, retain the test. Iterations use offsets 0, 8. Aliasing, bounds and language semantics must remain valid.

Use Zero to Hero for structured Computer Science including Compiler Design. The GATE category is the browse-all route.