summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorbors <bors@rust-lang.org>2018-05-30 09:24:20 +0000
committerbors <bors@rust-lang.org>2018-05-30 09:24:20 +0000
commit20af72b943527d584df4b99e157262f9b297b3e4 (patch)
tree9fa410f7b57d6491ef63ec9d56f60f3698c6297d
parentAuto merge of #51017 - estebank:crate-name-in-path, r=michaelwoerister (diff)
parentfix off by one error (diff)
downloadgrust-20af72b943527d584df4b99e157262f9b297b3e4.tar.gz
grust-20af72b943527d584df4b99e157262f9b297b3e4.tar.bz2
grust-20af72b943527d584df4b99e157262f9b297b3e4.tar.xz
Auto merge of #51106 - davidtwco:issue-50934, r=nikomatsakis
Optimize the way that loans are killed in borrowck dataflow Fixes #50934. r? @nikomatsakis
-rw-r--r--src/librustc_mir/borrow_check/nll/region_infer/mod.rs2
-rw-r--r--src/librustc_mir/dataflow/impls/borrows.rs90
2 files changed, 78 insertions, 14 deletions
diff --git a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
index 5a1ab73b2b..dea2683789 100644
--- a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
@@ -352,7 +352,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
352 } 352 }
353 353
354 /// Returns access to the value of `r` for debugging purposes. 354 /// Returns access to the value of `r` for debugging purposes.
355 pub(super) fn region_value_str(&self, r: RegionVid) -> String { 355 crate fn region_value_str(&self, r: RegionVid) -> String {
356 let inferred_values = self.inferred_values 356 let inferred_values = self.inferred_values
357 .as_ref() 357 .as_ref()
358 .expect("region values not yet inferred"); 358 .expect("region values not yet inferred");
diff --git a/src/librustc_mir/dataflow/impls/borrows.rs b/src/librustc_mir/dataflow/impls/borrows.rs
index 78886baf51..a109389aa3 100644
--- a/src/librustc_mir/dataflow/impls/borrows.rs
+++ b/src/librustc_mir/dataflow/impls/borrows.rs
@@ -17,10 +17,11 @@ use rustc::hir::def_id::DefId;
17use rustc::middle::region; 17use rustc::middle::region;
18use rustc::mir::{self, Location, Place, Mir}; 18use rustc::mir::{self, Location, Place, Mir};
19use rustc::ty::TyCtxt; 19use rustc::ty::TyCtxt;
20use rustc::ty::RegionKind; 20use rustc::ty::{RegionKind, RegionVid};
21use rustc::ty::RegionKind::ReScope; 21use rustc::ty::RegionKind::ReScope;
22 22
23use rustc_data_structures::bitslice::BitwiseOperator; 23use rustc_data_structures::bitslice::BitwiseOperator;
24use rustc_data_structures::fx::{FxHashMap, FxHashSet};
24use rustc_data_structures::indexed_set::IdxSet; 25use rustc_data_structures::indexed_set::IdxSet;
25use rustc_data_structures::indexed_vec::IndexVec; 26use rustc_data_structures::indexed_vec::IndexVec;
26use rustc_data_structures::sync::Lrc; 27use rustc_data_structures::sync::Lrc;
@@ -46,9 +47,65 @@ pub struct Borrows<'a, 'gcx: 'tcx, 'tcx: 'a> {
46 root_scope: Option<region::Scope>, 47 root_scope: Option<region::Scope>,
47 48
48 borrow_set: Rc<BorrowSet<'tcx>>, 49 borrow_set: Rc<BorrowSet<'tcx>>,
50 borrows_out_of_scope_at_location: FxHashMap<Location, Vec<BorrowIndex>>,
49 51
50 /// NLL region inference context with which NLL queries should be resolved 52 /// NLL region inference context with which NLL queries should be resolved
51 nonlexical_regioncx: Rc<RegionInferenceContext<'tcx>>, 53 _nonlexical_regioncx: Rc<RegionInferenceContext<'tcx>>,
54}
55
56fn precompute_borrows_out_of_scope<'a, 'tcx>(
57 mir: &'a Mir<'tcx>,
58 regioncx: &Rc<RegionInferenceContext<'tcx>>,
59 borrows_out_of_scope_at_location: &mut FxHashMap<Location, Vec<BorrowIndex>>,
60 borrow_index: BorrowIndex,
61 borrow_region: RegionVid,
62 location: Location,
63) {
64 // Keep track of places we've locations to check and locations that we have checked.
65 let mut stack = vec![ location ];
66 let mut visited = FxHashSet();
67 visited.insert(location);
68
69 debug!(
70 "borrow {:?} has region {:?} with value {:?}",
71 borrow_index,
72 borrow_region,
73 regioncx.region_value_str(borrow_region),
74 );
75 debug!("borrow {:?} starts at {:?}", borrow_index, location);
76 while let Some(location) = stack.pop() {
77 // If region does not contain a point at the location, then add to list and skip
78 // successor locations.
79 if !regioncx.region_contains_point(borrow_region, location) {
80 debug!("borrow {:?} gets killed at {:?}", borrow_index, location);
81 borrows_out_of_scope_at_location
82 .entry(location)
83 .or_insert(vec![])
84 .push(borrow_index);
85 continue;
86 }
87
88 let bb_data = &mir[location.block];
89 // If this is the last statement in the block, then add the
90 // terminator successors next.
91 if location.statement_index == bb_data.statements.len() {
92 // Add successors to locations to visit, if not visited before.
93 if let Some(ref terminator) = bb_data.terminator {
94 for block in terminator.successors() {
95 let loc = block.start_location();
96 if visited.insert(loc) {
97 stack.push(loc);
98 }
99 }
100 }
101 } else {
102 // Visit next statement in block.
103 let loc = location.successor_within_block();
104 if visited.insert(loc) {
105 stack.push(loc);
106 }
107 }
108 }
52} 109}
53 110
54impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> { 111impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> {
@@ -65,18 +122,28 @@ impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> {
65 region::Scope::CallSite(tcx.hir.body(body_id).value.hir_id.local_id) 122 region::Scope::CallSite(tcx.hir.body(body_id).value.hir_id.local_id)
66 }); 123 });
67 124
125 let mut borrows_out_of_scope_at_location = FxHashMap();
126 for (borrow_index, borrow_data) in borrow_set.borrows.iter_enumerated() {
127 let borrow_region = borrow_data.region.to_region_vid();
128 let location = borrow_set.borrows[borrow_index].reserve_location;
129
130 precompute_borrows_out_of_scope(mir, &nonlexical_regioncx,
131 &mut borrows_out_of_scope_at_location,
132 borrow_index, borrow_region, location);
133 }
134
68 Borrows { 135 Borrows {
69 tcx: tcx, 136 tcx: tcx,
70 mir: mir, 137 mir: mir,
71 borrow_set: borrow_set.clone(), 138 borrow_set: borrow_set.clone(),
139 borrows_out_of_scope_at_location,
72 scope_tree, 140 scope_tree,
73 root_scope, 141 root_scope,
74 nonlexical_regioncx, 142 _nonlexical_regioncx: nonlexical_regioncx,
75 } 143 }
76 } 144 }
77 145
78 crate fn borrows(&self) -> &IndexVec<BorrowIndex, BorrowData<'tcx>> { &self.borrow_set.borrows } 146 crate fn borrows(&self) -> &IndexVec<BorrowIndex, BorrowData<'tcx>> { &self.borrow_set.borrows }
79
80 pub fn scope_tree(&self) -> &Lrc<region::ScopeTree> { &self.scope_tree } 147 pub fn scope_tree(&self) -> &Lrc<region::ScopeTree> { &self.scope_tree }
81 148
82 pub fn location(&self, idx: BorrowIndex) -> &Location { 149 pub fn location(&self, idx: BorrowIndex) -> &Location {
@@ -89,12 +156,10 @@ impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> {
89 fn kill_loans_out_of_scope_at_location(&self, 156 fn kill_loans_out_of_scope_at_location(&self,
90 sets: &mut BlockSets<BorrowIndex>, 157 sets: &mut BlockSets<BorrowIndex>,
91 location: Location) { 158 location: Location) {
92 let regioncx = &self.nonlexical_regioncx;
93
94 // NOTE: The state associated with a given `location` 159 // NOTE: The state associated with a given `location`
95 // reflects the dataflow on entry to the statement. If it 160 // reflects the dataflow on entry to the statement.
96 // does not contain `borrow_region`, then then that means 161 // Iterate over each of the borrows that we've precomputed
97 // that the statement at `location` kills the borrow. 162 // to have went out of scope at this location and kill them.
98 // 163 //
99 // We are careful always to call this function *before* we 164 // We are careful always to call this function *before* we
100 // set up the gen-bits for the statement or 165 // set up the gen-bits for the statement or
@@ -102,10 +167,9 @@ impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> {
102 // terminator *does* introduce a new loan of the same 167 // terminator *does* introduce a new loan of the same
103 // region, then setting that gen-bit will override any 168 // region, then setting that gen-bit will override any
104 // potential kill introduced here. 169 // potential kill introduced here.
105 for (borrow_index, borrow_data) in self.borrow_set.borrows.iter_enumerated() { 170 if let Some(indices) = self.borrows_out_of_scope_at_location.get(&location) {
106 let borrow_region = borrow_data.region.to_region_vid(); 171 for index in indices {
107 if !regioncx.region_contains_point(borrow_region, location) { 172 sets.kill(&index);
108 sets.kill(&borrow_index);
109 } 173 }
110 } 174 }
111 } 175 }