Auto merge of #132527 - DianQK:gvn-stmt-iter, r=oli-obk

gvn: Invalid dereferences for all non-local mutations

Fixes #132353.

This PR removes the computation value by traversing SSA locals through `for_each_assignment_mut`.

Because the `for_each_assignment_mut` traversal skips statements which have side effects, such as dereference assignments, the computation may be unsound. Instead of `for_each_assignment_mut`, we compute values by traversing in reverse postorder.

Because we compute and use the symbolic representation of values on the fly, I invalidate all old values when encountering a dereference assignment. The current approach does not prevent the optimization of a clone to a copy.

In the future, we may add an alias model, or dominance information for dereference assignments, or SSA form to help GVN.

r? cjgillot

cc `@jieyouxu` #132356
cc `@RalfJung` #133474

6 files changed, 139 insertions, 170 deletions

diff --git a/tests/mir-opt/pre-codegen/clone_as_copy.rs b/tests/mir-opt/pre-codegen/clone_as_copy.rs
index ae4661e93fd..f5ff1854d38 100644
--- a/tests/mir-opt/pre-codegen/clone_as_copy.rs
+++ b/tests/mir-opt/pre-codegen/clone_as_copy.rs
@@ -1,5 +1,3 @@
-//@ compile-flags: -Zunsound-mir-opts
-// FIXME: see <https://github.com/rust-lang/rust/issues/132353>
 //@ compile-flags: -Cdebuginfo=full
 
 // Check if we have transformed the nested clone to the copy in the complete pipeline.
