Basic blocks and flow graphs

ACompressed recap

🧾

Three-address code is cut into basic blocks at leaders: the first instruction, every jump target, and every instruction after a jump. The flow graph connects blocks by jump edges and fall-through edges (none after an unconditional jump). “CFG” can mean context-free grammar or control flow graph; read the context.

BMerged rule card

4.4 Basic blocks: leader rules and partitioning; control flow graphs (the second meaning of “CFG”); counting blocks and edges

• Basic block: enter only at the first instruction, leave only after the last.
• Leaders: first instruction; jump targets; instructions after jumps (and after return/halt).
• Block = leader … before next leader.
• Flow graph edges: jump target, and fall-through unless the block ends in an unconditional jump.
• CFG = context-free grammar (parsing) vs control flow graph (optimization): read the context.

CInterleaved GATE-style questions

Q1NAT1 markLeaders

How many leaders does the code s = 0; i = 0; while (i < 10) { s = s + i; i = i + 2; } t = s * 2; have after translation (8 instructions as in Lesson 4.2.3)?

Numerical answer: ________

Q2NAT2 marksEdges

How many flow-graph edges does that code have?

Numerical answer: ________

Q3MCQ1 markFall-through

A block ending in goto L has a fall-through edge to the next block:

• (A) always
• (B) never
• (C) only in loops
• (D) only if L is the next block

Q4MSQ2 marksLeaders

In 1 x = 0; 2 if x > 5 goto 5; 3 x = x + 1; 4 goto 2; 5 y = x, which instructions are leaders?

• (A) 1
• (B) 2
• (C) 3
• (D) 5

Q5NAT2 marksBlocks

For if (x > 0 && y > 0) z = 1; else z = 0; w = z + 1; translated as in Lesson 4.2.3, how many basic blocks are there?

Numerical answer: ________

Q6MCQ1 markDefinition

Inside a basic block:

• (A) there may be jumps into the middle
• (B) control enters at the first instruction and leaves after the last
• (C) every instruction is a leader
• (D) there must be a loop

Q7MCQ1 markName clash

“The CFG has 12 productions” refers to:

• (A) a control flow graph
• (B) a context-free grammar
• (C) a basic block
• (D) a DAG

Q8NAT1 markEdges

A flow graph has blocks B1 (ends in a conditional jump to B3), B2 (no jump), B3 (unconditional jump to B1), B4 (last, no jump). How many edges?

Numerical answer: ________