llvm / llvm/llvm-project

[WebAssembly] Possible missed memarg-offset folding after DAG combine rewrites scaled GEP address

Open
#189,519 1 comment 0 reactions 0 assignees View on GitHub
backend:WebAssembly
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.