Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

likely/unlikely hints dropped in release mode #96275

Closed
SUPERCILEX opened this issue Apr 21, 2022 · 8 comments
Closed

likely/unlikely hints dropped in release mode #96275

SUPERCILEX opened this issue Apr 21, 2022 · 8 comments
Labels
A-LLVM Area: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues. C-bug Category: This is a bug. I-slow Issue: Problems and improvements with respect to performance of generated code.

Comments

@SUPERCILEX
Copy link
Contributor

SUPERCILEX commented Apr 21, 2022

I tried this code:

#![feature(core_intrinsics)]
#![feature(bench_black_box)]

use std::intrinsics::unlikely;

pub fn foo(a: bool) {
    if unlikely(a) {
        std::hint::black_box(42);
    }

    std::hint::black_box(0xDEAD);
    std::hint::black_box(0xBEEF);
}

I expected to see this happen: llvm.expect should be present in the IR
Instead, this happened: it's in debug mode, but gets dropped in release mode

Discovered here: #93668 (comment)

@SUPERCILEX
Copy link
Contributor Author

From @Kobzol:

When the std::intrinsics::unlikely/likely function is used, the codegen doesn't emit llvm.expect annotation in release mode. Curiously enough, in debug mode it does emit it.

A minimal example:

#![feature(core_intrinsics)]

use std::intrinsics::unlikely;

pub fn foo(x: bool) {
    if unlikely(x) {
        println!("foo: {x}");
    }
    println!("bar");
}

Playground link here. In debug mode, LLVM IR contains llvm.expect. In release mode, it doesn't.

This has been previously noted here (maybe it indeed started with LLVM 13?) and more recently here.

I can take a look into this, if you can point me into the right direction. There is a codegen test for likely/unlikely, but it uses -C no-prepopulate-passes, which does not correspond to what release (-O) does.

@nikic
Copy link
Contributor

nikic commented Apr 21, 2022

The playground like doesn't work. Note that llvm.expect is expected to get dropped during optimization and replaced with branch weight metadata -- but I believe there is an open issue that the form in which rustc emits if does not allow LLVM to attach the metadata.

@nikic nikic added A-LLVM Area: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues. I-slow Issue: Problems and improvements with respect to performance of generated code. labels Apr 21, 2022
@Kobzol
Copy link
Contributor

Kobzol commented Apr 21, 2022

Sorry, fixed link here.

Just so that I understand it correctly, "during optimization" means in rustc or in LLVM? I kind of assumed that even in "release" mode, the LLVM IR that gets emitted is IR before applying any LLVM opt passes/optimizations. That's why I expected to see llvm.expect in there.

@nikic
Copy link
Contributor

nikic commented Apr 21, 2022

@Kobzol --emit output is always the final (optimized) result. You'd have to pass -C no-prepopulate-passes to disable optimization.

@Kobzol
Copy link
Contributor

Kobzol commented Apr 21, 2022

Ooh, that makes sense, thanks. If that was not the case, the debug and release output would probably not even differ.

