Pre-RFC: Stabilization of `likely(bool)`, `unlikely(bool)` & `assume(bool)` intrinsics

[alonely0]

@scottmcm

Assume is now a MIR primitive, in part to avoid needing a Call and another BB ever time you use it. We might be able to do the same with some kind of "expect this value".

If assume and unreachable_unchecked have MIR primitives, could we make likely & unlikely have their own that expand to llvm.expect?

[CAD97]

@scottmcm

Alternatively, we could have some kind of builtin# for an unpredictable select, rather than trying to expose the same "here's a pseudo-function that's useless in most places" form that C extensions tend to use.

(Just cause I thought of it)

The two major advantages of using pseudofunctions for intrinsics are:

• Obvious syntax that looks like a function makes sense if the builtin roughly has function call semantics (is a value expression taking a fixed arity list of value expressions as arguments).
• A reasonably simple and straightforward place to attach documentation to the list of and individual intrinsics, roughly matching existing documentation expectations of developers.

IIUC we currently have roughly three different ways of giving magic powers to std library code: builtin# (arbitrary syntax), extern "rust-intrinsic" (pseudofunction), and #[rustc_builtin_macro] (pseudomacro). (And, well, #[lang].) If it weren't for the discoverability benefits of core::intrinsics, I'd suggest normalizing everything to builtin#functionlike(...) (for builtins which act like they have simple function semantics) and builtin#macrolike!() (for things which which don't behave like a simple function). And the fact that transmute is stably exposed as extern "rust-intrinsic" because it's a function with extra magic typeck constraints right now. (Also the whole point of builtin# IIRC was to be able to use non-functionlike syntaxes, e.g. perhaps builtin#yeet value, for internal/experimental functionality that wouldn't like having to introduce more bracketing.)

[8573]

I also would support propagating unreachable_unchecked's _unchecked suffix to assume. It may be redundant, but I would consider it useful to emphasize and make obvious, both to the writer and to a reviewer, that this is doing dangerous, encouraging more careful review.

[alonely0]

Isn't that the purpose of unsafe?

[scottmcm]

@CAD97

I'd suggest normalizing everything to builtin#functionlike(...) (for builtins which act like they have simple function semantics)

The thing I like more about the current way of doing intrinsics is that -- at least for the things that work as functions -- it means it can work like functions everywhere until the backend. (Modulo some things that don't work, like function pointers.)

[cg909]

@alonely0

I don't think that there's a way to inject LLVM IR without using intrinsics. We could use attributes, but they're still experimental on expressions, so that's a no.

I think attributes are a better match for likely, unlikely and unpredictable, as those practically only have an effect when control flow decisions directly depend on them (AFAIK the LLVM intrinsic llvm.expect, which is used to implement likely, only influences edge weight metadata on dependent branches and is a no-op if no branching directly depends on it). As attributes they could only be valid when directly attached to an if or match arm. If they are implemented as functions it's too easy to produce code that looks like it should affect the optimizer when it doesn't do anything.

In the end the compiler would of course desugar these attributes to intrinsic calls.

Attributes on statements (including expression statements) and on match arms are already stable. That would make it at least possible to use them on ifs and matches written like statements:

#[likely]
if foo == bar {
  println!("this is likely");
} else {
  println!("this is unlikely");
}

#[unlikely]
if let Some(bar) = foo {
  println!("we don't expect this Option to contain something here");
  return Err(bar);
}

#[unpredictable]
match foo {
  "bar" => call_a(),
  "baz" => call_b(),
  _ => call_c()
}

let x = match foo {
  #[likely]
  "bar" => 1,
  "baz" => 2,
  _ => 3,
};

If likely, unlikely and unpredictable were provided as functions, e.g. directly affecting an if let would be impossible:

let _ = likely(foo.is_some()); // most certainly has no effect for the `if let` below

if let Some(bar) = foo { // where should the `likely()` go?
  todo!();
}

[Neutron3529]

@cg909

If likely, unlikely and unpredictable were provided as functions, e.g. directly affecting an if let would be impossible:

Be aware of if-let chains

if let likely(Some(x))=a && let unlikely(Some(y))=b {
   // where should the `likely` go with attributes on statements?
}

Currently, such grammar is acceptable:

#![feature(let_chains)]
struct likely<T>(T);
fn main(){
    let a=Some(2);
    let b=Some(3);
    if let likely(Some(x))=likely(a) && let likely(Some(y))=likely(b) {
        println!("{x} {y}");
    }
}

[bjorn3]

@josh

I was talking about a built-in operation that expanded as directly as possible to the appropriate LLVM IR (llvm.expect ) without having to wait for functions to get inlined, to avoid the problem that @bjorn3 was referring to.

It was those LLVM intrinsics themself I was talking about. As far as I understand they stay calls until late in the compilation process.

[quaternic]

@Neutron3529

if let likely(Some(x))=a && let unlikely(Some(y))=b {
   // where should the `likely` go with attributes on statements?
}

let-else is a possible branch as well, so it might be useful to have:

#[unlikely]
let Err(e) = res else { return };

By extension of that, let-chains might then allow

// the if-branch as a whole is unlikely
// but the individual options are unpredictable
// so it might be best to first branch on
// `left.is_some() & right.is_some()`
#[unlikely]
if #[unpredictable] let Some(x) = a
&& #[unpredictable] let Some(y) = b {
    // this is unlikely
}

