Local optimization (peephole) in Compiler Design - Step-by-Step Execution

Concept Flow - Local optimization (peephole)

Input: Sequence of instructions

↓

Select small window (peephole)

↓

Analyze instructions in window

↓

Apply optimization rules if pattern matches

↓

Replace with optimized instructions

↓

Move window forward

↓

Repeat

↓

Output optimized code

Local optimization scans small groups of instructions to find and replace inefficient patterns with better ones, improving code step-by-step.

Execution Sample

Compiler Design

LOAD R1, 0
ADD R1, 5
STORE R1, X

This code loads 0 into R1, adds 5, then stores R1 to X. Peephole optimization can simplify this.

Analysis Table

Step	Window Instructions	Pattern Matched?	Action	Resulting Instructions
1	LOAD R1, 0 ADD R1, 5	Yes (Add after Load 0)	Replace with LOAD R1, 5	LOAD R1, 5 STORE R1, X
2	LOAD R1, 5 STORE R1, X	No	No change	LOAD R1, 5 STORE R1, X
3	STORE R1, X	No	No change	LOAD R1, 5 STORE R1, X

💡 No more windows to analyze; optimization complete.

State Tracker

Variable	Start	After Step 1	After Step 2	Final
Instructions	LOAD R1, 0 ADD R1, 5 STORE R1, X	LOAD R1, 5 STORE R1, X	LOAD R1, 5 STORE R1, X	LOAD R1, 5 STORE R1, X

Key Insights - 2 Insights

Why does peephole optimization only look at a small window of instructions?

Because it focuses on local patterns to simplify or improve code without needing to analyze the entire program, as shown in Step 1 where only two instructions are checked.

What happens if no pattern matches in the current window?

The instructions remain unchanged and the window moves forward, as seen in Steps 2 and 3 where no changes occur.

Visual Quiz - 3 Questions

Look at the execution table at Step 1. What optimization was applied?

A Removed STORE instruction

B Added an extra ADD instruction

C Replaced LOAD 0 and ADD 5 with LOAD 5

D No optimization applied

💡 Hint

Check the 'Action' and 'Resulting Instructions' columns in Step 1.

At which step does the peephole window find no matching pattern?

A Both Step 2 and Step 3

B Step 2

C Step 3

D Step 1

💡 Hint

Look at the 'Pattern Matched?' column for Steps 2 and 3.

If the initial code had 'ADD R1, 0' instead of 'ADD R1, 5', what would the optimization likely do at Step 1?

A No change because ADD 0 does nothing

B Replace LOAD 0 and ADD 0 with LOAD 0

C Replace LOAD 0 and ADD 0 with LOAD 5

D Remove the LOAD instruction

💡 Hint

Consider how adding zero affects the value and what peephole optimization tries to simplify.

Concept Snapshot

Local optimization (peephole):
- Examines small instruction windows
- Matches patterns to simplify or improve code
- Replaces inefficient sequences with better ones
- Moves window forward and repeats
- Improves code locally without full program analysis

Full Transcript

Local optimization, also called peephole optimization, works by looking at small groups of instructions in a program. It checks if these instructions match known inefficient patterns. If they do, it replaces them with better instructions. For example, loading zero and then adding five can be replaced by loading five directly. The process repeats by moving the small window forward until the whole code is checked. If no pattern matches, the instructions stay the same. This method improves code step-by-step without analyzing the entire program at once.

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