]>
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 | ||
7453a54e | 14 | use rustc_data_structures::bitvec::BitVector; |
3157f602 | 15 | use rustc_data_structures::indexed_vec::{Idx, IndexVec}; |
cc61c64b XL |
16 | use rustc::middle::const_val::ConstVal; |
17 | use rustc::mir::{self, Location, TerminatorKind, Literal}; | |
92a42be0 | 18 | use rustc::mir::visit::{Visitor, LvalueContext}; |
3157f602 | 19 | use rustc::mir::traversal; |
ea8adc8c | 20 | use rustc::ty; |
32a655c1 SL |
21 | use common; |
22 | use super::MirContext; | |
92a42be0 | 23 | |
32a655c1 SL |
24 | pub fn lvalue_locals<'a, 'tcx>(mircx: &MirContext<'a, 'tcx>) -> BitVector { |
25 | let mir = mircx.mir; | |
26 | let mut analyzer = LocalAnalyzer::new(mircx); | |
92a42be0 SL |
27 | |
28 | analyzer.visit_mir(mir); | |
29 | ||
c30ab7b3 | 30 | for (index, ty) in mir.local_decls.iter().map(|l| l.ty).enumerate() { |
32a655c1 | 31 | let ty = mircx.monomorphize(&ty); |
3157f602 | 32 | debug!("local {} has type {:?}", index, ty); |
92a42be0 | 33 | if ty.is_scalar() || |
32a655c1 | 34 | ty.is_box() || |
92a42be0 | 35 | ty.is_region_ptr() || |
a7813a04 | 36 | ty.is_simd() || |
32a655c1 | 37 | common::type_is_zero_size(mircx.ccx, ty) |
92a42be0 SL |
38 | { |
39 | // These sorts of types are immediates that we can store | |
40 | // in an ValueRef without an alloca. | |
32a655c1 SL |
41 | assert!(common::type_is_immediate(mircx.ccx, ty) || |
42 | common::type_is_fat_ptr(mircx.ccx, ty)); | |
43 | } else if common::type_is_imm_pair(mircx.ccx, ty) { | |
3157f602 | 44 | // We allow pairs and uses of any of their 2 fields. |
92a42be0 SL |
45 | } else { |
46 | // These sorts of types require an alloca. Note that | |
47 | // type_is_immediate() may *still* be true, particularly | |
48 | // for newtypes, but we currently force some types | |
49 | // (e.g. structs) into an alloca unconditionally, just so | |
50 | // that we don't have to deal with having two pathways | |
51 | // (gep vs extractvalue etc). | |
3157f602 | 52 | analyzer.mark_as_lvalue(mir::Local::new(index)); |
92a42be0 SL |
53 | } |
54 | } | |
55 | ||
3157f602 | 56 | analyzer.lvalue_locals |
92a42be0 SL |
57 | } |
58 | ||
32a655c1 SL |
59 | struct LocalAnalyzer<'mir, 'a: 'mir, 'tcx: 'a> { |
60 | cx: &'mir MirContext<'a, 'tcx>, | |
3157f602 | 61 | lvalue_locals: BitVector, |
7453a54e | 62 | seen_assigned: BitVector |
92a42be0 SL |
63 | } |
64 | ||
32a655c1 SL |
65 | impl<'mir, 'a, 'tcx> LocalAnalyzer<'mir, 'a, 'tcx> { |
66 | fn new(mircx: &'mir MirContext<'a, 'tcx>) -> LocalAnalyzer<'mir, 'a, 'tcx> { | |
abe05a73 | 67 | let mut analyzer = LocalAnalyzer { |
32a655c1 SL |
68 | cx: mircx, |
69 | lvalue_locals: BitVector::new(mircx.mir.local_decls.len()), | |
70 | seen_assigned: BitVector::new(mircx.mir.local_decls.len()) | |
abe05a73 XL |
71 | }; |
72 | ||
73 | // Arguments get assigned to by means of the function being called | |
74 | for idx in 0..mircx.mir.arg_count { | |
75 | analyzer.seen_assigned.insert(idx + 1); | |
7453a54e | 76 | } |
abe05a73 XL |
77 | |
78 | analyzer | |
92a42be0 SL |
79 | } |
80 | ||
3157f602 XL |
81 | fn mark_as_lvalue(&mut self, local: mir::Local) { |
82 | debug!("marking {:?} as lvalue", local); | |
83 | self.lvalue_locals.insert(local.index()); | |
92a42be0 | 84 | } |
7453a54e | 85 | |
3157f602 XL |
86 | fn mark_assigned(&mut self, local: mir::Local) { |
87 | if !self.seen_assigned.insert(local.index()) { | |
88 | self.mark_as_lvalue(local); | |
7453a54e SL |
89 | } |
90 | } | |
92a42be0 SL |
91 | } |
92 | ||
32a655c1 | 93 | impl<'mir, 'a, 'tcx> Visitor<'tcx> for LocalAnalyzer<'mir, 'a, 'tcx> { |
92a42be0 SL |
94 | fn visit_assign(&mut self, |
95 | block: mir::BasicBlock, | |
96 | lvalue: &mir::Lvalue<'tcx>, | |
9e0c209e SL |
97 | rvalue: &mir::Rvalue<'tcx>, |
98 | location: Location) { | |
92a42be0 SL |
99 | debug!("visit_assign(block={:?}, lvalue={:?}, rvalue={:?})", block, lvalue, rvalue); |
100 | ||
c30ab7b3 | 101 | if let mir::Lvalue::Local(index) = *lvalue { |
3157f602 | 102 | self.mark_assigned(index); |
cc61c64b | 103 | if !self.cx.rvalue_creates_operand(rvalue) { |
3157f602 | 104 | self.mark_as_lvalue(index); |
92a42be0 | 105 | } |
3157f602 | 106 | } else { |
9e0c209e | 107 | self.visit_lvalue(lvalue, LvalueContext::Store, location); |
92a42be0 SL |
108 | } |
109 | ||
9e0c209e | 110 | self.visit_rvalue(rvalue, location); |
92a42be0 SL |
111 | } |
112 | ||
3157f602 XL |
113 | fn visit_terminator_kind(&mut self, |
114 | block: mir::BasicBlock, | |
9e0c209e SL |
115 | kind: &mir::TerminatorKind<'tcx>, |
116 | location: Location) { | |
3157f602 XL |
117 | match *kind { |
118 | mir::TerminatorKind::Call { | |
cc61c64b XL |
119 | func: mir::Operand::Constant(box mir::Constant { |
120 | literal: Literal::Value { | |
ea8adc8c | 121 | value: &ty::Const { val: ConstVal::Function(def_id, _), .. }, .. |
cc61c64b | 122 | }, .. |
3157f602 XL |
123 | }), |
124 | ref args, .. | |
ea8adc8c | 125 | } if Some(def_id) == self.cx.ccx.tcx().lang_items().box_free_fn() => { |
3157f602 XL |
126 | // box_free(x) shares with `drop x` the property that it |
127 | // is not guaranteed to be statically dominated by the | |
128 | // definition of x, so x must always be in an alloca. | |
129 | if let mir::Operand::Consume(ref lvalue) = args[0] { | |
9e0c209e | 130 | self.visit_lvalue(lvalue, LvalueContext::Drop, location); |
3157f602 XL |
131 | } |
132 | } | |
133 | _ => {} | |
134 | } | |
135 | ||
9e0c209e | 136 | self.super_terminator_kind(block, kind, location); |
3157f602 XL |
137 | } |
138 | ||
92a42be0 SL |
139 | fn visit_lvalue(&mut self, |
140 | lvalue: &mir::Lvalue<'tcx>, | |
9e0c209e SL |
141 | context: LvalueContext<'tcx>, |
142 | location: Location) { | |
92a42be0 SL |
143 | debug!("visit_lvalue(lvalue={:?}, context={:?})", lvalue, context); |
144 | ||
3157f602 | 145 | if let mir::Lvalue::Projection(ref proj) = *lvalue { |
ea8adc8c XL |
146 | // Allow uses of projections of immediate pair fields. |
147 | if let LvalueContext::Consume = context { | |
148 | if let mir::Lvalue::Local(_) = proj.base { | |
3157f602 | 149 | if let mir::ProjectionElem::Field(..) = proj.elem { |
ea8adc8c XL |
150 | let ty = proj.base.ty(self.cx.mir, self.cx.ccx.tcx()); |
151 | ||
152 | let ty = self.cx.monomorphize(&ty.to_ty(self.cx.ccx.tcx())); | |
153 | if common::type_is_imm_pair(self.cx.ccx, ty) { | |
3157f602 XL |
154 | return; |
155 | } | |
54a0048b | 156 | } |
3157f602 XL |
157 | } |
158 | } | |
3157f602 | 159 | |
ea8adc8c XL |
160 | // A deref projection only reads the pointer, never needs the lvalue. |
161 | if let mir::ProjectionElem::Deref = proj.elem { | |
162 | return self.visit_lvalue(&proj.base, LvalueContext::Consume, location); | |
163 | } | |
164 | } | |
5bcae85e | 165 | |
ea8adc8c XL |
166 | self.super_lvalue(lvalue, context, location); |
167 | } | |
5bcae85e | 168 | |
ea8adc8c XL |
169 | fn visit_local(&mut self, |
170 | &index: &mir::Local, | |
171 | context: LvalueContext<'tcx>, | |
172 | _: Location) { | |
173 | match context { | |
174 | LvalueContext::Call => { | |
175 | self.mark_assigned(index); | |
176 | } | |
5bcae85e | 177 | |
ea8adc8c XL |
178 | LvalueContext::StorageLive | |
179 | LvalueContext::StorageDead | | |
180 | LvalueContext::Validate | | |
181 | LvalueContext::Inspect | | |
182 | LvalueContext::Consume => {} | |
3157f602 | 183 | |
ea8adc8c XL |
184 | LvalueContext::Store | |
185 | LvalueContext::Borrow { .. } | | |
186 | LvalueContext::Projection(..) => { | |
187 | self.mark_as_lvalue(index); | |
92a42be0 | 188 | } |
3157f602 | 189 | |
ea8adc8c XL |
190 | LvalueContext::Drop => { |
191 | let ty = mir::Lvalue::Local(index).ty(self.cx.mir, self.cx.ccx.tcx()); | |
192 | let ty = self.cx.monomorphize(&ty.to_ty(self.cx.ccx.tcx())); | |
193 | ||
194 | // Only need the lvalue if we're actually dropping it. | |
195 | if self.cx.ccx.shared().type_needs_drop(ty) { | |
196 | self.mark_as_lvalue(index); | |
197 | } | |
92a42be0 SL |
198 | } |
199 | } | |
92a42be0 SL |
200 | } |
201 | } | |
3157f602 XL |
202 | |
203 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] | |
204 | pub enum CleanupKind { | |
205 | NotCleanup, | |
206 | Funclet, | |
207 | Internal { funclet: mir::BasicBlock } | |
208 | } | |
209 | ||
7cac9316 XL |
210 | impl CleanupKind { |
211 | pub fn funclet_bb(self, for_bb: mir::BasicBlock) -> Option<mir::BasicBlock> { | |
212 | match self { | |
213 | CleanupKind::NotCleanup => None, | |
214 | CleanupKind::Funclet => Some(for_bb), | |
215 | CleanupKind::Internal { funclet } => Some(funclet), | |
216 | } | |
217 | } | |
218 | } | |
219 | ||
32a655c1 | 220 | pub fn cleanup_kinds<'a, 'tcx>(mir: &mir::Mir<'tcx>) -> IndexVec<mir::BasicBlock, CleanupKind> { |
3157f602 XL |
221 | fn discover_masters<'tcx>(result: &mut IndexVec<mir::BasicBlock, CleanupKind>, |
222 | mir: &mir::Mir<'tcx>) { | |
223 | for (bb, data) in mir.basic_blocks().iter_enumerated() { | |
224 | match data.terminator().kind { | |
225 | TerminatorKind::Goto { .. } | | |
226 | TerminatorKind::Resume | | |
227 | TerminatorKind::Return | | |
ea8adc8c | 228 | TerminatorKind::GeneratorDrop | |
3157f602 | 229 | TerminatorKind::Unreachable | |
ea8adc8c | 230 | TerminatorKind::SwitchInt { .. } | |
abe05a73 XL |
231 | TerminatorKind::Yield { .. } | |
232 | TerminatorKind::FalseEdges { .. } => { | |
3157f602 XL |
233 | /* nothing to do */ |
234 | } | |
235 | TerminatorKind::Call { cleanup: unwind, .. } | | |
236 | TerminatorKind::Assert { cleanup: unwind, .. } | | |
237 | TerminatorKind::DropAndReplace { unwind, .. } | | |
238 | TerminatorKind::Drop { unwind, .. } => { | |
239 | if let Some(unwind) = unwind { | |
240 | debug!("cleanup_kinds: {:?}/{:?} registering {:?} as funclet", | |
241 | bb, data, unwind); | |
242 | result[unwind] = CleanupKind::Funclet; | |
243 | } | |
244 | } | |
245 | } | |
246 | } | |
247 | } | |
248 | ||
249 | fn propagate<'tcx>(result: &mut IndexVec<mir::BasicBlock, CleanupKind>, | |
250 | mir: &mir::Mir<'tcx>) { | |
251 | let mut funclet_succs = IndexVec::from_elem(None, mir.basic_blocks()); | |
252 | ||
253 | let mut set_successor = |funclet: mir::BasicBlock, succ| { | |
254 | match funclet_succs[funclet] { | |
255 | ref mut s @ None => { | |
256 | debug!("set_successor: updating successor of {:?} to {:?}", | |
257 | funclet, succ); | |
258 | *s = Some(succ); | |
259 | }, | |
260 | Some(s) => if s != succ { | |
261 | span_bug!(mir.span, "funclet {:?} has 2 parents - {:?} and {:?}", | |
262 | funclet, s, succ); | |
263 | } | |
264 | } | |
265 | }; | |
266 | ||
267 | for (bb, data) in traversal::reverse_postorder(mir) { | |
268 | let funclet = match result[bb] { | |
269 | CleanupKind::NotCleanup => continue, | |
270 | CleanupKind::Funclet => bb, | |
271 | CleanupKind::Internal { funclet } => funclet, | |
272 | }; | |
273 | ||
274 | debug!("cleanup_kinds: {:?}/{:?}/{:?} propagating funclet {:?}", | |
275 | bb, data, result[bb], funclet); | |
276 | ||
277 | for &succ in data.terminator().successors().iter() { | |
278 | let kind = result[succ]; | |
279 | debug!("cleanup_kinds: propagating {:?} to {:?}/{:?}", | |
280 | funclet, succ, kind); | |
281 | match kind { | |
282 | CleanupKind::NotCleanup => { | |
283 | result[succ] = CleanupKind::Internal { funclet: funclet }; | |
284 | } | |
285 | CleanupKind::Funclet => { | |
7cac9316 XL |
286 | if funclet != succ { |
287 | set_successor(funclet, succ); | |
288 | } | |
3157f602 XL |
289 | } |
290 | CleanupKind::Internal { funclet: succ_funclet } => { | |
291 | if funclet != succ_funclet { | |
292 | // `succ` has 2 different funclet going into it, so it must | |
293 | // be a funclet by itself. | |
294 | ||
295 | debug!("promoting {:?} to a funclet and updating {:?}", succ, | |
296 | succ_funclet); | |
297 | result[succ] = CleanupKind::Funclet; | |
298 | set_successor(succ_funclet, succ); | |
299 | set_successor(funclet, succ); | |
300 | } | |
301 | } | |
302 | } | |
303 | } | |
304 | } | |
305 | } | |
306 | ||
307 | let mut result = IndexVec::from_elem(CleanupKind::NotCleanup, mir.basic_blocks()); | |
308 | ||
309 | discover_masters(&mut result, mir); | |
310 | propagate(&mut result, mir); | |
311 | debug!("cleanup_kinds: result={:?}", result); | |
312 | result | |
313 | } |