Local optimization (peephole) in Compiler Design - Full Explanation

Introduction

When a computer program is translated into machine instructions, some parts can be made simpler or faster. Local optimization looks at small sections of these instructions to find easy improvements that make the program run better without changing what it does.

Explanation

Scope of Local Optimization

Local optimization focuses on a small window of instructions, usually just a few lines, rather than the whole program. This limited view allows quick checks and changes that improve efficiency in that small area.

Local optimization improves small instruction groups to make code faster or smaller.

Peephole Technique

The peephole method slides a small window over the instruction list, examining a few instructions at a time. It looks for patterns that can be replaced with simpler or faster instructions without changing the program's meaning.

Peephole optimization scans small instruction sets to find and fix inefficiencies.

Common Optimizations

Typical improvements include removing instructions that do nothing, combining multiple instructions into one, or replacing slow instructions with faster equivalents. These changes reduce the program size and speed up execution.

Common peephole optimizations remove redundant code and simplify instruction sequences.

Benefits and Limitations

Local optimization is fast and easy to apply, making it useful in many compilers. However, it only improves small parts and cannot find bigger improvements that need a wider view of the program.

Local optimization is quick but limited to small code sections.

Real World Analogy

Imagine proofreading a short paragraph in a book to fix typos and awkward phrases. You focus only on a few sentences at a time, making quick fixes that improve clarity without rewriting the whole chapter.

Scope of Local Optimization → Focusing on a few sentences instead of the whole chapter

Peephole Technique → Looking closely at small parts of text to spot errors

Common Optimizations → Fixing typos and simplifying phrases to improve readability

Benefits and Limitations → Quick fixes that help but don’t rewrite the entire story

Diagram

Diagram

┌───────────────┐
│ Instruction 1 │
├───────────────┤
│ Instruction 2 │  ← Peephole window slides here
├───────────────┤
│ Instruction 3 │
├───────────────┤
│ Instruction 4 │
└───────────────┘

A sliding window (peephole) moves over a small group of instructions to check for improvements.

Key Facts

Local optimization → Improving small sections of code to make it more efficient without changing its behavior.

Peephole optimization → A technique that examines a few instructions at a time to find and fix inefficiencies.

Redundant instructions → Instructions that do not affect the program and can be safely removed.

Instruction combining → Replacing multiple instructions with a single, simpler instruction.

Limitation of local optimization → It cannot optimize beyond the small window it examines.

Common Confusions

Local optimization improves the entire program.

Local optimization improves the entire program. Local optimization only looks at small groups of instructions, not the whole program, so it cannot find large-scale improvements.

Peephole optimization changes what the program does.

Peephole optimization changes what the program does. Peephole optimization only changes instructions in ways that keep the program’s behavior exactly the same.

Summary

Local optimization improves small parts of machine code to make programs faster or smaller.

Peephole optimization slides a small window over instructions to spot and fix inefficiencies.

This method is quick and useful but cannot find improvements that need a bigger view of the program.

Practice

1. What is the main goal of local optimization (peephole) in compiler design?

easy

A. To improve small sequences of instructions by removing redundancies

B. To rewrite the entire program in a different language

C. To increase the number of instructions for clarity

D. To change the program's output for optimization

Solution

1. Step 1: Understand local optimization scope

   Local optimization focuses on small instruction sequences, not the whole program.

2. Step 2: Identify the goal of peephole optimization

   Peephole optimization removes unnecessary or redundant instructions to make code faster and smaller without changing its meaning.

3. Final Answer:

   To improve small sequences of instructions by removing redundancies -> Option A

4. Quick Check:

   Local optimization = remove redundancies [OK]

Hint: Focus on small instruction sequences and redundancy removal [OK]

Common Mistakes:

• Thinking it rewrites the whole program
• Believing it changes program output
• Assuming it adds more instructions

2. Which of the following is a correct example of a peephole optimization?

easy

A. Replacing LOAD A; LOAD A with LOAD A

B. Changing variable names for readability

C. Adding comments to the code

D. Rearranging functions in the source file

Solution

