🧠 Basic Blocks and Flow Graphs (Compiler Construction)

These topics belong to the Code Optimization phase of a compiler. They help in analyzing program structure so that the compiler can optimize execution efficiently.

---

📌 1. Basic Block

📖 Definition

A Basic Block is a sequence of consecutive statements in which:

• Control enters only at the beginning
• Control leaves only at the end
• No branching occurs inside the block

👉 In simple words:

A straight-line code segment with no jumps in or out (except at entry and exit).

---

⚙️ 2. Characteristics of Basic Block

✔ Single entry point ✔ Single exit point ✔ No jump in middle ✔ No jump out except last statement

---

🧠 3. How to Identify Basic Blocks (VERY IMPORTANT)

Step 1: Find Leaders

A leader is the first statement of a basic block.

A statement is a leader if:

1. It is the first statement of program
2. It is the target of a jump (label)
3. It immediately follows a jump instruction

---

Step 2: Form Blocks

Each leader starts a new basic block until next leader appears.

---

📊 Example

Code:

1. a = b + c
2. d = a + e
3. if a > b goto L1
4. x = y + z
5. goto L2
6. L1: p = q + r
7. L2: s = t + u

---

🔹 Step 1: Identify Leaders

• 1 (first statement)
• 4 (after conditional jump)
• 6 (label L1)
• 7 (label L2)

---

🔹 Step 2: Form Basic Blocks

🔹 Block B1:

1. a = b + c
2. d = a + e
3. if a > b goto L1

🔹 Block B2:

4. x = y + z
5. goto L2

🔹 Block B3:

6. L1: p = q + r

🔹 Block B4:

7. L2: s = t + u

---

📌 4. Flow Graph (Control Flow Graph - CFG)

📖 Definition

A Flow Graph (or Control Flow Graph) is a directed graph where:

• Nodes represent basic blocks
• Edges represent flow of control

---

🧠 5. Purpose of Flow Graph

✔ Represents program structure ✔ Helps in optimization ✔ Used in dead code elimination ✔ Helps in loop detection ✔ Used in register allocation

---

📊 Flow Graph Example

From previous basic blocks:

   B1
  /  \
 v    v
B2    B3
  \    /
   v  v
    B4

---

🔹 Explanation:

• B1 → B2 (false condition)
• B1 → B3 (true condition)
• B2 → B4 (jump)
• B3 → B4 (fall-through or jump)

---

🧠 6. Types of Edges in Flow Graph

🔹 1. Unconditional Edge

• Always executed

Example:

goto L2

---

🔹 2. Conditional Edge

• Based on condition

Example:

if a > b goto L1

---

🔹 3. Fall-through Edge

• Next sequential block

---

🧠 7. Properties of Flow Graph

✔ Directed graph ✔ Nodes = basic blocks ✔ Edges = control flow ✔ Has entry and exit nodes ✔ May contain loops

---

🧠 8. Loops in Flow Graph

📖 Definition

A loop is a cycle in a flow graph where control returns to a previous block.

---

🔹 Example:

B2 → B3 → B4 → B2 (cycle)

---

⭐ Loop Types:

• Natural loop (single entry)
• Irreducible loop (multiple entries)

---

🧠 9. Importance in Compiler Optimization

Basic blocks and flow graphs are used for:

✔ Dead code elimination ✔ Common subexpression elimination ✔ Loop optimization ✔ Code motion ✔ Register allocation

---

📌 10. Key Exam Points

✔ Basic block = straight-line code sequence ✔ Entry only at first statement ✔ Flow graph = graph of basic blocks ✔ Nodes = basic blocks ✔ Edges = control flow ✔ Used for optimization ✔ Helps identify loops

---

🎯 Final Exam Definition

A Basic Block is a sequence of consecutive statements in which control enters only at the beginning and leaves only at the end without any jumps in between. A Flow Graph (Control Flow Graph) is a directed graph where nodes represent basic blocks and edges represent the flow of control between them, used for program optimization.

---

📊 FINAL REVISION TABLE

Concept	Meaning	Key Feature
Basic Block	Straight-line code	Single entry/exit
Leader	First statement of block	Starts block
Flow Graph	Control structure graph	Nodes + edges
Node	Basic block	Code segment
Edge	Control transfer	Jump/flow
Loop	Cycle in graph	Repetition

---