Peephole Optimizations

Your Task

Implement a peephole optimizer for x86 assembly or TAC.

Requirements

1. Implement pattern matching for:

   • Redundant move elimination
   • Algebraic identity removal
   • Strength reduction (multiply/divide by powers of 2)
   • Jump chain elimination

2. Create a pattern database:

   • Define patterns as instruction sequences
   • Define replacement sequences
   • Match and replace

3. Handle these specific patterns (minimum):

   • mov X, X → remove
   • add X, 0 → remove
   • mul X, 1 → remove
   • mul X, 0 → mov X, 0
   • mul X, 2^n → shl X, n
   • jmp L; L: → remove jump

4. Run until fixed point (no more matches)

Success Criteria

• Reduce instruction count on test programs
• Correctly handle all edge cases
• Report optimization statistics