llvm / llvm/llvm-project

Optimize lexicographical-`<` on unsigned pairs better

Open
#212,903 0 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

Lexicographical `<` on a pair of unsigned numbers like `std::pair` in C++ or `(u32, u32)` in Rust can be simplified to comparison of a `u64` with the correct byte ordering but unfortunately LLVM does not do that today.

```llvm
define i1 @src(i64 noundef %a, i64 noundef %b) noundef zeroext {
start:
%a1.sroa.4.0.extract.shift = lshr i64 noundef %a, 32
%b2.sroa.4.0.extract.shift = lshr i64 noundef %b, 32
%_10 = icmp eq i64 %a1.sroa.4.0.extract.shift, %b2.sroa.4.0.extract.shift
%b2.sroa.0.0.extract.trunc = trunc i64 noundef %b to i32
%a1.sroa.0.0.extract.trunc = trunc i64 noundef %a to i32
%x0 = icmp ult i32 %a1.sroa.0.0.extract.trunc, %b2.sroa.0.0.extract.trunc
%_11 = icmp samesign ult i64 %a1.sroa.4.0.extract.shift, %b2.sroa.4.0.extract.shift
%_0.sroa.0.0.in = select i1 %_10, i1 %x0, i1 %_11
ret i1 %_0.sroa.0.0.in
}
=>
define i1 @tgt(i64 noundef %a, i64 noundef %b) noundef zeroext {
start:
%c = icmp ult i64 noundef %a, noundef %b
ret i1 %c
}
Transformation seems to be correct!
```

The above is written without pointers to make an Alive2 proof, but of course a more realistic version is something passed with pointers, as [pair's `operator<`](https://en.cppreference.com/cpp/utility/pair/operator_cmp) and [tuple's `PartialOrd::lt`](https://doc.rust-lang.org/std/primitive.tuple.html#impl-PartialOrd-for-(T,)) both do.

Comparing in field declaration order is unfortunately backwards from what would be ideal for little-endian, giving something like
```llvm
define noundef zeroext i1 @demo(ptr noalias nofree noundef readonly align 4 captures(none) dereferenceable(8) %a, ptr noalias nofree noundef readonly align 4 captures(none) dereferenceable(8) %b) unnamed_addr {
start:
%_8 = load i32, ptr %a, align 4, !noundef !4
%_9 = load i32, ptr %b, align 4, !noundef !4
%0 = icmp eq i32 %_8, %_9
%1 = icmp ult i32 %_8, %_9
%2 = getelementptr inbounds nuw i8, ptr %a, i64 4
%_11 = load i32, ptr %2, align 4
%3 = getelementptr inbounds nuw i8, ptr %b, i64 4
%_12 = load i32, ptr %3, align 4
%4 = icmp ult i32 %_11, %_12
%_3.sroa.0.0 = select i1 %0, i1 %4, i1 %1
ret i1 %_3.sroa.0.0
}
```

```asm
demo:
mov ecx, dword ptr [rdi]
mov eax, dword ptr [rdi + 4]
xor edx, edx
cmp eax, dword ptr [rsi + 4]
setb dl
xor eax, eax
cmp ecx, dword ptr [rsi]
setb al
cmove eax, edx
ret
```
But that could potentially be better with something doing one comparison, perhaps
```asm
demo_alt:
rorx rax, qword ptr [rdi], 32
rorx rcx, qword ptr [rsi], 32
cmp rax, rcx
setb al
ret
```

And if someone *does* write the comparison with a different field order, it still doesn't compile down:
```llvm
define noundef zeroext i1 @demo2(ptr noalias nofree noundef readonly align 4 captures(none) dereferenceable(8) %_1, ptr noalias nofree noundef readonly align 4 captures(none) dereferenceable(8) %_2) unnamed_addr {
start:
%0 = getelementptr inbounds nuw i8, ptr %_1, i64 4
%a1 = load i32, ptr %0, align 4, !noundef !4
%1 = getelementptr inbounds nuw i8, ptr %_2, i64 4
%b1 = load i32, ptr %1, align 4, !noundef !4
%_8 = icmp eq i32 %a1, %b1
%b0 = load i32, ptr %_2, align 4
%a0 = load i32, ptr %_1, align 4
%2 = icmp ult i32 %a0, %b0
%_9 = icmp ult i32 %a1, %b1
%_0.sroa.0.0.in = select i1 %_8, i1 %2, i1 %_9
ret i1 %_0.sroa.0.0.in
}
```

```asm
demo2:
mov eax, dword ptr [rdi]
mov ecx, dword ptr [rdi + 4]
xor edx, edx
cmp eax, dword ptr [rsi]
setb dl
xor eax, eax
cmp ecx, dword ptr [rsi + 4]
setb al
cmove eax, edx
ret
```
where ideally it could just be
```asm
mov rax, qword ptr [rdi]
cmp rax, qword ptr [rsi]
setb al
ret
```

(And of course for the other kinds of `icmp`s too, but `<` is probably the most important.)

---

I have no idea where the right place to fix this is, though 😬

It would be nice if things like https://github.com/bevyengine/bevy/pull/10558/changes#diff-64745065a7cefb843c5c5a881c561330ee9d06d3f1f36c28321788b97e64d88fR169-R172 weren't ever needed because LLVM could always notice the optimal thing for cases like this.

cc https://github.com/rust-lang/rust/issues/140167

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the scalar IR examples in Alive2 and the LLVM Godbolt links to confirm the missed transformation and expected instruction counts. Then locate the LLVM optimization pass responsible for integer comparisons; done means the pair-like unsigned lexicographical comparison is recognized as a packed integer comparison without regressing the other icmp cases described.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, rust
Domain
compilers, performance
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.