summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Wood <david@davidtw.co>2018-05-27 11:15:52 +0100
committerDavid Wood <david@davidtw.co>2018-05-27 11:15:52 +0100
commitbbcace5080a73ea36417b1d4f6b846a2a01f9202 (patch)
treea5cccc25e45f35b579528d935b59e3abaca69799
parentAuto merge of #51090 - kennytm:tidy-check-missing-tracking-issue, r=alexcrichton (diff)
downloadgrust-bbcace5080a73ea36417b1d4f6b846a2a01f9202.tar.gz
grust-bbcace5080a73ea36417b1d4f6b846a2a01f9202.tar.bz2
grust-bbcace5080a73ea36417b1d4f6b846a2a01f9202.tar.xz
Use precomputed DFS of borrows that out of scope at a location.
-rw-r--r--src/librustc_mir/dataflow/impls/borrows.rs130
1 files changed, 116 insertions, 14 deletions
diff --git a/src/librustc_mir/dataflow/impls/borrows.rs b/src/librustc_mir/dataflow/impls/borrows.rs
index 04c62854c5..7018ab345d 100644
--- a/src/librustc_mir/dataflow/impls/borrows.rs
+++ b/src/librustc_mir/dataflow/impls/borrows.rs
@@ -15,12 +15,13 @@ use rustc;
15use rustc::hir; 15use rustc::hir;
16use rustc::hir::def_id::DefId; 16use 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, TerminatorKind};
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;
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,103 @@ 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 // Start by dealing with the current location.
65 if !regioncx.region_contains_point(borrow_region, location) {
66 borrows_out_of_scope_at_location
67 .entry(location.clone())
68 .and_modify(|m| m.push(borrow_index))
69 .or_insert(vec![ borrow_index ]);
70 }
71
72 let bb_data = &mir[location.block];
73 // If we are on the last statement, then check the terminator
74 // to determine which location to proceed to.
75 if location.statement_index == bb_data.statements.len() - 1 {
76 if let Some(ref terminator) = bb_data.terminator {
77 match terminator.kind {
78 TerminatorKind::Goto { target } |
79 TerminatorKind::FalseEdges { real_target: target, .. } |
80 TerminatorKind::FalseUnwind { real_target: target, .. } => {
81 precompute_borrows_out_of_scope(
82 mir, regioncx, borrows_out_of_scope_at_location,
83 borrow_index, borrow_region, target.start_location()
84 );
85 },
86 TerminatorKind::SwitchInt { ref targets, .. } => {
87 for block in targets {
88 precompute_borrows_out_of_scope(
89 mir, regioncx, borrows_out_of_scope_at_location,
90 borrow_index, borrow_region, block.start_location()
91 );
92 }
93 },
94 TerminatorKind::Drop { target, unwind, .. } |
95 TerminatorKind::DropAndReplace { target, unwind, .. } => {
96 precompute_borrows_out_of_scope(
97 mir, regioncx, borrows_out_of_scope_at_location,
98 borrow_index, borrow_region, target.start_location()
99 );
100
101 if let Some(unwind_block) = unwind {
102 precompute_borrows_out_of_scope(
103 mir, regioncx, borrows_out_of_scope_at_location,
104 borrow_index, borrow_region, unwind_block.start_location()
105 );
106 }
107 },
108 TerminatorKind::Call { ref destination, cleanup, .. } => {
109 if let Some((_, block)) = destination {
110 precompute_borrows_out_of_scope(
111 mir, regioncx, borrows_out_of_scope_at_location,
112 borrow_index, borrow_region, block.start_location()
113 );
114 }
115
116 if let Some(block) = cleanup {
117 precompute_borrows_out_of_scope(
118 mir, regioncx, borrows_out_of_scope_at_location,
119 borrow_index, borrow_region, block.start_location()
120 );
121 }
122 },
123 TerminatorKind::Assert { target, cleanup, .. } |
124 TerminatorKind::Yield { resume: target, drop: cleanup, .. } => {
125 precompute_borrows_out_of_scope(
126 mir, regioncx, borrows_out_of_scope_at_location,
127 borrow_index, borrow_region, target.start_location()
128 );
129
130 if let Some(block) = cleanup {
131 precompute_borrows_out_of_scope(
132 mir, regioncx, borrows_out_of_scope_at_location,
133 borrow_index, borrow_region, block.start_location()
134 );
135 }
136 },
137 _ => {},
138 };
139 };
140 // If we're not on the last statement, then go to the next
141 // statement in this block.
142 } else {
143 precompute_borrows_out_of_scope(mir, regioncx, borrows_out_of_scope_at_location,
144 borrow_index, borrow_region,
145 location.successor_within_block());
146 }
52} 147}
53 148
54impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> { 149impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> {
@@ -65,18 +160,28 @@ impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> {
65 region::Scope::CallSite(tcx.hir.body(body_id).value.hir_id.local_id) 160 region::Scope::CallSite(tcx.hir.body(body_id).value.hir_id.local_id)
66 }); 161 });
67 162
163 let mut borrows_out_of_scope_at_location = FxHashMap();
164 for (borrow_index, borrow_data) in borrow_set.borrows.iter_enumerated() {
165 let borrow_region = borrow_data.region.to_region_vid();
166 let location = borrow_set.borrows[borrow_index].reserve_location;
167
168 precompute_borrows_out_of_scope(mir, &nonlexical_regioncx,
169 &mut borrows_out_of_scope_at_location,
170 borrow_index, borrow_region, location);
171 }
172
68 Borrows { 173 Borrows {
69 tcx: tcx, 174 tcx: tcx,
70 mir: mir, 175 mir: mir,
71 borrow_set: borrow_set.clone(), 176 borrow_set: borrow_set.clone(),
177 borrows_out_of_scope_at_location,
72 scope_tree, 178 scope_tree,
73 root_scope, 179 root_scope,
74 nonlexical_regioncx, 180 _nonlexical_regioncx: nonlexical_regioncx,
75 } 181 }
76 } 182 }
77 183
78 crate fn borrows(&self) -> &IndexVec<BorrowIndex, BorrowData<'tcx>> { &self.borrow_set.borrows } 184 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 } 185 pub fn scope_tree(&self) -> &Lrc<region::ScopeTree> { &self.scope_tree }
81 186
82 pub fn location(&self, idx: BorrowIndex) -> &Location { 187 pub fn location(&self, idx: BorrowIndex) -> &Location {
@@ -89,12 +194,10 @@ impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> {
89 fn kill_loans_out_of_scope_at_location(&self, 194 fn kill_loans_out_of_scope_at_location(&self,
90 sets: &mut BlockSets<BorrowIndex>, 195 sets: &mut BlockSets<BorrowIndex>,
91 location: Location) { 196 location: Location) {
92 let regioncx = &self.nonlexical_regioncx;
93
94 // NOTE: The state associated with a given `location` 197 // NOTE: The state associated with a given `location`
95 // reflects the dataflow on entry to the statement. If it 198 // reflects the dataflow on entry to the statement.
96 // does not contain `borrow_region`, then then that means 199 // Iterate over each of the borrows that we've precomputed
97 // that the statement at `location` kills the borrow. 200 // to have went out of scope at this location and kill them.
98 // 201 //
99 // We are careful always to call this function *before* we 202 // We are careful always to call this function *before* we
100 // set up the gen-bits for the statement or 203 // set up the gen-bits for the statement or
@@ -102,10 +205,9 @@ impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> {
102 // terminator *does* introduce a new loan of the same 205 // terminator *does* introduce a new loan of the same
103 // region, then setting that gen-bit will override any 206 // region, then setting that gen-bit will override any
104 // potential kill introduced here. 207 // potential kill introduced here.
105 for (borrow_index, borrow_data) in self.borrow_set.borrows.iter_enumerated() { 208 if let Some(indices) = self.borrows_out_of_scope_at_location.get(&location) {
106 let borrow_region = borrow_data.region.to_region_vid(); 209 for index in indices {
107 if !regioncx.region_contains_point(borrow_region, location) { 210 sets.kill(&index);
108 sets.kill(&borrow_index);
109 } 211 }
110 } 212 }
111 } 213 }