]>
Commit | Line | Data |
---|---|---|
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 | ||
15 | use rustc::mir::*; | |
16 | use rustc::mir::visit::{PlaceContext, MutatingUseContext, MutVisitor, Visitor}; | |
17 | use rustc::mir::traversal::ReversePostorder; | |
18 | use rustc::ty::TyCtxt; | |
19 | use syntax_pos::Span; | |
20 | ||
21 | use rustc_data_structures::indexed_vec::{IndexVec, Idx}; | |
22 | ||
23 | use std::{iter, mem, usize}; | |
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 { | |
46 | debug!("is_promotable: self={:?}", self); | |
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. | |
58 | #[derive(Debug)] | |
59 | pub enum Candidate { | |
60 | /// Borrow of a constant temporary. | |
61 | Ref(Location), | |
62 | ||
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 }, | |
69 | } | |
70 | ||
71 | struct TempCollector<'tcx> { | |
72 | temps: IndexVec<Local, TempState>, | |
73 | span: Span, | |
74 | mir: &'tcx Mir<'tcx>, | |
75 | } | |
76 | ||
77 | impl<'tcx> Visitor<'tcx> for TempCollector<'tcx> { | |
78 | fn visit_local(&mut self, | |
79 | &index: &Local, | |
80 | context: PlaceContext<'tcx>, | |
81 | location: Location) { | |
82 | debug!("visit_local: index={:?} context={:?} location={:?}", index, context, location); | |
83 | // We're only interested in temporaries | |
84 | if self.mir.local_kind(index) != LocalKind::Temp { | |
85 | return; | |
86 | } | |
87 | ||
88 | // Ignore drops, if the temp gets promoted, | |
89 | // then it's constant and thus drop is noop. | |
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 | ); | |
96 | return; | |
97 | } | |
98 | ||
99 | let temp = &mut self.temps[index]; | |
100 | debug!("visit_local: temp={:?}", temp); | |
101 | if *temp == TempState::Undefined { | |
102 | match context { | |
103 | PlaceContext::MutatingUse(MutatingUseContext::Store) | | |
104 | PlaceContext::MutatingUse(MutatingUseContext::AsmOutput) | | |
105 | PlaceContext::MutatingUse(MutatingUseContext::Call) => { | |
106 | *temp = TempState::Defined { | |
107 | location, | |
108 | uses: 0 | |
109 | }; | |
110 | return; | |
111 | } | |
112 | _ => { /* mark as unpromotable below */ } | |
113 | } | |
114 | } else if let TempState::Defined { ref mut uses, .. } = *temp { | |
115 | // We always allow borrows, even mutable ones, as we need | |
116 | // to promote mutable borrows of some ZSTs e.g., `&mut []`. | |
117 | let allowed_use = context.is_borrow() || context.is_nonmutating_use(); | |
118 | debug!("visit_local: allowed_use={:?}", allowed_use); | |
119 | if allowed_use { | |
120 | *uses += 1; | |
121 | return; | |
122 | } | |
123 | /* mark as unpromotable below */ | |
124 | } | |
125 | *temp = TempState::Unpromotable; | |
126 | } | |
127 | ||
128 | fn visit_source_info(&mut self, source_info: &SourceInfo) { | |
129 | self.span = source_info.span; | |
130 | } | |
131 | } | |
132 | ||
133 | pub fn collect_temps(mir: &Mir<'_>, | |
134 | rpo: &mut ReversePostorder<'_, '_>) -> IndexVec<Local, TempState> { | |
135 | let mut collector = TempCollector { | |
136 | temps: IndexVec::from_elem(TempState::Undefined, &mir.local_decls), | |
137 | span: mir.span, | |
138 | mir, | |
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> { | |
147 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
148 | source: &'a mut Mir<'tcx>, | |
149 | promoted: Mir<'tcx>, | |
150 | temps: &'a mut IndexVec<Local, TempState>, | |
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 { | |
159 | let span = self.promoted.span; | |
160 | self.promoted.basic_blocks_mut().push(BasicBlockData { | |
161 | statements: vec![], | |
162 | terminator: Some(Terminator { | |
163 | source_info: SourceInfo { | |
164 | span, | |
165 | scope: OUTERMOST_SOURCE_SCOPE | |
166 | }, | |
167 | kind: TerminatorKind::Return | |
168 | }), | |
169 | is_cleanup: false | |
170 | }) | |
171 | } | |
172 | ||
173 | fn assign(&mut self, dest: Local, rvalue: Rvalue<'tcx>, span: Span) { | |
174 | let last = self.promoted.basic_blocks().last().unwrap(); | |
175 | let data = &mut self.promoted[last]; | |
176 | data.statements.push(Statement { | |
177 | source_info: SourceInfo { | |
178 | span, | |
179 | scope: OUTERMOST_SOURCE_SCOPE | |
180 | }, | |
181 | kind: StatementKind::Assign(Place::Local(dest), box rvalue) | |
182 | }); | |
183 | } | |
184 | ||
185 | /// Copies the initialization of this temp to the | |
186 | /// promoted MIR, recursing through temps. | |
187 | fn promote_temp(&mut self, temp: Local) -> Local { | |
188 | let old_keep_original = self.keep_original; | |
189 | let loc = match self.temps[temp] { | |
190 | TempState::Defined { location, uses } if uses > 0 => { | |
191 | if uses > 1 { | |
192 | self.keep_original = true; | |
193 | } | |
194 | location | |
195 | } | |
196 | state => { | |
197 | span_bug!(self.promoted.span, "{:?} not promotable: {:?}", | |
198 | temp, state); | |
199 | } | |
200 | }; | |
201 | if !self.keep_original { | |
202 | self.temps[temp] = TempState::PromotedOut; | |
203 | } | |
204 | ||
205 | let no_stmts = self.source[loc.block].statements.len(); | |
206 | let new_temp = self.promoted.local_decls.push( | |
207 | LocalDecl::new_temp(self.source.local_decls[temp].ty, | |
208 | self.source.local_decls[temp].source_info.span)); | |
209 | ||
210 | debug!("promote({:?} @ {:?}/{:?}, {:?})", | |
211 | temp, loc, no_stmts, self.keep_original); | |
212 | ||
213 | // First, take the Rvalue or Call out of the source MIR, | |
214 | // or duplicate it, depending on keep_original. | |
215 | if loc.statement_index < no_stmts { | |
216 | let (rvalue, source_info) = { | |
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 { | |
229 | let unit = box Rvalue::Aggregate(box AggregateKind::Tuple, vec![]); | |
230 | mem::replace(rhs, unit) | |
231 | }, statement.source_info) | |
232 | }; | |
233 | ||
234 | let mut rvalue = *rvalue; | |
235 | self.visit_rvalue(&mut rvalue, loc); | |
236 | self.assign(new_temp, rvalue, source_info.span); | |
237 | } else { | |
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 { | |
251 | target, | |
252 | }) | |
253 | } | |
254 | }; | |
255 | ||
256 | match terminator.kind { | |
257 | TerminatorKind::Call { mut func, mut args, from_hir_call, .. } => { | |
258 | self.visit_operand(&mut func, loc); | |
259 | for arg in &mut args { | |
260 | self.visit_operand(arg, loc); | |
261 | } | |
262 | ||
263 | let last = self.promoted.basic_blocks().last().unwrap(); | |
264 | let new_target = self.new_block(); | |
265 | ||
266 | *self.promoted[last].terminator_mut() = Terminator { | |
267 | kind: TerminatorKind::Call { | |
268 | func, | |
269 | args, | |
270 | cleanup: None, | |
271 | destination: Some((Place::Local(new_temp), new_target)), | |
272 | from_hir_call, | |
273 | }, | |
274 | ..terminator | |
275 | }; | |
276 | } | |
277 | ref kind => { | |
278 | span_bug!(terminator.source_info.span, "{:?} not promotable", kind); | |
279 | } | |
280 | }; | |
281 | }; | |
282 | ||
283 | self.keep_original = old_keep_original; | |
284 | new_temp | |
285 | } | |
286 | ||
287 | fn promote_candidate(mut self, candidate: Candidate) { | |
288 | let mut operand = { | |
289 | let promoted = &mut self.promoted; | |
290 | let promoted_id = Promoted::new(self.source.promoted.len()); | |
291 | let mut promoted_place = |ty, span| { | |
292 | promoted.span = span; | |
293 | promoted.local_decls[RETURN_PLACE] = | |
294 | LocalDecl::new_return_place(ty, span); | |
295 | Place::Promoted(box (promoted_id, ty)) | |
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 { | |
302 | StatementKind::Assign(_, box Rvalue::Ref(_, _, ref mut place)) => { | |
303 | // Find the underlying local for this (necessarily interior) borrow. | |
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 | }; | |
309 | ||
310 | let ty = place.ty(local_decls, self.tcx).to_ty(self.tcx); | |
311 | let span = statement.source_info.span; | |
312 | ||
313 | Operand::Move(mem::replace(place, promoted_place(ty, span))) | |
314 | } | |
315 | _ => bug!() | |
316 | } | |
317 | } | |
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; | |
324 | let operand = Operand::Copy(promoted_place(ty, span)); | |
325 | mem::replace(&mut args[index], operand) | |
326 | } | |
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, | |
335 | _ => bug!() | |
336 | } | |
337 | } | |
338 | } | |
339 | }; | |
340 | ||
341 | assert_eq!(self.new_block(), START_BLOCK); | |
342 | self.visit_operand(&mut operand, Location { | |
343 | block: BasicBlock::new(0), | |
344 | statement_index: usize::MAX | |
345 | }); | |
346 | ||
347 | let span = self.promoted.span; | |
348 | self.assign(RETURN_PLACE, Rvalue::Use(operand), span); | |
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> { | |
355 | fn visit_local(&mut self, | |
356 | local: &mut Local, | |
357 | _: PlaceContext<'tcx>, | |
358 | _: Location) { | |
359 | if self.source.local_kind(*local) == LocalKind::Temp { | |
360 | *local = self.promote_temp(*local); | |
361 | } | |
362 | } | |
363 | } | |
364 | ||
365 | pub fn promote_candidates<'a, 'tcx>(mir: &mut Mir<'tcx>, | |
366 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
367 | mut temps: IndexVec<Local, TempState>, | |
368 | candidates: Vec<Candidate>) { | |
369 | // Visit candidates in reverse, in case they're nested. | |
370 | debug!("promote_candidates({:?})", candidates); | |
371 | ||
372 | for candidate in candidates.into_iter().rev() { | |
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 | } | |
381 | } | |
382 | _ => {} | |
383 | } | |
384 | } | |
385 | Candidate::Argument { .. } => {} | |
386 | } | |
387 | ||
388 | ||
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(); | |
393 | ||
394 | let promoter = Promoter { | |
395 | promoted: Mir::new( | |
396 | IndexVec::new(), | |
397 | // FIXME: maybe try to filter this to avoid blowing up | |
398 | // memory usage? | |
399 | mir.source_scopes.clone(), | |
400 | mir.source_scope_local_data.clone(), | |
401 | IndexVec::new(), | |
402 | None, | |
403 | initial_locals, | |
404 | IndexVec::new(), | |
405 | 0, | |
406 | vec![], | |
407 | mir.span, | |
408 | vec![], | |
409 | ), | |
410 | tcx, | |
411 | source: mir, | |
412 | temps: &mut temps, | |
413 | keep_original: false | |
414 | }; | |
415 | promoter.promote_candidate(candidate); | |
416 | } | |
417 | ||
418 | // Eliminate assignments to, and drops of promoted temps. | |
419 | let promoted = |index: Local| temps[index] == TempState::PromotedOut; | |
420 | for block in mir.basic_blocks_mut() { | |
421 | block.statements.retain(|statement| { | |
422 | match statement.kind { | |
423 | StatementKind::Assign(Place::Local(index), _) | | |
424 | StatementKind::StorageLive(index) | | |
425 | StatementKind::StorageDead(index) => { | |
426 | !promoted(index) | |
427 | } | |
428 | _ => true | |
429 | } | |
430 | }); | |
431 | let terminator = block.terminator_mut(); | |
432 | match terminator.kind { | |
433 | TerminatorKind::Drop { location: Place::Local(index), target, .. } => { | |
434 | if promoted(index) { | |
435 | terminator.kind = TerminatorKind::Goto { | |
436 | target, | |
437 | }; | |
438 | } | |
439 | } | |
440 | _ => {} | |
441 | } | |
442 | } | |
443 | } |