Auto merge of #145541 - cjgillot:dest-prop-live-range, r=Amanieu

Reimplement DestinationPropagation according to live ranges.

This PR reimplements DestinationPropagation as a problem of merging live-ranges of locals. We merge locals that have disjoint live-ranges. This allows merging several locals in the same round by updating live range information.

Live ranges are mainly computed using the `MaybeLiveLocals` analysis. The subtlety is that we split each statement and terminator in 2 positions. The first position is the regular statement. The second position is a shadow, which is always more live. It encodes partial writes and dead writes as a local being live for half a statement. This half statement ensures that writes conflict with another local's writes and regular liveness.

r? `@Amanieu`

8 files changed, 31 insertions, 29 deletions

diff --git a/tests/mir-opt/dest-prop/cycle.main.DestinationPropagation.panic-abort.diff b/tests/mir-opt/dest-prop/cycle.main.DestinationPropagation.panic-abort.diff
index 5d8aaedae37..a2f10be31a9 100644
--- a/tests/mir-opt/dest-prop/cycle.main.DestinationPropagation.panic-abort.diff
+++ b/tests/mir-opt/dest-prop/cycle.main.DestinationPropagation.panic-abort.diff
@@ -8,25 +8,23 @@
       let _5: ();
       let mut _6: i32;
       scope 1 {
--         debug x => _1;
-+         debug x => _6;
+          debug x => _1;
           let _2: i32;
           scope 2 {
 -             debug y => _2;
-+             debug y => _6;
++             debug y => _1;
               let _3: i32;
               scope 3 {
 -                 debug z => _3;
-+                 debug z => _6;
++                 debug z => _1;
               }
           }
       }
   
       bb0: {
 -         StorageLive(_1);
--         _1 = val() -> [return: bb1, unwind unreachable];
 +         nop;
-+         _6 = val() -> [return: bb1, unwind unreachable];
+          _1 = val() -> [return: bb1, unwind unreachable];
       }
   
       bb1: {
@@ -49,9 +47,10 @@
           StorageLive(_5);
 -         StorageLive(_6);
 -         _6 = copy _1;
+-         _5 = std::mem::drop::<i32>(move _6) -> [return: bb2, unwind unreachable];
 +         nop;
 +         nop;
-          _5 = std::mem::drop::<i32>(move _6) -> [return: bb2, unwind unreachable];
++         _5 = std::mem::drop::<i32>(move _1) -> [return: bb2, unwind unreachable];
       }
   
       bb2: {
diff --git a/tests/mir-opt/dest-prop/cycle.main.DestinationPropagation.panic-unwind.diff b/tests/mir-opt/dest-prop/cycle.main.DestinationPropagation.panic-unwind.diff
index 05c9bcc1d73..a08488615b1 100644
--- a/tests/mir-opt/dest-prop/cycle.main.DestinationPropagation.panic-unwind.diff
+++ b/tests/mir-opt/dest-prop/cycle.main.DestinationPropagation.panic-unwind.diff
@@ -8,25 +8,23 @@
       let _5: ();
       let mut _6: i32;
       scope 1 {
--         debug x => _1;
-+         debug x => _6;
+          debug x => _1;
           let _2: i32;
           scope 2 {
 -             debug y => _2;
-+             debug y => _6;
++             debug y => _1;
               let _3: i32;
               scope 3 {
 -                 debug z => _3;
-+                 debug z => _6;
++                 debug z => _1;
               }
           }
       }
   
       bb0: {
 -         StorageLive(_1);
--         _1 = val() -> [return: bb1, unwind continue];
 +         nop;
-+         _6 = val() -> [return: bb1, unwind continue];
+          _1 = val() -> [return: bb1, unwind continue];
       }
   
       bb1: {
@@ -49,9 +47,10 @@
           StorageLive(_5);
 -         StorageLive(_6);
 -         _6 = copy _1;
+-         _5 = std::mem::drop::<i32>(move _6) -> [return: bb2, unwind continue];
 +         nop;
 +         nop;
-          _5 = std::mem::drop::<i32>(move _6) -> [return: bb2, unwind continue];
++         _5 = std::mem::drop::<i32>(move _1) -> [return: bb2, unwind continue];
       }
   
       bb2: {
diff --git a/tests/mir-opt/dest-prop/dead_stores_79191.f.DestinationPropagation.after.panic-abort.mir b/tests/mir-opt/dest-prop/dead_stores_79191.f.DestinationPropagation.after.panic-abort.mir
index eb4209731c6..15061da8120 100644
--- a/tests/mir-opt/dest-prop/dead_stores_79191.f.DestinationPropagation.after.panic-abort.mir
+++ b/tests/mir-opt/dest-prop/dead_stores_79191.f.DestinationPropagation.after.panic-abort.mir
@@ -7,16 +7,16 @@ fn f(_1: usize) -> usize {
     let mut _3: usize;
     let mut _4: usize;
     scope 1 {
-        debug b => _3;
+        debug b => _2;
     }
 
     bb0: {
         nop;
-        _3 = copy _1;
+        _2 = copy _1;
         _1 = const 5_usize;
         nop;
         nop;
-        _1 = move _3;
+        _1 = move _2;
         nop;
         nop;
         nop;
diff --git a/tests/mir-opt/dest-prop/dead_stores_79191.f.DestinationPropagation.after.panic-unwind.mir b/tests/mir-opt/dest-prop/dead_stores_79191.f.DestinationPropagation.after.panic-unwind.mir
index fe9a7376a58..ddfe4dc5b3e 100644
--- a/tests/mir-opt/dest-prop/dead_stores_79191.f.DestinationPropagation.after.panic-unwind.mir
+++ b/tests/mir-opt/dest-prop/dead_stores_79191.f.DestinationPropagation.after.panic-unwind.mir
@@ -7,16 +7,16 @@ fn f(_1: usize) -> usize {
     let mut _3: usize;
     let mut _4: usize;
     scope 1 {
-        debug b => _3;
+        debug b => _2;
     }
 
     bb0: {
         nop;
-        _3 = copy _1;
+        _2 = copy _1;
         _1 = const 5_usize;
         nop;
         nop;
-        _1 = move _3;
+        _1 = move _2;
         nop;
         nop;
         nop;
diff --git a/tests/mir-opt/dest-prop/dead_stores_better.f.DestinationPropagation.after.panic-abort.mir b/tests/mir-opt/dest-prop/dead_stores_better.f.DestinationPropagation.after.panic-abort.mir
index eb4209731c6..15061da8120 100644
--- a/tests/mir-opt/dest-prop/dead_stores_better.f.DestinationPropagation.after.panic-abort.mir
+++ b/tests/mir-opt/dest-prop/dead_stores_better.f.DestinationPropagation.after.panic-abort.mir
@@ -7,16 +7,16 @@ fn f(_1: usize) -> usize {
     let mut _3: usize;
     let mut _4: usize;
     scope 1 {
-        debug b => _3;
+        debug b => _2;
     }
 
     bb0: {
         nop;
-        _3 = copy _1;
+        _2 = copy _1;
         _1 = const 5_usize;
         nop;
         nop;
-        _1 = move _3;
+        _1 = move _2;
         nop;
         nop;
         nop;
diff --git a/tests/mir-opt/dest-prop/dead_stores_better.f.DestinationPropagation.after.panic-unwind.mir b/tests/mir-opt/dest-prop/dead_stores_better.f.DestinationPropagation.after.panic-unwind.mir
index fe9a7376a58..ddfe4dc5b3e 100644
--- a/tests/mir-opt/dest-prop/dead_stores_better.f.DestinationPropagation.after.panic-unwind.mir
+++ b/tests/mir-opt/dest-prop/dead_stores_better.f.DestinationPropagation.after.panic-unwind.mir
@@ -7,16 +7,16 @@ fn f(_1: usize) -> usize {
     let mut _3: usize;
     let mut _4: usize;
     scope 1 {
-        debug b => _3;
+        debug b => _2;
     }
 
     bb0: {
         nop;
-        _3 = copy _1;
+        _2 = copy _1;
         _1 = const 5_usize;
         nop;
         nop;
-        _1 = move _3;
+        _1 = move _2;
         nop;
         nop;
         nop;
diff --git a/tests/mir-opt/nrvo_miscompile_111005.rs b/tests/mir-opt/nrvo_miscompile_111005.rs
index 03008fa8191..131f7b8f6f9 100644
--- a/tests/mir-opt/nrvo_miscompile_111005.rs
+++ b/tests/mir-opt/nrvo_miscompile_111005.rs
@@ -1,4 +1,3 @@
-// skip-filecheck
 // This is a miscompilation, #111005 to track
 
 //@ test-mir-pass: RenameReturnPlace
@@ -10,6 +9,11 @@ use core::intrinsics::mir::*;
 // EMIT_MIR nrvo_miscompile_111005.wrong.RenameReturnPlace.diff
 #[custom_mir(dialect = "runtime", phase = "initial")]
 pub fn wrong(arg: char) -> char {
+    // CHECK-LABEL: fn wrong(
+    // CHECK: _0 = copy _1;
+    // FIXME: This is wrong:
+    // CHECK-NEXT: _0 = const 'b';
+    // CHECK-NEXT: return;
     mir! {
         {
             let temp = arg;
diff --git a/tests/mir-opt/pre-codegen/clone_as_copy.enum_clone_as_copy.PreCodegen.after.mir b/tests/mir-opt/pre-codegen/clone_as_copy.enum_clone_as_copy.PreCodegen.after.mir
index 9f88e1961ec..e67f362ee04 100644
--- a/tests/mir-opt/pre-codegen/clone_as_copy.enum_clone_as_copy.PreCodegen.after.mir
+++ b/tests/mir-opt/pre-codegen/clone_as_copy.enum_clone_as_copy.PreCodegen.after.mir
@@ -6,8 +6,8 @@ fn enum_clone_as_copy(_1: &Enum1) -> Enum1 {
     scope 1 (inlined <Enum1 as Clone>::clone) {
         debug self => _1;
         let mut _2: isize;
-        let mut _3: &AllCopy;
-        let mut _4: &NestCopy;
+        let _3: &AllCopy;
+        let _4: &NestCopy;
         scope 2 {
             debug __self_0 => _3;
             scope 6 (inlined <AllCopy as Clone>::clone) {