Auto merge of #30945 - nagisa:mir-optional-block-dest, r=nikomatsakis

As an attempt to make loop body destination be optional, author implemented a pretty self contained
change and deemed it to be (much) uglier than the alternative of just keeping the unit temporary.
Having the temporary created lazily also has a nice property of not figuring in the MIR of
functions which do not use loops of any sort.

r? @nikomatsakis

8 files changed, 163 insertions, 63 deletions

diff --git a/src/librustc_mir/build/expr/into.rs b/src/librustc_mir/build/expr/into.rs
index 63eb7607204..4261efe8215 100644
--- a/src/librustc_mir/build/expr/into.rs
+++ b/src/librustc_mir/build/expr/into.rs
@@ -146,11 +146,13 @@ impl<'a,'tcx> Builder<'a,'tcx> {
                 // start the loop
                 this.cfg.terminate(block, Terminator::Goto { target: loop_block });
 
-                this.in_loop_scope(loop_block, exit_block, |this| {
+                let might_break = this.in_loop_scope(loop_block, exit_block, move |this| {
                     // conduct the test, if necessary
                     let body_block;
-                    let opt_cond_expr = opt_cond_expr; // FIXME rustc bug
                     if let Some(cond_expr) = opt_cond_expr {
+                        // This loop has a condition, ergo its exit_block is reachable.
+                        this.find_loop_scope(expr_span, None).might_break = true;
+
                         let loop_block_end;
                         let cond = unpack!(loop_block_end = this.as_operand(loop_block, cond_expr));
                         body_block = this.cfg.start_new_block();
@@ -163,21 +165,22 @@ impl<'a,'tcx> Builder<'a,'tcx> {
                         body_block = loop_block;
                     }
 
-                    // execute the body, branching back to the test
-                    // We write body’s “return value” into the destination of loop. This is fine,
-                    // because:
-                    //
-                    // * In Rust both loop expression and its body are required to have `()`
-                    //   as the “return value”;
-                    // * The destination will be considered uninitialised (given it was
-                    //   uninitialised before the loop) during the first iteration, thus
-                    //   disallowing its use inside the body. Alternatively, if it was already
-                    //   initialised, the `destination` can only possibly have a value of `()`,
-                    //   therefore, “mutating” the destination during iteration is fine.
-                    let body_block_end = unpack!(this.into(destination, body_block, body));
+                    // The “return” value of the loop body must always be an unit, but we cannot
+                    // reuse that as a “return” value of the whole loop expressions, because some
+                    // loops are diverging (e.g. `loop {}`). Thus, we introduce a unit temporary as
+                    // the destination for the loop body and assign the loop’s own “return” value
+                    // immediately after the iteration is finished.
+                    let tmp = this.get_unit_temp();
+                    // Execute the body, branching back to the test.
+                    let body_block_end = unpack!(this.into(&tmp, body_block, body));
                     this.cfg.terminate(body_block_end, Terminator::Goto { target: loop_block });
-                    exit_block.unit()
-                })
+                });
+                // If the loop may reach its exit_block, we assign an empty tuple to the
+                // destination to keep the MIR well-formed.
+                if might_break {
+                    this.cfg.push_assign_unit(exit_block, expr_span, destination);
+                }
+                exit_block.unit()
             }
             ExprKind::Assign { lhs, rhs } => {
                 // Note: we evaluate assignments right-to-left. This
@@ -217,7 +220,10 @@ impl<'a,'tcx> Builder<'a,'tcx> {
                                        |loop_scope| loop_scope.continue_block)
             }
             ExprKind::Break { label } => {
-                this.break_or_continue(expr_span, label, block, |loop_scope| loop_scope.break_block)
+                this.break_or_continue(expr_span, label, block, |loop_scope| {
+                    loop_scope.might_break = true;
+                    loop_scope.break_block
+                })
             }
             ExprKind::Return { value } => {
                 block = match value {
@@ -303,11 +309,13 @@ impl<'a,'tcx> Builder<'a,'tcx> {
                             block: BasicBlock,
                             exit_selector: F)
                             -> BlockAnd<()>
-        where F: FnOnce(&LoopScope) -> BasicBlock
+        where F: FnOnce(&mut LoopScope) -> BasicBlock
     {
-        let loop_scope = self.find_loop_scope(span, label);
-        let exit_block = exit_selector(&loop_scope);
-        self.exit_scope(span, loop_scope.extent, block, exit_block);
+        let (exit_block, extent) = {
+            let loop_scope = self.find_loop_scope(span, label);
+            (exit_selector(loop_scope), loop_scope.extent)
+        };
+        self.exit_scope(span, extent, block, exit_block);
         self.cfg.start_new_block().unit()
     }
 }
diff --git a/src/librustc_mir/build/mod.rs b/src/librustc_mir/build/mod.rs
index d217eb06647..a7459d62368 100644
--- a/src/librustc_mir/build/mod.rs
+++ b/src/librustc_mir/build/mod.rs
@@ -26,6 +26,7 @@ pub struct Builder<'a, 'tcx: 'a> {
     var_decls: Vec<VarDecl<'tcx>>,
     var_indices: FnvHashMap<ast::NodeId, u32>,
     temp_decls: Vec<TempDecl<'tcx>>,
+    unit_temp: Option<Lvalue<'tcx>>,
 }
 
 struct CFG<'tcx> {
@@ -96,6 +97,7 @@ pub fn construct<'a,'tcx>(hir: Cx<'a,'tcx>,
         temp_decls: vec![],
         var_decls: vec![],
         var_indices: FnvHashMap(),
+        unit_temp: None
     };
 
     assert_eq!(builder.cfg.start_new_block(), START_BLOCK);
@@ -156,6 +158,18 @@ impl<'a,'tcx> Builder<'a,'tcx> {
             block.and(arg_decls)
         })
     }
