Basic Blocks, Flow Graphs and DAG Construction for GATE: Code Optimization Numericals

Code-optimization numericals in GATE reduce to two procedures: partition three-address code into basic blocks, then build a DAG for one block. A guessed partition usually misses a leader, and one missed leader changes both the block count and the flow-graph edges. Applied literally, the three leader rules fix the block count before any box is drawn, and the control transfers leaving each block fix the edge count.

Basic blocks and the three leader rules

A basic block is a maximal consecutive sequence of instructions with one entry and one exit. Control enters at the first instruction. Once the block starts, every instruction runs in order until control leaves at the end.

Find leaders before drawing block boundaries:

1. The first instruction is a leader.

2. Every target of a conditional or unconditional jump is a leader.

3. Every instruction immediately following a conditional or unconditional jump is a leader.

After marking all leaders, a block begins at one leader and ends immediately before the next leader. The final block continues to the end of the listing.

Rule 3 matters even when the preceding jump is unconditional and the following instruction cannot be reached from that jump. It may still be reached from somewhere else, and a block may not have an internal entry point.

For the wider relationship among intermediate code, DAGs and local transformations, keep syntax-directed translation and code optimization beside this procedure.

Worked basic-block partition

Use this numbered three-address code:

(1) t1 = a + b
(2) t2 = c + d
(3) if t2 < 10 goto (6)
(4) t3 = t1 * t2
(5) goto (7)
(6) t3 = t1 + t2
(7) x = t3

Apply each rule independently.

• Instruction (1) is a leader because it is first.

• Instruction (4) is a leader because it immediately follows the conditional jump at (3).

• Instruction (6) is a leader twice over: it is the target of (3) and follows the jump at (5).

• Instruction (7) is a leader because it is the target of (5).

The leader set is therefore {1, 4, 6, 7}. Now cut immediately before each new leader:

B1 = (1), (2), (3)
B2 = (4), (5)
B3 = (6)
B4 = (7)

There are four basic blocks. Instruction (6) being identified by two rules does not create two blocks or count as two leaders. It is one instruction and one leader.

Constructing the flow graph

A flow graph has one node for each basic block and one directed edge for each possible transfer of control. Include explicit jumps and possible fall-through transfers.

From B1, the condition at (3) has two outcomes. If t2 < 10, control jumps to (6), so add B1 -> B3. Otherwise execution falls through to (4), so add B1 -> B2.

Block B2 ends with goto (7), giving B2 -> B4. Block B3 contains (6) and then falls through to (7), giving B3 -> B4. Block B4 is the exit.

The final count is:

nodes = 4
edges = 4
edges = {B1->B2, B1->B3, B2->B4, B3->B4}

DAG construction for one basic block

A DAG for a basic block represents values and their dependencies. Leaves stand for values available on entry. Interior nodes stand for computations. A variable name is attached to the node holding its current value.

The key optimization rule is sharing. If the same operator is applied to the same current operand values, reuse the existing node. If an operand has been redefined, it is a different value and the old computation cannot be reused merely because the variable spelling matches.

Build a DAG for this block:

(1) a = b + c
(2) b = a - d
(3) c = b + c
(4) d = a - d

Start with leaves b0, c0, and d0, representing the values of b, c, and d on entry.

1. For (1), create n1 = b0 + c0 and label n1 with a.

2. For (2), create n2 = n1 - d0 and label n2 with b.

3. For (3), use the current value of b, which is n2, and the old value of c, which is still c0. Create n3 = n2 + c0 and label it with c.

4. For (4), the current a is still n1, and the current d is still d0. The expression n1 - d0 already exists as n2, so do not create another operator node. Add d as a second label on n2.

There are three leaves and three interior nodes, so the DAG has 3 + 3 = 6 nodes. Each of the three binary operator nodes has two child edges, so it has 3 * 2 = 6 edges. Statements (2) and (4) share one computation.

Counting drills and common traps

GATE can ask for the number of leaders, blocks, flow-graph edges, DAG nodes, DAG edges, or common subexpressions. Keep the objects separate. A source instruction is not automatically a DAG node, and a block boundary is not automatically a flow edge.

Use these checks:

• Mark targets and post-jump instructions before forming any block.

• Count the non-jump outcome of a conditional as a fall-through edge.

• Count a fall-through from one block to the next unless the first block ends in an unconditional transfer or exit.

• Share a DAG operator node only when every operand still denotes the same value.

• When a variable is reassigned, move its label to the new value node.

Drill on a listing with a loop, because a back edge is where counts usually break:

(1) i = 1
(2) t1 = i * 4
(3) t2 = a[t1]
(4) if t2 < 10 goto (7)
(5) i = i + 1
(6) goto (2)
(7) x = i

Instruction (1) is a leader as the first instruction. Instruction (2) is a leader only because (6) jumps back to it, and that is the leader most hand partitions miss. Instruction (5) follows the conditional jump at (4), and (7) is both the target of (4) and the instruction after (6). The leader set is {1, 2, 5, 7}, giving B1 = (1), B2 = (2), (3), (4), B3 = (5), (6) and B4 = (7).

Block B1 falls through to B2. Block B2 branches to B4 when t2 < 10 holds and falls through to B3 otherwise. Block B3 ends in goto (2), so it points back to B2. The counts are four nodes and four edges, {B1->B2, B2->B3, B2->B4, B3->B2}, and the last of those is the back edge that makes B2 and B3 a loop.

The KnowledgeGate question bank carries over 700 published Compiler Design questions, and its code-optimization set drills exactly these leader and counting patterns. Related Compiler Design parsing MCQs help keep syntax analysis separate from the later optimization phase.

How GATE tests this topic

The usual stem supplies a three-address code listing and asks for a block or edge count. A second pattern supplies straight-line code and asks how many DAG nodes remain after common subexpressions are shared. The answer is exact once the leader and value-version rules are applied.

For year-specific wording, use the official GATE portal of the organising IIT. The GATE preparation category collects the courses and test series that cover compiler design alongside the rest of the core papers.

Short version and next step

Leaders are the first instruction, every jump target, and every instruction after a jump. Blocks run from one leader to just before the next. Flow edges are possible transfers, while a DAG shares repeated computations only when the operand values are unchanged.

Partition two more listings on paper and annotate why each edge exists. Then use the GATE Test Series to time code-optimization numericals after your counts are consistently correct.