菜单
Implements common subexpression elimination (CSE). Use when: (1) Building compilers, (2) Optimizing code, (3) Program analysis.
用 Codex 或 Claude 帮你安装 复制这段 Prompt，粘贴到 Codex、Claude 或其他助手里，让它检查 Skill 页面并帮你完成安装。
基于 SOC 职业分类
Implement abstract machines for defining and executing operational semantics of programming languages.
Implements alias and points-to analysis for pointer programs. Use for: (1) Optimizing compilers, (2) Verifying memory safety, (3) Program understanding, (4) Parallelization.
Define program meaning through logical assertions and proof rules (Hoare logic).
Transforms closures to explicit environments. Use when: (1) Implementing functional languages, (2) Building compilers, (3) Understanding closures.
Implements general dataflow analysis framework. Use when: (1) Building compilers, (2) Static analysis tools, (3) Program verification.
Builds denotational semantic models. Use when: (1) Formalizing language semantics, (2) Proving program properties, (3) Semantic analysis.
| 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"] |
Implements common subexpression elimination optimization.
| Concept | Description |
|---|---|
| Available expression | Computed and not killed |
| Killing | Expression invalidated |
| Global | Across basic blocks |
| Conservative | Avoid aliasing issues |
constant-propagation-pass - Constant propagationdead-code-eliminator - Remove dead codeloop-optimizer - Loop optimizations| 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 |
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 |
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 |
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 |
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.