Skip to content

Improve assumptions about the value of isqrt#154115

Closed
Apersoma wants to merge 34 commits intorust-lang:mainfrom
Apersoma:extra-sqrt-assumptions
Closed

Improve assumptions about the value of isqrt#154115
Apersoma wants to merge 34 commits intorust-lang:mainfrom
Apersoma:extra-sqrt-assumptions

Conversation

@Apersoma
Copy link
Copy Markdown
Contributor

Adds assumptions about isqrt being non-zero and less than its input an collects them into a the int_sqrt file to reduce duplication between uint_macro and int_macro.

All assumptions were checked to make sure they were effective with the following code in godbolt:

#[inline]
fn sqrt(x: u64) -> u64 {
    let s = x.isqrt();

    if x > 0 {
        unsafe {core::hint::assert_unchecked(s > 0)}
    }
    unsafe {
        core::hint::assert_unchecked(s <= x);
        core::hint::assert_unchecked(s*s <= x);
    }
    s
}

#[unsafe(no_mangle)]
fn test(n: u64) { 
    for x in 1..n {
        let s = sqrt(x);
        println!("{}", n - s);
        println!("{}", n - s*s);
        println!("{}", n/s);
    }
}

@rustbot rustbot added S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. T-libs Relevant to the library team, which will review and decide on the PR/issue. labels Mar 19, 2026
@rustbot
Copy link
Copy Markdown
Collaborator

rustbot commented Mar 19, 2026

r? @joboet

rustbot has assigned @joboet.
They will have a look at your PR within the next two weeks and either review your PR or reassign to another reviewer.

Use r? to explicitly pick a reviewer

Why was this reviewer chosen?

The reviewer was selected based on:

  • Owners of files modified in this PR: @scottmcm, libs
  • @scottmcm, libs expanded to 8 candidates
  • Random selection from Mark-Simulacrum, joboet, scottmcm

mati865 and others added 25 commits March 19, 2026 21:28
Because rustc doesn't handle split debuginfo for these targets,
enabling that option causes them to be missing some of the debuginfo.
Ubuntu 26.04 has `llvm-22` packages that we can test with.
The `Dockerfile` is otherwise the same as the `llvm-21` runners.
When encountering an inference error where a return type must be known, like when calling `Iterator::sum::<T>()` without specifying `T`, look for all `T` that would satisfy `Sum<S>`. If only one, suggest it.

```
error[E0283]: type annotations needed
  --> $DIR/cannot-infer-iterator-sum-return-type.rs:4:9
   |
LL |     let sum = v
   |         ^^^
...
LL |         .sum(); // `sum::<T>` needs `T` to be specified
   |          --- type must be known at this point
   |
   = note: cannot satisfy `_: Sum<i32>`
help: the trait `Sum` is implemented for `i32`
  --> $SRC_DIR/core/src/iter/traits/accum.rs:LL:COL
  ::: $SRC_DIR/core/src/iter/traits/accum.rs:LL:COL
   |
   = note: in this macro invocation
note: required by a bound in `std::iter::Iterator::sum`
  --> $SRC_DIR/core/src/iter/traits/iterator.rs:LL:COL
   = note: this error originates in the macro `integer_sum_product` (in Nightly builds, run with -Z macro-backtrace for more info)
help: consider giving `sum` an explicit type, where the type for type parameter `S` is specified
   |
LL |     let sum: i32 = v
   |            +++++
```
The compiler is unaware of the restricted range of the input, so it is
unable to optimize out the final division and modulus. By doing this
manually, we get a nontrivial performance gain.
This is nitpicky, but the lack of a sensible order has been bugging me.

- Within `mod $name`, put all the typedefs together.
- After that:
  - First, types definitions and their impls.
  - Then the `TyCtxt*` impls, in a sensible order.
    - Likewise, put `TyCtxt::at` before the similar methods.
- Also reflow some overly long lines.
- Use `$crate` more consistently.
- Add a couple of useful comments.
- Remove some unnecessary local variables.
As `maybe_into_query_key`. Partly to use `key` instead of `param`, and
also to make the link to the trait more obvious.
This is more consistent with what the trait is called elsewhere in tree
(specifically compiler-builtins and test-float-parse).
`RawFloat` is currently used specifically for the implementation of the
lemire algorithm, but it is useful for more than that. Split it into
three different traits:

