Local optimization (peephole) in Compiler Design - Mini Project: Build & Apply

Local Optimization with Peephole Technique

📖 Scenario: You are working on a simple compiler that translates assembly-like instructions. Sometimes, small sequences of instructions can be improved to run faster or use fewer steps. This is called local optimization using the peephole technique.Imagine you have a short list of instructions, and you want to find and replace inefficient patterns with better ones.

🎯 Goal: Build a small peephole optimizer that scans a list of instructions and replaces a specific inefficient pattern with a better one.For example, replace the sequence LOAD A followed by STORE A with a single MOVE A instruction.

📋 What You'll Learn

Create a list called instructions with the exact sequence: 'LOAD A', 'STORE A', 'ADD B', 'LOAD C', 'STORE C'

Create a variable called optimized_instructions initialized as an empty list

Use a while loop with an index variable i to scan through instructions

Replace every occurrence of 'LOAD A' followed immediately by 'STORE A' with 'MOVE A' in optimized_instructions, copying other instructions unchanged

💡 Why This Matters

🌍 Real World

Compilers use peephole optimization to improve small parts of generated code, making programs run faster and use less memory.

💼 Career

Understanding peephole optimization is important for compiler developers, performance engineers, and anyone working on low-level code optimization.

1

Create the initial instruction list

Create a list called instructions with these exact strings in order: 'LOAD A', 'STORE A', 'ADD B', 'LOAD C', 'STORE C'.

Compiler Design

# Create the list of instructions
# Your code here

Need a hint?

Use square brackets [] to create a list and separate items with commas.

2

Prepare the optimized instructions list and index

Create an empty list called optimized_instructions and a variable i set to 0 to use as an index for scanning.

Compiler Design

instructions = ['LOAD A', 'STORE A', 'ADD B', 'LOAD C', 'STORE C']
# Create an empty list called optimized_instructions
# Create an index variable i set to 0
# Your code here

Need a hint?

Use [] to create an empty list and assign 0 to i.

3

Scan and optimize instructions using a while loop

Use a while loop that runs while i is less than the length of instructions. Inside the loop, check if the current instruction is 'LOAD A' and the next instruction is 'STORE A'. If yes, append 'MOVE A' to optimized_instructions and increase i by 2. Otherwise, append the current instruction and increase i by 1.

Compiler Design

instructions = ['LOAD A', 'STORE A', 'ADD B', 'LOAD C', 'STORE C']
optimized_instructions = []
i = 0
# Use a while loop to scan instructions and optimize
# Your code here

Need a hint?

Remember to check the next instruction exists before accessing it to avoid errors.

4

Complete the peephole optimization

Add a final comment line # Peephole optimization complete after the loop to mark the end of the optimization process.

Compiler Design

instructions = ['LOAD A', 'STORE A', 'ADD B', 'LOAD C', 'STORE C']
optimized_instructions = []
i = 0
while i < len(instructions):
    if i + 1 < len(instructions) and instructions[i] == 'LOAD A' and instructions[i + 1] == 'STORE A':
        optimized_instructions.append('MOVE A')
        i += 2
    else:
        optimized_instructions.append(instructions[i])
        i += 1
# Add a final comment to mark completion
# Your code here

Need a hint?

This comment helps others understand where the optimization ends.