Wrong optimization

[Grobycn]

I tried this code:

fn max_turbulence_size(arr: Vec<i32>) -> i32 {
    let mut prev = 0;
    let mut cnt = 0;
    let mut ret = 0;
    for w in arr.windows(2) {
        let d = w[1] - w[0];
        if d == 0 {
            cnt = 0;
        } else if d > 0 {
            if prev < 0 {
                cnt += 1;
            } else {
                cnt = 1;
            }
        } else {
            if prev > 0 {
                cnt += 1;
            } else {
                cnt = 1;
            }
        }
        // Uncomment the follow line will give the right answer
        // println!("{} {}", d, prev);
        ret = ret.max(cnt);
        // The follow line seems optimized out if we don't access `prev`, `d` simultaneously.
        prev = d;
    }
    ret + 1
}

fn main() {
    let v = vec![9,4,2,10,7,8,8,1,9];
    let ans = max_turbulence_size(v);
    // The right answer is 5. But when build with release, the output is 2
    println!("{}", ans);
}

I expected to see this happen: 5 is printed.

Instead, this happened: when build with release, the output is 2.

Meta

rustc --version --verbose:

rustc 1.58.0-nightly (2885c4748 2021-11-20)
binary: rustc
commit-hash: 2885c474823637ae69c5967327327a337aebedb2
commit-date: 2021-11-20
host: x86_64-unknown-linux-gnu
release: 1.58.0-nightly
LLVM version: 13.0.0

I also test all the following rust version at playground, and got wrong answer when build with release.

stable: 1.61.0
beta: 1.62.0-beta.6
nightly: 1.64.0-nightly (2022-06-25 20a6f3a)

[Uriopass]

Simplified the function a bit:

pub fn buggy(arr: Vec<i32>) -> i32 {
    let mut prev = 0;
    let mut cnt = 0;
    // The entire loop is optimized away in release: https://godbolt.org/z/j538GxzT1
    for d in arr {
        if d > 0 {
            if prev < 0 {
                cnt += 1;
            } else {
                cnt = 1;
            }
        } else {
            if prev > 0 {
                cnt += 1;
            } else {
                cnt = 1;
            }
        }
        prev = d;
    }
    cnt
}

fn main() {
    let v = vec![-1,1];
    let ans = buggy(v);
    // The right answer is 2. But when build with release, the output is 1
    println!("{}", ans);
}

It seems that something assumes that d = prev in the loop. However doing it explicitely by changing the condition to if d == prev doesn't trigger the bug.

[SNCPlay42]

Per godbolt this produced the correct result on 1.55 and misoptimises on 1.56 and later.

@rustbot label A-codegen I-unsound T-compiler regression-from-stable-to-stable

[nikic]

Works with -C no-prepopulate-passes, so presumably an LLVM miscompile. Assigning to me for investigation.

[nbdd0121]

This C version has the same issue: https://godbolt.org/z/E86n349nr, so likely a LLVM bug.

@rustbot label: +A-LLVM

[nikic]

Miscompile still present on current main, and appears to be introduced during this -indvars transform: https://alive2.llvm.org/ce/z/I-4JjZ

[nikic]

Upstream issue: llvm/llvm-project#56242

[apiraino]

WG-prioritization assigning priority (Zulip discussion).

@rustbot label -I-prioritize +P-critical

[anastygnome]

LLVM miscompile. The optimiser mistakenly analyses the loop as invariant.

[nikic]

Upstream fix: llvm/llvm-project@e4d1d0c

[pnkfelix]

Closing as fixed. I believe PR #98567 fixed this in nightly, and I believe PR #99098 fixed this in beta.