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

const if to supress instantiation/codegen of unreachable branches #3582

Open
the8472 opened this issue Mar 7, 2024 · 29 comments
Open

const if to supress instantiation/codegen of unreachable branches #3582

the8472 opened this issue Mar 7, 2024 · 29 comments
Labels
T-lang Relevant to the language team, which will review and decide on the RFC.

Comments

@the8472
Copy link
Member

the8472 commented Mar 7, 2024

Currently there's a suboptimal interaction between const asserts and const generics.

A more general function that is valid for all N cannot call a function that asserts at compile time that N fulfills some conditions even if the call is on a branch that's dead for the invalid N.

I.e. this does not compile:

#![feature(inline_const)]

// method in std
fn method_with_precondition<const N: usize>() {
    const { assert!(N > 0) };
}

// user method, no way to opt out of asserts for N = 0
fn generic_caller_method<const N: usize>() -> fn() {
    if N > 0 {
        panic_on_zero::<N>
    } else {
        || {} // fallback
    }
}

fn main() {
    let _fun = foo::<0>();
}
error[E0080]: evaluation of `panic_on_zero::<0>::{constant#0}` failed
 --> src/main.rs:5:13
  |
5 |     const { assert!(N > 0) };
  |             ^^^^^^^^^^^^^^ the evaluated program panicked at 'assertion failed: N > 0', src/main.rs:5:13
  |
  = note: this error originates in the macro `assert` (in Nightly builds, run with -Z macro-backtrace for more info)

This blocks / requires unpleasant choices in several T-libs features that want to check for N != 0 or similar constraints:

If const-eval in the dead branches is expensive it might also help compile perf.

There are efforts (rust-lang/rust#99682) to move monomorphization-time errors to check time and also apply those checks to dead code (rust-lang/rust#112879), which will make it even more difficult to discharge compile-time obligations imposed by callees.

Currently the language does not seem to have any way to select different code paths in generic contexts without also instantiating those paths. Even generic_const_exprs does not offer this unless it gets extended rust-lang/project-const-generics#26

Therefore it would be useful if we could write the case above as

fn foo<const N: usize>() -> fn() {
    const if N > 0 { 
        panic_on_zero::<N>
    } else {
        || {} // fallback
    }
}

so that panic_on_zero::<0> will never be instantiated.

@Jules-Bertholet
Copy link
Contributor

Jules-Bertholet commented Mar 7, 2024

I would note pattern types as an alternative; you could constrain an input const parameter with a pattern (eg const N: usize in 1..), and combine this with trait machinery to select an impl based on the value of the const:

#![feature(inline_const)]

fn panic_on_zero<const N: usize>() {
    const { assert!(N > 0) };
}

trait FooImpl<const N: usize> {
    const FN: fn();
}

impl<const N: usize in 1..> FooImpl<N> for () {
    const FN: fn() = panic_on_zero::<N>;
}

impl FooImpl<0> for () {
    const FN: fn() = || {};
}

fn foo<const N: usize>() -> fn() {
    <() as FooImpl<N>>::FN
}

fn main() {
    let _fun = foo::<0>();
}

@Lokathor
Copy link
Contributor

Lokathor commented Mar 7, 2024

That is significantly harder to understand/review.

@the8472
Copy link
Member Author

the8472 commented Mar 7, 2024

That looks like the same kind of unification as the const expr issue that I linked to.

@oli-obk
Copy link
Contributor

oli-obk commented Mar 7, 2024

I'm a big proponent of pattern types, but I have to agree this is not a good use case for it.

On the topic at hand, do you want a generic_const_exprs like scheme where this shows up in where bounds and needs to have where bounds all the way up to where it is monomorphic? Or do you want this to be a post monomorphization error explicitly? Or well, in the case of the example, a way to avoid post monomorphization errors?

@the8472
Copy link
Member Author

the8472 commented Mar 7, 2024

Oh, having the issue written like this (returning a function pointer) I now realize that anonymous consts + function pointers might help, if the optimizer plays along.

I.e.

fn foo<const N: usize>() -> fn() {
    const {
       if N > 0 { 
          panic_on_zero::<N>
       } else {
          || {} // fallback
       }
    } 
}

But this is not as ergonomic as a real const-if because it means callers needs to hide the dead branches inside functions that get selected by a const block.

At least the playground doesn't complain.

Edit: #3582 (comment) says that this will stop working in the future.

@Jules-Bertholet
Copy link
Contributor

That is significantly harder to understand/review.

I fully agree, but if pattern types are added to the language for other reasons anyway, then perhaps the ergonomics improvement alone wouldn't justify a separate dedicated const if. (I'm not arguing for this claim, just raising the possibility.)

