Support detecting const-eval vs non-const-eval in a const fn

[oli-obk]

There are multiple thousand intrinsics for various platforms which users might want to use to speed up their code. It is unrealistic to implement all of these (although a certain subgroup like https://github.com/rust-lang-nursery/stdsimd/blob/05c2f61c384e2097a3a4c648344114fc4ac983be/coresimd/simd_llvm.rs seem to be manageable.

@rkruppe and @gnzlbg mentioned (with discomfort) a way to "runtime" detect whether we're in const eval or runtime (which would get completely optimized during codegen). While this would be trivial to implement, it seems very unfortunate to have to resolve to this.
There's precedent in c++ for such an escape hatch.

I am not very happy that we even need that many intrinsics outside the libstd and don't quite understand why these can't be optimizations that "just happen". Requiring users to "fix" optimizer deficiencies by giving them multiple thousand ways to gain a few cycles seems suboptimal.

It's perfectly fine not to support calling e.g. an interrupt register fiddling intrinsic at compile-time (there's no use for doing that, or it could be a noop in many cases). But when/if performance intrinsics are sprinkled onto code used by many users and there's an algorithm that works both at compile-time and runtime and could be optimized, it seems very unfortunate to scrap compile-time evaluability.

[gnzlbg]

There is a solution proposed for C++20 (I am not sure if it has been merged - EDIT: It was accepted LEWG and sent to LWG and CWG) called is_constant_evaluated (latest paper: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0595r1.html) that attacks this problem.

Having to choose between whether code can be const evaluated or whether it performs good at run-time is a weird spot to be in as a programmer. I don't know whether this problem is worth solving, but the problem is real. The C++ solution, doesn't feel right, but I don't have any alternatives either.

[oli-obk]

@gnzlbg gave us a great summary on irc. Here's the gist:

• while it moved from LEWG to CWG and LWG, people had mixed feelings about it
  • basically, std library writers want it,
  • and compiler writers wanted to expose it as an extension
• everybody agreed that it shouldn't be a widely used feature, and that it is hard to reason about it
• it was also argued when exactly should it return true
  • const FOO: i32 = foo(); it will return true
  • but what about let foo: i32 = foo(); ?
  • should it also return true if foo() is const propagated by optimizatons ?
  • will that depend on compiler-optimizations ?
    • so there was some agreement that it should not, and that it should be clear what it returns for every program
• they changed the name from if constexpr() { ... } to if std::is_constant_evaluated() to discourage its use
• clang/LLVM main devs argued strongly on its favour

[oli-obk]

Note that we can "just" add such a std::is_constant_evaluated function and make it unsafe to make it clear what's going on. The unsafe documentation would then state that the result of this function may not change the behaviour of any code. There could even be an additional -Z flag for fuzzers and testing that turns the flag to true during regular compilation

[gnzlbg]

When miri evaluates Rust program like this:

fn bar(x: i32) -> i32 { x * 2 }
const fn foo(x: i32) -> i32 {
    if unsafe { is_constant_evaluated() } {
        x * 2
    } else {
        // unsafe required because `bar` is 
        // not a `const fn` (hence not `const`-safe):
        unsafe { bar(x) }
    }
}

it could attempt to evaluate both branches, and compare that both produce the same result, which is the only effect that both branches can have. If the bar branch attempts to mutate global memory, read from a static, etc. miri could error.

[oli-obk]

We have changed course. Discussion is in https://github.com/rust-lang/rust/pull/64683/files/223c832b3894fe6ce6d61d4f459f0aa827bec264#discussion_r327153517

The TLDR is that we'd create an intrinsic

pub fn const_eval_select<ARG, F, G, RET>(arg: ARG, called_in_const: F, called_at_rt: G) -> RET;

that calls called_in_const(arg) if we're in a const eval context and called_at_rt(arg) if not. F and G must be function types (not function pointers).

[minerva]

When miri evaluates Rust program like this:

fn bar(x: i32) -> i32 { x * 2 }
const fn foo(x: i32) -> i32 {
    if unsafe { is_constant_evaluated() } {
        x * 2
    } else {
        // unsafe required because `bar` is 
        // not a `const fn` (hence not `const`-safe):
        unsafe { bar(x) }
    }
}

it could attempt to evaluate both branches, and compare that both produce the same result, which is the only effect that both branches can have. If the bar branch attempts to mutate global memory, read from a static, etc. miri could error.

How about a language-level if const { .. }? I think C++20 demonstrates why a library function to handle this job in conjunction with a regular if is a bad solution.

const fn foo(x: i32) -> i32 {
    if const {
        x * 2
    } else {
        unsafe { bar(x) }
    }
}

Similar to how ISO NB comments tried to change C++20's if (std::is_constant_evaluated()) { .. } to
if consteval { .. }.

[oli-obk]

I think we race-conditioned on posting. See my above post for a solution that is much simpler to implement, since it doesn't pollute the const part of a function with the non-const part.

[tarcieri]

What are the next steps that need to happen towards stabilizing a feature like this?

It would be very nice for crypto-bigint, where we have fairly aggressively leveraged const fn for all operations we can support in order to be able to compute constants at compile time, but would also like to eventually be able to use core::arch intrinsics (e.g. MULX) for performance optimizations outside of a Miri context.

