common-subexpression-eliminator

name	common-subexpression-eliminator
description	Implements common subexpression elimination (CSE). Use when: (1) Building compilers, (2) Optimizing code, (3) Program analysis.
version	1.0.0
tags	["optimization","compiler-pass","cse","code-motion"]
difficulty	intermediate
languages	["python","rust"]
dependencies	["ssa-constructor"]

Common Subexpression Eliminator

Implements common subexpression elimination optimization.

When to Use

• Building optimizing compilers
• Program optimization
• Code analysis
• Performance tuning

What This Skill Does

1. Identifies redundancy - Finds repeated computations
2. Eliminates - Reuses computed values
3. Handles memory - Aliasing considerations
4. Optimizes - Global and local CSE

Key Concepts

Concept	Description
Available expression	Computed and not killed
Killing	Expression invalidated
Global	Across basic blocks
Conservative	Avoid aliasing issues

Tips

• Handle aliasing conservatively
• Consider side effects
• Use hash for fast comparison
• Track memory operations

Related Skills

• constant-propagation-pass - Constant propagation
• dead-code-eliminator - Remove dead code
• loop-optimizer - Loop optimizations

Canonical References

Reference	Why It Matters
Cocke, "Global Common Subexpression Elimination" (1970)	Original CSE algorithm
Tjaden & Flynt, "Global Subexpression Elimination" (1970s)	Early CSE work
Rosen, "Global Value Numbers and Redundant Computations" (1988)	Value numbering framework
Click & Cooper, "Combining Analyses, Optimizing and Using Them" (1995)	Integration of CSE with other analyses

Research Tools & Artifacts

Real-world CSE implementations to study:

Tool	Why It Matters
GCC GIMPLE	Production CSE in GCC
LLVM SELC	Scalar evolution-based CSE
MLIR CSE	dialect-level commoning
GraalVM Truffle	Partial evaluation with CSE
HotSpot C1/C2	Client/server compiler CSE

Key Optimizations

• Redundant load elimination (RLE): Beyond expression CSE
• Store CSE: Common stores to same location
• Linear-speed redundancy: Profitable vs redundant

Research Frontiers

Current CSE research:

Direction	Key Papers	Challenge
Value numbering	Rosen, Wegman & Zadeck, "Global Value Numbers and Redundant Computations" (POPL 1988)	More powerful than CSE
SCEV (Scalar Evolution)	LLVM's SCEV analysis	Loop-carried dependencies
Partial redundancy	Morel & Renvoise, "Global Optimization by Suppression of Partial Redundancies" (CACM 1979)	Redundancy across paths
Lazy code motion	Knoop, Rüthing & Steffen, "Lazy Code Motion" (PLDI 1992)	Optimal placement

Hot Topics

1. Redundancy in quantum circuits: CSE for quantum compilation
2. Graph RE: Redundancy elimination in dataflow graphs
3. Approximate computing: Tolerable approximation in CSE

Implementation Pitfalls

Common CSE bugs:

Pitfall	Real Example	Prevention
Aliasing violations	CSE on aliased pointers	Conservative with pointers
Side effects	CSE removing io operations	Track purity precisely
Memory ordering	Out-of-order store CSE	Model memory precisely
Division safety	CSE on division by zero	Check divisor non-zero
Overflow	CSE changing overflow	Preserve overflow behavior
Load/store ordering	Reordering loads incorrectly	Model memory model

The "Pointer Aliasing" Bug

CSE incorrectly assuming no aliasing:

// May alias - CSE would be wrong
a[i] = x;
b[j] = a[i];  // Could be same as a[i] above!

Solution: Conservative - don't CSE if pointers could alias.