Implement likely/unlikely intrinsic (tracking issue for RFC 1131)

[nikomatsakis]

Tracking issue for rust-lang/rfcs#1131:

• Implement the likely/unlikely intrinsic
• Re-export in std::hint
• Document
• Stabilize

[pythonesque]

FWIW, looking through my own code, I actually think the fact that this can't apply to match variants is going to be fairly hard on idiomatic Rust (for example, it means you can't use it when matching on an Option, which is going to be extremely common since it amounts to if (likely(ptr != NULL)) in C).

[Aatch]

@pythonesque once I get this done, I plan on writing a follow-up RFC for a #[likely] attribute you can put on match arms. Since it's already possible to put attributes on arms (to support conditional compilation of them), it should be fairly easy to implement.

[Craig-Macomber]

It might be worth having an "unpredictable" option in addition to likely and unlikely. There is now something to lower it to in LLVM: http://reviews.llvm.org/D12341

[apasel422]

@Aatch Are you still working on this?

[vi]

Shall #[likely] be also on Result?

enum Result<T, E> {
   #[likely]
   Ok(T),
   Err(E)
}

I expect for most code Ok is likely and Err is unlikely. Of course, annotating if or match should override enum variant's annotation.

[Aatch]

@vi I think hinting should be only be used rarely, so it being on the type doesn't seem like a good idea. Result is a bit more general purpose than just error-handling, sot that kind of hinting would impact code where it's inappropriate. Hinting should only really be done at the site itself.

[vi]

@Aatch, Is it a good idea to have likely in every place where something is likely? Can it also serve for self-documentation: follow "likelies" and see happy path?

[Aatch]

@vi is is not. As a general rule, people are pretty bad at knowing what cases are actually likely or not. Branch hinting is a fairly specific optimisation hint, used incorrectly it can actually make code slower. It should also only really be used when the unlikely case is known to be very unlikely.

Basically, you should only use it if it makes your code faster, otherwise it should be there.

[pczarn]

@vi It might be good idea if the likely thing is cheap, and the unlikely thing is expensive. For example, Vec::push is expensive if it causes a reallocation, and very cheap otherwise.

In my opinion, frequent use of likely is either unnecessary or just manual profile-guided optimization.

[Stebalien]

Instead of arguing about it, why not just test it? Annotate Result, and then see if rustc bootstraps significantly faster. This won't give a definitive answer but will help determine if it's worth considering.

[comex]

Now that MIR is a thing, it would be nice if this were implemented.

[nikomatsakis]

@comex I do agree =)

@Aatch Not sure what your time is like, but if you don't have time to implement this, it seems like a case where we might be able to mentor someone. The idea would be to leave a comment explaining roughly how you think it should work, and then tagging the issue with E-mentor and E-help-wanted. I of course can do this too and will try to remember to do so. =)

[nikomatsakis]

Unassigning @Aatch since, empirically, he doesn't seem to be actively hacking on this right now. =) (Feel free to correct me.)

[seanmonstar]

@nikomatsakis PR up, though I could use some help adding tests.

[Aatch]

Copying @nagisa's comment from #36181:

#llvm told me expect intrinsic is more harmful than it is helpful and that the branch weight metadata should be emitted instead. Might be worth to go back and reconsider the RFC, since the branch weight metadata is more powerful and expressive and would be better expressed as attributes in source too.

why is clang > 3.6 not emiting expect intrinsic for __builtin_expect?
nagisa: it turns out that the expect intrinsic overall harmed the optimizer by inhibiting certain optimizations
so we now directly lower __builtin_expect to branch probabilities in the frontend when generating IR

I think that keeping the intrinsics is a good idea. They should be fairly obvious for people coming from C/C++. Attributes aren't mutually exclusive with the intrinsics, so we're not exactly cutting ourselves off with intrinsics.

Supporting branch weights at the MIR level would probably be the easiest implementation for lowering to the metadata ourselves.

[chriskrycho]

Just adding a note here as I'm processing everything in #38643: it will need docs before stabilization. @nikomatsakis would you mind adding a note to that effect in the root of the issue?

[nikomatsakis]

@chriskrycho done

[joshtriplett]

@Amanieu I'd personally like to have both, since likely and unlikely intrinsics work in more contexts (e.g. sub-expressions).

EDIT: I now agree that an attribute makes sense.

[scottmcm]

@Amanieu I would also like to have that. One thing that got mentioned in the meeting was that we have #[cold] for functions and closures, so allowing that on blocks might be an interesting way to phrase it.

(Albeit one can mostly write #[cold] { ... } as (#[cold]||{ ... })().)

[Amanieu]

Clang's CodeGenFunction::EmitBranchOnBoolExpr has special handling for __builtin_expect (which is what likely/unlikely use under the hood) which is not present in rustc.

Specifically, it performs the following transformations with boolean expressions:

likely(a && b) => likely(a) && likely(b)
unlikely(a && b) => a && unlikely(b)
likely(a || b) => a || likely(b)
unlikely(a || b) => unlikely(a) || unlikely(b)

In rustc this would need to be done during THIR to MIR lowering, which would require the compiler to treat these intrinsics specially.

Additionally, the llvm.expect intrinsic is designed to work when its result is directly passed to a br LLVM IR instruction. It does not work if used outside of this context (example), which is not very obvious.

[joshtriplett]

@Amanieu Those transformations seem potentially useful. I personally wouldn't consider them necessary to make these intrinsics useful, though. Would you consider those transformations to be blockers?

[iago-lito]

I have a naive question here: besides likely and unlikely hints, sometimes I have a guarantee that the branch taken will actually be (uniformly) random. Would such a hint be useful at all for compilation? Would it be equivalent to every branch being unlikely?

[the8472]

sometimes I have a guarantee that the branch taken will actually be (uniformly) random.

LLVM already has unpreditable for that. This came up in #53823

[MSxDOS]

These intrinsics no longer have any effect for my code (starting with #87570 ?).
Easily compared by importing them as use core::intrinsics::{likely as unlikely, unlikely as likely}; or replacing with blank functions, in all cases produced binaries are identical.

[the8472]

@MSxDOS that's probably worth a regression issue.

[Amanieu]

We discussed this during the libs-api meeting and don't think that a function is the correct interface for exposing probabilities on LLVM IR branch instruction (or equivalents in other backends). We would instead prefer an attribute-based solution which would work on both if and match arms.

Passing this back to T-lang.

[joshtriplett]

For this tracking issue, for the intrinsics, we're marking these as "perma-unstable", like most LLVM intrinsics.

We'd love to see a lang MCP for #[likely] and #[unlikely] attributes.

[saethlin]

#120370 should now work, at least sometimes. I don't know if #88767 is fixed, but since reviewing the fix PR I now have the opinion that a #[cold] on arms or the intrinsics::cold_path() strategy is the right way to provide this branch hinting information.