llvm / llvm/llvm-project

[DAGCombine] could shrink more load/masked-merge/store patterns to narrow stores

Open
#198,356 5 comments 0 reactions 1 assignee Claimed by @ParkHanbum View on GitHub
llvm:codegen llvm:SelectionDAG missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

## Summary

SelectionDAG's `ReduceLoadOpStoreWidth` / `ShrinkLoadReplaceStoreWithStore`
already handles the literal-constant form of a load/masked-merge/store idiom
when the preserved load operand has the shape `(and (load P), C)`:

```llvm
%old = load i64, ptr %p, align 8
%new = and i64 %x, 65535
%old.rest = and i64 %old, -65536
%merged = or disjoint i64 %old.rest, %new
store i64 %merged, ptr %p, align 8
```

On little-endian targets, this correctly lowers to a narrow store:

```asm
movw %si, (%rdi)
retq
```

There are closely related canonical forms that are not recognized, even though
they describe the same byte replacement.

## Reproducer

```llvm
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

declare void @llvm.assume(i1)

define void @src(ptr %p, i64 %x, i64 %C) {
entry:
%is.low16.mask = icmp eq i64 %C, 65535
call void @llvm.assume(i1 %is.low16.mask)

%notC = xor i64 %C, -1
%old = load i64, ptr %p, align 8
%new.bytes = and i64 %x, %C
%old.rest = and i64 %old, %notC
%merged = or disjoint i64 %old.rest, %new.bytes
store i64 %merged, ptr %p, align 8
ret void
}
```

Run:

```sh
llc -O2 repro.ll -o -
```

Current output:

```asm
movq (%rdi), %rax
xorq %rax, %rsi
andq %rdx, %rsi
xorq %rax, %rsi
movq %rsi, (%rdi)
retq
```

Expected output:

```asm
movw %si, (%rdi)
retq
```

The same pattern applies to low 8 and low 32 masks:

```llvm
; low 8
%is.low8.mask = icmp eq i64 %C, 255
; expected: store i8 (trunc i64 %x), ptr %p

; low 32
%is.low32.mask = icmp eq i64 %C, 4294967295
; expected: store i32 (trunc i64 %x), ptr %p
```

## Notes

The relevant code is in:

* `llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp`
* `CheckForMaskedLoad`
* `ShrinkLoadReplaceStoreWithStore`
* `DAGCombiner::ReduceLoadOpStoreWidth`

The existing matcher is quite specific about the shape of the masked load side.
It may be worth generalizing it to recognize equivalent masked-merge forms, for
example when the load-preserving mask has already been canonicalized separately
from the replacement mask.

## Correctness

For the low-16 case, the source:

```llvm
store i64 ((load i64, ptr %p) & ~0xffff) | (%x & 0xffff), ptr %p
```

is equivalent on little-endian targets to:

```llvm
store i16 (trunc i64 %x to i16), ptr %p
```

when the memory operation is simple/non-volatile/non-atomic and the usual
SelectionDAG chain-dependency checks are satisfied. The same argument applies
to low 8 and low 32 masks with `store i8` and `store i32`, respectively.

Alive Proof: https://alive2.llvm.org/ce/z/ycDrm5
Compiler-explorer sample & perf : https://compiler-explorer.com/z/rhcY6vsMr
RealWorld Usage: https://github.com/dtcxzyw/llvm-opt-benchmark-nightly/blob/f4c50e2416e5cef12ac1bd102510ee8f322cfcd7/report/redis/quicklist.ll#L135

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.