By 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
- Identifies redundancy - Finds repeated computations
- Eliminates - Reuses computed values
- Handles memory - Aliasing considerations
- 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 propagationdead-code-eliminator- Remove dead codeloop-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
- Redundancy in quantum circuits: CSE for quantum compilation
- Graph RE: Redundancy elimination in dataflow graphs
- 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.