Then I'm not sure if this issue is really valid, since after optimization these annotations can indeed easily disappear. I guess the root of the issue is then the fact that the annotation isn't always behaving as expected (e.g. here), which might be caused by the issue that you have described, with attaching metadata to ifs. (is there a link to that open issue? I couldn't find it in this repo).

@nikic
Copy link
Contributor

nikic commented Apr 21, 2022

Closing this as a duplicate of #88767, which has a bit more analysis and a link to the relevant LLVM change.

@nikic nikic closed this as completed Apr 21, 2022
@RalfJung
Copy link
Member

RalfJung commented Apr 21, 2022

You'd have to pass -C no-prepopulate-passes to disable optimization.

Just not passing -O should disable optimizations, no?

I've seen this "no-prepopulate" thing before and it's one of our worst-named options -- the name explains absolutely nothing about what it does, unless you already know very well how LLVM works... -C disable-optimizations or so would have been so much clearer.^^ Alas, this is stable, so -- water under the bridge.

@nikic
Copy link
Contributor

nikic commented Apr 21, 2022

You'd have to pass -C no-prepopulate-passes to disable optimization.

Just not passing -O should disable optimizations, no?

Yes-ish. We both generate different code at O0 (e.g. omitting some attributes) and LLVM does some optimization at O0 (e.g. inlining #[inline(always)] functions), so not specifying -O and using -O -C no-prepopulate-passes are not quite the same. Though for many cases the distinction is not relevant.

bors added a commit to rust-lang-ci/rust that referenced this issue Jan 22, 2024
#[cold] on match arms

### Edit

This should be in T-lang. I'm not sure how I can change it.

There is discussion: https://rust-lang.zulipchat.com/#narrow/stream/213817-t-lang/topic/Allow.20.23.5Bcold.5D.20on.20match.20and.20if.20arms

### Summary

Adds the possibility to use `#[cold]` attribute on match arms to hint the optimizer that the arm is unlikely to be taken.

### Motivation

These hints are sometimes thought to help branch prediction, but the effect is probably marginal. Modern CPUs don't support hints on conditional branch instructions. They either have the current branch in the BTB (branch prediction buffer), or not, in which case the branch is predicted not to be taken.

These hints are, however, helpful in letting the compiler know what is the fast path, so it can be optimized at the expense of the slow path.

`grep`-ing the LLVM code for BlockFrequencyInfo and BranchProbabilityInfo shows that these hints are used at many places in the optimizer. Such as:
- block placement - improve locality by making the fast path compact and move everything else out of the way
- inlining, loop unrolling - these optimizations can be less aggressive on the cold path therefore reducing code size
- register allocation - preferably keep in registers the data needed on the fast path

### History

RFC 1131 ( rust-lang#26179 ) added `likely` and `unlikely` intrinsics, which get converted to `llvm.expect.i8`. However this LLVM instruction is fragile and may get removed by some optimization passes. The problems with the intrinsics have been reported several times: rust-lang#96276 , rust-lang#96275 , rust-lang#88767

### Other languages

Clang and GCC C++ compilers provide `__builtin_expect`. Since C++20, it is also possible to use `[[likely]]` and `[[unlikely]]` attributes.

Use:
```
if (__builtin_expect(condition, false)) { ... this branch is UNlikely ... }

if (condition) [[likely]] { ... this branch is likely... }
```

Note that while clang provides `__builtin_expect`, it does not convert it to `llvm.expect.i8`. Instead, it looks at the surrounding code and if there is a condition, emits branch weight metadata for conditional branches.

### Design

Implementing `likely`/`unlikely` type of functions properly to emit branch weights would add significant complexity to the compiler. Additionally, these functions are not easy to use with `match` arms.

Replacing the functions with attributes is easier to implement and will also work with `match`.

A question remains whether these attributes should be named `likely`/`unlikely` as in C++, or if we could reuse the already existing `#[cold]` attribute. `#[cold]` has the same meaning as `unlikely`, i.e., marking the slow path, but it can currently only be used on entire functions.

I personally prefer `#[cold]` because it already exists in Rust and is a short word that looks better in code. It has one disadvantage though.
This code:
```
if cond #[likely] { ... }
```
becomes:
```
if cond { ... } #[cold] { ... empty cold branch ... }
```

In this PR, I implemented the possibility to add `#[cold]` attribute on match arms. Use is as follows:
```
match x {
    #[cold] true => { ... } // the true arm is UNlikely
    _ => { ... } // the false arm is likely
}
```

### Limitations
The implementation only works on bool, or integers with single value arm and an otherwise arm. Extending it to other types and to `if` statements should not be too difficult.
bors added a commit to rust-lang-ci/rust that referenced this issue Nov 17, 2024
Likely unlikely fix

RFC 1131 ( rust-lang#26179 ) added likely/unlikely intrinsics, but they have been broken for a while: rust-lang#96276 , rust-lang#96275 , rust-lang#88767 . This PR tries to fix them.

Changes:
- added a new `cold_path()` intrinsic
- `likely()` and `unlikely()` changed to regular functions implemented using `cold_path()`
github-actions bot pushed a commit to rust-lang/miri that referenced this issue Nov 18, 2024
Likely unlikely fix

RFC 1131 ( rust-lang/rust#26179 ) added likely/unlikely intrinsics, but they have been broken for a while: rust-lang/rust#96276 , rust-lang/rust#96275 , rust-lang/rust#88767 . This PR tries to fix them.

Changes:
- added a new `cold_path()` intrinsic
- `likely()` and `unlikely()` changed to regular functions implemented using `cold_path()`
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-LLVM Area: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues. C-bug Category: This is a bug. I-slow Issue: Problems and improvements with respect to performance of generated code.
Projects
None yet
Development

No branches or pull requests

4 participants