Auto merge of #45821 - djzin:unreachable-match-arms, r=nikomatsakis

always add an unreachable branch on matches to give more info to llvm

As part of https://github.com/djzin/rustc-optimization I discovered that some simple enum optimizations (src/unary/three_valued_enum.rs and src/unary/four_valued_enum.rs in the repo) are not applied - and the reason for this is that we erase the info that the discriminant of an enum is one of the options by putting the last one in an "otherwise" branch. This patch adds an extra branch so that LLVM can know what the possibilities are for the discriminant, which fixes the three- and four- valued cases.

Note that for whatever reason, this doesn't fix the case of 2 variants (most notably `Option` and `Result` have 2 variants) - a pass re-ordering might fix this or we may wish to add "assume" annotations on discriminants to force it to optimize.

5 files changed, 103 insertions, 31 deletions

diff --git a/src/librustc_mir/build/matches/test.rs b/src/librustc_mir/build/matches/test.rs
index 4792bf2b213..1cf35af3a9e 100644
--- a/src/librustc_mir/build/matches/test.rs
+++ b/src/librustc_mir/build/matches/test.rs
@@ -205,7 +205,7 @@ impl<'a, 'gcx, 'tcx> Builder<'a, 'gcx, 'tcx> {
                 if let Some(otherwise_block) = otherwise_block {
                     targets.push(otherwise_block);
                 } else {
-                    values.pop();
+                    targets.push(self.unreachable_block());
                 }
                 debug!("num_enum_variants: {}, tested variants: {:?}, variants: {:?}",
                        num_enum_variants, values, variants);
diff --git a/src/librustc_mir/build/mod.rs b/src/librustc_mir/build/mod.rs
index 0489a03c97e..83326f73237 100644
--- a/src/librustc_mir/build/mod.rs
+++ b/src/librustc_mir/build/mod.rs
@@ -307,6 +307,8 @@ struct Builder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     cached_resume_block: Option<BasicBlock>,
     /// cached block with the RETURN terminator
     cached_return_block: Option<BasicBlock>,
+    /// cached block with the UNREACHABLE terminator
+    cached_unreachable_block: Option<BasicBlock>,
 }
 
 struct CFG<'tcx> {
@@ -400,6 +402,11 @@ fn construct_fn<'a, 'gcx, 'tcx, A>(hir: Cx<'a, 'gcx, 'tcx>,
                               TerminatorKind::Goto { target: return_block });
         builder.cfg.terminate(return_block, source_info,
                               TerminatorKind::Return);
+        // Attribute any unreachable codepaths to the function's closing brace
+        if let Some(unreachable_block) = builder.cached_unreachable_block {
+            builder.cfg.terminate(unreachable_block, source_info,
+                                  TerminatorKind::Unreachable);
+        }
         return_block.unit()
     }));
     assert_eq!(block, builder.return_block());
@@ -502,7 +509,8 @@ impl<'a, 'gcx, 'tcx> Builder<'a, 'gcx, 'tcx> {
             var_indices: NodeMap(),
             unit_temp: None,
             cached_resume_block: None,
-            cached_return_block: None
+            cached_return_block: None,
+            cached_unreachable_block: None,
         };
 
         assert_eq!(builder.cfg.start_new_block(), START_BLOCK);
@@ -631,6 +639,17 @@ impl<'a, 'gcx, 'tcx> Builder<'a, 'gcx, 'tcx> {
             }
         }
     }
+
+    fn unreachable_block(&mut self) -> BasicBlock {
+        match self.cached_unreachable_block {
+            Some(ub) => ub,
+            None => {
+                let ub = self.cfg.start_new_block();
+                self.cached_unreachable_block = Some(ub);
+                ub
+            }
+        }
+    }
 }
 
 ///////////////////////////////////////////////////////////////////////////
