MIR Optimization: Common Subexpression Elimination (CSE)

[gakonst]

Summary

Implement CSE to eliminate redundant computations by reusing previously computed values.

Parent issue: #687

Context

CSE identifies when the same computation is performed multiple times and reuses the first result:

v1 = add(x, y)
...
v2 = add(x, y)   ; Same as v1!

In SSA form, this is straightforward: hash instructions by (opcode, operands) and reuse matching values.

Tasks

Local CSE (within basic blocks)

• Hash pure instructions by (opcode, operands, type)
• For each instruction, check if equivalent already computed
• Replace uses with existing value, mark instruction for removal

Instruction canonicalization

• For commutative ops (add, mul, and, or, xor, eq), sort operands
• add(y, x) canonicalizes to add(x, y) for consistent hashing
• Handle constants specially (always on right for commutative ops)

Side effect handling

• Only CSE pure (side-effect-free) instructions
• SLOAD with same slot can be CSE'd if no intervening SSTORE
• MLOAD similarly, if no intervening MSTORE
• Conservative: don't CSE across calls or stores initially

Global CSE (optional, advanced)

• CSE across basic blocks using dominator information
• Value at use point must be dominated by original computation
• More complex, defer to later iteration

Example

; Before CSE
  v0 = arg(0)
  v1 = arg(1)
  v2 = add(v0, v1)
  v3 = mul(v2, 2)
  v4 = add(v0, v1)     ; Same as v2!
  v5 = mul(v4, 3)
  v6 = add(v3, v5)
  return v6

; After CSE
  v0 = arg(0)
  v1 = arg(1)
  v2 = add(v0, v1)
  v3 = mul(v2, 2)
  v5 = mul(v2, 3)      ; Reuse v2 instead of v4
  v6 = add(v3, v5)
  return v6

Patterns to follow

From Venom:

• Use practical, local CSE focused on EVM cost model
• Especially valuable for avoiding redundant SLOAD/keccak256

From Sonatina:

• Instruction hashing infrastructure for value numbering

Acceptance Criteria

• Redundant pure computations eliminated
• Commutative ops normalized and CSE'd correctly
• Side-effecting instructions NOT incorrectly CSE'd
• Tests for SLOAD/MLOAD CSE with and without intervening stores

Estimated Complexity

Medium - Local CSE is simple, global CSE is harder

Dependencies

• MIR structure (done)
• Instruction canonicalization helpers

[Ayushdubey86]

Is this something open to outsiders? if yes, can i look into it?