Auto merge of #41148 - arielb1:dead-unwind, r=nagisa

borrowck::mir::dataflow: ignore unwind edges of empty drops

This avoids creating drop flags in many unnecessary situations.

Fixes #41110.

r? @nagisa

beta-nominating because regression. However, that is merely a small perf regression and codegen changes are always risky, so we might let this slide for 1.17.

4 files changed, 174 insertions, 38 deletions

diff --git a/src/librustc_borrowck/borrowck/mir/dataflow/mod.rs b/src/librustc_borrowck/borrowck/mir/dataflow/mod.rs
index 8b246105f61..f0f082a2561 100644
--- a/src/librustc_borrowck/borrowck/mir/dataflow/mod.rs
+++ b/src/librustc_borrowck/borrowck/mir/dataflow/mod.rs
@@ -181,6 +181,7 @@ pub struct DataflowAnalysis<'a, 'tcx: 'a, O>
     where O: BitDenotation
 {
     flow_state: DataflowState<O>,
+    dead_unwinds: &'a IdxSet<mir::BasicBlock>,
     mir: &'a Mir<'tcx>,
 }
 
@@ -377,6 +378,7 @@ impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D>
 {
     pub fn new(_tcx: TyCtxt<'a, 'tcx, 'tcx>,
                mir: &'a Mir<'tcx>,
+               dead_unwinds: &'a IdxSet<mir::BasicBlock>,
                denotation: D) -> Self {
         let bits_per_block = denotation.bits_per_block();
         let usize_bits = mem::size_of::<usize>() * 8;
@@ -397,6 +399,7 @@ impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D>
 
         DataflowAnalysis {
             mir: mir,
+            dead_unwinds: dead_unwinds,
             flow_state: DataflowState {
                 sets: AllSets {
                     bits_per_block: bits_per_block,
@@ -452,7 +455,9 @@ impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D>
                 ref target, value: _, location: _, unwind: Some(ref unwind)
             } => {
                 self.propagate_bits_into_entry_set_for(in_out, changed, target);
-                self.propagate_bits_into_entry_set_for(in_out, changed, unwind);
+                if !self.dead_unwinds.contains(&bb) {
+                    self.propagate_bits_into_entry_set_for(in_out, changed, unwind);
+                }
             }
             mir::TerminatorKind::SwitchInt { ref targets, .. } => {
                 for target in targets {
@@ -461,7 +466,9 @@ impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D>
             }
             mir::TerminatorKind::Call { ref cleanup, ref destination, func: _, args: _ } => {
                 if let Some(ref unwind) = *cleanup {
-                    self.propagate_bits_into_entry_set_for(in_out, changed, unwind);
+                    if !self.dead_unwinds.contains(&bb) {
+                        self.propagate_bits_into_entry_set_for(in_out, changed, unwind);
+                    }
                 }
                 if let Some((ref dest_lval, ref dest_bb)) = *destination {
                     // N.B.: This must be done *last*, after all other
diff --git a/src/librustc_borrowck/borrowck/mir/elaborate_drops.rs b/src/librustc_borrowck/borrowck/mir/elaborate_drops.rs
index 88ec86cc95d..713e6566662 100644
--- a/src/librustc_borrowck/borrowck/mir/elaborate_drops.rs
+++ b/src/librustc_borrowck/borrowck/mir/elaborate_drops.rs
@@ -11,8 +11,8 @@
 use super::gather_moves::{HasMoveData, MoveData, MovePathIndex, LookupResult};
 use super::dataflow::{MaybeInitializedLvals, MaybeUninitializedLvals};
 use super::dataflow::{DataflowResults};
-use super::{drop_flag_effects_for_location, on_all_children_bits};
-use super::on_lookup_result_bits;
+use super::{on_all_children_bits, on_all_drop_children_bits};
+use super::{drop_flag_effects_for_location, on_lookup_result_bits};
 use super::MoveDataParamEnv;
 use rustc::ty::{self, TyCtxt};
 use rustc::mir::*;
@@ -24,6 +24,7 @@ use rustc_data_structures::indexed_vec::Idx;
 use rustc_mir::util::patch::MirPatch;
 use rustc_mir::util::elaborate_drops::{DropFlagState, elaborate_drop};
 use rustc_mir::util::elaborate_drops::{DropElaborator, DropStyle, DropFlagMode};
+use syntax::ast;
 use syntax_pos::Span;
 
 use std::fmt;
@@ -49,12 +50,13 @@ impl<'tcx> MirPass<'tcx> for ElaborateDrops {
                 move_data: move_data,
                 param_env: param_env
             };
+            let dead_unwinds = find_dead_unwinds(tcx, mir, id, &env);
             let flow_inits =
-                super::do_dataflow(tcx, mir, id, &[],
+                super::do_dataflow(tcx, mir, id, &[], &dead_unwinds,
                                    MaybeInitializedLvals::new(tcx, mir, &env),
                                    |bd, p| &bd.move_data().move_paths[p]);
             let flow_uninits =
-                super::do_dataflow(tcx, mir, id, &[],
+                super::do_dataflow(tcx, mir, id, &[], &dead_unwinds,
                                    MaybeUninitializedLvals::new(tcx, mir, &env),
                                    |bd, p| &bd.move_data().move_paths[p]);
 
@@ -74,6 +76,67 @@ impl<'tcx> MirPass<'tcx> for ElaborateDrops {
 
 impl Pass for ElaborateDrops {}
 
+/// Return the set of basic blocks whose unwind edges are known
+/// to not be reachable, because they are `drop` terminators
+/// that can't drop anything.
+fn find_dead_unwinds<'a, 'tcx>(
+    tcx: TyCtxt<'a, 'tcx, 'tcx>,
+    mir: &Mir<'tcx>,
+    id: ast::NodeId,
+    env: &MoveDataParamEnv<'tcx>)
+    -> IdxSetBuf<BasicBlock>
+{
+    debug!("find_dead_unwinds({:?})", mir.span);
+    // We only need to do this pass once, because unwind edges can only
+    // reach cleanup blocks, which can't have unwind edges themselves.
+    let mut dead_unwinds = IdxSetBuf::new_empty(mir.basic_blocks().len());
+    let flow_inits =
+        super::do_dataflow(tcx, mir, id, &[], &dead_unwinds,
+                           MaybeInitializedLvals::new(tcx, mir, &env),
+                           |bd, p| &bd.move_data().move_paths[p]);
+    for (bb, bb_data) in mir.basic_blocks().iter_enumerated() {
+        match bb_data.terminator().kind {
+            TerminatorKind::Drop { ref location, unwind: Some(_), .. } |
+            TerminatorKind::DropAndReplace { ref location, unwind: Some(_), .. } => {
+                let mut init_data = InitializationData {
+                    live: flow_inits.sets().on_entry_set_for(bb.index()).to_owned(),
+                    dead: IdxSetBuf::new_empty(env.move_data.move_paths.len()),
+                };
+                debug!("find_dead_unwinds @ {:?}: {:?}; init_data={:?}",
+                       bb, bb_data, init_data.live);
+                for stmt in 0..bb_data.statements.len() {
+                    let loc = Location { block: bb, statement_index: stmt };
+                    init_data.apply_location(tcx, mir, env, loc);
+                }
+
+                let path = match env.move_data.rev_lookup.find(location) {
+                    LookupResult::Exact(e) => e,
+                    LookupResult::Parent(..) => {
+                        debug!("find_dead_unwinds: has parent; skipping");
+                        continue
+                    }
+                };
+
+                debug!("find_dead_unwinds @ {:?}: path({:?})={:?}", bb, location, path);
+
+                let mut maybe_live = false;
+                on_all_drop_children_bits(tcx, mir, &env, path, |child| {
+                    let (child_maybe_live, _) = init_data.state(child);
+                    maybe_live |= child_maybe_live;
+                });
+
+                debug!("find_dead_unwinds @ {:?}: maybe_live={}", bb, maybe_live);
+                if !maybe_live {
+                    dead_unwinds.add(&bb);
+                }
+            }
+            _ => {}
+        }
+    }
+
+    dead_unwinds
+}
+
 struct InitializationData {
     live: IdxSetBuf<MovePathIndex>,
     dead: IdxSetBuf<MovePathIndex>
@@ -144,17 +207,14 @@ impl<'a, 'b, 'tcx> DropElaborator<'a, 'tcx> for Elaborator<'a, 'b, 'tcx> {
                 let mut some_live = false;
                 let mut some_dead = false;
                 let mut children_count = 0;
-                on_all_children_bits(
-                    self.tcx(), self.mir(), self.ctxt.move_data(),
-                    path, |child| {
-                        if self.ctxt.path_needs_drop(child) {
-                            let (live, dead) = self.init_data.state(child);
-                            debug!("elaborate_drop: state({:?}) = {:?}",
-                                   child, (live, dead));
-                            some_live |= live;
-                            some_dead |= dead;
-                            children_count += 1;
-                        }
+                on_all_drop_children_bits(
+                    self.tcx(), self.mir(), self.ctxt.env, path, |child| {
+                        let (live, dead) = self.init_data.state(child);
+                        debug!("elaborate_drop: state({:?}) = {:?}",
+                               child, (live, dead));
+                        some_live |= live;
+                        some_dead |= dead;
+                        children_count += 1;
                     });
                 ((some_live, some_dead), children_count != 1)
             }
@@ -276,15 +336,6 @@ impl<'b, 'tcx> ElaborateDropsCtxt<'b, 'tcx> {
         self.patch
     }
 
-    fn path_needs_drop(&self, path: MovePathIndex) -> bool
-    {
-        let lvalue = &self.move_data().move_paths[path].lvalue;
-        let ty = lvalue.ty(self.mir, self.tcx).to_ty(self.tcx);
-        debug!("path_needs_drop({:?}, {:?} : {:?})", path, lvalue, ty);
-
-        self.tcx.type_needs_drop_given_env(ty, self.param_env())
-    }
-
     fn collect_drop_flags(&mut self)
     {
         for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
@@ -318,14 +369,12 @@ impl<'b, 'tcx> ElaborateDropsCtxt<'b, 'tcx> {
                 }
             };
 
-            on_all_children_bits(self.tcx, self.mir, self.move_data(), path, |child| {
-                if self.path_needs_drop(child) {
-                    let (maybe_live, maybe_dead) = init_data.state(child);
-                    debug!("collect_drop_flags: collecting {:?} from {:?}@{:?} - {:?}",
-                           child, location, path, (maybe_live, maybe_dead));
-                    if maybe_live && maybe_dead {
-                        self.create_drop_flag(child)
-                    }
+            on_all_drop_children_bits(self.tcx, self.mir, self.env, path, |child| {
+                let (maybe_live, maybe_dead) = init_data.state(child);
+                debug!("collect_drop_flags: collecting {:?} from {:?}@{:?} - {:?}",
+                       child, location, path, (maybe_live, maybe_dead));
+                if maybe_live && maybe_dead {
+                    self.create_drop_flag(child)
                 }
             });
         }
diff --git a/src/librustc_borrowck/borrowck/mir/mod.rs b/src/librustc_borrowck/borrowck/mir/mod.rs
index 9237bb31f6b..dc01cbe5e76 100644
--- a/src/librustc_borrowck/borrowck/mir/mod.rs
+++ b/src/librustc_borrowck/borrowck/mir/mod.rs
@@ -17,6 +17,7 @@ use rustc::mir::{self, BasicBlock, BasicBlockData, Mir, Statement, Terminator, L
 use rustc::session::Session;
 use rustc::ty::{self, TyCtxt};
 use rustc_mir::util::elaborate_drops::DropFlagState;
+use rustc_data_structures::indexed_set::{IdxSet, IdxSetBuf};
 
 mod abs_domain;
 pub mod elaborate_drops;
@@ -64,14 +65,18 @@ pub fn borrowck_mir(bcx: &mut BorrowckCtxt,
     let param_env = ty::ParameterEnvironment::for_item(tcx, id);
     let move_data = MoveData::gather_moves(mir, tcx, &param_env);
     let mdpe = MoveDataParamEnv { move_data: move_data, param_env: param_env };
+    let dead_unwinds = IdxSetBuf::new_empty(mir.basic_blocks().len());
     let flow_inits =
-        do_dataflow(tcx, mir, id, attributes, MaybeInitializedLvals::new(tcx, mir, &mdpe),
+        do_dataflow(tcx, mir, id, attributes, &dead_unwinds,
+                    MaybeInitializedLvals::new(tcx, mir, &mdpe),
                     |bd, i| &bd.move_data().move_paths[i]);
     let flow_uninits =
-        do_dataflow(tcx, mir, id, attributes, MaybeUninitializedLvals::new(tcx, mir, &mdpe),
+        do_dataflow(tcx, mir, id, attributes, &dead_unwinds,
+                    MaybeUninitializedLvals::new(tcx, mir, &mdpe),
                     |bd, i| &bd.move_data().move_paths[i]);
     let flow_def_inits =
-        do_dataflow(tcx, mir, id, attributes, DefinitelyInitializedLvals::new(tcx, mir, &mdpe),
+        do_dataflow(tcx, mir, id, attributes, &dead_unwinds,
+                    DefinitelyInitializedLvals::new(tcx, mir, &mdpe),
                     |bd, i| &bd.move_data().move_paths[i]);
 
     if has_rustc_mir_with(attributes, "rustc_peek_maybe_init").is_some() {
@@ -108,6 +113,7 @@ fn do_dataflow<'a, 'tcx, BD, P>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                 mir: &Mir<'tcx>,
                                 node_id: ast::NodeId,
                                 attributes: &[ast::Attribute],
+                                dead_unwinds: &IdxSet<BasicBlock>,
                                 bd: BD,
                                 p: P)
                                 -> DataflowResults<BD>
@@ -137,7 +143,7 @@ fn do_dataflow<'a, 'tcx, BD, P>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         node_id: node_id,
         print_preflow_to: print_preflow_to,
         print_postflow_to: print_postflow_to,
-        flow_state: DataflowAnalysis::new(tcx, mir, bd),
+        flow_state: DataflowAnalysis::new(tcx, mir, dead_unwinds, bd),
     };
 
     mbcx.dataflow(p);
@@ -303,6 +309,27 @@ fn on_all_children_bits<'a, 'tcx, F>(
     on_all_children_bits(tcx, mir, move_data, move_path_index, &mut each_child);
 }
 
+fn on_all_drop_children_bits<'a, 'tcx, F>(
+    tcx: TyCtxt<'a, 'tcx, 'tcx>,
+    mir: &Mir<'tcx>,
+    ctxt: &MoveDataParamEnv<'tcx>,
+    path: MovePathIndex,
+    mut each_child: F)
+    where F: FnMut(MovePathIndex)
+{
+    on_all_children_bits(tcx, mir, &ctxt.move_data, path, |child| {
+        let lvalue = &ctxt.move_data.move_paths[path].lvalue;
+        let ty = lvalue.ty(mir, tcx).to_ty(tcx);
+        debug!("on_all_drop_children_bits({:?}, {:?} : {:?})", path, lvalue, ty);
+
+        if tcx.type_needs_drop_given_env(ty, &ctxt.param_env) {
+            each_child(child);
+        } else {
+            debug!("on_all_drop_children_bits - skipping")
+        }
+    })
+}
+
 fn drop_flag_effects_for_function_entry<'a, 'tcx, F>(
     tcx: TyCtxt<'a, 'tcx, 'tcx>,
     mir: &Mir<'tcx>,
diff --git a/src/test/mir-opt/issue-41110.rs b/src/test/mir-opt/issue-41110.rs
new file mode 100644
index 00000000000..fec635b3abf
--- /dev/null
+++ b/src/test/mir-opt/issue-41110.rs
@@ -0,0 +1,53 @@
+// 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.
+
+// check that we don't emit multiple drop flags when they are not needed.
+
+fn main() {
+    let x = S.other(S.id());
+}
+
+pub fn test() {
+    let u = S;
+    let mut v = S;
+    drop(v);
+    v = u;
+}
+
+struct S;
+impl Drop for S {
+    fn drop(&mut self) {
+    }
+}
+
+impl S {
+    fn id(self) -> Self { self }
+    fn other(self, s: Self) {}
+}
+
+// END RUST SOURCE
+// START rustc.node4.ElaborateDrops.after.mir
+//    let mut _2: S;
+//    let mut _3: ();
+//    let mut _4: S;
+//    let mut _5: S;
+//    let mut _6: bool;
+//
+//    bb0: {
+// END rustc.node4.ElaborateDrops.after.mir
+// START rustc.node13.ElaborateDrops.after.mir
+//    let mut _2: ();
+//    let mut _4: ();
+//    let mut _5: S;
+//    let mut _6: S;
+//    let mut _7: bool;
+//
+//    bb0: {
+// END rustc.node13.ElaborateDrops.after.mir