Fold adjacent narrow loads used in shift/or byte packing into a wider load
- 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
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