llvm / llvm/llvm-project

[CodeGenPrepare] misses masked byte-insert store narrowing

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

Description

LLVM currently leaves some masked byte-insert read-modify-write patterns as wide integer stores until late codegen.

A common IR shape is:

```llvm
%old = load i32, ptr %p, align 8
%shifted = shl i32 %x, 16
%ins = and i32 %shifted, 16711680
%clr = and i32 %old, -16711681
%new = or disjoint i32 %clr, %ins
store i32 %new, ptr %p, align 8
```

This is equivalent, on little-endian targets, to:
```llvm
%byte = trunc i32 %x to i8
%p.byte = getelementptr i8, ptr %p, i64 2
store i8 %byte, ptr %p.byte, align 2
```

The wide form is a read-modify-write sequence, while the narrowed form is just a byte store. This can remove the load, dynamic mask/shift/or chain, and the wide store.

For example, with llvm-mca on a reduced x86-64 case:

```text
src
Iterations: 100
Instructions: 1100
Total Cycles: 706
Total uOps: 1500
Block RThroughput: 3.8

tgt
Iterations: 100
Instructions: 300
Total Cycles: 104
Total uOps: 300
Block RThroughput: 1.0
```

I prototyped a CodeGenPrepare fold that rewrites this when:

```text
- the load and store use the same pointer
- the stored value is (load & ~Mask) | (insert & Mask)
- Mask is exactly an 8-bit shifted mask
- insert is either x or x << shift
- shift matches the mask position
- the shift has no poison-generating flags
- there is no memory clobber / mayThrow between the load and store
- the load/store are simple non-atomic non-volatile accesses
- the target allows i8 stores
I then ran the patched opt over llvm-opt-benchmark/bench/**/optimized/*.ll.
```

Result:
```text
Files scanned: 38,729
Matches: 40
```

AliveProof : https://alive2.llvm.org/ce/z/fmw2LY
Compiler-explorer & perf : https://compiler-explorer.com/z/Ts754cbfM

RealWorld Usage: https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/qemu/optimized/tcg-op.ll#L7

see more usage

https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/qemu/optimized/tcg-op.ll#L7
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/qemu/optimized/tcg-op.ll#L25
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/qemu/optimized/tcg-op.ll#L41
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/qemu/optimized/tcg-op.ll#L57
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/qemu/optimized/tcg-op.ll#L75
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/qemu/optimized/tcg-op.ll#L95
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/qemu/optimized/tcg-op.ll#L117
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/abc/optimized/ifMan.ll#L1029
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/abc/optimized/ifMan.ll#L3057
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/abc/optimized/ifMan.ll#L3431
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/opencv/optimized/sift.dispatch.ll#L5222
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/glslang/optimized/glslang_tab.ll#L42636
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/glslang/optimized/SpirvIntrinsics.ll#L4312
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/glslang/optimized/ParseHelper.ll#L31286
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/ozz-animation/optimized/jsoncpp.ll#L3129
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/ozz-animation/optimized/jsoncpp.ll#L20591
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/minetest/optimized/COBJMeshFileLoader.ll#L6885
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/minetest/optimized/COBJMeshFileLoader.ll#L7069
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/minetest/optimized/COBJMeshFileLoader.ll#L7252
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/sentencepiece/optimized/normalizer.ll#L3782
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/sentencepiece/optimized/normalizer.ll#L4424
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/sentencepiece/optimized/normalizer.ll#L6678
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/php/optimized/php_dom.ll#L1652
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/sentencepiece/optimized/unigram_model.ll#L14817
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/sentencepiece/optimized/unigram_model.ll#L15459
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/sentencepiece/optimized/unigram_model.ll#L17713
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/sentencepiece/optimized/builder.ll#L21884
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/sentencepiece/optimized/builder.ll#L22526
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/sentencepiece/optimized/builder.ll#L24780
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/llvm/optimized/SemaInit.ll#L8114
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/ffmpeg/optimized/movtextenc.ll#L1077
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/postgres/optimized/ts_parse.ll#L993
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/postgres/optimized/ts_parse.ll#L1103
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/openusd/optimized/primIndex_Graph.ll#L327
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/c3c/optimized/expr.ll#L1178
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/c3c/optimized/ast.ll#L596
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/c3c/optimized/ast.ll#L632
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/c3c/optimized/parse_global.ll#L3312
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/c3c/optimized/sema_decls.ll#L2307
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/quickjs/optimized/quickjs.ll#L69554

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.