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