]>
Commit | Line | Data |
---|---|---|
92a42be0 SL |
1 | // Copyright 2012-2014 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 | ||
3157f602 | 11 | //! An analysis to determine which locals require allocas and |
92a42be0 SL |
12 | //! which do not. |
13 | ||
b7449926 | 14 | use rustc_data_structures::bitvec::BitArray; |
8faf50e0 | 15 | use rustc_data_structures::graph::dominators::Dominators; |
3157f602 | 16 | use rustc_data_structures::indexed_vec::{Idx, IndexVec}; |
0531ce1d | 17 | use rustc::mir::{self, Location, TerminatorKind}; |
ff7c6d11 | 18 | use rustc::mir::visit::{Visitor, PlaceContext}; |
3157f602 | 19 | use rustc::mir::traversal; |
ea8adc8c | 20 | use rustc::ty; |
ff7c6d11 XL |
21 | use rustc::ty::layout::LayoutOf; |
22 | use type_of::LayoutLlvmExt; | |
2c00a5a8 | 23 | use super::FunctionCx; |
92a42be0 | 24 | |
b7449926 | 25 | pub fn non_ssa_locals(fx: &FunctionCx<'a, 'll, 'tcx>) -> BitArray<mir::Local> { |
2c00a5a8 XL |
26 | let mir = fx.mir; |
27 | let mut analyzer = LocalAnalyzer::new(fx); | |
92a42be0 SL |
28 | |
29 | analyzer.visit_mir(mir); | |
30 | ||
c30ab7b3 | 31 | for (index, ty) in mir.local_decls.iter().map(|l| l.ty).enumerate() { |
2c00a5a8 | 32 | let ty = fx.monomorphize(&ty); |
3157f602 | 33 | debug!("local {} has type {:?}", index, ty); |
2c00a5a8 | 34 | let layout = fx.cx.layout_of(ty); |
ff7c6d11 | 35 | if layout.is_llvm_immediate() { |
92a42be0 | 36 | // These sorts of types are immediates that we can store |
b7449926 | 37 | // in an Value without an alloca. |
ff7c6d11 | 38 | } else if layout.is_llvm_scalar_pair() { |
3157f602 | 39 | // We allow pairs and uses of any of their 2 fields. |
92a42be0 SL |
40 | } else { |
41 | // These sorts of types require an alloca. Note that | |
ff7c6d11 | 42 | // is_llvm_immediate() may *still* be true, particularly |
92a42be0 SL |
43 | // for newtypes, but we currently force some types |
44 | // (e.g. structs) into an alloca unconditionally, just so | |
45 | // that we don't have to deal with having two pathways | |
46 | // (gep vs extractvalue etc). | |
83c7162d | 47 | analyzer.not_ssa(mir::Local::new(index)); |
92a42be0 SL |
48 | } |
49 | } | |
50 | ||
83c7162d | 51 | analyzer.non_ssa_locals |
92a42be0 SL |
52 | } |
53 | ||
b7449926 XL |
54 | struct LocalAnalyzer<'mir, 'a: 'mir, 'll: 'a, 'tcx: 'll> { |
55 | fx: &'mir FunctionCx<'a, 'll, 'tcx>, | |
83c7162d | 56 | dominators: Dominators<mir::BasicBlock>, |
b7449926 | 57 | non_ssa_locals: BitArray<mir::Local>, |
83c7162d XL |
58 | // The location of the first visited direct assignment to each |
59 | // local, or an invalid location (out of bounds `block` index). | |
60 | first_assignment: IndexVec<mir::Local, Location> | |
92a42be0 SL |
61 | } |
62 | ||
b7449926 XL |
63 | impl LocalAnalyzer<'mir, 'a, 'll, 'tcx> { |
64 | fn new(fx: &'mir FunctionCx<'a, 'll, 'tcx>) -> Self { | |
83c7162d XL |
65 | let invalid_location = |
66 | mir::BasicBlock::new(fx.mir.basic_blocks().len()).start_location(); | |
abe05a73 | 67 | let mut analyzer = LocalAnalyzer { |
2c00a5a8 | 68 | fx, |
83c7162d | 69 | dominators: fx.mir.dominators(), |
b7449926 | 70 | non_ssa_locals: BitArray::new(fx.mir.local_decls.len()), |
83c7162d | 71 | first_assignment: IndexVec::from_elem(invalid_location, &fx.mir.local_decls) |
abe05a73 XL |
72 | }; |
73 | ||
74 | // Arguments get assigned to by means of the function being called | |
83c7162d XL |
75 | for arg in fx.mir.args_iter() { |
76 | analyzer.first_assignment[arg] = mir::START_BLOCK.start_location(); | |
7453a54e | 77 | } |
abe05a73 XL |
78 | |
79 | analyzer | |
92a42be0 SL |
80 | } |
81 | ||
83c7162d XL |
82 | fn first_assignment(&self, local: mir::Local) -> Option<Location> { |
83 | let location = self.first_assignment[local]; | |
84 | if location.block.index() < self.fx.mir.basic_blocks().len() { | |
85 | Some(location) | |
86 | } else { | |
87 | None | |
88 | } | |
92a42be0 | 89 | } |
7453a54e | 90 | |
83c7162d XL |
91 | fn not_ssa(&mut self, local: mir::Local) { |
92 | debug!("marking {:?} as non-SSA", local); | |
8faf50e0 | 93 | self.non_ssa_locals.insert(local); |
83c7162d XL |
94 | } |
95 | ||
96 | fn assign(&mut self, local: mir::Local, location: Location) { | |
97 | if self.first_assignment(local).is_some() { | |
98 | self.not_ssa(local); | |
99 | } else { | |
100 | self.first_assignment[local] = location; | |
7453a54e SL |
101 | } |
102 | } | |
92a42be0 SL |
103 | } |
104 | ||
b7449926 | 105 | impl Visitor<'tcx> for LocalAnalyzer<'mir, 'a, 'll, 'tcx> { |
92a42be0 SL |
106 | fn visit_assign(&mut self, |
107 | block: mir::BasicBlock, | |
ff7c6d11 | 108 | place: &mir::Place<'tcx>, |
9e0c209e SL |
109 | rvalue: &mir::Rvalue<'tcx>, |
110 | location: Location) { | |
ff7c6d11 | 111 | debug!("visit_assign(block={:?}, place={:?}, rvalue={:?})", block, place, rvalue); |
92a42be0 | 112 | |
ff7c6d11 | 113 | if let mir::Place::Local(index) = *place { |
83c7162d | 114 | self.assign(index, location); |
2c00a5a8 | 115 | if !self.fx.rvalue_creates_operand(rvalue) { |
83c7162d | 116 | self.not_ssa(index); |
92a42be0 | 117 | } |
3157f602 | 118 | } else { |
ff7c6d11 | 119 | self.visit_place(place, PlaceContext::Store, location); |
92a42be0 SL |
120 | } |
121 | ||
9e0c209e | 122 | self.visit_rvalue(rvalue, location); |
92a42be0 SL |
123 | } |
124 | ||
3157f602 XL |
125 | fn visit_terminator_kind(&mut self, |
126 | block: mir::BasicBlock, | |
9e0c209e SL |
127 | kind: &mir::TerminatorKind<'tcx>, |
128 | location: Location) { | |
0531ce1d | 129 | let check = match *kind { |
3157f602 | 130 | mir::TerminatorKind::Call { |
0531ce1d | 131 | func: mir::Operand::Constant(ref c), |
3157f602 | 132 | ref args, .. |
0531ce1d | 133 | } => match c.ty.sty { |
b7449926 | 134 | ty::FnDef(did, _) => Some((did, args)), |
0531ce1d XL |
135 | _ => None, |
136 | }, | |
137 | _ => None, | |
138 | }; | |
139 | if let Some((def_id, args)) = check { | |
140 | if Some(def_id) == self.fx.cx.tcx.lang_items().box_free_fn() { | |
3157f602 XL |
141 | // box_free(x) shares with `drop x` the property that it |
142 | // is not guaranteed to be statically dominated by the | |
143 | // definition of x, so x must always be in an alloca. | |
ff7c6d11 XL |
144 | if let mir::Operand::Move(ref place) = args[0] { |
145 | self.visit_place(place, PlaceContext::Drop, location); | |
3157f602 XL |
146 | } |
147 | } | |
3157f602 XL |
148 | } |
149 | ||
9e0c209e | 150 | self.super_terminator_kind(block, kind, location); |
3157f602 XL |
151 | } |
152 | ||
ff7c6d11 XL |
153 | fn visit_place(&mut self, |
154 | place: &mir::Place<'tcx>, | |
155 | context: PlaceContext<'tcx>, | |
9e0c209e | 156 | location: Location) { |
ff7c6d11 | 157 | debug!("visit_place(place={:?}, context={:?})", place, context); |
2c00a5a8 | 158 | let cx = self.fx.cx; |
ff7c6d11 XL |
159 | |
160 | if let mir::Place::Projection(ref proj) = *place { | |
161 | // Allow uses of projections that are ZSTs or from scalar fields. | |
162 | let is_consume = match context { | |
163 | PlaceContext::Copy | PlaceContext::Move => true, | |
164 | _ => false | |
165 | }; | |
166 | if is_consume { | |
2c00a5a8 XL |
167 | let base_ty = proj.base.ty(self.fx.mir, cx.tcx); |
168 | let base_ty = self.fx.monomorphize(&base_ty); | |
ff7c6d11 XL |
169 | |
170 | // ZSTs don't require any actual memory access. | |
2c00a5a8 XL |
171 | let elem_ty = base_ty.projection_ty(cx.tcx, &proj.elem).to_ty(cx.tcx); |
172 | let elem_ty = self.fx.monomorphize(&elem_ty); | |
173 | if cx.layout_of(elem_ty).is_zst() { | |
ff7c6d11 XL |
174 | return; |
175 | } | |
176 | ||
177 | if let mir::ProjectionElem::Field(..) = proj.elem { | |
2c00a5a8 | 178 | let layout = cx.layout_of(base_ty.to_ty(cx.tcx)); |
ff7c6d11 XL |
179 | if layout.is_llvm_immediate() || layout.is_llvm_scalar_pair() { |
180 | // Recurse with the same context, instead of `Projection`, | |
181 | // potentially stopping at non-operand projections, | |
83c7162d | 182 | // which would trigger `not_ssa` on locals. |
ff7c6d11 XL |
183 | self.visit_place(&proj.base, context, location); |
184 | return; | |
54a0048b | 185 | } |
3157f602 XL |
186 | } |
187 | } | |
3157f602 | 188 | |
ff7c6d11 | 189 | // A deref projection only reads the pointer, never needs the place. |
ea8adc8c | 190 | if let mir::ProjectionElem::Deref = proj.elem { |
ff7c6d11 | 191 | return self.visit_place(&proj.base, PlaceContext::Copy, location); |
ea8adc8c XL |
192 | } |
193 | } | |
5bcae85e | 194 | |
ff7c6d11 | 195 | self.super_place(place, context, location); |
ea8adc8c | 196 | } |
5bcae85e | 197 | |
ea8adc8c | 198 | fn visit_local(&mut self, |
83c7162d | 199 | &local: &mir::Local, |
ff7c6d11 | 200 | context: PlaceContext<'tcx>, |
83c7162d | 201 | location: Location) { |
ea8adc8c | 202 | match context { |
ff7c6d11 | 203 | PlaceContext::Call => { |
83c7162d | 204 | self.assign(local, location); |
ea8adc8c | 205 | } |
5bcae85e | 206 | |
ff7c6d11 XL |
207 | PlaceContext::StorageLive | |
208 | PlaceContext::StorageDead | | |
83c7162d XL |
209 | PlaceContext::Validate => {} |
210 | ||
ff7c6d11 | 211 | PlaceContext::Copy | |
83c7162d XL |
212 | PlaceContext::Move => { |
213 | // Reads from uninitialized variables (e.g. in dead code, after | |
214 | // optimizations) require locals to be in (uninitialized) memory. | |
215 | // NB: there can be uninitialized reads of a local visited after | |
216 | // an assignment to that local, if they happen on disjoint paths. | |
217 | let ssa_read = match self.first_assignment(local) { | |
218 | Some(assignment_location) => { | |
219 | assignment_location.dominates(location, &self.dominators) | |
220 | } | |
221 | None => false | |
222 | }; | |
223 | if !ssa_read { | |
224 | self.not_ssa(local); | |
225 | } | |
226 | } | |
ff7c6d11 XL |
227 | |
228 | PlaceContext::Inspect | | |
229 | PlaceContext::Store | | |
230 | PlaceContext::AsmOutput | | |
231 | PlaceContext::Borrow { .. } | | |
232 | PlaceContext::Projection(..) => { | |
83c7162d | 233 | self.not_ssa(local); |
92a42be0 | 234 | } |
3157f602 | 235 | |
ff7c6d11 | 236 | PlaceContext::Drop => { |
83c7162d | 237 | let ty = mir::Place::Local(local).ty(self.fx.mir, self.fx.cx.tcx); |
2c00a5a8 | 238 | let ty = self.fx.monomorphize(&ty.to_ty(self.fx.cx.tcx)); |
ea8adc8c | 239 | |
ff7c6d11 | 240 | // Only need the place if we're actually dropping it. |
2c00a5a8 | 241 | if self.fx.cx.type_needs_drop(ty) { |
83c7162d | 242 | self.not_ssa(local); |
ea8adc8c | 243 | } |
92a42be0 SL |
244 | } |
245 | } | |
92a42be0 SL |
246 | } |
247 | } | |
3157f602 XL |
248 | |
249 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] | |
250 | pub enum CleanupKind { | |
251 | NotCleanup, | |
252 | Funclet, | |
253 | Internal { funclet: mir::BasicBlock } | |
254 | } | |
255 | ||
7cac9316 XL |
256 | impl CleanupKind { |
257 | pub fn funclet_bb(self, for_bb: mir::BasicBlock) -> Option<mir::BasicBlock> { | |
258 | match self { | |
259 | CleanupKind::NotCleanup => None, | |
260 | CleanupKind::Funclet => Some(for_bb), | |
261 | CleanupKind::Internal { funclet } => Some(funclet), | |
262 | } | |
263 | } | |
264 | } | |
265 | ||
32a655c1 | 266 | pub fn cleanup_kinds<'a, 'tcx>(mir: &mir::Mir<'tcx>) -> IndexVec<mir::BasicBlock, CleanupKind> { |
3157f602 XL |
267 | fn discover_masters<'tcx>(result: &mut IndexVec<mir::BasicBlock, CleanupKind>, |
268 | mir: &mir::Mir<'tcx>) { | |
269 | for (bb, data) in mir.basic_blocks().iter_enumerated() { | |
270 | match data.terminator().kind { | |
271 | TerminatorKind::Goto { .. } | | |
272 | TerminatorKind::Resume | | |
ff7c6d11 | 273 | TerminatorKind::Abort | |
3157f602 | 274 | TerminatorKind::Return | |
ea8adc8c | 275 | TerminatorKind::GeneratorDrop | |
3157f602 | 276 | TerminatorKind::Unreachable | |
ea8adc8c | 277 | TerminatorKind::SwitchInt { .. } | |
abe05a73 | 278 | TerminatorKind::Yield { .. } | |
2c00a5a8 XL |
279 | TerminatorKind::FalseEdges { .. } | |
280 | TerminatorKind::FalseUnwind { .. } => { | |
3157f602 XL |
281 | /* nothing to do */ |
282 | } | |
283 | TerminatorKind::Call { cleanup: unwind, .. } | | |
284 | TerminatorKind::Assert { cleanup: unwind, .. } | | |
285 | TerminatorKind::DropAndReplace { unwind, .. } | | |
286 | TerminatorKind::Drop { unwind, .. } => { | |
287 | if let Some(unwind) = unwind { | |
288 | debug!("cleanup_kinds: {:?}/{:?} registering {:?} as funclet", | |
289 | bb, data, unwind); | |
290 | result[unwind] = CleanupKind::Funclet; | |
291 | } | |
292 | } | |
293 | } | |
294 | } | |
295 | } | |
296 | ||
297 | fn propagate<'tcx>(result: &mut IndexVec<mir::BasicBlock, CleanupKind>, | |
298 | mir: &mir::Mir<'tcx>) { | |
299 | let mut funclet_succs = IndexVec::from_elem(None, mir.basic_blocks()); | |
300 | ||
301 | let mut set_successor = |funclet: mir::BasicBlock, succ| { | |
302 | match funclet_succs[funclet] { | |
303 | ref mut s @ None => { | |
304 | debug!("set_successor: updating successor of {:?} to {:?}", | |
305 | funclet, succ); | |
306 | *s = Some(succ); | |
307 | }, | |
308 | Some(s) => if s != succ { | |
309 | span_bug!(mir.span, "funclet {:?} has 2 parents - {:?} and {:?}", | |
310 | funclet, s, succ); | |
311 | } | |
312 | } | |
313 | }; | |
314 | ||
315 | for (bb, data) in traversal::reverse_postorder(mir) { | |
316 | let funclet = match result[bb] { | |
317 | CleanupKind::NotCleanup => continue, | |
318 | CleanupKind::Funclet => bb, | |
319 | CleanupKind::Internal { funclet } => funclet, | |
320 | }; | |
321 | ||
322 | debug!("cleanup_kinds: {:?}/{:?}/{:?} propagating funclet {:?}", | |
323 | bb, data, result[bb], funclet); | |
324 | ||
83c7162d | 325 | for &succ in data.terminator().successors() { |
3157f602 XL |
326 | let kind = result[succ]; |
327 | debug!("cleanup_kinds: propagating {:?} to {:?}/{:?}", | |
328 | funclet, succ, kind); | |
329 | match kind { | |
330 | CleanupKind::NotCleanup => { | |
331 | result[succ] = CleanupKind::Internal { funclet: funclet }; | |
332 | } | |
333 | CleanupKind::Funclet => { | |
7cac9316 XL |
334 | if funclet != succ { |
335 | set_successor(funclet, succ); | |
336 | } | |
3157f602 XL |
337 | } |
338 | CleanupKind::Internal { funclet: succ_funclet } => { | |
339 | if funclet != succ_funclet { | |
340 | // `succ` has 2 different funclet going into it, so it must | |
341 | // be a funclet by itself. | |
342 | ||
343 | debug!("promoting {:?} to a funclet and updating {:?}", succ, | |
344 | succ_funclet); | |
345 | result[succ] = CleanupKind::Funclet; | |
346 | set_successor(succ_funclet, succ); | |
347 | set_successor(funclet, succ); | |
348 | } | |
349 | } | |
350 | } | |
351 | } | |
352 | } | |
353 | } | |
354 | ||
355 | let mut result = IndexVec::from_elem(CleanupKind::NotCleanup, mir.basic_blocks()); | |
356 | ||
357 | discover_masters(&mut result, mir); | |
358 | propagate(&mut result, mir); | |
359 | debug!("cleanup_kinds: result={:?}", result); | |
360 | result | |
361 | } |