llvm / llvm/llvm-project

[GVNHoist] Hoisting a load drops its optimized MemorySSA clobber, so the pass's own later rounds refuse a legal hoist

Open
#221,578 0 comments 0 reactions 0 assignees View on GitHub
llvm:GVN missed-optimization
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.