* `Float`: Anything that is reasonably applicable to all floating point
  types.
* `FloatExt`: Items that should be part of `Float` but don't work for
  all float types. This will eventually be merged back into `Float`.
* `Lemire`: Items that are specific to the Lemire algorithm.
`Float` and `FloatExt` are already used by both parsing and printing, so
move them out of `dec2flt` to a new module in `num::imp`. `Int` `Cast`
have the potential to be used more places in the future, so move them
there as well. `Lemire` is the only remaining trait; since it is small,
move it into the `dec2flt` root.

The `fmt::LowerExp` bound is removed from `Float` here since the trait
is moving into a module without `#[cfg(not(no_fp_fmt_parse))]` and it
isn't implemented with that config (it's not easily possible to add
`cfg` attributes to a single supertrait, unfortunately). This isn't a
problem since it isn't actually being used.
`-Zunpretty=expanded,hygiene` was not printing syntax context annotations
for identifiers and lifetimes inside `macro_rules!` bodies. These tokens
are printed via `print_tt()` → `token_to_string_ext()`, which converts
tokens to strings without calling `ann_post()`. This meant that
macro-generated `macro_rules!` definitions with hygienic metavar
parameters (e.g. multiple `$marg` distinguished only by hygiene) were
printed with no way to tell them apart.

This was fixed by adding a match on `token.kind` in `print_tt()` to call
`ann_post()` for `Ident`, `NtIdent`, `Lifetime`, and `NtLifetime`
tokens, matching how `print_ident()` and `print_lifetime()` already
handle AST-level identifiers and lifetimes.

Signed-off-by: Andrew V. Teylu <[email protected]>
Add `unpretty-debug-shadow` test covering macro body tokens that
reference a shadowed variable, and simplify the `unpretty-debug-metavars`
test macro.

Signed-off-by: Andrew V. Teylu <[email protected]>
Match the other derive macros in the module (Ord, PartialEq, PartialOrd) by
linking to the section in the trait documentation about how the derive macro
works.
When calling an fn that returns a return type as a returned expression, point at the return type to explain that it affects the expected type.

```
error[E0308]: mismatched types
    --> f56.rs:5:15
     |
   3 | fn main() {
     |          - the call expression's return type is influenced by this return type
   4 |     let a = 0;
   5 |     ptr::read(&a)
     |     --------- ^^ expected `*const ()`, found `&{integer}`
     |     |
     |     arguments to this function are incorrect
     |
     = note: expected raw pointer `*const ()`
                  found reference `&{integer}`
note: function defined here
    --> library/core/src/ptr/mod.rs:1681:21
     |
1681 | pub const unsafe fn read<T>(src: *const T) -> T {
     |                     ^^^^
```
@rustbot
Copy link
Copy Markdown
Collaborator

rustbot commented Mar 19, 2026

HIR ty lowering was modified

cc @fmease

Some changes occurred in match checking

cc @Nadrieril

Some changes occurred in need_type_info.rs

cc @lcnr

Some changes occurred in rustc_ty_utils::consts.rs

cc @BoxyUwU

Some changes occurred in float parsing

cc @tgross35

Some changes occurred in integer formatting

cc @tgross35

Some changes occurred in src/doc/rustc/src/platform-support

cc @Noratrieb

@rustbot rustbot added A-CI Area: Our Github Actions CI A-testsuite Area: The testsuite used to check the correctness of rustc T-bootstrap Relevant to the bootstrap subteam: Rust's build system (x.py and src/bootstrap) T-infra Relevant to the infrastructure team, which will review and decide on the PR/issue. labels Mar 19, 2026
@Apersoma
Copy link
Copy Markdown
Contributor Author

Apersoma commented Mar 19, 2026

i don't think i rebased this properly lol

@Apersoma Apersoma closed this Mar 19, 2026
@rustbot rustbot removed the S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. label Mar 19, 2026
@tgross35
Copy link
Copy Markdown
Contributor

tgross35 commented Mar 19, 2026

Can't the signed integers just do x.cast_unsigned().isqrt()?

