llvm / llvm/llvm-project

Fold adjacent narrow loads used in shift/or byte packing into a wider load

Open
#201,107 4 comments 0 reactions 0 assignees View on GitHub
llvm:optimizations missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

I found a pattern where several adjacent narrow loads are zero-extended, shifted, and ORed together to construct a wider integer value. In some cases, this can be reduced to a single wider load followed by a shift, and optionally a byte swap depending on the byte order being constructed.

For example, the following pattern builds a big-endian 32-bit value from four adjacent i8 loads and then shifts it into position:

```llvm
declare void @llvm.assume(i1)
declare i32 @llvm.bswap.i32(i32)

define i64 @src_pack4_i8_be_shift_var_step(ptr %p, i64 %acc, i64 %s, i64 %step) {
%step.is.8 = icmp eq i64 %step, 8
call void @llvm.assume(i1 %step.is.8)

%lo = icmp uge i64 %s, 24
call void @llvm.assume(i1 %lo)
%hi = icmp ult i64 %s, 64
call void @llvm.assume(i1 %hi)

%step2 = shl i64 %step, 1
%step3 = add i64 %step2, %step

%b0 = load i8, ptr %p, align 1
%z0 = zext i8 %b0 to i64
%sh0 = shl i64 %z0, %s
%or0 = or i64 %acc, %sh0

%p1 = getelementptr i8, ptr %p, i64 1
%s1 = sub nsw i64 %s, %step
%b1 = load i8, ptr %p1, align 1
%z1 = zext i8 %b1 to i64
%sh1 = shl i64 %z1, %s1
%or1 = or i64 %or0, %sh1

%p2 = getelementptr i8, ptr %p, i64 2
%s2 = sub nsw i64 %s, %step2
%b2 = load i8, ptr %p2, align 1
%z2 = zext i8 %b2 to i64
%sh2 = shl i64 %z2, %s2
%or2 = or i64 %or1, %sh2

%p3 = getelementptr i8, ptr %p, i64 3
%s3 = sub nsw i64 %s, %step3
%b3 = load i8, ptr %p3, align 1
%z3 = zext i8 %b3 to i64
%sh3 = shl i64 %z3, %s3
%r = or i64 %or2, %sh3

ret i64 %r
}
```
On a little-endian target, this is equivalent to:
```llvm
define i64 @tgt_pack4_i8_be_shift_var_step(ptr %p, i64 %acc, i64 %s, i64 %step) {
%lo = icmp uge i64 %s, 24
call void @llvm.assume(i1 %lo)
%hi = icmp ult i64 %s, 64
call void @llvm.assume(i1 %hi)

%step2 = shl i64 %step, 1
%step3 = add i64 %step2, %step
%s3 = sub nsw i64 %s, %step3

%word.le = load i32, ptr %p, align 1
%word.be = call i32 @llvm.bswap.i32(i32 %word.le)
%word64 = zext i32 %word.be to i64
%shifted = shl i64 %word64, %s3
%r = or i64 %acc, %shifted

ret i64 %r
}
```
This transform has been checked with Alive2 under the assumptions that step == 8 and 24 <= s < 64.

The important part is not specifically the bswap. The more general optimization opportunity is to recognize when adjacent narrow loads are used to construct a contiguous wider integer through non-overlapping shifts and ORs. Depending on the order of the bytes being constructed, the result can be represented as a plain wider load, a wider load plus bswap, or a wider load plus another simple reordering operation.

For this specific case:
```
p[0] << s |
p[1] << (s - 8) |
p[2] << (s - 16) |
p[3] << (s - 24)
```
can be represented as:
```
zext(bswap32(load i32 p)) << (s - 24)
```
on a little-endian target.

The required conditions seem to be:

the narrow loads are adjacent;
the loads are ordinary non-volatile, non-atomic loads;
the wider load reads exactly the same bytes;
the shifted bit ranges do not overlap;
the shift amounts are known to be in range;
the transform accounts for target endianness.

This pattern appears in byte packing / bitstream decoding code, where source code often loads bytes one by one and combines them with shifts and ORs. Recognizing this pattern could reduce multiple loads and several shift/or operations into one wider load and a small number of integer operations.

AliveProof : https://alive2.llvm.org/ce/z/C4NjBf
Compiler-explorer sample & perf : https://compiler-explorer.com/z/dsG9hKn5f
RealWorld Usage : https://github.com/dtcxzyw/llvm-opt-benchmark-nightly/blob/e4419a3b46026ae3b573db3d710d4f069bbbbee0/report/oiio/ImfFastHuf.ll#L460-L461

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the LLVM IR pattern from the issue with the linked Alive2 proof and Compiler Explorer sample. Read the referenced ImfFastHuf.ll lines as a real-world case, then locate the relevant LLVM optimization pass and its tests. Done means covered adjacent-load orderings preserve endianness and are verified by IR tests and performance checks.

Written by the indexing model from the issue text.

Assessment

Domain
compilers, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.