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