@Apersoma
Copy link
Copy Markdown
Contributor Author

Apersoma commented Mar 20, 2026

Can't the signed integers just do x.cast_unsigned().isqrt()?

yes, will change it to that when I reopen this

@Apersoma
Copy link
Copy Markdown
Contributor Author

realized the above is wrong because it will use the upper bound for the unsigned integer instead of the signed integer if I do that.

/// # Safety:
///
/// `$n` must be nonnegative
macro_rules! isqrt_of_nonnegative {
Copy link
Copy Markdown
Contributor

@tgross35 tgross35 Apr 14, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

View changes since the review

Can't this all live in the uint implementations, then signed integers cast to unsigned (after the negative check) and call that? To avoid the extra macro here.

MAX_RESULT is different but that can just be an additional (narrower) assertion for signed integers. And you can do the >=0 assertion there since it's not meaningful for unsigned.

#[allow(unused_comparisons, reason = "Unknown if `$n` is signed or unsigned.")]
crate::hint::assert_unchecked(result >= 0);
crate::hint::assert_unchecked(result <= MAX_RESULT);
if $n > 0 {
Copy link
Copy Markdown
Contributor

@tgross35 tgross35 Apr 14, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

View changes since the review

This is part of the macro's precondition, no?

Comment on lines +363 to +364
crate::hint::assert_unchecked(result * result <= $n);
crate::hint::assert_unchecked(result <= $n);
Copy link
Copy Markdown
Contributor

@tgross35 tgross35 Apr 14, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

View changes since the review

Aren't these redundant? If not, could you show an asm case indicating that?

@tgross35
Copy link
Copy Markdown
Contributor

Ah! Sorry, I submitted that review on the wrong PR. Will copy the relevant bits over to the new one.

JonathanBrouwer added a commit to JonathanBrouwer/rust that referenced this pull request Apr 23, 2026
…tgross35

Improved assumptions relating to isqrt

Improved various assumptions relating to values yielded by `isqrt`.
Does not solve but does improve rust-lang#132763.

Re-openeing of rust-lang#154115

Added assumptions are:
* if `x` is nonzero then `x.isqrt()`  is nonzero
* `x.isqrt() <= x`
* `x.isqrt() * x.isqrt() <= x`
rust-timer added a commit that referenced this pull request Apr 23, 2026
Rollup merge of #155265 - Apersoma:isqrt-smarter, r=jhpratt,tgross35

Improved assumptions relating to isqrt

Improved various assumptions relating to values yielded by `isqrt`.
Does not solve but does improve #132763.

Re-openeing of #154115

Added assumptions are:
* if `x` is nonzero then `x.isqrt()`  is nonzero
* `x.isqrt() <= x`
* `x.isqrt() * x.isqrt() <= x`
pull Bot pushed a commit to LeeeeeeM/miri that referenced this pull request Apr 24, 2026
Improved assumptions relating to isqrt

Improved various assumptions relating to values yielded by `isqrt`.
Does not solve but does improve rust-lang/rust#132763.

Re-openeing of rust-lang/rust#154115

Added assumptions are:
* if `x` is nonzero then `x.isqrt()`  is nonzero
* `x.isqrt() <= x`
* `x.isqrt() * x.isqrt() <= x`
github-actions Bot pushed a commit to rust-lang/rustc-dev-guide that referenced this pull request Apr 24, 2026
Improved assumptions relating to isqrt

Improved various assumptions relating to values yielded by `isqrt`.
Does not solve but does improve rust-lang/rust#132763.

Re-openeing of rust-lang/rust#154115

Added assumptions are:
* if `x` is nonzero then `x.isqrt()`  is nonzero
* `x.isqrt() <= x`
* `x.isqrt() * x.isqrt() <= x`
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

A-CI Area: Our Github Actions CI A-testsuite Area: The testsuite used to check the correctness of rustc T-bootstrap Relevant to the bootstrap subteam: Rust's build system (x.py and src/bootstrap) T-infra Relevant to the infrastructure team, which will review and decide on the PR/issue. T-libs Relevant to the library team, which will review and decide on the PR/issue.

Projects

None yet

Development

Successfully merging this pull request may close these issues.