[Neutron3529]

@quaternic

#[unlikely]
if #[unpredictable] let Some(x) = a
&& #[unpredictable] let Some(y) = b {
    // this is unlikely
}

The combination seems great, but how compiler dealing with such code?

#[likely]
if #[unlikely] let Some(x) = a
&& #[unlikely] let Some(y) = b {
    // ?
}

[alonely0]

Sorry, as @CAD97 pointed out, this comment is completely wrong and is the result of me forgetting that statements with attributes has been a thing for a very long time. Don't waste your time reading this comment, I'm only leaving it posted for information preservation & historical purposes.

@Neutron3529

The combination seems great, but how compiler dealing with such code?

In short, it can't, feel free to read the following rant, or just skip it to get to the alternatives, which are in use today by the way.

// start rant. TL;DR: We can't go with the attributes idea.

This not only would require the experimental attributes on expressions feature, but also attributes on statements. With all due respect and not wanting to offend anyone whatsoever, can we get someone from the compiler and/or the language design teams to tell us (I'm actually curious) on a scale of ten how nuts/stupid/impossible this is? As far as I know, this would require severe changes to the grammar[1] and the parser[2], which I don't think are worth it for just enabling a feature that around 0.01% of the Rust users will ever use; and which its implementation has only been brought up in the first place because the optimizer isn't good enough at its job. The worst thing is that I'm well inside that small cohort, and I'm arguing against my best interests here (perhaps because I just want this to get stabilized ASAP, and we're instead rambling about hardly possible, if at all, grammar & language design changes).

• [1] we would actually be setting ourselves up to allow both #[attr] let foo = <expr>; AND let x = #[attr] <expr>;, and adding an attribute to a let outside of hinting a branch seems nonsense to me. Let doesn't even produce a value in the first place!
• [2] we've already struggled enough (and still struggling) with attributes on expressions, I don't even want to think about the heavy-lifting necessary for bringing that to statements. This applies even if we're just allowing them for if let & let-else statements.

// end_rant

Regarding the actual problem, hinting if let and let-else branches, this is easily solved by doing something like this before the branch (tweak it to your use-case):

likely(foo.is_some());

You can just do that before the actual branches. The optimizer will register the weight changes / PGO for the status of the variable, discard the branch because its results are unused and it has no side effects, and compute the following branches (the if let / let-else) with the new weights / PGO. This is all provided you are not doing stuff with atomic/volatile values, in which case you would have to declare them as separate variables first, call the hint, and then use the local variables in your branch.

If we go for the option of implementing a MIR primitive for llvm.expect, and have these hints use it, calling them like this would actually, in my mind, make a lot of sense. Both semantically and syntactically, this is as close as it gets to injecting llvm.expect on a branch, and to me, it feels so elegant and low-level, yet so simple. Of course, we still want to use them inside an if statement when we can, and having them be outside of it would be reserved for if let & let-else.

[CAD97]

@alonely0

This not only would require the experimental attributes on expressions feature, but also attributes on statements.

Applying outer attributes to let statements is already stable, as are outer attributes on expression statements, expressions in comma separated lists, and block tail expressions, so long as the annotated expressions are not binops or ranges.

Macro statements don't take outer arguments per the reference grammar, but rustc still accepts it. Item statements obviously accept outer attributes.

@alonely0

we've already struggled enough (and still struggling) with attributes on expressions, I don't even want to think about the heavy-lifting necessary for bringing that to statements. This applies even if we're just allowing them for if let & let-else statements.

