Description
While trying some inline assembly in my solutions to an online math puzzle site (without spoiling which one), I ran into a case that gets the right answer in debug mode or opt-level = 1, but fails at opt-level = 2 or higher. I've extracted as much as I could to make this stand alone.
[package]
name = "mul_bug"
version = "0.1.0"
edition = "2021"
[dependencies]
primal-sieve = "0.3.2"
[profile.release]
opt-level = 2 # 1 is OKuse primal_sieve::Primes;
use std::ops::{Add, MulAssign};
fn main() {
assert_eq!(solve(4), 650);
assert_eq!(solve(100), 202_476_099);
assert_eq!(solve(100_000), 403_221_585);
}
fn solve(n: u32) -> u32 {
let mut product = Mod(1);
// Changing to a regular `for` loop suppresses the bug.
// for p in Primes::all().take_while(|&p| p < n as usize) {
Primes::all().take_while(|&p| p < n as usize).for_each(|p| {
let p = p as u32;
let mut k = n / p;
let mut pp = p;
while let Some(x) = pp.checked_mul(p) {
pp = x;
k += n / pp;
}
product *= Mod(p).pow(2 * k) + Mod(1);
});
// }
product.0
}
#[derive(Clone, Copy)]
struct Mod(u32);
impl Mod {
const MOD: u32 = 10u32.pow(9) + 9;
}
impl Add for Mod {
type Output = Mod;
fn add(mut self, rhs: Mod) -> Mod {
if rhs.0 != 0 {
let neg_rhs = Self::MOD - rhs.0;
if self.0 < neg_rhs {
self.0 += rhs.0;
} else {
self.0 -= neg_rhs;
}
}
self
}
}
impl MulAssign for Mod {
fn mul_assign(&mut self, rhs: Mod) {
// Adding this up-casting implementation and the `assert_eq` supresses the bug.
// let x = (u64::from(self.0) * u64::from(rhs.0) % u64::from(Self::MOD)) as u32;
unsafe {
core::arch::asm!(
"mul edx",
"div {:e}",
in(reg) Self::MOD,
inout("eax") rhs.0 => _,
inout("edx") self.0,
options(pure, nomem, nostack),
);
}
// assert_eq!(self.0, x);
}
}
impl Mod {
fn pow(self, mut exp: u32) -> Self {
if exp == 0 {
return Mod(1);
}
if self.0 < 2 {
return self;
}
let mut base = self;
while exp & 1 == 0 {
base *= base;
exp >>= 1;
}
let mut acc = base;
exp >>= 1;
while exp != 0 {
base *= base;
if exp & 1 == 1 {
acc *= base;
}
exp >>= 1;
}
acc
}
}I expected to see this happen: the 3 assertions in main should pass.
Instead, this happened: the first assertion fails.
$ cargo +nightly run --release
[...]
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `654705331`,
right: `650`', src/main.rs:5:5
As noted in the code comments, it works if I change the for_each to a regular for loop. It also works if I add an assertion in my MulAssign comparing the asm! result to a u64 computation. Furthermore, n = 4 only needs primes [2, 3], but it works if I hard-code that instead of using primal.
Meta
This failure is reproducible on both i686 and x86_64, from 1.59.0 (which stabilized asm!) through nightly.
The bad left value is consistent from run to run, but different between versions -- 1.59.0 gets 0 instead.
$ rustc +1.59.0 -Vv
rustc 1.59.0 (9d1b2106e 2022-02-23)
binary: rustc
commit-hash: 9d1b2106e23b1abd32fce1f17267604a5102f57a
commit-date: 2022-02-23
host: x86_64-unknown-linux-gnu
release: 1.59.0
LLVM version: 13.0.0
$ rustc +nightly -Vv
rustc 1.64.0-nightly (4d6d601c8 2022-07-26)
binary: rustc
commit-hash: 4d6d601c8a83284d6b23c253a3e2a060fd197316
commit-date: 2022-07-26
host: x86_64-unknown-linux-gnu
release: 1.64.0-nightly
LLVM version: 14.0.6