Miscompilation with mir-opt-level=2

[leonardo-m]

This little matrix processing code shows miscompilation if compiled with:

rustc -Z mir-opt-level=2 test.rs

But it compiles correctly with:

rustc -Z mir-opt-level=1 test.rs

With:

rustc 1.48.0-nightly 1fd5b9d516c035a898dcb437b2f982bea5d4bc88 2020-09-20 x86_64-pc-windows-gnu

fn main() {
    const MOD: i64 = 100_000_000;
    const N: u64 = 1_000_000_000_000;

    const SIZE: usize = 4;
    const SIZE64: u64 = SIZE as _;
    type Mat = [[i64; SIZE]; SIZE];

    fn matrix_prod(a: &Mat, b: &Mat, n: usize, m: usize, p: usize) -> Mat {
        let mut res: Mat = Mat::default();
        for i in 0 .. n {
            for j in 0 .. p {
                for k in 0 .. m {
                    res[i][j] = (res[i][j] + a[i][k] * b[k][j] % MOD) % MOD;
                }
            }
        }
        res
    }

    fn matrix_pow(mut a: Mat, s: usize, mut n: u64) -> Mat {
        let mut res: Mat = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]];

        while n != 0 {
            if (n & 1) != 0 {
                res = matrix_prod(&a, &res, s, s, s);
            }
            n >>= 1;
            a = matrix_prod(&a, &a, s, s, s);
        }
        res
    }

    const G1: Mat = [[0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [1, -2, 2, 2]];
    let g2 = matrix_pow(G1, SIZE, N - SIZE64);
    println!("{:?}", g2);
}

[jonas-schievink]

~> rustc +nightly -Zmir-opt-level=2 mis.rs -Zfuel=mis=27
warning: optimization-fuel-exhausted: DestinationPropagation DefId(0:11 ~ mis[317d]::main[0]::matrix_prod[0]) CandidateAssignment { dest: _20, src: _19, loc: bb6[3] }

warning: 1 warning emitted

~> ./mis
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
~> rustc +nightly -Zmir-opt-level=2 mis.rs -Zfuel=mis=26
warning: optimization-fuel-exhausted: DestinationPropagation DefId(0:11 ~ mis[317d]::main[0]::matrix_prod[0]) CandidateAssignment { dest: _0, src: _6, loc: bb4[8] }

warning: 1 warning emitted

~> ./mis
[[-66035979, 52978690, -50400250, 65261310], [-34738690, 3441401, -16498690, 80122370], [80122370, -94983430, -36313859, -56253950], [43746050, -7369730, -7491330, -48821759]]

[jonas-schievink]

Hmm, on first glance the replacement it performs looks correct: It replaces local _6 (res) with the return place _0. Previously the return place was only used in the return block by a _0 = _6 copy statement, so this transformation should be correct.

Maybe this part of the diff causes a problem?

-        StorageLive(_6);                 // scope 0 at mis.rs:10:13: 10:20
-        _6 = <[[i64; 4]; 4] as Default>::default() -> bb1; // scope 0 at mis.rs:10:28: 10:42
+        nop;                             // scope 0 at mis.rs:10:13: 10:20
+        _0 = <[[i64; 4]; 4] as Default>::default() -> bb1; // scope 0 at mis.rs:10:28: 10:42

We're using our return place as the return destination for the inner call. It's possible that there's an undocumented (and maybe unintended) assumption that the return place is not reused like this, either in other MIR optimizations or in codegen. Haven't looked too deeply yet though.

[jonas-schievink]

Ah, there's this bad call in LLVM IR:

  call fastcc void @_ZN3mis4main11matrix_prod17h8c1d34c6f8edb3ecE(
    [4 x [4 x i64]]* noalias nocapture nonnull sret dereferenceable(128) %g2,
    [4 x [4 x i64]]* noalias nonnull readonly align 8 dereferenceable(128) %0,
    [4 x [4 x i64]]* noalias nonnull readonly align 8 dereferenceable(128) %g2
  )

It passes a reference to %g2 as both the return pointer, and the second (immutable) argument.

[jonas-schievink]

...and we have this corresponding MIR, where we already incorrectly pass a reference to _0 as an argument, while also assigning the call result to it:

        _20 = &_0;                       // scope 1 at mis.rs:26:39: 26:43
        nop;                             // scope 1 at mis.rs:26:39: 26:43
        StorageLive(_22);                // scope 1 at mis.rs:26:45: 26:46
        _22 = _2;                        // scope 1 at mis.rs:26:45: 26:46
        StorageLive(_23);                // scope 1 at mis.rs:26:48: 26:49
        _23 = _2;                        // scope 1 at mis.rs:26:48: 26:49
        StorageLive(_24);                // scope 1 at mis.rs:26:51: 26:52
        _24 = _2;                        // scope 1 at mis.rs:26:51: 26:52
        _0 = matrix_prod(move _18, move _20, move _22, move _23, move _24) -> bb6; // scope 1 at mis.rs:26:23: 26:53
                                         // mir::Constant
                                         // + span: mis.rs:26:23: 26:34
                                         // + literal: Const { ty: for<'r, 's> fn(&'r [[i64; _]; _], &'s [[i64; _]; _], usize, usize, usize) -> [[i64; _]; _] {main::matrix_prod}, val: Value(Scalar(<ZST>)) }

The destination propagation pass already has code that prevents merging a call destination with one of the arguments, but here we pass a reference instead. Curiously, the &_0 was produced by merging _4 with _0, which is not really something the pass should be doing since a reference is taken to _4, and we avoid touching any local that has its address taken.

[tmiasko]

The propagation is disabled only if both locals have their address taken. Changing that to be more conservative does fix this issue.

Minimized:

type M = [i64; 2];

fn f(a: &M) -> M {
    let mut b: M = M::default();
    b[0] = a[0] * a[0];
    b
}

fn main() {
    let mut a: M = [1, 1];
    a = f(&a);
    std::process::exit((a[0] != 1) as i32);
}

[jonas-schievink]

Oof, this should have been an ||, not an &&

rust/compiler/rustc_mir/src/transform/dest_prop.rs

Lines 907 to 908 in c113030

	if self.ever_borrowed_locals.contains(dest.local)
	&& self.ever_borrowed_locals.contains(src.local)

[jonas-schievink]

Thanks @tmiasko!

[jonas-schievink]

Opened #77066 with a fix