diff --git a/tests/mir-opt/pre-codegen/deref_nested_borrows.rs b/tests/mir-opt/pre-codegen/deref_nested_borrows.rs
index 4f70ec36bc9..738cd981ae6 100644
--- a/tests/mir-opt/pre-codegen/deref_nested_borrows.rs
+++ b/tests/mir-opt/pre-codegen/deref_nested_borrows.rs
@@ -1,4 +1,3 @@
-//! Regression test for <https://github.com/rust-lang/rust/issues/130853>
 // EMIT_MIR_FOR_EACH_PANIC_STRATEGY
 
 fn src(x: &&u8) -> bool {
diff --git a/tests/mir-opt/pre-codegen/no_inlined_clone.{impl#0}-clone.PreCodegen.after.mir b/tests/mir-opt/pre-codegen/no_inlined_clone.{impl#0}-clone.PreCodegen.after.mir
index 62a9cd9131f..9020cf1ef37 100644
--- a/tests/mir-opt/pre-codegen/no_inlined_clone.{impl#0}-clone.PreCodegen.after.mir
+++ b/tests/mir-opt/pre-codegen/no_inlined_clone.{impl#0}-clone.PreCodegen.after.mir
@@ -3,13 +3,9 @@
 fn <impl at $DIR/no_inlined_clone.rs:9:10: 9:15>::clone(_1: &Foo) -> Foo {
     debug self => _1;
     let mut _0: Foo;
-    let mut _2: i32;
 
     bb0: {
-        StorageLive(_2);
-        _2 = copy ((*_1).0: i32);
-        _0 = Foo { a: move _2 };
-        StorageDead(_2);
+        _0 = copy (*_1);
         return;
     }
 }
diff --git a/tests/mir-opt/pre-codegen/slice_filter.variant_a-{closure#0}.PreCodegen.after.mir b/tests/mir-opt/pre-codegen/slice_filter.variant_a-{closure#0}.PreCodegen.after.mir
index 5a269717f82..cbdd194afd3 100644
--- a/tests/mir-opt/pre-codegen/slice_filter.variant_a-{closure#0}.PreCodegen.after.mir
+++ b/tests/mir-opt/pre-codegen/slice_filter.variant_a-{closure#0}.PreCodegen.after.mir
@@ -4,70 +4,65 @@ fn variant_a::{closure#0}(_1: &mut {closure@$DIR/slice_filter.rs:7:25: 7:39}, _2
     let mut _0: bool;
     let mut _3: &(usize, usize, usize, usize);
     let _4: &usize;
-    let mut _5: &(usize, usize, usize, usize);
+    let _5: &usize;
     let _6: &usize;
-    let mut _7: &(usize, usize, usize, usize);
-    let _8: &usize;
-    let mut _9: &(usize, usize, usize, usize);
-    let _10: &usize;
-    let mut _11: &&usize;
-    let _12: &usize;
-    let mut _13: &&usize;
-    let mut _16: bool;
-    let mut _17: &&usize;
-    let _18: &usize;
-    let mut _19: &&usize;
-    let mut _22: bool;
-    let mut _23: &&usize;
-    let _24: &usize;
-    let mut _25: &&usize;
-    let mut _28: bool;
-    let mut _29: &&usize;
-    let _30: &usize;
-    let mut _31: &&usize;
+    let _7: &usize;
+    let mut _8: &&usize;
+    let _9: &usize;
+    let mut _10: &&usize;
+    let mut _13: bool;
+    let mut _14: &&usize;
+    let _15: &usize;
+    let mut _16: &&usize;
+    let mut _19: bool;
+    let mut _20: &&usize;
+    let _21: &usize;
+    let mut _22: &&usize;
+    let mut _23: bool;
+    let mut _24: &&usize;
+    let _25: &usize;
+    let mut _26: &&usize;
     scope 1 {
         debug a => _4;
-        debug b => _6;
-        debug c => _8;
-        debug d => _10;
+        debug b => _5;
+        debug c => _6;
+        debug d => _7;
         scope 2 (inlined std::cmp::impls::<impl PartialOrd for &usize>::le) {
-            debug self => _11;
-            debug other => _13;
+            debug self => _8;
+            debug other => _10;
             scope 3 (inlined std::cmp::impls::<impl PartialOrd for usize>::le) {
                 debug self => _4;
-                debug other => _8;
-                let mut _14: usize;
-                let mut _15: usize;
+                debug other => _6;
+                let mut _11: usize;
+                let mut _12: usize;
             }
         }
         scope 4 (inlined std::cmp::impls::<impl PartialOrd for &usize>::le) {
-            debug self => _17;
-            debug other => _19;
+            debug self => _14;
+            debug other => _16;
             scope 5 (inlined std::cmp::impls::<impl PartialOrd for usize>::le) {
-                debug self => _10;
-                debug other => _6;
-                let mut _20: usize;
-                let mut _21: usize;
+                debug self => _7;
+                debug other => _5;
+                let mut _17: usize;
+                let mut _18: usize;
             }
         }
         scope 6 (inlined std::cmp::impls::<impl PartialOrd for &usize>::le) {
-            debug self => _23;
-            debug other => _25;
+            debug self => _20;
+            debug other => _22;
             scope 7 (inlined std::cmp::impls::<impl PartialOrd for usize>::le) {
-                debug self => _8;
+                debug self => _6;
                 debug other => _4;
-                let mut _26: usize;
-                let mut _27: usize;
             }
         }
         scope 8 (inlined std::cmp::impls::<impl PartialOrd for &usize>::le) {
-            debug self => _29;
-            debug other => _31;
+            debug self => _24;
+            debug other => _26;
             scope 9 (inlined std::cmp::impls::<impl PartialOrd for usize>::le) {
-                debug self => _6;
-                debug other => _10;
-                let mut _32: usize;
-                let mut _33: usize;
+                debug self => _5;
+                debug other => _7;
+                let mut _27: usize;
+                let mut _28: usize;
             }
         }
     }
@@ -75,129 +70,116 @@ fn variant_a::{closure#0}(_1: &mut {closure@$DIR/slice_filter.rs:7:25: 7:39}, _2
     bb0: {
         _3 = copy (*_2);
         _4 = &((*_3).0: usize);
-        _5 = copy (*_2);
-        _6 = &((*_5).1: usize);
-        _7 = copy (*_2);
-        _8 = &((*_7).2: usize);
-        _9 = copy (*_2);
-        _10 = &((*_9).3: usize);
-        StorageLive(_16);
-        StorageLive(_11);
-        _11 = &_4;
+        _5 = &((*_3).1: usize);
+        _6 = &((*_3).2: usize);
+        _7 = &((*_3).3: usize);
         StorageLive(_13);
-        StorageLive(_12);
-        _12 = copy _8;
-        _13 = &_12;
-        StorageLive(_14);
-        _14 = copy ((*_3).0: usize);
-        StorageLive(_15);
-        _15 = copy ((*_7).2: usize);
-        _16 = Le(move _14, move _15);
-        StorageDead(_15);
-        StorageDead(_14);
-        switchInt(move _16) -> [0: bb1, otherwise: bb2];
+        StorageLive(_8);
+        _8 = &_4;
+        StorageLive(_10);
+        StorageLive(_9);
+        _9 = copy _6;
+        _10 = &_9;
+        _11 = copy ((*_3).0: usize);
+        _12 = copy ((*_3).2: usize);
+        _13 = Le(copy _11, copy _12);
+        switchInt(move _13) -> [0: bb1, otherwise: bb2];
     }
 
     bb1: {
-        StorageDead(_12);
-        StorageDead(_13);
-        StorageDead(_11);
+        StorageDead(_9);
+        StorageDead(_10);
+        StorageDead(_8);
         goto -> bb4;
     }
 
     bb2: {
-        StorageDead(_12);
-        StorageDead(_13);
-        StorageDead(_11);
-        StorageLive(_22);
-        StorageLive(_17);
-        _17 = &_10;
+        StorageDead(_9);
+        StorageDead(_10);
+        StorageDead(_8);
         StorageLive(_19);
+        StorageLive(_14);
+        _14 = &_7;
+        StorageLive(_16);
+        StorageLive(_15);
+        _15 = copy _5;
+        _16 = &_15;
+        StorageLive(_17);
+        _17 = copy ((*_3).3: usize);
         StorageLive(_18);
-        _18 = copy _6;
-        _19 = &_18;
-        StorageLive(_20);
-        _20 = copy ((*_9).3: usize);
-        StorageLive(_21);
-        _21 = copy ((*_5).1: usize);
-        _22 = Le(move _20, move _21);
-        StorageDead(_21);
-        StorageDead(_20);
-        switchInt(move _22) -> [0: bb3, otherwise: bb8];
+        _18 = copy ((*_3).1: usize);
+        _19 = Le(move _17, move _18);
+        StorageDead(_18);
+        StorageDead(_17);
+        switchInt(move _19) -> [0: bb3, otherwise: bb8];
     }
 
     bb3: {
-        StorageDead(_18);
-        StorageDead(_19);
-        StorageDead(_17);
+        StorageDead(_15);
+        StorageDead(_16);
+        StorageDead(_14);
         goto -> bb4;
     }
 
     bb4: {
-        StorageLive(_28);
         StorageLive(_23);
-        _23 = &_8;
-        StorageLive(_25);
-        StorageLive(_24);
-        _24 = copy _4;
-        _25 = &_24;
-        StorageLive(_26);
-        _26 = copy ((*_7).2: usize);
-        StorageLive(_27);
-        _27 = copy ((*_3).0: usize);
-        _28 = Le(move _26, move _27);
-        StorageDead(_27);
-        StorageDead(_26);
-        switchInt(move _28) -> [0: bb5, otherwise: bb6];
+        StorageLive(_20);
+        _20 = &_6;
+        StorageLive(_22);
+        StorageLive(_21);
+        _21 = copy _4;
+        _22 = &_21;
+        _23 = Le(copy _12, copy _11);
+        switchInt(move _23) -> [0: bb5, otherwise: bb6];
     }
 
     bb5: {
-        StorageDead(_24);
-        StorageDead(_25);
-        StorageDead(_23);
+        StorageDead(_21);
+        StorageDead(_22);
+        StorageDead(_20);
         _0 = const false;
         goto -> bb7;
     }
 
     bb6: {
-        StorageDead(_24);
+        StorageDead(_21);
+        StorageDead(_22);
+        StorageDead(_20);
+        StorageLive(_24);
+        _24 = &_5;
+        StorageLive(_26);
+        StorageLive(_25);
+        _25 = copy _7;
+        _26 = &_25;
+        StorageLive(_27);
+        _27 = copy ((*_3).1: usize);
+        StorageLive(_28);
+        _28 = copy ((*_3).3: usize);
+        _0 = Le(move _27, move _28);
+        StorageDead(_28);
+        StorageDead(_27);
         StorageDead(_25);
-        StorageDead(_23);
-        StorageLive(_29);
-        _29 = &_6;
-        StorageLive(_31);
-        StorageLive(_30);
-        _30 = copy _10;
-        _31 = &_30;
-        StorageLive(_32);
-        _32 = copy ((*_5).1: usize);
-        StorageLive(_33);
-        _33 = copy ((*_9).3: usize);
-        _0 = Le(move _32, move _33);
-        StorageDead(_33);
-        StorageDead(_32);
-        StorageDead(_30);
-        StorageDead(_31);
-        StorageDead(_29);
+        StorageDead(_26);
+        StorageDead(_24);
         goto -> bb7;
     }
 
     bb7: {
-        StorageDead(_28);
+        StorageDead(_23);
         goto -> bb9;
     }
 
     bb8: {
-        StorageDead(_18);
-        StorageDead(_19);
-        StorageDead(_17);
+        StorageDead(_15);
+        StorageDead(_16);
+        StorageDead(_14);
         _0 = const true;
         goto -> bb9;
     }
 
     bb9: {
-        StorageDead(_22);
-        StorageDead(_16);
+        StorageDead(_19);
+        StorageDead(_13);
         return;
     }
 }
diff --git a/tests/mir-opt/pre-codegen/slice_filter.variant_b-{closure#0}.PreCodegen.after.mir b/tests/mir-opt/pre-codegen/slice_filter.variant_b-{closure#0}.PreCodegen.after.mir
index f93f7264dec..bc7a31d5219 100644
--- a/tests/mir-opt/pre-codegen/slice_filter.variant_b-{closure#0}.PreCodegen.after.mir
+++ b/tests/mir-opt/pre-codegen/slice_filter.variant_b-{closure#0}.PreCodegen.after.mir
@@ -4,46 +4,40 @@ fn variant_b::{closure#0}(_1: &mut {closure@$DIR/slice_filter.rs:11:25: 11:41},
     let mut _0: bool;
     let mut _3: &(usize, usize, usize, usize);
     let _4: usize;
-    let mut _5: &(usize, usize, usize, usize);
+    let _5: usize;
     let _6: usize;
-    let mut _7: &(usize, usize, usize, usize);
-    let _8: usize;
-    let mut _9: &(usize, usize, usize, usize);
-    let _10: usize;
-    let mut _11: bool;
-    let mut _12: bool;
-    let mut _13: bool;
+    let _7: usize;
+    let mut _8: bool;
+    let mut _9: bool;
+    let mut _10: bool;
     scope 1 {
         debug a => _4;
-        debug b => _6;
-        debug c => _8;
-        debug d => _10;
+        debug b => _5;
+        debug c => _6;
+        debug d => _7;
     }
 
     bb0: {
         _3 = copy (*_2);
         _4 = copy ((*_3).0: usize);
-        _5 = copy (*_2);
-        _6 = copy ((*_5).1: usize);
-        _7 = copy (*_2);
-        _8 = copy ((*_7).2: usize);
-        _9 = copy (*_2);
-        _10 = copy ((*_9).3: usize);
-        StorageLive(_11);
-        _11 = Le(copy _4, copy _8);
-        switchInt(move _11) -> [0: bb2, otherwise: bb1];
+        _5 = copy ((*_3).1: usize);
+        _6 = copy ((*_3).2: usize);
+        _7 = copy ((*_3).3: usize);
+        StorageLive(_8);
+        _8 = Le(copy _4, copy _6);
+        switchInt(move _8) -> [0: bb2, otherwise: bb1];
     }
 
     bb1: {
-        StorageLive(_12);
-        _12 = Le(copy _10, copy _6);
-        switchInt(move _12) -> [0: bb2, otherwise: bb6];
+        StorageLive(_9);
+        _9 = Le(copy _7, copy _5);
+        switchInt(move _9) -> [0: bb2, otherwise: bb6];
     }
 
     bb2: {
-        StorageLive(_13);
-        _13 = Le(copy _8, copy _4);
-        switchInt(move _13) -> [0: bb3, otherwise: bb4];
+        StorageLive(_10);
+        _10 = Le(copy _6, copy _4);
+        switchInt(move _10) -> [0: bb3, otherwise: bb4];
     }
 
     bb3: {
@@ -52,12 +46,12 @@ fn variant_b::{closure#0}(_1: &mut {closure@$DIR/slice_filter.rs:11:25: 11:41},
     }
 
     bb4: {
-        _0 = Le(copy _6, copy _10);
+        _0 = Le(copy _5, copy _7);
         goto -> bb5;
     }
 
     bb5: {
-        StorageDead(_13);
+        StorageDead(_10);
         goto -> bb7;
     }
 
@@ -67,8 +61,8 @@ fn variant_b::{closure#0}(_1: &mut {closure@$DIR/slice_filter.rs:11:25: 11:41},
     }
 
     bb7: {
-        StorageDead(_12);
-        StorageDead(_11);
+        StorageDead(_9);
+        StorageDead(_8);
         return;
     }
 }
diff --git a/tests/mir-opt/pre-codegen/try_identity.old.PreCodegen.after.mir b/tests/mir-opt/pre-codegen/try_identity.old.PreCodegen.after.mir
index ac485f485b1..889e80d26e1 100644
--- a/tests/mir-opt/pre-codegen/try_identity.old.PreCodegen.after.mir
+++ b/tests/mir-opt/pre-codegen/try_identity.old.PreCodegen.after.mir
@@ -19,14 +19,14 @@ fn old(_1: Result<T, E>) -> Result<T, E> {
     }
 
     bb1: {
-        _3 = move ((_1 as Ok).0: T);
-        _0 = Result::<T, E>::Ok(copy _3);
+        _3 = copy ((_1 as Ok).0: T);
+        _0 = copy _1;
         goto -> bb3;
     }
 
     bb2: {
-        _4 = move ((_1 as Err).0: E);
-        _0 = Result::<T, E>::Err(copy _4);
+        _4 = copy ((_1 as Err).0: E);
+        _0 = copy _1;
         goto -> bb3;
     }