llvm / llvm/llvm-project

Use `range` attributes to pick smaller branch assembly phrasings

Open
#192,772 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

Compare these two functions:
```llvm
define void @test_directly(i32 noundef range(i32 -1, 1114112) %x) local_unnamed_addr #0 {
start:
%0 = icmp eq i32 %x, -1 ; <-- Note `x == -1`
br i1 %0, label %bb1, label %bb2
bb1:
tail call void @foo(i32 noundef %x)
br label %bb3
bb2:
tail call void @bar(i32 noundef %x)
br label %bb3
bb3:
ret void
}

define void @test_relative(i32 noundef range(i32 -1, 1114112) %x) local_unnamed_addr #0 {
start:
%0 = icmp slt i32 %x, 0 ; <-- Note `x < 0`
br i1 %0, label %bb1, label %bb2
bb1:
tail call void @foo(i32 noundef %x)
br label %bb3
bb2:
tail call void @bar(i32 noundef %x)
br label %bb3
bb3:
ret void
}
```

They're equivalent because under that `range` restriction, `x == -1` and `x < 0` are equivalent tests.

The latter is slightly better (at least on x86) because it can use `test`+`jns` which saves a byte over `cmp`+`jne`, per

I don't know where would be best to fix this -- is it worth changing the `icmp` in the middle-end? [(it doesn't today)](https://llvm.godbolt.org/z/ssfo68s6d) should this be backend-only? -- but it would be nice if it did the right thing regardless of which way the programmer wrote it.

---

Context: this comes from looking at `Option` and `Option>` in rust, since we emit `range` attributes for them (cc https://github.com/rust-lang/rust/pull/155473)

Contributor guide

Open the contributing guide

Research direction

Start with the two LLVM IR examples and the linked Godbolt comparisons, then investigate the middle-end `icmp` handling versus backend branch selection described in the issue. Done means equivalent range-constrained tests select the smaller branch assembly regardless of whether the source comparison is `x == -1` or `x < 0`.

Written by the indexing model from the issue text.

Assessment

Domain
compilers, performance
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.