The main struggle with attributes on expressions is actually specifically when they're ambiguous with a statement attribute. It's fairly simple to say that attributes on expressions bind tighter than binary operators, so #[a] b + #[c] d is (#[a] {b}) + (#[c] {d}), not #[a] {b + #[c] {d}}, but this is less clear when you have a statement expression, e.g.

#[a]
b + d;

Barring that example, the choice of how tightly outer attributes bind is still an arbitrary choice, but it's a choice that's easier to make.

@alonely0

adding an attribute to a let outside of hinting a branch seems nonsense to me. Let doesn't even produce a value in the first place!

Marking an irrefutable let as likely/unlikely obviously doesn't make sense. Marking a refutable let, however, does make sense; you're hinting as to whether the refutable pattern match is successful.

@alonely0

perhaps because I just want this to get stabilized ASAP, and we're instead rambling about hardly possible, if at all, grammar & language design changes

Rust has a track record, for better or for worse, of refusing to stabilize the "simple, works, but potentially suboptimal" choice when a potentially better design is known to exist.

@alonely0

Regarding the actual problem, hinting if let and let-else branches, this is easily solved by doing something like this before the branch (tweak it to your use-case):

likely(foo.is_some());

This was specifically called out as not working above:

@cg909

If likely, unlikely and unpredictable were provided as functions, e.g. directly affecting an if let would be impossible:

let _ = likely(foo.is_some()); // most certainly has no effect for the `if let` below

[because] the LLVM intrinsic llvm.expect, which is used to implement likely, only influences edge weight metadata on dependent branches and is a no-op if no branching directly depends on it

so asserting that

@alonely0

The optimizer will register the weight changes / PGO for the status of the variable, discard the branch because its results are unused and it has no side effects, and compute the following branches (the if let / let-else) with the new weights / PGO.

is false for existing backends. The issue is that you end up with low-level code that looks something like

let foo: Option<&T>;

// likely(foo.is_some());
let _1: usize = transmute_copy(&foo);
let _2: bool = _1 != 0;
likely(_2);

// if let Some(bar) = foo
let _3: usize = transmute_copy(&foo);
let _4: bool = _3 != 0;
if _4 {
    let bar: &T = transmute_copy(&foo);

    // todo!()
}

and if the optimizer is going to "propagate the weight changes for the variable", then it needs to reverse the computation of the test boolean if it wants to derive information about the shared variable which is actually used to derive the later branch.

Your scheme might work for likely(b); if b { /* ... */ }, since the same variable is used both in the hint and in the branch. But using a non-place expression in the hint is basically never going to work.

@alonely0

it feels so elegant and low-level, yet so simple

On the contrary, likely(foo.is_some()); is frighteningly high-level for the optimizer, since you're deriving a single boolean from a larger state and saying "hey this is likely" then throwing that boolean away and deriving a new boolean which could be related, but it might not be, the optimizer needs to derive that somehow, and you've derived the new test in a different manner. This is a nightmare to resolve and turn into something useful for the optimizer. Where on the other hand, taking specific branching operations (e.g. an if or a fallible pattern match in let/match) and hinting the relative likelihood of the branches is much more directly meaningful to the optimizer.

[alonely0]

I stand absolutely corrected, thanks! However, is the attributes alternative completely viable, then?

[bleo]

I don't know whether this has already been brought up or just isn't true for most people, but when I read

if unlikely(x > 0) {
   // ...
} else if likely(x < 0) {
   // ...
}

or

if unpredictable(value) {
   // ...
}

I immediately think that this code will execute if and only if the expression is probabilistically likely or unlikely true. (Even more so in the unpredictable case). The function names likely and unlikely indicate, to me, that the likeliness and not the original value is returned. Thus, I prefer the attribute solution or, if a function was necessary, a name such as which_is_likely, to be used as

if which_is_likely(x > 0) {}
else which_is_unlikely(x < 0) {}

which reads far more naturally as "If, which is likely, x is greater than 0" etc.

[the8472]

llvm has expect.with.probability which seems more general than likely/unlikely/unpredictable. Should we expose that instead?

[8573]

@bleo

Thus, I prefer the attribute solution or, if a function was necessary, a name such as which_is_likely,

I would support this, though I suppose it's too verbose for most users' tastes.

[kornel]

You could use it as:

use std::hint;

