[GVNHoist] Hoisting a load drops its optimized MemorySSA clobber, so the pass's own later rounds refuse a legal hoist
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
Missed optimization case: a single `gvn-hoist` run stops one hoist short of its own fixpoint.
Moving a hoisted load's `MemoryUse` (`MSSAUpdater->moveToPlace`, `GVNHoist.cpp:1013-1017` on main) leaves it unoptimized, and the next round of the pass's internal fixpoint loop reads that defining access as a dependence (`safeToHoistLdSt`, `:715-719`) and refuses a hoist its own algorithm computes.
test.ll
```llvm
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
@p = external global i32
@q = external global i32
define i32 @f(i1 %c, i1 %d) {
entry:
br i1 %c, label %left, label %right
left:
store i32 0, ptr @q
br i1 %d, label %left.a, label %left.b
left.a:
%la = load i32, ptr @p
br label %exit
left.b:
%lb = load i32, ptr @p
br label %exit
right:
%lr = load i32, ptr @p
br label %exit
exit:
%r = phi i32 [ %la, %left.a ], [ %lb, %left.b ], [ %lr, %right ]
ret i32 %r
}
```
`opt -passes=gvn-hoist test.ll -S` hoists `%la`/`%lb` into `left` (round one) and stops: two loads of `@p` remain, none in `entry`, although after round one `%la` and `%lr` are the same expression under a common dominator.
Rebuilding MemorySSA is what recovers the hoist.
A second `gvn-hoist` invocation without it changes nothing (byte-identical to the single run).
```
opt -passes='gvn-hoist' test.ll -S -o stale.ll
opt -passes='gvn-hoist,invalidate,gvn-hoist' test.ll -S -o fresh.ll
diff fresh.ll stale.ll
```
```diff
11d10
< %la = load i32, ptr @p, align 4
15a15
> %la = load i32, ptr @p, align 4
24a25
> %lr = load i32, ptr @p, align 4
28c29
< %r = phi i32 [ %la, %left.a ], [ %la, %left.b ], [ %la, %right ]
---
> %r = phi i32 [ %la, %left.a ], [ %la, %left.b ], [ %lr, %right ]
```
After round one, `%la`'s defining access is the store to `@q` (`print`: cached `MemoryUse(1)` vs `MemoryUse(liveOnEntry)` after a rebuild), `entry` properly dominates it, so the round-two hoist is refused.
Contributor guide
Research direction
Start with GVNHoist.cpp:1013-1017 and the dependence check in safeToHoistLdSt at lines 715-719. Reproduce the behavior using the supplied test.ll and the two opt command sequences, comparing stale.ll with fresh.ll. Done means the single gvn-hoist run no longer stops before the additional legal hoist demonstrated after MemorySSA is rebuilt.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 50/100