llvm / llvm/llvm-project

[SelectOptimize][AArch64] Converts profitable select into unpredictable branch for sentinel-loop conditional increment

Open
#223,947 1 comment 0 reactions 0 assignees View on GitHub
backend:AArch64 missed-optimization
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.