[SelectOptimize][AArch64] Converts profitable select into unpredictable branch for sentinel-loop conditional increment
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
`SelectOptimize` converts a conditional-increment pattern inside a sentinel-terminated loop into a branch on AArch64, even though the branch is data-dependent and effectively unpredictable in the motivating workload. The `select`-based lowering (`csel`) is faster in practice; the branch-based lowering that `SelectOptimize` produces introduces a mispredicted branch on every iteration.
This was discovered while investigating a performance regression in Rust's `BinaryHeap::sift_down`, where the same conditional-increment shape appears in the sift-down bounds/comparison loop.
## Reproducer
compile the code below with `llc -O3`.
```llvm
target datalayout = "e-m:e-p270:32:32-p271:32-p272:64:64-i8:8:32-i16:16:32-i64:64-i128-n32:64-S128-Fn32"
target triple = "aarch64-unknown-linux-gnu"
define i64 @conditional_increment(ptr %data, i64 %base, i64 %sentinel) {
entry:
br label %loop
loop:
%index = phi i64 [ 0, %entry ], [ %index.next, %body ]
%done = icmp eq i64 %index, %sentinel
br i1 %done, label %exit, label %body
body:
%offset = or i64 %index, 1
%ptr = getelementptr [8 x i8], ptr %data, i64 %offset
%value = load i64, ptr %ptr, align 8
%condition = icmp ule i64 %base, %value
%increment = zext i1 %condition to i64
%index.next = add i64 %base, %increment
br label %loop
exit:
ret i64 %index
}
```
## Expected behavior
The `select`/`csel-based` lowering of `%increment`/`%index.next` should be preserved.
```asm
ldr x8, [x0, x8]
cmp x1, x8
cinc x8, x1, ls // using cinc instead of b.h1
cmp x8, x2
b.ne .LBB0_1
```
## Actual behavior
SelectOptimize converts the zext+add conditional-increment into an explicit branch, which leads to lots of branch miss in Rust [`BinaryHeap::sift_down`](https://github.com/rust-lang/rust/blob/28e8a8c81bf3b37909edac6c2a76e56f30cd492f/library/alloc/src/collections/binary_heap/mod.rs#L851).
```asm
ldr x8, [x0, x8]
cmp x1, x8
mov x8, x1
b.hi .LBB0_1
add x8, x1, #1
b .LBB0_1
```
cc @Amanieu
Contributor guide
Research direction
Start by compiling the supplied LLVM IR with llc -O3 for AArch64 and inspect the SelectOptimize transformation that produces the branch-based conditional increment. Compare the generated code with the csel-based expected output and the Rust BinaryHeap::sift_down example linked in the issue. Done means the profitable select form is preserved for this pattern without introducing the unpredictable branch.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- compilers, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100