Julia: Implement llvm branch prediction hint support

[kcajf]

It would be useful to be able to tell the compile which code branch is more probable, akin to GCC's __builtin_expect and Rust's likely/unlikely.
LLVM supports this via https://llvm.org/docs/LangRef.html#llvm-expect-intrinsic.

[StefanKarpinski]

Seems like we could just expose a fully general @expected(val, expr) construction instead of the more limited likely / unlikely. Of course, then @likely(expr) could be shorthand for @expected(true, expr) and @unlikely(expr) for @expected(false, expr).

[vtjnash]

Yes, note through that this usually has very little practical effect (x86 processors haven’t supported the flag in a long time) and so it’s mostly just theoretically interesting to some optimizations (such as inlining/outlining/coldcall)—but unclear if any of them actually use the information or even would consistently benefit from it.

[kcajf]

Ah, thanks @vtjnash, I didn't know that. I had assumed that most architectures could benefit from this through simply reordering branch instructions from most to least likely (which, admittedly, can usually be done quite easily in the programming language itself). I'll read up on it.

[chethega]

The super direct implementation would be

    expect(x::Bool) = Core.Intrinsics.llvmcall(("declare i1 @llvm.expect.i1(i1, i1 )",
    "%cond = icmp eq i8 %0, 1
     %res= call i1 @llvm.expect.i1(i1 %cond, i1 1)
     %res2 = zext i1 %res to i8
     ret i8 %res2"), Bool, Tuple{Bool},  x)

    assume(x::Bool) = Core.Intrinsics.llvmcall(("declare void @llvm.assume(i1)",
    "%cond = icmp eq i8 %0, 1
     call void @llvm.assume(i1 %cond)
     ret void"), Nothing, Tuple{Bool},  x)

These do filter through:

julia> xsqrt(x) = (assume(!(x<0)); sqrt(x));
julia> xsqrt(-1.0)
NaN

LLVM has successfully used the assumption: We told the compiler that x is nonnegative, and it dutifully removed all the dead code (actually check whether x is negative and throw an exception). But assumptions are hard to use: For example, assume(x>0) does not cut the cake, because llvm fails to figure out that this implies !(x<0). Also, violated assumption are very UB and contradictory assumption can probably spiral out of control (everything becomes unreachable, which implies an assumption on every branch leading to the now unreachable code).

Expectations may be easier, because users can simply write if expect(cond) or if !expect(cond) (going out on a limb that llvm is smart enough to understand this negation, but I don't know how to test that).

Do we want that?

[yuyichao]

Assume certainly works and I've been using it for a long time. I'm pretty sure we don't have the LLVM pass enabled for expect to work.