Basic Blocks, Loops and Optimization Methods in Compiler Design: A Worked Example

Basic blocks, natural loops and legal optimizations are often taught separately, but exam problems can combine them in one TAC fragment. With a=3 and b=5, the ten instructions below lead to four blocks, a natural loop, an exact trace to s=108, and two semantics-preserving rewrites. The same fragment carries every step, so an incorrect leader or edge can be caught by its effect on the final trace. For broader study, use the GATE CS Exam Preparation hub.

Basic blocks in compiler design: find the leaders first

A basic block is a maximal straight-line sequence with one entry and no jump except at its end. Use three rules: the first instruction is a leader; every jump target is a leader; and the instruction immediately after any conditional or unconditional jump is a leader, if it exists.

With a=3 and b=5 fixed before entry, the TAC is:

1: i=0
2: s=0
3: if i>=4 goto 10
4: t0=a*b
5: t1=8*i
6: t2=t0+t1
7: s=s+t2
8: i=i+1
9: goto 3
10: return s

The rules give leaders 1, 3, 4, 10. Thus B1={1,2}, B2={3}, B3={4,5,6,7,8,9}, and B4={10}. Line 4 follows the conditional jump, so it starts a block. Line 10 is both a target and the instruction after line 9. Basic-block analysis follows the front-end work described in Parsing in Compiler Design: Top-Down and Bottom-Up Explained, but the leader calculation comes directly from this TAC.

Control-flow graph and natural loop: derive every edge

Possible transfers give B1 -> B2. In B2, false goes to B3, while true goes to B4. The unconditional jump gives B3 -> B2. No fall-through edge leaves B3, because line 9 always jumps.

In an entry-rooted graph, block D dominates block N when every path from entry to N passes through D. Here B2 dominates B3. Therefore B3 -> B2 is a back edge: its head B2 dominates its tail B3. Its natural loop is exactly {B2,B3}, with header B2 and exit edge B2 -> B4. B1 can serve as the preheader because it is the only predecessor of B2 outside the loop and has no other successor.

To construct the natural loop, start with the back-edge head and tail, then add predecessors recursively until reaching the header. Starting from B3 adds B2 and stops there, so neither B1 nor B4 enters the set.

Basic-block execution: trace the unoptimized loop to 108

Execute the original fragment before changing it. At i=0, t0=3*5=15, t1=8*0=0, t2=15+0=15, and s=0+15=15. At i=1, t1=8, t2=15+8=23, and s=15+23=38. At i=2, t1=16, t2=31, and s=38+31=69. At i=3, t1=24, t2=39, and s=69+39=108.

Every later transformation must preserve the returned value shown in this table. The increment then makes i=4; the test is true, so execution returns 108. Lines 4 and 5 each run four times. This run therefore performs 4+4=8 dynamic multiplications. That is the baseline. A shorter transformed loop is correct only if it preserves the same returned value.

Code-optimization methods: local, global and loop transformations

Local work stays within one block. Global work crosses blocks and control-flow joins. Loop work uses the header, back edge, preheader, and definitions. See Syntax-directed Translation and Code Optimization.

For example, x=7,y=5; p=x+y; q=x+y; r=q*2 gives p=q=12 and r=24 because neither x nor y changes before q. Insert x=x+1 before q, and q becomes 8+5=13, so reusing p for q would be invalid.

Loop optimization worked step by step: move invariants and reduce strength

First apply loop-invariant code motion. t0=a*b has unchanged operands because neither a nor b is assigned in {B2,B3}. Move it to B1, the preheader, where t0=3*5=15. Its multiplication now executes once instead of four times.

Next strength-reduce t1=8*i. Initialise r=0 in the preheader because i=0 at loop entry. The transformed parts are:

preheader: t0=a*b; r=0
loop body: t2=t0+r; s=s+t2; r=r+8; i=i+1; goto 3

The induction invariant is r=8*i at the start of every iteration. It holds initially since 0=8*0. Each body execution increments both sides consistently: r takes 0,8,16,24 as i takes 0,1,2,3.

The terms remain 15,23,31,39, so the return remains 108. Dynamic multiplications fall from 8 to 1; four additions r=r+8 replace four 8*i multiplications. This reduces repeated work, not asymptotic time. Legality requires unchanged a and b, in-range arithmetic, and TAC operations without hidden side effects.

Basic-block and loop-optimization traps: what goes wrong and how to correct it

Mark definitions and uses, build edges, compute entry dominance, and find back edges. Prove each move invariant and safe. Then compare both traces side by side.

Blocks, loops and optimization methods in exam questions

Question forms can ask you to identify leaders and count blocks, select CFG edges, test dominance, find a back edge and natural-loop members, choose a legal optimization, calculate values before and after a rewrite, or count removed operations.

Use a 30-second recognition procedure on this fragment: leaders {1,3,4,10}; blocks B1 through B4; back edge B3 -> B2; natural loop {B2,B3}; result 108 before and after; dynamic multiplications 8 -> 1.

Practice questions on basic blocks, loops and code optimization turn the recognition steps into quick checks. After learning the recognition process, the GATE Test Series is an optional route for more practice.

Basic blocks, loops and methods: the short version and next step

Leaders form basic blocks. Blocks and transfers form the CFG. Dominance identifies the back edge, which defines the natural loop. Definitions and uses then decide which transformations are legal. Here the result is four blocks, loop {B2,B3}, final s=108, and 8 dynamic multiplications reduced to 1 without changing output.

For a complete subject sequence, use GATE Guidance by Sanchit Sir. Then redraw this four-block CFG on blank paper, check every edge, and re-derive the optimized trace without looking at either table.