Another mir-opt-level=4 miscompilation

[leonardo-m]

This is a bad bug report because the code to reproduce it is long. But I'm bad at spotting what the problem is here.

If I compile this code with

rustc -O -Z mir-opt-level=3 test.rs

It runs very quickly. If I compile it with:

rustc -O -Z mir-opt-level=4 test.rs

I think it goes into an infinite loop.

I think the miscompilation problem is in the "while b != 1" loop inside the residue() function.

I've seen that the asm for the residue() function (adding inline(never) to residue() and jacobi()) gets quite shorter if I use opt-level=4.

fn mul_mod(a: u32, b: u32, m: u32) -> u32 {
    ((a as u64 * b as u64) % (m as u64)) as u32
}

fn pow_mod(a: u32, n: u32, p: u32) -> u32 {
    if n == 0 {
        return 1;
    }
    if n % 2 == 0 {
        pow_mod(mul_mod(a, a, p), n / 2, p)
    } else {
        mul_mod(a, pow_mod(a, n - 1, p), p)
    }
}

fn jacobi(mut a: u32, mut m: u32) -> i32 {
    let mut t = 1;
    a %= m;
    while a != 0 {
        while (a & 1) == 0 {
            a >>= 1;
            if (m & 7) == 3 || (m & 7) == 5 {
                t = -t;
            }
        }
        let aux = a;
        a = m;
        m = aux;
        if (a & 3) == 3 && (m & 3) == 3 {
            t = -t;
        }
        a %= m;
    }
    if m == 1 { t } else { 0 }
}

fn residue(prime: u32, arg: u32) -> u32 {
    if jacobi(arg, prime) == -1 {
        return u32::MAX;
    }

    let mut y = 2;
    while jacobi(y, prime) != -1 {
        y += 1;
    }

    let mut r: u32 = 0;
    let mut q: u32 = prime - 1;
    while q % 2 == 0 {
        r += 1;
        q /= 2;
    }

    let mut result = prime - 1;
    result >>= r;
    y = pow_mod(y, result, prime);
    result >>= 1;
    let mut b = pow_mod(arg, result, prime);
    result = mul_mod(arg, b, prime);
    b *= result;
    b = b % prime;

    while b != 1 {
        let mut t = mul_mod(b, b, prime);
        let mut m: u32 = 1;
        while t != 1 {
            t *= t;
            t = t % prime;
            m += 1;
        }
        t = 0;
        t |= 1 << (r - m - 1);
        t = pow_mod(y, t, prime);
        y = mul_mod(t, t, prime);
        r = m;
        result = mul_mod(result, t, prime);
        b = mul_mod(b, y, prime);
    }
    result
}


fn main() {
    assert_eq!(residue(5, 4), 3);
}

Using:

rustc 1.59.0-nightly (e6b883c74 2021-12-08)
binary: rustc
commit-hash: e6b883c74f49f32cb5d1cbad3457f2b8805a4a38
commit-date: 2021-12-08
host: x86_64-pc-windows-gnu
release: 1.59.0-nightly
LLVM version: 13.0.0

[matthiaskrgr]

What is this mir-opt-level=4? Is this new? I have only heard of up to 0-3.
It is not an alias for -Zunsound-mir-opts, is it? :D

[leonardo-m]

I think the old "mir-opt-level=3" got renamed "-Z mir-opt-level=4" recently, few months ago. I think they got shifted by +1 :-)

[tmiasko]

fn main() {
    let a = true;
    let _ = &a;
    let mut b = false;
    b |= a;
    assert!(b);
}

$ rustc a.rs -Zmir-opt-level=4 && ./a
thread 'main' panicked at 'assertion failed: b', a.rs:6:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

[leonardo-m]

Is that a minimization? In the original code I think there are no references "&a".

[tmiasko]

The ConstPropagator::eval_rvalue_with_identities attempts to evaluates constant expressions where only one of operands is known using algebraic identities, but it incorrectly reports success when such an attempt fails.

Is that a minimization? In the original code I think there are no references "&a".

When a reference to a local variable is taken, the const propagator considers its value to be unknown. The example takes a reference to a to introduce an evaluation failure of BitOr(b, a).