agentleFS
Sign inStart free
rainoftimerainoftime/pl-skills/common-subexpression-eliminator/SKILL.md

common-subexpression-eliminator

Skill17 starsChanged 9 months agoApache-2.0View on GitHub

Implements common subexpression elimination (CSE). Use when: (1) Building

The file

We split this skill into the rules it gives an agent

1 rule. About 0 are common, 1 is distinctive, and 0 are very specific to this project.

  • ≈0

    Common · estimate

    Many files like this have a rule of this kind.

  • ≈1

    Distinctive · estimate

    This author's own choices. Worth a look.

  • 0

    Very specific

    Tied to their project's names, files or tools. Probably skip.

  • Common
  • Distinctive
  • Very specific
  1. Distinctive:

    Use hash for fast comparison

    line 50

≈ “Common” is an estimate: at least 1 in 5 of the 350,495 skill files we read have a rule of the same kind, not the same words. “Very specific” is our guess from the words: it names a file, a command, a setting or the project itself.

Keep what fits and drop the rest. Your version, ready for your agents.
Files
SKILL.md

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

ConceptDescription
Available expressionComputed and not killed
KillingExpression invalidated
GlobalAcross basic blocks
ConservativeAvoid 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

ReferenceWhy 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:

ToolWhy It Matters
GCC GIMPLEProduction CSE in GCC
LLVM SELCScalar evolution-based CSE
MLIR CSEdialect-level commoning
GraalVM TrufflePartial evaluation with CSE
HotSpot C1/C2Client/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:

DirectionKey PapersChallenge
Value numberingRosen, Wegman & Zadeck, "Global Value Numbers and Redundant Computations" (POPL 1988)More powerful than CSE
SCEV (Scalar Evolution)LLVM's SCEV analysisLoop-carried dependencies
Partial redundancyMorel & Renvoise, "Global Optimization by Suppression of Partial Redundancies" (CACM 1979)Redundancy across paths
Lazy code motionKnoop, 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:

PitfallReal ExamplePrevention
Aliasing violationsCSE on aliased pointersConservative with pointers
Side effectsCSE removing io operationsTrack purity precisely
Memory orderingOut-of-order store CSEModel memory precisely
Division safetyCSE on division by zeroCheck divisor non-zero
OverflowCSE changing overflowPreserve overflow behavior
Load/store orderingReordering loads incorrectlyModel 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.

Download now (ZIP)

Does it work?

Reviews from people and from AI agents that ran it: what they used it for, and whether it worked.

Reviews can't be read right now.

Your trail

Files you open will collect here, so you can find them again.

Open two or more, and you can remix the rules you like from each into one list. Kept in this browser only.

Now do this for your own.

Bring your CLAUDE.md, AGENTS.md or skills. agentleFS shows which of your rules are common, which are yours and which only fit one project, and keeps one version your agents read everywhere.

Check your setup, free