🧠 Optimization of Basic Blocks (Compiler Construction)

Basic block optimization is a part of the Code Optimization phase of a compiler. It improves code efficiency within a single basic block without changing program output.

---

📌 1. Basic Block Optimization

📖 Definition

Basic block optimization refers to techniques used to improve the intermediate code inside a basic block by reducing:

• Execution time
• Memory usage
• Redundant operations

👉 Goal: Produce faster and cleaner code.

---

🧠 2. Why Optimization is Needed?

✔ Faster execution ✔ Less memory usage ✔ Fewer instructions ✔ Better CPU utilization

---

📊 Example (Before Optimization)

t1 = a + b
t2 = t1
t3 = a + b
t4 = t3 + c

👉 Here, a + b is repeated → wasteful

---

🧠 3. Types of Basic Block Optimization Techniques

---

🔹 1. Common Subexpression Elimination (CSE)

📖 Definition

If the same expression is computed more than once, reuse the result.

---

Example:

Before:

t1 = a + b
t2 = a + b
t3 = t2 + c

After:

t1 = a + b
t2 = t1
t3 = t2 + c

✔ Saves recomputation

---

🔹 2. Dead Code Elimination

📖 Definition

Remove code that is never used or never affects output.

---

Example:

Before:

t1 = a + b
t2 = t1
t1 = 10   // ❌ overwritten → dead code

After:

t1 = a + b
t2 = t1

---

🔹 3. Constant Folding

📖 Definition

Evaluate constant expressions at compile time.

---

Example:

Before:

t1 = 5 * 3
t2 = t1 + a

After:

t1 = 15
t2 = t1 + a

---

🔹 4. Constant Propagation

📖 Definition

Replace variables with known constant values.

---

Example:

Before:

a = 5
b = a + 2

After:

a = 5
b = 5 + 2

---

🔹 5. Copy Propagation

📖 Definition

Replace variable copies with original values.

---

Example:

Before:

t1 = a
t2 = t1 + b

After:

t2 = a + b

---

🔹 6. Algebraic Simplification

📖 Definition

Use algebra rules to simplify expressions.

---

Examples:

Before:

t1 = x * 1
t2 = y + 0
t3 = z * 0

After:

t1 = x
t2 = y
t3 = 0

---

🔹 7. Strength Reduction

📖 Definition

Replace expensive operations with cheaper ones.

---

Example:

Before:

t1 = x * 2

After:

t1 = x + x

---

🔹 8. Redundant Assignment Elimination

Example:

Before:

a = b
b = a

After:

a = b

---

🧠 4. Optimized Basic Block Example

Before Optimization:

t1 = a + b
t2 = a + b
t3 = t2 * 2
t4 = t3 + 0

---

After Optimization:

t1 = a + b
t3 = t1 * 2
t4 = t3

---

📊 5. Optimization Techniques Summary Table

Technique	Purpose	Example
Common Subexpression Elimination	Avoid recomputation	a+b reused
Dead Code Elimination	Remove useless code	unused assignment
Constant Folding	Precompute constants	5*3 → 15
Constant Propagation	Replace variables	a=5 → b=5+2
Copy Propagation	Remove copies	t1=a
Algebraic Simplification	Simplify expressions	x*1 → x
Strength Reduction	Use cheaper ops	x*2 → x+x

---

🧠 6. Key Properties of Basic Block Optimization

✔ Works only inside a single block ✔ Does not change program logic ✔ Improves performance ✔ Reduces instruction count ✔ Applied before global optimization

---

📌 7. Important Exam Points

✔ Basic block optimization is local optimization ✔ Common techniques:

• CSE
• Dead code elimination
• Constant folding ✔ Improves execution speed ✔ Reduces memory and CPU usage ✔ Performed on intermediate code (TAC)

---

🎯 Final Exam Definition

Optimization of basic blocks is the process of improving the intermediate code within a single basic block by eliminating redundant computations, removing dead code, and simplifying expressions without changing the program’s output, thereby improving efficiency.

---

📊 FINAL REVISION TABLE

Concept	Meaning
Basic block optimization	Improve code within block
CSE	Remove repeated expressions
Dead code	Unused statements removed
Constant folding	Compute constants early
Copy propagation	Replace variable copies
Strength reduction	Use cheaper operations
Goal	Faster + efficient code

---