# Rainoftime Pl Skills Common Subexpression Eliminator

> Common Subexpression Eliminator

- Skill: `tomevault-io/rainoftime-pl-skills-common-subexpression-eliminator` (Agent Skill, multi-file: 2 files)
- Install (CLI): `npx skillmds@latest add tomevault-io/rainoftime-pl-skills-common-subexpression-eliminator`
- Raw SKILL.md: https://api.skillmd.com/api/skills/tomevault-io/rainoftime-pl-skills-common-subexpression-eliminator/raw
- Safety review: pending (external: skill-scanner PASS, skillspector PASS)
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- Author: tomevault-io (https://skillmd.com/u/tomevault-io)
- Updated: 2026-09-17
- Page: https://skillmd.com/skills/tomevault-io/rainoftime-pl-skills-common-subexpression-eliminator

---


# 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:
```c
// 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.

---
> Converted and distributed by [TomeVault](https://tomevault.io/claim/rainoftime) — claim your Tome and manage your conversions.
<!-- tomevault:4.0:skill_md:2026-04-11 -->