diff --git a/src/test/codegen/match-optimizes-away.rs b/src/test/codegen/match-optimizes-away.rs
new file mode 100644
index 00000000000..c0f2f64f82c
--- /dev/null
+++ b/src/test/codegen/match-optimizes-away.rs
@@ -0,0 +1,44 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+//
+// no-system-llvm
+// compile-flags: -O
+#![crate_type="lib"]
+
+pub enum Three { First, Second, Third }
+use Three::*;
+
+pub enum Four { First, Second, Third, Fourth }
+use Four::*;
+
+#[no_mangle]
+pub fn three_valued(x: Three) -> Three {
+    // CHECK-LABEL: @three_valued
+    // CHECK-NEXT: {{^.*:$}}
+    // CHECK-NEXT: ret i8 %0
+    match x {
+        First => First,
+        Second => Second,
+        Third => Third,
+    }
+}
+
+#[no_mangle]
+pub fn four_valued(x: Four) -> Four {
+    // CHECK-LABEL: @four_valued
+    // CHECK-NEXT: {{^.*:$}}
+    // CHECK-NEXT: ret i8 %0
+    match x {
+        First => First,
+        Second => Second,
+        Third => Third,
+        Fourth => Fourth,
+    }
+}
diff --git a/src/test/codegen/match.rs b/src/test/codegen/match.rs
index aa100da6013..660b6346c57 100644
--- a/src/test/codegen/match.rs
+++ b/src/test/codegen/match.rs
@@ -21,12 +21,15 @@ pub enum E {
 #[no_mangle]
 pub fn exhaustive_match(e: E) {
 // CHECK: switch{{.*}}, label %[[OTHERWISE:[a-zA-Z0-9_]+]] [
-// CHECK-NEXT: i[[TY:[0-9]+]] [[DISCR:[0-9]+]], label %[[TRUE:[a-zA-Z0-9_]+]]
+// CHECK-NEXT: i[[TY:[0-9]+]] [[DISCR:[0-9]+]], label %[[A:[a-zA-Z0-9_]+]]
+// CHECK-NEXT: i[[TY:[0-9]+]] [[DISCR:[0-9]+]], label %[[B:[a-zA-Z0-9_]+]]
 // CHECK-NEXT: ]
-// CHECK: [[TRUE]]:
+// CHECK: [[A]]:
 // CHECK-NEXT: br label %[[EXIT:[a-zA-Z0-9_]+]]
-// CHECK: [[OTHERWISE]]:
+// CHECK: [[B]]:
 // CHECK-NEXT: br label %[[EXIT:[a-zA-Z0-9_]+]]
+// CHECK: [[OTHERWISE]]:
+// CHECK-NEXT: unreachable
     match e {
         E::A => (),
         E::B => (),
diff --git a/src/test/mir-opt/match_false_edges.rs b/src/test/mir-opt/match_false_edges.rs
index 02e9d39668d..318db7a9e3e 100644
--- a/src/test/mir-opt/match_false_edges.rs
+++ b/src/test/mir-opt/match_false_edges.rs
@@ -54,24 +54,24 @@ fn main() {
 //      ...
 //      _2 = std::option::Option<i32>::Some(const 42i32,);
 //      _5 = discriminant(_2);
-//      switchInt(_5) -> [0isize: bb5, otherwise: bb3];
+//      switchInt(_5) -> [0isize: bb5, 1isize: bb3, otherwise: bb7];
 //  }
 //  bb1: { // arm1
 //      StorageLive(_7);
 //      _7 = _3;
 //      _1 = (const 1i32, _7);
 //      StorageDead(_7);
-//      goto -> bb11;
+//      goto -> bb12;
 //  }
 //  bb2: { // binding3(empty) and arm3
 //      _1 = (const 3i32, const 3i32);
-//      goto -> bb11;
+//      goto -> bb12;
 //  }
 //  bb3: {
-//      falseEdges -> [real: bb7, imaginary: bb4]; //pre_binding1
+//      falseEdges -> [real: bb8, imaginary: bb4]; //pre_binding1
 //  }
 //  bb4: {
-//      falseEdges -> [real: bb10, imaginary: bb5]; //pre_binding2
+//      falseEdges -> [real: bb11, imaginary: bb5]; //pre_binding2
 //  }
 //  bb5: {
 //      falseEdges -> [real: bb2, imaginary: bb6]; //pre_binding3
@@ -79,28 +79,31 @@ fn main() {
 //  bb6: {
 //      unreachable;
 //  }
-//  bb7: { // binding1 and guard
+//  bb7: {
+//      unreachable;
+//  }
+//  bb8: { // binding1 and guard
 //      StorageLive(_3);
 //      _3 = ((_2 as Some).0: i32);
 //      StorageLive(_6);
-//      _6 = const guard() -> bb8;
+//      _6 = const guard() -> bb9;
 //  }
-//  bb8: { // end of guard
-//      switchInt(_6) -> [0u8: bb9, otherwise: bb1];
+//  bb9: { // end of guard
+//      switchInt(_6) -> [0u8: bb10, otherwise: bb1];
 //  }
-//  bb9: { // to pre_binding2
+//  bb10: { // to pre_binding2
 //      falseEdges -> [real: bb4, imaginary: bb4];
 //  }
-//  bb10: { // bindingNoLandingPads.before.mir2 and arm2
+//  bb11: { // bindingNoLandingPads.before.mir2 and arm2
 //      StorageLive(_4);
 //      _4 = ((_2 as Some).0: i32);
 //      StorageLive(_8);
 //      _8 = _4;
 //      _1 = (const 2i32, _8);
 //      StorageDead(_8);
-//      goto -> bb11;
+//      goto -> bb12;
 //  }
-//  bb11: {
+//  bb12: {
 //      ...
 //      return;
 //  }
@@ -111,53 +114,56 @@ fn main() {
 //      ...
 //      _2 = std::option::Option<i32>::Some(const 42i32,);
 //      _5 = discriminant(_2);
-//      switchInt(_5) -> [0isize: bb4, otherwise: bb3];
+//      switchInt(_5) -> [0isize: bb4, 1isize: bb3, otherwise: bb7];
 //  }
 //  bb1: { // arm1
 //      StorageLive(_7);
 //      _7 = _3;
 //      _1 = (const 1i32, _7);
 //      StorageDead(_7);
-//      goto -> bb11;
+//      goto -> bb12;
 //  }
 //  bb2: { // binding3(empty) and arm3
 //      _1 = (const 3i32, const 3i32);
-//      goto -> bb11;
+//      goto -> bb12;
 //  }
 //  bb3: {
-//      falseEdges -> [real: bb7, imaginary: bb4]; //pre_binding1
+//      falseEdges -> [real: bb8, imaginary: bb4]; //pre_binding1
 //  }
 //  bb4: {
 //      falseEdges -> [real: bb2, imaginary: bb5]; //pre_binding2
 //  }
 //  bb5: {
-//      falseEdges -> [real: bb10, imaginary: bb6]; //pre_binding3
+//      falseEdges -> [real: bb11, imaginary: bb6]; //pre_binding3
 //  }
 //  bb6: {
 //      unreachable;
 //  }
-//  bb7: { // binding1 and guard
+//  bb7: {
+//      unreachable;
+//  }
+//  bb8: { // binding1 and guard
 //      StorageLive(_3);
 //      _3 = ((_2 as Some).0: i32);
 //      StorageLive(_6);
-//      _6 = const guard() -> bb8;
+//      _6 = const guard() -> bb9;
 //  }
-//  bb8: { // end of guard
-//      switchInt(_6) -> [0u8: bb9, otherwise: bb1];
+//  bb9: { // end of guard
+//      switchInt(_6) -> [0u8: bb10, otherwise: bb1];
 //  }
-//  bb9: { // to pre_binding2
+//  bb10: { // to pre_binding2
 //      falseEdges -> [real: bb5, imaginary: bb4];
 //  }
-//  bb10: { // binding2 and arm2
+//  bb11: { // binding2 and arm2
 //      StorageLive(_4);
 //      _4 = ((_2 as Some).0: i32);
 //      StorageLive(_8);
 //      _8 = _4;
 //      _1 = (const 2i32, _8);
 //      StorageDead(_8);
-//      goto -> bb11;
+//      goto -> bb12;
 //  }
-//  bb11: {
+//  bb12: {
 //      ...
 //      return;
 //  }