I would also note, that with pattern types as const generic parameters, much of what is now implemented as post-mono assertions could become pre-mono checks, eg:

// Now checked pre-mono
fn require_nonzero<const N: usize in 1..>() {}  

trait FooImpl<const N: usize> {
    const FN: fn();
}

impl<const N: usize in 1..> FooImpl<N> for () {
    const FN: fn() = require_nonzero::<N>;
}

impl FooImpl<0> for () {
    const FN: fn() = || {};
}

fn foo<const N: usize>() -> fn() {
    <() as FooImpl<N>>::FN
}

fn main() {
    let _fun = foo::<0>();
}

A hypothetical const match could then improve the ergonomics:

// Now checked pre-mono
fn require_nonzero<const N: usize in 1..>() {} 

fn foo<const N: usize>() -> fn() {
    const match N {
        N_1_PLUS @ 1.. => require_nonzero::<N_1_PLUS>,
        0 => || {},
    }
}

fn main() {
    let _fun = foo::<0>();
}

@Lokathor
Copy link
Contributor

Lokathor commented Mar 7, 2024

Well, once there's const match then there's not a strong argument against const if, since it would seem that const if is a strict subset of const match.

@the8472
Copy link
Member Author

the8472 commented Mar 7, 2024

Imo that's just restating the problem. In this context pattern types are ~isomorphic to generic_const_exprs with
Conditional<{(1..).contains(N)}>. And here too impls may very well only exist for some pattern of N and not all N, meaning more-generic caller faces the same issue.
And const-match is the ~same solution to the problem.

@Jules-Bertholet
Copy link
Contributor

Jules-Bertholet commented Mar 7, 2024

Pattern types are ~isomorphic to generic_const_exprs with Conditional<{(1..).contains(N)}>.

The advantage of the pattern types approach specifically is that the compiler can do exhaustiveness, disjointness etc checking, so rust-lang/project-const-generics#26 is potentially tractable even for impls involving them. With arbitrary generic_const_exprs, you need a full SMT solver or post-mono errors

@oli-obk
Copy link
Contributor

oli-obk commented Mar 7, 2024

I think even if we come up with a perfect where bound based system, having an escape hatch that you explicitly need to opt into is good.

It may be easier on the compiler implementation side to require a const if expression to be of function pointer type and its branches to only be path expressions. So basically sugar for

#[rustc_arg_required_const(0)]
#[rustc_intrinsic]
fn const_if<A, R>(cond: bool, on_true: fn(A) -> R, on_false: fn(A) -> R) -> fn(A) -> R;

where, due to the magical nature of rustc_arg_required_const being an explicit hack (that we already have for legacy SIMD reasons) where the argument must be const, we can do expressions without triggering generic_const_exprs checks.

@the8472
Copy link
Member Author

the8472 commented Mar 7, 2024

It may be easier on the compiler implementation side to require a const if expression to be of function pointer type and its branches to only be path expressions. So basically sugar for

#[rustc_arg_required_const(0)]
#[rustc_intrinsic]
fn const_if<A, R>(cond: bool, on_true: fn(A) -> R, on_false: fn(A) -> R) -> fn(A) -> R;

Would that mean less work for the compiler compared to #3582 (comment)

@oli-obk
Copy link
Contributor

oli-obk commented Mar 7, 2024

Would that mean less work for the compiler compared to #3582 (comment)

that only works because rust-lang/rust#112879 hasn't landed in forever because it's such a massive perf regression

@the8472
Copy link
Member Author

the8472 commented Mar 7, 2024

I'll cite that as another reason to have const-if then.

@tgross35
Copy link
Contributor

tgross35 commented Mar 8, 2024

This seems like a component of something more generally usable, along the lines of Zig's comptime type operations. That is, if we support branching and pruning on const generics, it would be cohesive to allow behavior based on generic types (if T == u32 { ... }) - which we may or may not want.

Pattern types do indeed make selecting behavior more complicated, but something like a pattern type in the where bounds does seem more consistent with generic types if the intent is simply that compiling fails in certain conditions.