if hint::likely(x > 0) {

[alonely0]

If we go with the attributes route (which nobody has confirmed yet if it is viable; though my guess is that it is), we could just add an optional argument for probability, that switches the LLVM IR code to llvm.expect.with.probability instead of llvm.expect. It shouldn't be that difficult, we just have to parse the input at compile-time. I'd be down to implement this patch if someone walks me through it (I've never contributed code to rustc and it's kinda intimidating).

[matthieum]

Hint: assume.

C++23 introduces [[assume(...)]], which comes with very specific semantics:

Otherwise, the statement does nothing. In particular, the expression is not evaluated (but it is still potentially evaluated).

The fact that the expression is not evaluated makes it strictly better than the "equivalent":

if !condition {
     unsafe { std::hint::unreachable_unchecked() };
}

It may be worthwhile using the same semantics for assume in Rust, and thus perhaps use an attribute rather than a macro or function, to better highlight the special semantics. It should be clearer with an attribute that the code is not, in fact, executed.

Note: assume is part of a set of invariants which also contains pre-conditions and post-conditions. While pre-conditions can be expressed internally with assume -- as functions have a single entry -- it is not as easy for post-conditions, and further it can be beneficial to make post-conditions visible externally as the caller can then optimize based on them even without inlining.

Hints: likely and unlikely.

First of all, the likely and unlikely hints do not, in general, have any effect on the branch predictor. They are purely about code-placement: the code of the likely branch will followed the check immediately, while the code of the unlikely branch will require a jmp, and may thus suffer an instruction cache miss.

With that in mind, it may be worthwhile to think about a different name which better conveys that this is strictly about code-placement, and is not, really, about likelihood.

Perhaps #[immediate] would be a better name than #[likely]?

[cg909]

Hint: assume.

@matthieum

It may be worthwhile using the same semantics for assume in Rust, and thus perhaps use an attribute rather than a macro or function, to better highlight the special semantics. It should be clearer with an attribute that the code is not, in fact, executed.

To me the use of an attribute on a null statement in C++23 looks a bit like a language level hack. For Rust a macro would probably be a better way of conveying that it doesn't behave like a normal function call. Especially as Rust currently doesn't have something like null statements:

#[assume(x == true)];

currently produces a compile error:

error: expected statement after outer attribute
warning: unnecessary trailing semicolon

Allowing free-standing attributes as their own "statements" would open a whole new can of worms.

Hints: likely and unlikely.

@matthieum

First of all, the likely and unlikely hints do not, in general, have any effect on the branch predictor. They are purely about code-placement: the code of the likely branch will followed the check immediately, while the code of the unlikely branch will require a jmp, and may thus suffer an instruction cache miss.

Code-placement is an implementation detail. Even on the level of LLVM IR they're still about branch weights. Even if it only affects code placement on most architectures the goal still is to optimize for the more likely branch.

Besides, the x86 instruction set has branch hint opcode prefixes but AFAIK they are only honored by Pentium 4 and thus not really used. Also there are architectures that have branch hint instructions, like Intel Cell SPUs with their hbr instruction.

Also thinking about other optimizations: the likeliness hints may also affect inlining decisions and a compiler backend might generate e.g. prefetch instructions to further optimize for the most likely branch. Likely and unlikely are hints to the compiler, so it can do anything with that information as long as it doesn't change observable behaviour.

@alonely0

If we go with the attributes route (which nobody has confirmed yet if it is viable; though my guess is that it is), we could just add an optional argument for probability, that switches the LLVM IR code to llvm.expect.with.probability instead of llvm.expect. It shouldn't be that difficult, we just have to parse the input at compile-time.

I also think it's viable. The compiler could either directly place branch weights on the if/match arms or emit a core::intrinsics::likely call around the branch condition.

I vaguely remember a discussion about a likeliness attribute with an optional probability argument from a few years ago, but wasn't able to find it in the Internals forum. Maybe I misremembered the context of that discussion.

Either way, when including probabilities there would be two possible routes:

1. Provide a single attribute instead of likely/unlikely, e.g. #[likely(probability=0.0)] or #[likeliness=0.0]

2. Provide likely and unlikely with optional probabilities, e.g. #[likely(probability=0.9)], #[unlikely(probability=0.2)].

   In the latter case it's probably neccessary to restrict the attribute value to > 0.5 for likely and < 0.5 for unlikely. Otherwise confusing combinations like #[likely(probability=0.0)] and #[unlikely(probability=1.0)] would be possible.

Hint: unpredictable

I'd also like to boost the proposal by @scottmcm to include an #[unpredictable] attribute. This could help to guide the optimizer to generate branchless code (when possible) even if that would be slower than a correctly predicted branch.

LLVM IR has an analogous metadata attribute unpredictable that can be attached to branch and switch instructions.