+
+    fn get_unit_temp(&mut self) -> Lvalue<'tcx> {
+        match self.unit_temp {
+            Some(ref tmp) => tmp.clone(),
+            None => {
+                let ty = self.hir.unit_ty();
+                let tmp = self.temp(ty);
+                self.unit_temp = Some(tmp.clone());
+                tmp
+            }
+        }
+    }
 }
 
 ///////////////////////////////////////////////////////////////////////////
diff --git a/src/librustc_mir/build/scope.rs b/src/librustc_mir/build/scope.rs
index 90d6a90682f..dae525c84d0 100644
--- a/src/librustc_mir/build/scope.rs
+++ b/src/librustc_mir/build/scope.rs
@@ -103,31 +103,41 @@ pub struct Scope<'tcx> {
 
 #[derive(Clone, Debug)]
 pub struct LoopScope {
-    pub extent: CodeExtent, // extent of the loop
-    pub continue_block: BasicBlock, // where to go on a `loop`
+    /// Extent of the loop
+    pub extent: CodeExtent,
+    /// Where the body of the loop begins
+    pub continue_block: BasicBlock,
+    /// Block to branch into when the loop terminates (either by being `break`-en out from, or by
+    /// having its condition to become false)
     pub break_block: BasicBlock, // where to go on a `break
+    /// Indicates the reachability of the break_block for this loop
+    pub might_break: bool
 }
 
 impl<'a,'tcx> Builder<'a,'tcx> {
     /// Start a loop scope, which tracks where `continue` and `break`
     /// should branch to. See module comment for more details.
-    pub fn in_loop_scope<F, R>(&mut self,
+    ///
+    /// Returns the might_break attribute of the LoopScope used.
+    pub fn in_loop_scope<F>(&mut self,
                                loop_block: BasicBlock,
                                break_block: BasicBlock,
                                f: F)
-                               -> BlockAnd<R>
-        where F: FnOnce(&mut Builder<'a, 'tcx>) -> BlockAnd<R>
+                               -> bool
+        where F: FnOnce(&mut Builder<'a, 'tcx>)
     {
         let extent = self.extent_of_innermost_scope();
         let loop_scope = LoopScope {
             extent: extent.clone(),
             continue_block: loop_block,
             break_block: break_block,
+            might_break: false
         };
         self.loop_scopes.push(loop_scope);
-        let r = f(self);
-        assert!(self.loop_scopes.pop().unwrap().extent == extent);
-        r
+        f(self);
+        let loop_scope = self.loop_scopes.pop().unwrap();
+        assert!(loop_scope.extent == extent);
+        loop_scope.might_break
     }
 
     /// Convenience wrapper that pushes a scope and then executes `f`
@@ -181,28 +191,21 @@ impl<'a,'tcx> Builder<'a,'tcx> {
     pub fn find_loop_scope(&mut self,
                            span: Span,
                            label: Option<CodeExtent>)
-                           -> LoopScope {
-        let loop_scope =
-            match label {
-                None => {
-                    // no label? return the innermost loop scope
-                    self.loop_scopes.iter()
-                                    .rev()
-                                    .next()
-                }
-                Some(label) => {
-                    // otherwise, find the loop-scope with the correct id
-                    self.loop_scopes.iter()
-                                    .rev()
-                                    .filter(|loop_scope| loop_scope.extent == label)
-                                    .next()
-                }
-            };
-
-        match loop_scope {
-            Some(loop_scope) => loop_scope.clone(),
-            None => self.hir.span_bug(span, "no enclosing loop scope found?"),
-        }
+                           -> &mut LoopScope {
+        let Builder { ref mut loop_scopes, ref mut hir, .. } = *self;
+        match label {
+            None => {
+                // no label? return the innermost loop scope
+                loop_scopes.iter_mut().rev().next()
+            }
+            Some(label) => {
+                // otherwise, find the loop-scope with the correct id
+                loop_scopes.iter_mut()
+                           .rev()
+                           .filter(|loop_scope| loop_scope.extent == label)
+                           .next()
+            }
+        }.unwrap_or_else(|| hir.span_bug(span, "no enclosing loop scope found?"))
     }
 
     /// Branch out of `block` to `target`, exiting all scopes up to
@@ -214,20 +217,19 @@ impl<'a,'tcx> Builder<'a,'tcx> {
                       extent: CodeExtent,
                       block: BasicBlock,
                       target: BasicBlock) {
-        let popped_scopes =
-            match self.scopes.iter().rev().position(|scope| scope.extent == extent) {
-                Some(p) => p + 1,
-                None => self.hir.span_bug(span, &format!("extent {:?} does not enclose",
-                                                              extent)),
-            };
-
-        for scope in self.scopes.iter_mut().rev().take(popped_scopes) {
+        let Builder { ref mut scopes, ref mut cfg, ref mut hir, .. } = *self;
+
+        let scope_count = 1 + scopes.iter().rev().position(|scope| scope.extent == extent)
+                                                 .unwrap_or_else(||{
+            hir.span_bug(span, &format!("extent {:?} does not enclose", extent))
+        });
+
+        for scope in scopes.iter_mut().rev().take(scope_count) {
             for &(kind, drop_span, ref lvalue) in &scope.drops {
-                self.cfg.push_drop(block, drop_span, kind, lvalue);
+                cfg.push_drop(block, drop_span, kind, lvalue);
             }
         }
-
-        self.cfg.terminate(block, Terminator::Goto { target: target });
+        cfg.terminate(block, Terminator::Goto { target: target });
     }
 
     /// Creates a path that performs all required cleanup for unwinding.
diff --git a/src/librustc_mir/hair/cx/mod.rs b/src/librustc_mir/hair/cx/mod.rs
index b49dc6d8962..7019b40bb25 100644
--- a/src/librustc_mir/hair/cx/mod.rs
+++ b/src/librustc_mir/hair/cx/mod.rs
@@ -58,6 +58,10 @@ impl<'a,'tcx:'a> Cx<'a, 'tcx> {
         self.tcx.types.bool
     }
 
+    pub fn unit_ty(&mut self) -> Ty<'tcx> {
+        self.tcx.mk_nil()
+    }
+
     pub fn str_literal(&mut self, value: token::InternedString) -> Literal<'tcx> {
         Literal::Value { value: ConstVal::Str(value) }
     }
diff --git a/src/test/compile-fail/loop-does-not-diverge.rs b/src/test/compile-fail/loop-does-not-diverge.rs
index cd320ba148a..451b30629b6 100644
--- a/src/test/compile-fail/loop-does-not-diverge.rs
+++ b/src/test/compile-fail/loop-does-not-diverge.rs
@@ -18,5 +18,4 @@ fn forever() -> ! {
 }
 
 fn main() {
-  if 1 == 2 { forever(); }
 }
diff --git a/src/test/compile-fail/loop-proper-liveness.rs b/src/test/compile-fail/loop-proper-liveness.rs
new file mode 100644
index 00000000000..e411313c273
--- /dev/null
+++ b/src/test/compile-fail/loop-proper-liveness.rs
@@ -0,0 +1,42 @@
+// Copyright 2015 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.
+
+fn test1() {
+    // In this test the outer 'a loop may terminate without `x` getting initialised. Although the
+    // `x = loop { ... }` statement is reached, the value itself ends up never being computed and
+    // thus leaving `x` uninit.
+    let x: i32;
+    'a: loop {
+        x = loop { break 'a };
+    }
+    println!("{:?}", x); //~ ERROR use of possibly uninitialized variable
+}
+
+// test2 and test3 should not fail.
+fn test2() {
+    // In this test the `'a` loop will never terminate thus making the use of `x` unreachable.
+    let x: i32;
+    'a: loop {
+        x = loop { continue 'a };
+    }
+    println!("{:?}", x);
+}
+
+fn test3() {
+    let x: i32;
+    // Similarly, the use of variable `x` is unreachable.
+    'a: loop {
+        x = loop { return };
+    }
+    println!("{:?}", x);
+}
+
+fn main() {
+}
diff --git a/src/test/compile-fail/loop-properly-diverging-2.rs b/src/test/compile-fail/loop-properly-diverging-2.rs
new file mode 100644
index 00000000000..c22091ce63c
--- /dev/null
+++ b/src/test/compile-fail/loop-properly-diverging-2.rs
@@ -0,0 +1,16 @@
+// Copyright 2015 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.
+
+fn forever2() -> i32 {
+  let x: i32 = loop { break }; //~ ERROR mismatched types
+  x
+}
+
+fn main() {}
diff --git a/src/test/compile-fail/loop-properly-diverging.rs b/src/test/compile-fail/loop-properly-diverging.rs
new file mode 100644
index 00000000000..01dfbcc1b9e
--- /dev/null
+++ b/src/test/compile-fail/loop-properly-diverging.rs
@@ -0,0 +1,15 @@
+// Copyright 2015 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.
+
+fn forever2() -> ! { //~ ERROR computation may converge in a function marked as diverging
+  loop { break }
+}
+
+fn main() {}