fn foo<const N: usize>() -> fn() 
where N == 0
{
    || {} // fallback
}

@scottmcm
Copy link
Member

I think we should not guarantee that if T::FOO -- and particularly not that if expensive_const_fn(10, 20) will do this -- but would absolutely be in favour of a const if/const match or similar for people to opt-in to the guarantee if they really need the guarantee.

(Rather like how we're trying to guarantee less about &expression_that_happens_to_be_const and asking people to put const { … } to request it explicitly.)

@the8472
Copy link
Member Author

the8472 commented Apr 10, 2024

Yeah I already wasn't expecting if SOME_CONST to get that effect at runtime, that's why the initial comment also suggests const if. And about the effect of if false at const-time there is rust-lang/rust#122301

@RalfJung
Copy link
Member

RalfJung commented May 8, 2024

This is basically the RFC issue equivalent of rust-lang/rust#122301, right? They're asking the same question, it seems to me -- providing a way to control which constants (and callee functions) in a function body are monomorphized.

I agree this should have explicit syntax, something like if const. Note that we are stabilizing const { ... } Soon (TM), so this will change behavior of code like

if const { ... } {
  const { panic!() }
}

Currently we basically guarantee that the panic! will be evaluated, but in the future we'd want to guarantee that it does not get evaluated.

Sounds like we should land a change to the docs about guaranteed evaluation that says that inside a if const, we don't make guarantees currently?

EDIT: the proposal above actually was const if, not if const. const if doesn't overlap with const expressions so if that's the way we intend to go, we need to do nothing.


I think I can see how we can implement this, but it's not trivial and may be expensive, too. Basically, currently we have required_consts and mentioned_items, for consts and other items that unconditionally must be monomorphized if this function gets monomorphized. For this feature, we'd have to generalize them to something like

struct MonoCondition {
  must_be_true: List<Const>,
  must_be_false: List<Const>,
}

required_consts: List<(MonoCondition, Const)>,
// similar for mentioned_items

and then instead of evaluating all required_consts, we only evaluate those were all "must be true" consts are true and all "must be false" consts are false.

When computing required_consts, we keep track of the syntactic nesting of which if const are around us. If we are in the then branch of some if const, we add the const to must_be_true; if we are in the else branch, we add it to must_be_false. With mentioned_items this will may be non-trivial as we're collecting those pretty late, so the CFG already was simplified and transformed a bit... I am not sure how to compute MonoCondition in a general CFG. MIR has some "scope" information though so maybe that can be used.

During inlining, we have to carefully take into account the if const around the inlining site, and add the required_consts of the inlined function with the new conditions as dictated by the syntactic place they get inlined in.

And of course the mono collector can't just traverse all basic blocks, it has to ensure to only walk one side of an if const branch.

@the8472
Copy link
Member Author

the8472 commented May 8, 2024

This is basically the RFC issue equivalent of rust-lang/rust#122301, right? They're asking the same question, it seems to me -- providing a way to control which constants (and callee functions) in a function body are monomorphized.

Yeah. I filed this RFC issue because I thought it's not possible at all in current rust. Shortly after I discovered that the function pointer approach does work but was then informed that it perhaps is not guaranteed behavior, so I filed the rust issue to get clarification on whether it can be relied on.
If the answer to rust-lang/rust#122301 is NO then we need an explict mechanism a bit more urgently. If YES then at least in principle const asserts could be worked around with with a const_if! macro building on the function pointer trick.

rust issue: can we rely on the hack/trick?
rfc issue: can we have nice syntax for it?

EDIT: the proposal above actually was const if, not if const. const if doesn't overlap with const expressions so if that's the way we intend to go, we need to do nothing.

correct

I think I can see how we can implement this, but it's not trivial and may be expensive, too.

If it's prohibitive then the alternatives mentioned upthread such as unifying multiple function impls with non-overlapping where bounds or pattern types or something like const_eval_select could work too. But they're less ergonomic than const if since they would require a bunch of helper functions, can't reuse locals and so on.

@RalfJung
Copy link
Member

RalfJung commented May 8, 2024

If it's prohibitive then the alternatives mentioned upthread such as unifying multiple function impls with non-overlapping where bounds or pattern types or something like const_eval_select could work too. But they're less ergonomic than const if since they would require a bunch of helper functions, can't reuse locals and so on.

Agreed. It seems worth at least exploring the const if approach, then we can see what benchmarks say. I won't have the time to do any implementation work on that though. But I can help drafting the RFC.

@RalfJung
Copy link
Member

RalfJung commented May 8, 2024

Additionally the ability to suppress codegen of branches of would help compile times by emitting less IR and not instantiating dead callees

That is entirely independent of whether we evaluate the consts, so if we emit IR for the dead arm of an if const { ... } feel free to open an issue -- but this part should be removed from this RFC issue. The new language feature should be only about controlling which consts we evaluate.

You mention a bunch of tracking issues, but I am not entirely sure what to look for in them. I guess it's related to "Should this be a type error for N != 0? (See also this same question in [T]::as_chunks.)" in rust-lang/rust#100450? But I dont' know where I can find that "same question" (I guess I could go hunt for it, but there's no link), and there's background discussion here as well, so -- I understand the feature request in the abstract, but the issue description currently does not help to understand the concrete pain t-libs (or t-libs-api?) is running into.

@the8472
Copy link
Member Author

the8472 commented May 8, 2024

Additionally the ability to suppress codegen of branches of would help compile times by emitting less IR and not instantiating dead callees

That is entirely independent of whether we evaluate the consts, so if we emit IR for the dead arm of an if const { ... } feel free to open an issue -- but this part should be removed from this RFC issue. The new language feature should be only about controlling which consts we evaluate.

We used to emit IR at least. I can put it more generally to say that it's also a performance benefit because the compiler does not have to visit the items mentioned in the dead branch. This can be a significant benefit when choosing between two different implementations where each has a deep, generic call-tree that would have to be visited.

I have already used rust-lang/rust#122301 to optimized compile performance and would use const if instead if it were available.

You mention a bunch of tracking issues, but I am not entirely sure what to look for in them.

They all follow a similar pattern that I already outlined in the code example above the linked tracking issues.

  1. we'd like to stabilize some fn array_method_with_precondition<const N: usize> method today that should become a fn array_method_with_precondition<const N: usize>() where N > 0 in the future.
  2. currently those methods contain runtime asserts, but we would prefer it to be a compile-time assert that could be upgraded to a where bound later
  3. if we did add a compile assert then generic callers would fail to compile even if the codepath calling array_method_with_precondition is statically dead for N=0 because the compiler is too eager checking the constants of callees and there is no way for the caller to opt out of this behavior

@RalfJung
Copy link
Member

RalfJung commented May 8, 2024

We used to emit IR at least.

Used to, yeah. @saethlin did some work on that recently though in the context of the library UB checks, that should mean we no longer emit this IR.

I can put it more generally to say that it's also a performance benefit because the compiler does not have to visit the items mentioned in the dead branch. This can be a significant benefit when choosing between two different implementations where each has a deep, generic call-tree that would have to be visited.

Right, if the bottleneck is not codegen but actually just recursively traversing these functions then we still do that under if const -- we used to not do that, but rust-lang/rust#122568 made us do that. That wasn't a big perf regression, though.

I have already used rust-lang/rust#122301 to optimized compile performance and would use const if instead if it were available.

Do you have links to those PRs?

They all follow a similar pattern that I already outlined in the code example above the linked tracking issues.

Okay, makes sense, thanks.

As I mentioned in #122301, I think if we implement const if we can get the guarantee you need for the pattern in rust-lang/rust#122301 basically for free. Or, conversely, giving that guarantee (or at least doing all the implementation work for that) is a prerequisite for const if. Also, even const if cannot protect monomorphic functions from being "monomorphized" (in the sense of having their consts evaluated). So there will always be the caveat that any monomorphic function (and anything it calls) may be fully codegen'd and their consts evaluated for no apparent reason.

@the8472
Copy link
Member Author

the8472 commented May 8, 2024

I have already used rust-lang/rust#122301 to optimized compile performance and would use const if instead if it were available.

Do you have links to those PRs?

rust-lang/rust#122785 to prove that it's useful. I have not yet added more because I wasn't sure how shaky that foundation is.

Also, even const if cannot protect monomorphic functions from being "monomorphized" (in the sense of having their consts evaluated).

Would that also be true for crate-private methods?
The cases I have in mind involve generic callees.
I could imagine a case where someone wants to use it as a sort of late cfg. E.g. to select code-paths based on size_of or other compiletime calculations and not having to deal with asserts from the unused impls could be useful. But if that does arise I guess we could tell them to add a phantom generic param.

@RalfJung
Copy link
Member

RalfJung commented May 8, 2024

rust-lang/rust#122785 to prove that it's useful. I have not yet added more because I wasn't sure how shaky that foundation is.

Lol that landed a day after rust-lang/rust#122568. ^^

@saethlin's rust-lang/rust#123272 landed later. I can't tell how much of an effect rust-lang/rust#121421 had without that later fix. It may be worth trying to revert rust-lang/rust#122785 to see if it still makes a difference -- it should not make a difference in terms of how much we codegen, and I would be somewhat surprised if just the traversal of "mentioned" items makes such a difference.

Would that also be true for crate-private methods?

Yes. The initial reachability analysis is necessarily conservative and there's no good way to exclude any monomorphic function from being considered. We can do our best to fix issues like rust-lang/rust#119214 but it's not possible to fix them all (without completely re-thinking how we handle monomorphic items that "may or may not" be needed by downstream crates).

As I said, I think we should actually do item collection starting with all monomorphic items as roots, and const blocks in monomorphic items should be considered like const items (which we also always evaluate). The only way I see to fix the problem of "we sometimes do evaluate them and sometimes don't" (rust-lang/rust#122814) is to always evaluate them.

But if that does arise I guess we could tell them to add a phantom generic param.

... until polymorphization optimizes away the pram and codegen's the function anyway. ;)

@the8472
Copy link
Member Author

the8472 commented May 9, 2024

It may be worth trying to revert rust-lang/rust#122785 to see if it still makes a difference

rust-lang/rust#124907 the difference is tiny now

@RalfJung
Copy link
Member

RalfJung commented May 9, 2024

Thanks for checking!

@CAD97
Copy link

CAD97 commented May 26, 2024

I think we'd prefer to avoid a situation where const if condition { … } and if (const { condition }) { … } are both valid but have subtly different guarantees, especially if common compilation modes skip monomorphization of dead arms of the latter as an optimization. Avoiding this is one of two reasons I typically spell this as static if instead.

The second is that there's a desire for a construct which guards not just post-mono asserts but also pre-mono bounds. In an ideal future, I'd like to be able to have a function declare a pre-mono bound of e.g. where const { N > 0 } and still be able to call it from a function without that bound by handling the fallback case. Translating the pattern refinement types example:

fn require_nonzero<const N: usize>()
where
    const { N > 0 },
{
}

fn foo<const N: usize>() {
    static if N > 0 {
        // this scope checked with the added bound of
        // where const { N > 0 }
        // (purely syntactic resolution, no SMT solving)
        require_nonzero::<N>();
    } else {
        // ideally only instantiated when bound is false
        // allowing even compile_error! as a fallback
        // but also ideally still otherwise typechecked
        fallback();
    }
}

Further overloading the meaning of static isn't great, but neither is overloading the meaning of const to include controlling code instantiation.

const match as used above functions by rebinding a new, more tightly bound const name. static if would function by a kind of refinement typing, introducing additional generic bounds to the controlled scope.

This is wishful thinking, to be sure, but despite the details being hairy, the base concept is straightforward (and basically just a port of the C++ constexpr if semantics to Rust generics).

@the8472
Copy link
Member Author

the8472 commented May 30, 2024

The second is that there's a desire for a construct which guards not just post-mono asserts but also pre-mono bounds. In an ideal future, I'd like to be able to have a function declare a pre-mono bound of e.g. where const { N > 0 } and still be able to call it from a function without that bound by handling the fallback case.

Yes, this is critical for the libs usecase. Without it we can't promote a const assert to a bound later on.

@bstrie
Copy link
Contributor

bstrie commented Jul 18, 2024

Further overloading the meaning of static isn't great, but neither is overloading the meaning of const to include controlling code instantiation.

I don't think we need to burden either const or static with this unfortunate overload. For that matter, we don't need to burden if with the complexity of handling both branching and code instantiation.

We already have where for this use case, so I'd suggest it makes more sense just to allow where blocks in these positions for selective code instantiation:

fn foo<const N: usize>() {
    where N > 0 {
        require_nonzero::<N>();
    } else {
        fallback();
    }
}

This seems like a natural and straightforward extension that doesn't conflict with the existing semantics of where.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
T-lang Relevant to the language team, which will review and decide on the RFC.
Projects
None yet
Development

No branches or pull requests

10 participants