1. Step 1: Identify peephole optimization examples

   Peephole optimization looks at small instruction sequences to remove redundancies.

2. Step 2: Evaluate each option

   Replacing LOAD A; LOAD A with LOAD A removes duplicate instructions, which is a classic peephole optimization. Options A, B, and D do not optimize instructions.

3. Final Answer:

   Replacing LOAD A; LOAD A with LOAD A -> Option A

4. Quick Check:

   Remove duplicate instructions = peephole optimization [OK]

Hint: Look for removing repeated instructions in short sequences [OK]

Common Mistakes:

• Confusing code readability changes with optimization
• Thinking comments affect optimization
• Assuming rearranging functions is peephole optimization

3. Consider this instruction sequence before peephole optimization:

LOAD R1, #5
ADD R1, R1, #0
STORE R1, 100(R2)

What will be the optimized sequence after applying peephole optimization?

medium

A. LOAD R1, #5
ADD R1, #0
STORE R1, 100(R2)

B. LOAD R1, #5
ADD R1, R1, #0
STORE R1, 100(R2)

C. LOAD R1, #5
STORE R1, 100(R2)

D. ADD R1, R1, #0
STORE R1, 100(R2)

Solution

1. Step 1: Identify redundant instructions

   The instruction ADD R1, R1, #0 adds zero, which does not change the value in R1, so it is redundant.

2. Step 2: Remove redundant instruction

   Removing the redundant ADD instruction leaves LOAD R1, #5 and STORE R1, 100(R2).

3. Final Answer:

   LOAD R1, #5 STORE R1, 100(R2) -> Option C

4. Quick Check:

   Remove add zero = optimized sequence [OK]

Hint: Remove instructions that do not change values (like add zero) [OK]

Common Mistakes:

• Keeping redundant add zero instruction
• Removing load instruction incorrectly
• Misunderstanding instruction effects

4. Identify the error in this peephole optimization attempt:

Original: LOAD R2, #10
SUB R2, R2, #0
STORE R2, 200(R3)

Optimized: LOAD R2, #10
SUB R2, R2, #10
STORE R2, 200(R3)

medium

A. The load instruction should be removed

B. No error, optimization is correct

C. The store instruction is missing

D. The subtraction of zero was incorrectly replaced with subtraction of ten

Solution

1. Step 1: Compare original and optimized subtraction

   Original subtracts zero, which does nothing. Optimized subtracts ten, which changes the value incorrectly.

2. Step 2: Identify the error in optimization

   Replacing subtraction by zero with subtraction by ten changes program meaning, which is incorrect for peephole optimization.

3. Final Answer:

   The subtraction of zero was incorrectly replaced with subtraction of ten -> Option D

4. Quick Check:

   Incorrect instruction change = error in peephole optimization [OK]

Hint: Ensure optimized instructions do not change program meaning [OK]

Common Mistakes:

• Changing instruction values incorrectly
• Removing necessary instructions
• Assuming all changes are optimizations

5. Given this code snippet:

LOAD R3, #0
ADD R3, R3, #5
ADD R3, R3, #0
STORE R3, 300(R4)

Which peephole optimization sequence correctly optimizes this code without changing its meaning?

hard

A. LOAD R3, #0
ADD R3, R3, #0
STORE R3, 300(R4)

B. LOAD R3, #5
STORE R3, 300(R4)

C. ADD R3, R3, #5
STORE R3, 300(R4)

D. LOAD R3, #5
ADD R3, R3, #0
STORE R3, 300(R4)

Solution

1. Step 1: Analyze the original instructions

   Loading zero into R3, then adding 5, then adding 0, is equivalent to loading 5 directly into R3.

2. Step 2: Apply peephole optimization

   Replace the sequence with a single instruction LOAD R3, #5 and then store. This removes redundant instructions without changing meaning.

3. Final Answer:

   LOAD R3, #5 STORE R3, 300(R4) -> Option B

4. Quick Check:

   Combine load and add zero to direct load [OK]

Hint: Combine load and add instructions when possible [OK]

Common Mistakes:

• Keeping redundant add zero
• Not combining load and add
• Removing load instruction incorrectly