[fee1-dead]

I don't think we would want to stabilize const_eval_select, that said, we could constify some intrinsics by implementing a slower version for const eval using const_eval_select, and stabilize those intrinsics instead.

[oli-obk]

We should probably open an issue in the stdarch repository to kick off the discussion on whether most (all?) intrinsics that are "just math" should get this treatment.

[tarcieri]

That'd be great! If there were an example to use as a starting point, I could probably help implement some of the ones we're interested in using.

_mulx_u32 and _mulx_u64 are both fairly straightforward "just math" intrinsics, FWIW.

[oli-obk]

Here's an example of how to wrap _mulx_u64: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=fceb186657495c471f96667a4e7b79e9

[tarcieri]

After going down a very deep rabbit hole it seems ADX and MULX can't currently be emitted as intrinsics due to an LLVM bug: rust-lang/stdarch#666

It seems the best path forward is probably higher-level wrappers we could use instead: rust-lang/rust#85532

...and ideally those could be Miri supported / const friendly.

All that said, there are SIMD operations we'd potentially like to use in a const context as well, so I guess I'll keep my eye on rust-lang/miri#662

[RalfJung]

AFAIK there are plans for some high-level portable SIMD API; probably that would be the most suitable entry point for CTFE const_eval_select branches. But I am not sure how far off into the future that is...

Regarding rust-lang/miri#662; it is not clear if const_eval_select will help Miri -- after all, Miri is evaluating runtime code, not const code. The portable SIMD API is again the nicest solution here, since it only needs a fairly small number of intrinsics that we can just implement in Miri (some of them we already have, in fact).

[oli-obk]

we can "just" rename const_eval_select and create an intrinsic that takes an additional const generic string argument, which can then be used via some flag. So if you pass no flags, you get the pure rust (and const) impl, otherwise you get the impl for your feature flag. Then backends can individually enable features they support and just fall back to the (probably slower) const impl by default. Miri would then not enable any such flags, and the complexity would all be pushed to the intrinsic providers instead of requiring miri logic, cranelift logic and CTFE logic.

[tarcieri]

Regarding const and asm!, I'm curious if there might be some way to integrate const_eval_select into CPU feature detection macros like is_x86_feature_detected!.

In the cases where we (prospectively) want to use asm! or other non-const-safe platform-specific things like intrinsics, they're accompanied with CPU feature detection with a pure Rust fallback anyway, so I'm curious if it would be possible to integrate these features together such that asm! could be allowable in a const fn if it's always guarded by a CPU feature detection macro.

[oli-obk]

Regarding const and asm!, I'm curious if there might be some way to integrate const_eval_select into CPU feature detection macros like is_x86_feature_detected!.

Not exactly. The problem is that you cannot have non-const and const code within the same function, you need to have separate functions, so what I would imagine would work is

x86_feature_select!(the_feature, non_const_fn, const_fn, (first_arg: Foo, second_arg:Bar) ->ReturnType)

which expands to

fn foobar(first_arg: Foo, second_arg: Bar) -> ReturnType {
    if is_x86_feature_detected!(the_feature) {
        non_const_fn(first_arg, second_arg)
    } else {
        const_fn(first_arg, second_arg)
    }
}
const_eval_select((first_arg, second_arg), const_fn, foobar)

This should work right now.

[tarcieri]

I noticed const_eval_select isn't yet callable as a const fn. Is the plan to eventually allow that? (which would violate the rules for a const fn calling a non-const fn, but that would never actually happen in a const fn context)

[RalfJung]

I don't quite know what you mean? The standard library calls const_eval_select in const fn in quite a few places.

[tarcieri]

So it's callable from a const fn even though it's not declared a const fn itself? I see it defined as:

https://github.com/rust-lang/rust/blob/2862500152d89996ab2b682f22ed7e8923396992/library/core/src/intrinsics.rs#L2499

pub fn const_eval_select<ARG: Tuple, F, G, RET>(

[RalfJung]

It's a super special magic intrinsic. And highly unstable. ;)

[RalfJung]

Also, intrinsics are never const fn. That's not even accepted by rustc. You can't declare an extern fn to be const, in most situations that wouldn't make any sense. They care callable from const fn if they have a rustc_const_(un)stable attribute.

[tarcieri]

Any hopes for a stable API for this sort of thing in the future?

As an example use case beyond SIMD: I would like to use asm! to invoke cmov*/csel* for constant-time predication when available, but fall back on e.g. a bitmask-based selection in const fn, which seems easy enough to write with const_eval_select.

In crypto-bigint we ended up adding an entire const fn-friendly subtle-alike system for constant-time selection in order to solve this problem, which we provide in addition to the subtle traits. That approach comes with worries that LLVM's optimizer might rewrite bitmasking with branches in the non-const case, which is what we'd otherwise use subtle's optimization barriers to avoid.

[RalfJung]

Hopes? Yeah for sure.^^ We even had an RFC that was meant to pave the way: rust-lang/rfcs#3352. However, that didn't go anywhere, so a new approach is needed. I don't think currently anyone is pushing for it. Personally I'm considering const_mut_refs to be higher priority so that's the big const-eval feature I am currently pushing towards.

The current interface is also rather awkward, with how it forces you to write two functions to select between. It's really just a hack, and we'd probably want something nicer.