llvm / llvm/llvm-project

[InstCombine] Missed store combine for reversed byte stores when a disjoint wide store is present

Open
#198,242 0 comments 0 reactions 1 assignee Claimed by @ParkHanbum View on GitHub
llvm:instcombine
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

## Summary

LLVM codegen can combine this reversed-byte-store pattern:

```llvm
store i8 (trunc %v), ptr %base+63
store i8 (trunc (%v >> 8)), ptr %base+62
...
store i8 (trunc (%v >> 56)), ptr %base+56
```

into a byte-swap plus one wide store on little-endian targets.

However, if there is a disjoint `i64` store to `%base+72` in the same block,
the combine no longer fires. This leaves eight byte stores in the final
assembly, even though the target form lowers well on many backends.

The addresses `%base+56..63` and `%base+72..79` do not overlap.

## Reproducer

```llvm
define void @src_wide_before(ptr %dst, i64 %v) {
entry:
%p72 = getelementptr inbounds i8, ptr %dst, i64 72
store i64 %v, ptr %p72, align 8

%b0 = trunc i64 %v to i8
%p63 = getelementptr inbounds i8, ptr %dst, i64 63
store i8 %b0, ptr %p63, align 1

%s8 = lshr i64 %v, 8
%b1 = trunc i64 %s8 to i8
%p62 = getelementptr inbounds i8, ptr %dst, i64 62
store i8 %b1, ptr %p62, align 2

%s16 = lshr i64 %v, 16
%b2 = trunc i64 %s16 to i8
%p61 = getelementptr inbounds i8, ptr %dst, i64 61
store i8 %b2, ptr %p61, align 1

%s24 = lshr i64 %v, 24
%b3 = trunc i64 %s24 to i8
%p60 = getelementptr inbounds i8, ptr %dst, i64 60
store i8 %b3, ptr %p60, align 4

%s32 = lshr i64 %v, 32
%b4 = trunc i64 %s32 to i8
%p59 = getelementptr inbounds i8, ptr %dst, i64 59
store i8 %b4, ptr %p59, align 1

%s40 = lshr i64 %v, 40
%b5 = trunc i64 %s40 to i8
%p58 = getelementptr inbounds i8, ptr %dst, i64 58
store i8 %b5, ptr %p58, align 2

%s48 = lshr i64 %v, 48
%b6 = trunc i64 %s48 to i8
%p57 = getelementptr inbounds i8, ptr %dst, i64 57
store i8 %b6, ptr %p57, align 1

%s56 = lshr i64 %v, 56
%b7 = trunc i64 %s56 to i8
%p56 = getelementptr inbounds i8, ptr %dst, i64 56
store i8 %b7, ptr %p56, align 8

ret void
}

define void @tgt_wide_before(ptr %dst, i64 %v) {
entry:
%p72 = getelementptr inbounds i8, ptr %dst, i64 72
store i64 %v, ptr %p72, align 8

%bswap = call i64 @llvm.bswap.i64(i64 %v)
%p56 = getelementptr inbounds i8, ptr %dst, i64 56
store i64 %bswap, ptr %p56, align 8
ret void
}

declare i64 @llvm.bswap.i64(i64)
```

## Commands

```sh
llc -O2 -mtriple=x86_64-unknown-linux-gnu repro.ll -o -
llc -O2 -mtriple=x86_64-unknown-linux-gnu -mcpu=haswell repro.ll -o -
llc -O2 -mtriple=aarch64-unknown-linux-gnu repro.ll -o -
llc -O2 -mtriple=riscv64-unknown-linux-gnu -mattr=+zbb repro.ll -o -
```

Tested with:

```text
LLVM version 23.0.0git
Optimized build with assertions.
```

## Actual x86-64 codegen

For `@src_wide_before`, x86-64 keeps eight byte stores:

