]>
Commit | Line | Data |
---|---|---|
a7813a04 XL |
1 | //! A pass that promotes borrows of constant rvalues. |
2 | //! | |
3 | //! The rvalues considered constant are trees of temps, | |
4 | //! each with exactly one initialization, and holding | |
5 | //! a constant value with no interior mutability. | |
6 | //! They are placed into a new MIR constant body in | |
7 | //! `promoted` and the borrow rvalue is replaced with | |
8 | //! a `Literal::Promoted` using the index into `promoted` | |
9 | //! of that constant MIR. | |
10 | //! | |
11 | //! This pass assumes that every use is dominated by an | |
12 | //! initialization and can otherwise silence errors, if | |
13 | //! move analysis runs after promotion on broken MIR. | |
14 | ||
c30ab7b3 | 15 | use rustc::mir::*; |
13cf67c4 | 16 | use rustc::mir::visit::{PlaceContext, MutatingUseContext, MutVisitor, Visitor}; |
3157f602 | 17 | use rustc::mir::traversal::ReversePostorder; |
8faf50e0 | 18 | use rustc::ty::TyCtxt; |
3157f602 | 19 | use syntax_pos::Span; |
a7813a04 | 20 | |
3157f602 | 21 | use rustc_data_structures::indexed_vec::{IndexVec, Idx}; |
a7813a04 | 22 | |
8faf50e0 | 23 | use std::{iter, mem, usize}; |
a7813a04 XL |
24 | |
25 | /// State of a temporary during collection and promotion. | |
26 | #[derive(Copy, Clone, PartialEq, Eq, Debug)] | |
27 | pub enum TempState { | |
28 | /// No references to this temp. | |
29 | Undefined, | |
30 | /// One direct assignment and any number of direct uses. | |
31 | /// A borrow of this temp is promotable if the assigned | |
32 | /// value is qualified as constant. | |
33 | Defined { | |
34 | location: Location, | |
35 | uses: usize | |
36 | }, | |
37 | /// Any other combination of assignments/uses. | |
38 | Unpromotable, | |
39 | /// This temp was part of an rvalue which got extracted | |
40 | /// during promotion and needs cleanup. | |
41 | PromotedOut | |
42 | } | |
43 | ||
44 | impl TempState { | |
45 | pub fn is_promotable(&self) -> bool { | |
13cf67c4 | 46 | debug!("is_promotable: self={:?}", self); |
a7813a04 XL |
47 | if let TempState::Defined { uses, .. } = *self { |
48 | uses > 0 | |
49 | } else { | |
50 | false | |
51 | } | |
52 | } | |
53 | } | |
54 | ||
55 | /// A "root candidate" for promotion, which will become the | |
56 | /// returned value in a promoted MIR, unless it's a subset | |
57 | /// of a larger candidate. | |
476ff2be | 58 | #[derive(Debug)] |
a7813a04 XL |
59 | pub enum Candidate { |
60 | /// Borrow of a constant temporary. | |
61 | Ref(Location), | |
62 | ||
2c00a5a8 XL |
63 | /// Currently applied to function calls where the callee has the unstable |
64 | /// `#[rustc_args_required_const]` attribute as well as the SIMD shuffle | |
65 | /// intrinsic. The intrinsic requires the arguments are indeed constant and | |
66 | /// the attribute currently provides the semantic requirement that arguments | |
67 | /// must be constant. | |
68 | Argument { bb: BasicBlock, index: usize }, | |
a7813a04 XL |
69 | } |
70 | ||
c30ab7b3 SL |
71 | struct TempCollector<'tcx> { |
72 | temps: IndexVec<Local, TempState>, | |
73 | span: Span, | |
74 | mir: &'tcx Mir<'tcx>, | |
a7813a04 XL |
75 | } |
76 | ||
c30ab7b3 | 77 | impl<'tcx> Visitor<'tcx> for TempCollector<'tcx> { |
ea8adc8c XL |
78 | fn visit_local(&mut self, |
79 | &index: &Local, | |
ff7c6d11 | 80 | context: PlaceContext<'tcx>, |
ea8adc8c | 81 | location: Location) { |
13cf67c4 | 82 | debug!("visit_local: index={:?} context={:?} location={:?}", index, context, location); |
ea8adc8c XL |
83 | // We're only interested in temporaries |
84 | if self.mir.local_kind(index) != LocalKind::Temp { | |
85 | return; | |
86 | } | |
c30ab7b3 | 87 | |
ea8adc8c XL |
88 | // Ignore drops, if the temp gets promoted, |
89 | // then it's constant and thus drop is noop. | |
13cf67c4 XL |
90 | // Non-uses are also irrelevent. |
91 | if context.is_drop() || !context.is_use() { | |
92 | debug!( | |
93 | "visit_local: context.is_drop={:?} context.is_use={:?}", | |
94 | context.is_drop(), context.is_use(), | |
95 | ); | |
ea8adc8c XL |
96 | return; |
97 | } | |
a7813a04 | 98 | |
ea8adc8c | 99 | let temp = &mut self.temps[index]; |
13cf67c4 | 100 | debug!("visit_local: temp={:?}", temp); |
ea8adc8c XL |
101 | if *temp == TempState::Undefined { |
102 | match context { | |
13cf67c4 XL |
103 | PlaceContext::MutatingUse(MutatingUseContext::Store) | |
104 | PlaceContext::MutatingUse(MutatingUseContext::AsmOutput) | | |
105 | PlaceContext::MutatingUse(MutatingUseContext::Call) => { | |
ea8adc8c XL |
106 | *temp = TempState::Defined { |
107 | location, | |
108 | uses: 0 | |
109 | }; | |
32a655c1 | 110 | return; |
a7813a04 | 111 | } |
ea8adc8c | 112 | _ => { /* mark as unpromotable below */ } |
a7813a04 | 113 | } |
ea8adc8c XL |
114 | } else if let TempState::Defined { ref mut uses, .. } = *temp { |
115 | // We always allow borrows, even mutable ones, as we need | |
0731742a | 116 | // to promote mutable borrows of some ZSTs e.g., `&mut []`. |
13cf67c4 XL |
117 | let allowed_use = context.is_borrow() || context.is_nonmutating_use(); |
118 | debug!("visit_local: allowed_use={:?}", allowed_use); | |
ea8adc8c XL |
119 | if allowed_use { |
120 | *uses += 1; | |
121 | return; | |
122 | } | |
123 | /* mark as unpromotable below */ | |
a7813a04 | 124 | } |
ea8adc8c | 125 | *temp = TempState::Unpromotable; |
a7813a04 XL |
126 | } |
127 | ||
3157f602 XL |
128 | fn visit_source_info(&mut self, source_info: &SourceInfo) { |
129 | self.span = source_info.span; | |
130 | } | |
a7813a04 XL |
131 | } |
132 | ||
9fa01778 XL |
133 | pub fn collect_temps(mir: &Mir<'_>, |
134 | rpo: &mut ReversePostorder<'_, '_>) -> IndexVec<Local, TempState> { | |
a7813a04 | 135 | let mut collector = TempCollector { |
c30ab7b3 SL |
136 | temps: IndexVec::from_elem(TempState::Undefined, &mir.local_decls), |
137 | span: mir.span, | |
3b2f2976 | 138 | mir, |
a7813a04 XL |
139 | }; |
140 | for (bb, data) in rpo { | |
141 | collector.visit_basic_block_data(bb, data); | |
142 | } | |
143 | collector.temps | |
144 | } | |
145 | ||
146 | struct Promoter<'a, 'tcx: 'a> { | |
94b46f34 | 147 | tcx: TyCtxt<'a, 'tcx, 'tcx>, |
a7813a04 XL |
148 | source: &'a mut Mir<'tcx>, |
149 | promoted: Mir<'tcx>, | |
c30ab7b3 | 150 | temps: &'a mut IndexVec<Local, TempState>, |
a7813a04 XL |
151 | |
152 | /// If true, all nested temps are also kept in the | |
153 | /// source MIR, not moved to the promoted MIR. | |
154 | keep_original: bool | |
155 | } | |
156 | ||
157 | impl<'a, 'tcx> Promoter<'a, 'tcx> { | |
158 | fn new_block(&mut self) -> BasicBlock { | |
3157f602 XL |
159 | let span = self.promoted.span; |
160 | self.promoted.basic_blocks_mut().push(BasicBlockData { | |
a7813a04 XL |
161 | statements: vec![], |
162 | terminator: Some(Terminator { | |
3157f602 | 163 | source_info: SourceInfo { |
3b2f2976 | 164 | span, |
94b46f34 | 165 | scope: OUTERMOST_SOURCE_SCOPE |
3157f602 | 166 | }, |
a7813a04 XL |
167 | kind: TerminatorKind::Return |
168 | }), | |
169 | is_cleanup: false | |
3157f602 | 170 | }) |
a7813a04 XL |
171 | } |
172 | ||
c30ab7b3 | 173 | fn assign(&mut self, dest: Local, rvalue: Rvalue<'tcx>, span: Span) { |
3157f602 XL |
174 | let last = self.promoted.basic_blocks().last().unwrap(); |
175 | let data = &mut self.promoted[last]; | |
a7813a04 | 176 | data.statements.push(Statement { |
3157f602 | 177 | source_info: SourceInfo { |
3b2f2976 | 178 | span, |
94b46f34 | 179 | scope: OUTERMOST_SOURCE_SCOPE |
3157f602 | 180 | }, |
0bf4aa26 | 181 | kind: StatementKind::Assign(Place::Local(dest), box rvalue) |
a7813a04 XL |
182 | }); |
183 | } | |
184 | ||
9fa01778 | 185 | /// Copies the initialization of this temp to the |
a7813a04 | 186 | /// promoted MIR, recursing through temps. |
c30ab7b3 | 187 | fn promote_temp(&mut self, temp: Local) -> Local { |
a7813a04 | 188 | let old_keep_original = self.keep_original; |
476ff2be SL |
189 | let loc = match self.temps[temp] { |
190 | TempState::Defined { location, uses } if uses > 0 => { | |
a7813a04 XL |
191 | if uses > 1 { |
192 | self.keep_original = true; | |
193 | } | |
476ff2be | 194 | location |
a7813a04 | 195 | } |
3157f602 XL |
196 | state => { |
197 | span_bug!(self.promoted.span, "{:?} not promotable: {:?}", | |
198 | temp, state); | |
a7813a04 XL |
199 | } |
200 | }; | |
201 | if !self.keep_original { | |
3157f602 | 202 | self.temps[temp] = TempState::PromotedOut; |
a7813a04 XL |
203 | } |
204 | ||
476ff2be SL |
205 | let no_stmts = self.source[loc.block].statements.len(); |
206 | let new_temp = self.promoted.local_decls.push( | |
cc61c64b XL |
207 | LocalDecl::new_temp(self.source.local_decls[temp].ty, |
208 | self.source.local_decls[temp].source_info.span)); | |
476ff2be SL |
209 | |
210 | debug!("promote({:?} @ {:?}/{:?}, {:?})", | |
211 | temp, loc, no_stmts, self.keep_original); | |
a7813a04 XL |
212 | |
213 | // First, take the Rvalue or Call out of the source MIR, | |
214 | // or duplicate it, depending on keep_original. | |
476ff2be | 215 | if loc.statement_index < no_stmts { |
0bf4aa26 | 216 | let (rvalue, source_info) = { |
476ff2be SL |
217 | let statement = &mut self.source[loc.block].statements[loc.statement_index]; |
218 | let rhs = match statement.kind { | |
219 | StatementKind::Assign(_, ref mut rhs) => rhs, | |
220 | _ => { | |
221 | span_bug!(statement.source_info.span, "{:?} is not an assignment", | |
222 | statement); | |
223 | } | |
224 | }; | |
225 | ||
226 | (if self.keep_original { | |
227 | rhs.clone() | |
228 | } else { | |
0bf4aa26 | 229 | let unit = box Rvalue::Aggregate(box AggregateKind::Tuple, vec![]); |
476ff2be SL |
230 | mem::replace(rhs, unit) |
231 | }, statement.source_info) | |
5bcae85e | 232 | }; |
476ff2be | 233 | |
0bf4aa26 | 234 | let mut rvalue = *rvalue; |
476ff2be SL |
235 | self.visit_rvalue(&mut rvalue, loc); |
236 | self.assign(new_temp, rvalue, source_info.span); | |
a7813a04 | 237 | } else { |
476ff2be SL |
238 | let terminator = if self.keep_original { |
239 | self.source[loc.block].terminator().clone() | |
240 | } else { | |
241 | let terminator = self.source[loc.block].terminator_mut(); | |
242 | let target = match terminator.kind { | |
243 | TerminatorKind::Call { destination: Some((_, target)), .. } => target, | |
244 | ref kind => { | |
245 | span_bug!(terminator.source_info.span, "{:?} not promotable", kind); | |
246 | } | |
247 | }; | |
248 | Terminator { | |
249 | source_info: terminator.source_info, | |
250 | kind: mem::replace(&mut terminator.kind, TerminatorKind::Goto { | |
3b2f2976 | 251 | target, |
476ff2be | 252 | }) |
a7813a04 XL |
253 | } |
254 | }; | |
a7813a04 | 255 | |
476ff2be | 256 | match terminator.kind { |
0bf4aa26 | 257 | TerminatorKind::Call { mut func, mut args, from_hir_call, .. } => { |
476ff2be SL |
258 | self.visit_operand(&mut func, loc); |
259 | for arg in &mut args { | |
260 | self.visit_operand(arg, loc); | |
261 | } | |
a7813a04 | 262 | |
476ff2be SL |
263 | let last = self.promoted.basic_blocks().last().unwrap(); |
264 | let new_target = self.new_block(); | |
a7813a04 | 265 | |
476ff2be SL |
266 | *self.promoted[last].terminator_mut() = Terminator { |
267 | kind: TerminatorKind::Call { | |
3b2f2976 XL |
268 | func, |
269 | args, | |
476ff2be | 270 | cleanup: None, |
0bf4aa26 XL |
271 | destination: Some((Place::Local(new_temp), new_target)), |
272 | from_hir_call, | |
476ff2be SL |
273 | }, |
274 | ..terminator | |
275 | }; | |
a7813a04 | 276 | } |
476ff2be SL |
277 | ref kind => { |
278 | span_bug!(terminator.source_info.span, "{:?} not promotable", kind); | |
279 | } | |
280 | }; | |
281 | }; | |
a7813a04 | 282 | |
a7813a04 | 283 | self.keep_original = old_keep_original; |
3157f602 | 284 | new_temp |
a7813a04 XL |
285 | } |
286 | ||
287 | fn promote_candidate(mut self, candidate: Candidate) { | |
8faf50e0 | 288 | let mut operand = { |
94b46f34 | 289 | let promoted = &mut self.promoted; |
8faf50e0 XL |
290 | let promoted_id = Promoted::new(self.source.promoted.len()); |
291 | let mut promoted_place = |ty, span| { | |
94b46f34 XL |
292 | promoted.span = span; |
293 | promoted.local_decls[RETURN_PLACE] = | |
294 | LocalDecl::new_return_place(ty, span); | |
8faf50e0 | 295 | Place::Promoted(box (promoted_id, ty)) |
94b46f34 XL |
296 | }; |
297 | let (blocks, local_decls) = self.source.basic_blocks_and_local_decls_mut(); | |
298 | match candidate { | |
299 | Candidate::Ref(loc) => { | |
300 | let ref mut statement = blocks[loc.block].statements[loc.statement_index]; | |
301 | match statement.kind { | |
0bf4aa26 | 302 | StatementKind::Assign(_, box Rvalue::Ref(_, _, ref mut place)) => { |
b7449926 | 303 | // Find the underlying local for this (necessarily interior) borrow. |
a1dfa0c6 XL |
304 | let mut place = place; |
305 | while let Place::Projection(ref mut proj) = *place { | |
306 | assert_ne!(proj.elem, ProjectionElem::Deref); | |
307 | place = &mut proj.base; | |
308 | }; | |
94b46f34 XL |
309 | |
310 | let ty = place.ty(local_decls, self.tcx).to_ty(self.tcx); | |
94b46f34 XL |
311 | let span = statement.source_info.span; |
312 | ||
8faf50e0 | 313 | Operand::Move(mem::replace(place, promoted_place(ty, span))) |
94b46f34 XL |
314 | } |
315 | _ => bug!() | |
a7813a04 XL |
316 | } |
317 | } | |
94b46f34 XL |
318 | Candidate::Argument { bb, index } => { |
319 | let terminator = blocks[bb].terminator_mut(); | |
320 | match terminator.kind { | |
321 | TerminatorKind::Call { ref mut args, .. } => { | |
322 | let ty = args[index].ty(local_decls, self.tcx); | |
323 | let span = terminator.source_info.span; | |
8faf50e0 XL |
324 | let operand = Operand::Copy(promoted_place(ty, span)); |
325 | mem::replace(&mut args[index], operand) | |
94b46f34 | 326 | } |
a1dfa0c6 XL |
327 | // We expected a `TerminatorKind::Call` for which we'd like to promote an |
328 | // argument. `qualify_consts` saw a `TerminatorKind::Call` here, but | |
329 | // we are seeing a `Goto`. That means that the `promote_temps` method | |
330 | // already promoted this call away entirely. This case occurs when calling | |
331 | // a function requiring a constant argument and as that constant value | |
332 | // providing a value whose computation contains another call to a function | |
333 | // requiring a constant argument. | |
334 | TerminatorKind::Goto { .. } => return, | |
94b46f34 | 335 | _ => bug!() |
a7813a04 | 336 | } |
a7813a04 XL |
337 | } |
338 | } | |
339 | }; | |
94b46f34 XL |
340 | |
341 | assert_eq!(self.new_block(), START_BLOCK); | |
8faf50e0 | 342 | self.visit_operand(&mut operand, Location { |
9e0c209e SL |
343 | block: BasicBlock::new(0), |
344 | statement_index: usize::MAX | |
345 | }); | |
c30ab7b3 | 346 | |
94b46f34 | 347 | let span = self.promoted.span; |
8faf50e0 | 348 | self.assign(RETURN_PLACE, Rvalue::Use(operand), span); |
a7813a04 XL |
349 | self.source.promoted.push(self.promoted); |
350 | } | |
351 | } | |
352 | ||
353 | /// Replaces all temporaries with their promoted counterparts. | |
354 | impl<'a, 'tcx> MutVisitor<'tcx> for Promoter<'a, 'tcx> { | |
ea8adc8c XL |
355 | fn visit_local(&mut self, |
356 | local: &mut Local, | |
ff7c6d11 | 357 | _: PlaceContext<'tcx>, |
ea8adc8c XL |
358 | _: Location) { |
359 | if self.source.local_kind(*local) == LocalKind::Temp { | |
360 | *local = self.promote_temp(*local); | |
a7813a04 | 361 | } |
a7813a04 XL |
362 | } |
363 | } | |
364 | ||
365 | pub fn promote_candidates<'a, 'tcx>(mir: &mut Mir<'tcx>, | |
366 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
c30ab7b3 | 367 | mut temps: IndexVec<Local, TempState>, |
a7813a04 XL |
368 | candidates: Vec<Candidate>) { |
369 | // Visit candidates in reverse, in case they're nested. | |
476ff2be | 370 | debug!("promote_candidates({:?})", candidates); |
94b46f34 | 371 | |
a7813a04 | 372 | for candidate in candidates.into_iter().rev() { |
94b46f34 XL |
373 | match candidate { |
374 | Candidate::Ref(Location { block, statement_index }) => { | |
375 | match mir[block].statements[statement_index].kind { | |
376 | StatementKind::Assign(Place::Local(local), _) => { | |
377 | if temps[local] == TempState::PromotedOut { | |
378 | // Already promoted. | |
379 | continue; | |
380 | } | |
a7813a04 | 381 | } |
94b46f34 | 382 | _ => {} |
a7813a04 | 383 | } |
a7813a04 | 384 | } |
94b46f34 XL |
385 | Candidate::Argument { .. } => {} |
386 | } | |
387 | ||
a7813a04 | 388 | |
94b46f34 XL |
389 | // Declare return place local so that `Mir::new` doesn't complain. |
390 | let initial_locals = iter::once( | |
391 | LocalDecl::new_return_place(tcx.types.never, mir.span) | |
392 | ).collect(); | |
c30ab7b3 | 393 | |
8faf50e0 | 394 | let promoter = Promoter { |
3157f602 XL |
395 | promoted: Mir::new( |
396 | IndexVec::new(), | |
ea8adc8c XL |
397 | // FIXME: maybe try to filter this to avoid blowing up |
398 | // memory usage? | |
94b46f34 XL |
399 | mir.source_scopes.clone(), |
400 | mir.source_scope_local_data.clone(), | |
3157f602 | 401 | IndexVec::new(), |
ea8adc8c | 402 | None, |
c30ab7b3 | 403 | initial_locals, |
0731742a | 404 | IndexVec::new(), |
c30ab7b3 | 405 | 0, |
3157f602 | 406 | vec![], |
0731742a XL |
407 | mir.span, |
408 | vec![], | |
3157f602 | 409 | ), |
94b46f34 | 410 | tcx, |
c30ab7b3 | 411 | source: mir, |
a7813a04 XL |
412 | temps: &mut temps, |
413 | keep_original: false | |
414 | }; | |
a7813a04 XL |
415 | promoter.promote_candidate(candidate); |
416 | } | |
417 | ||
418 | // Eliminate assignments to, and drops of promoted temps. | |
c30ab7b3 | 419 | let promoted = |index: Local| temps[index] == TempState::PromotedOut; |
3157f602 | 420 | for block in mir.basic_blocks_mut() { |
a7813a04 XL |
421 | block.statements.retain(|statement| { |
422 | match statement.kind { | |
ff7c6d11 | 423 | StatementKind::Assign(Place::Local(index), _) | |
ea8adc8c XL |
424 | StatementKind::StorageLive(index) | |
425 | StatementKind::StorageDead(index) => { | |
a7813a04 XL |
426 | !promoted(index) |
427 | } | |
428 | _ => true | |
429 | } | |
430 | }); | |
431 | let terminator = block.terminator_mut(); | |
432 | match terminator.kind { | |
ff7c6d11 | 433 | TerminatorKind::Drop { location: Place::Local(index), target, .. } => { |
a7813a04 XL |
434 | if promoted(index) { |
435 | terminator.kind = TerminatorKind::Goto { | |
3b2f2976 | 436 | target, |
a7813a04 XL |
437 | }; |
438 | } | |
439 | } | |
440 | _ => {} | |
441 | } | |
442 | } | |
443 | } |