Implement Loop-Invariant Code Motion (LICM) optimization
@dragon540 已经在做这个了。
开始于 2026年8月14日。
评估
调研方向
Start with the proposed CFG loop detection, including loop headers, back edges, nesting, and dominance analysis. Then define invariant and safety checks before implementing hoisting to loop preheaders; completion should preserve SSA and exception semantics, support nested loops, and avoid side effects or potentially faulting operations.
由索引模型根据 Issue 内容生成。
描述
Description
Loop-Invariant Code Motion is a critical optimization that moves computations that don't change within a loop to execute before the loop. This can significantly improve performance for loop-heavy code.
Current Behavior
for (int i = 0; i < n; i++) {
int constant = x * y; // Recomputed every iteration
arr[i] = i + constant;
}
Expected Behavior
The optimizer should detect that x * y is loop-invariant and hoist it:
int constant = x * y; // Moved outside loop
for (int i = 0; i < n; i++) {
arr[i] = i + constant;
}
Implementation Requirements
1. Loop Detection
- Identify natural loops in CFG
- Find loop headers and back edges
- Build loop nesting tree
2. Invariant Analysis
- Identify instructions that don't depend on loop variables
- Check for side effects
- Verify safety of hoisting
3. Code Motion
- Move invariant code to loop preheader
- Preserve SSA form
- Update phi nodes if needed
4. Safety Checks
- Don't hoist potentially faulting operations
- Preserve exception semantics
- Check for aliasing issues
Test Cases
// Basic invariant hoisting
void basic(int *arr, int n, int x, int y) {
for (int i = 0; i < n; i++) {
int inv = x + y; // Should hoist
arr[i] = i * inv;
}
}
// Nested loops
void nested(int *arr, int n, int m) {
for (int i = 0; i < n; i++) {
int outer_inv = n * 2; // Hoist to function entry
for (int j = 0; j < m; j++) {
int inner_inv = i * 3; // Hoist to outer loop
arr[i*m + j] = outer_inv + inner_inv + j;
}
}
}
// Don't hoist side effects
void side_effects(int n) {
for (int i = 0; i < n; i++) {
int x = getchar(); // Don't hoist - side effect
process(x);
}
}
// Don't hoist potential faults
void safe(int *p, int n) {
for (int i = 0; i < n; i++) {
if (p) {
int x = *p; // Don't hoist - might fault if p becomes NULL
use(x);
}
}
}
Performance Impact
- Can reduce loop execution time by 20-50% for computation-heavy loops
- Especially effective for nested loops
- Reduces register pressure inside loops
Priority
MEDIUM - Significant performance improvement for common patterns
Complexity
HARD - Requires loop analysis and careful safety checking
Implementation Strategy
- Implement loop detection in CFG
- Add dominance analysis
- Implement invariant detection
- Add safe hoisting transformation
- Extend to nested loops
Benefits
- Major performance improvement for loops
- Reduces redundant computations
- Enables further optimizations
- Standard optimization in production compilers
Notes
- Start with innermost loops
- Be conservative about safety
- Consider profile-guided decisions
- Measure impact on real code
- 主要语言
- C
- 星标
- 1.4k
- 派生
- 168
- 平均合并
- 2 天 22 小时
- 30 天内合并 PR
- 3
环境准备
- 没有 Dockerfile 或 Docker Compose 文件
- 没有 Pull Request 模板
- 阅读贡献指南
从这里开始
- 先读完整个 Issue，再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库，在一个分支上完成修改。
- 提交 Pull Request，并在描述里引用这个 Issue 编号。
sysprog21/shecc 的其他 Issue
-
Enhance the rebuild logic of the bootstrap可能已有人在做 @DrXiao 于 4 天前认领。 未关闭
-
难度 4/5 3-5 天 新手友好度 38/100
-
enhancement
难度 5/5 一周以上 新手友好度 30/100
-
Import a GitHub Action for benchmarking purposes可能已有人在做 @DrXiao 于 442 天前认领。 未关闭
相似的 Issue
-
难度 2/5 1-3 小时 新手友好度 74/100
libsdl-org/SDL#16577 ·
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 66/100
维护者通常 1 天内回复
-
halt_error adds a trailing newline for non-string input, contrary to the manual可能已有人在做 @Huang-404-Q 今天认领。 未关闭
难度 1/5 1-3 小时 新手友好度 88/100
维护者通常 2 天内回复
-
难度 2/5 1-3 小时 新手友好度 78/100
MerginMaps/geodiff#272 ·
-
难度 2/5 1-3 小时 新手友好度 74/100
open-quantum-safe/liboqs#2644 ·
维护者通常 1 天内回复