```asm
src_wide_before:
movq %rsi, %rax
movq %rsi, 72(%rdi)
movb %al, 63(%rdi)
movb %ah, 62(%rdi)
movl %eax, %ecx
shrl $16, %ecx
movb %cl, 61(%rdi)
movl %eax, %ecx
shrl $24, %ecx
movb %cl, 60(%rdi)
movq %rsi, %rcx
shrq $32, %rcx
movb %cl, 59(%rdi)
movq %rsi, %rcx
shrq $40, %rcx
movb %cl, 58(%rdi)
movq %rsi, %rcx
shrq $48, %rcx
movb %cl, 57(%rdi)
shrq $56, %rax
movb %al, 56(%rdi)
retq
```

The canonicalized `@tgt_wide_before` lowers as desired:

```asm
tgt_wide_before:
movq %rsi, 72(%rdi)
bswapq %rsi
movq %rsi, 56(%rdi)
retq
```

With `-mcpu=haswell`, the target form is even shorter:

```asm
tgt_wide_before:
movq %rsi, 72(%rdi)
movbeq %rsi, 56(%rdi)
retq
```

## Actual AArch64 codegen

For `@src_wide_before`, AArch64 also keeps byte stores:

```asm
src_wide_before:
lsr x8, x1, #8
lsr x9, x1, #16
str x1, [x0, #72]
strb w1, [x0, #63]
strb w8, [x0, #62]
lsr x8, x1, #24
strb w9, [x0, #61]
lsr x9, x1, #32
strb w8, [x0, #60]
lsr x8, x1, #40
strb w9, [x0, #59]
lsr x9, x1, #56
strb w8, [x0, #58]
lsr x8, x1, #48
strb w9, [x0, #56]
strb w8, [x0, #57]
ret
```

The canonicalized form lowers to:

```asm
tgt_wide_before:
rev x8, x1
str x1, [x0, #72]
str x8, [x0, #56]
ret
```

## Control cases

The offset itself does not seem to be the issue. Without the disjoint
`store i64 %v, ptr %dst+72`, the same reversed byte stores at `%dst+56..63`
are combined successfully.

For example, x86-64 lowers the source directly to:

```asm
bswapq %rsi
movq %rsi, 56(%rdi)
```

AArch64 lowers the source directly to:

```asm
rev x8, x1
str x8, [x0, #56]
```

Putting the disjoint wide store in the middle of the byte-store sequence
also prevents the full combine. Some targets partially combine a few bytes
into 16-bit stores, but they still do not form the full byte-swap plus wide
store.

## Targets observed

The source with the disjoint wide store leaves byte or partial stores on:

- x86-64
- x86-64 `-mcpu=haswell`
- AArch64
- ARMv7
- RISC-V64 `+zbb`
- LoongArch64
- PPC64LE
- MIPS64EL r2
- wasm32

The canonicalized target form lowers well on these targets, for example to
`bswapq`/`movbeq`, `rev`, `rev8`, `revb.d`, `stdbrx`, or `dsbh`+`dshd`.

## Expected

The disjoint store to `%dst+72..79` should not prevent combining the stores
to `%dst+56..63`, since the ranges do not overlap and all stores are plain
non-volatile, non-atomic stores.

Expected x86-64 style lowering:

```asm
movq %rsi, 72(%rdi)
bswapq %rsi
movq %rsi, 56(%rdi)
```

or, where profitable:

```asm
movq %rsi, 72(%rdi)
movbeq %rsi, 56(%rdi)
```

## Notes

This looks like a missed backend store-combining opportunity. The combine
works for the minimal pattern and for the same pattern at offset 56, but it
fails once a disjoint wide store to the same base pointer is present in the
same memory chain.

Alive Proof: https://alive2.llvm.org/ce/z/3_5Dvm
Compiler-explorer: https://compiler-explorer.com/z/o57s6co1c
RealWorld Usage: https://github.com/dtcxzyw/llvm-opt-benchmark-nightly/blob/f4c50e2416e5cef12ac1bd102510ee8f322cfcd7/report/redis/sha256.ll#L166

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.