[WebAssembly] Possible missed memarg-offset folding after DAG combine rewrites scaled GEP address
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
### Summary
WebAssembly seems to miss a memarg-offset folding opportunity after DAGCombine
reassociates a scaled GEP-based address.
The important point is not that every address expression of this shape is safe
to fold. WebAssembly address selection is intentionally conservative: folding a
constant into a memarg offset is only valid when the corresponding address add
does not rely on unsigned wrapping semantics.
The issue is that the original IR carries useful no-wrap / inbounds information,
but after DAGCombine rewrites the address expression, the final top-level `ADD`
seen by WebAssembly address selection no longer exposes the information in the
form currently required by `SelectAddrAddOperands()`.
As a result, a constant offset that appears foldable is left as a separate
`i32.add` before the load.
### Reproducer
```llvm
@g = external global [4096 x i32]
declare void @llvm.assume(i1)
define i32 @load_scaled_gep_const_offset(i32 %n) {
%ok = icmp ule i32 %n, 3000
call void @llvm.assume(i1 %ok)
%add = add nuw nsw i32 %n, 10
%p = getelementptr inbounds [4096 x i32], ptr @g, i32 0, i32 %add
%v = load i32, ptr %p, align 4
ret i32 %v
}
```
SelectionDAG shape
Initially the address is effectively:
@g + ((n + 10) << 2)
where the IR has:
```llvm
%add = add nuw nsw i32 %n, 10
%p = getelementptr inbounds [4096 x i32], ptr @g, i32 0, i32 %add
```
After DAGCombine, the scaled constant part is reassociated out of the shift,
so the address becomes conceptually:
(@g + (n << 2)) + 40
This exposes a constant 40, which looks like a good candidate for the
WebAssembly memarg offset.
However, the final top-level address add is now a plain ADD without nuw.
Since WebAssembly address selection only folds addends from a top-level ADD
when the add is known not to unsigned-wrap, the selector rejects the fold and
keeps the constant as an explicit add.
Observed codegen shape
The generated code contains an extra add before the load, conceptually:
```asm
i32.const 2
i32.shl
global.get g
i32.add
i32.const 40
i32.add
i32.load 0
```
Desired codegen shape
For cases where the non-wrapping property can be proven or preserved, the
constant should be folded into the memarg offset:
```asm
i32.const 2
i32.shl
global.get g
i32.add
i32.load 40
```
Why this seems like a missed optimization
This does not appear to be a case where the selector should blindly ignore the
nuw requirement. That requirement is important for correctness because
WebAssembly memarg offsets do not model an arbitrary wrapping i32.add.
The narrower problem is that the pipeline has useful information earlier:
the inner add is nuw nsw,
the GEP is inbounds,
the index is range-limited by llvm.assume,
and the constant offset extracted by DAGCombine is positive,
but after reassociation, the final form no longer carries the proof in a way
that WebAssembly address selection can use.
So this looks like a mismatch between DAGCombine's reassociation and
WebAssembly address selection's required proof form.
Question
Is this an intended limitation, or should this be treated as a missed
optimization?
Possible directions seem to be:
preserve or reconstruct the relevant no-wrap information when DAGCombine
rewrites the scaled address,
teach WebAssembly address selection to recognize this specific proven-safe
pattern more directly,
or leave this as-is if the necessary proof is not soundly available at this
stage.
### Why this should be foldable
In this reproducer, the GEP address is:
@g + ((%n + 10) * 4)
because the element type is i32.
The llvm.assume constrains %n to 0 <= %n <= 3000, so %n + 10 stays within
the [4096 x i32] object. Therefore the scaled address can be split as:
@g + ((%n + 10) * 4)
= @g + (%n * 4) + 40
So the constant 40 is a positive in-bounds byte offset derived from the
original GEP. Conceptually, WebAssembly can lower this as:
base = @g + (%n * 4)
offset = 40
and emit:
i32.load offset=40
instead of materializing the + 40 as a separate i32.add before the load.
The missed part is that after DAGCombine exposes this as:
(@g + (%n << 2)) + 40
the final top-level ADD no longer carries the no-unsigned-wrap proof in the
form currently required by WebAssembly address selection.
Contributor guide
Research direction
Compile the provided LLVM IR reproducer for WebAssembly and inspect how DAGCombine changes the address before it reaches SelectAddrAddOperands(). Compare the observed extra i32.add with the desired memarg offset, then determine whether the original no-wrap, inbounds, and assume information can be preserved soundly; done means safe cases fold without weakening the no-wrap requirement.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- wasm
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100