]>
Commit | Line | Data |
---|---|---|
9e0c209e SL |
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 | //! Trivial copy propagation pass. | |
12 | //! | |
13 | //! This uses def-use analysis to remove values that have exactly one def and one use, which must | |
14 | //! be an assignment. | |
15 | //! | |
16 | //! To give an example, we look for patterns that look like: | |
17 | //! | |
18 | //! DEST = SRC | |
19 | //! ... | |
20 | //! USE(DEST) | |
21 | //! | |
22 | //! where `DEST` and `SRC` are both locals of some form. We replace that with: | |
23 | //! | |
24 | //! NOP | |
25 | //! ... | |
26 | //! USE(SRC) | |
27 | //! | |
28 | //! The assignment `DEST = SRC` must be (a) the only mutation of `DEST` and (b) the only | |
29 | //! (non-mutating) use of `SRC`. These restrictions are conservative and may be relaxed in the | |
30 | //! future. | |
31 | ||
abe05a73 | 32 | use rustc::hir; |
476ff2be | 33 | use rustc::mir::{Constant, Local, LocalKind, Location, Lvalue, Mir, Operand, Rvalue, StatementKind}; |
9e0c209e SL |
34 | use rustc::mir::visit::MutVisitor; |
35 | use rustc::ty::TyCtxt; | |
abe05a73 | 36 | use transform::{MirPass, MirSource}; |
cc61c64b | 37 | use util::def_use::DefUseAnalysis; |
9e0c209e SL |
38 | |
39 | pub struct CopyPropagation; | |
40 | ||
7cac9316 XL |
41 | impl MirPass for CopyPropagation { |
42 | fn run_pass<'a, 'tcx>(&self, | |
43 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
44 | source: MirSource, | |
45 | mir: &mut Mir<'tcx>) { | |
abe05a73 XL |
46 | // Don't run on constant MIR, because trans might not be able to |
47 | // evaluate the modified MIR. | |
48 | // FIXME(eddyb) Remove check after miri is merged. | |
49 | let id = tcx.hir.as_local_node_id(source.def_id).unwrap(); | |
50 | match (tcx.hir.body_owner_kind(id), source.promoted) { | |
51 | (_, Some(_)) | | |
52 | (hir::BodyOwnerKind::Const, _) | | |
53 | (hir::BodyOwnerKind::Static(_), _) => return, | |
54 | ||
55 | (hir::BodyOwnerKind::Fn, _) => { | |
56 | if tcx.is_const_fn(source.def_id) { | |
9e0c209e SL |
57 | // Don't run on const functions, as, again, trans might not be able to evaluate |
58 | // the optimized IR. | |
59 | return | |
60 | } | |
61 | } | |
62 | } | |
63 | ||
476ff2be SL |
64 | // We only run when the MIR optimization level is > 1. |
65 | // This avoids a slow pass, and messing up debug info. | |
66 | if tcx.sess.opts.debugging_opts.mir_opt_level <= 1 { | |
67 | return; | |
9e0c209e SL |
68 | } |
69 | ||
abe05a73 | 70 | let mut def_use_analysis = DefUseAnalysis::new(mir); |
9e0c209e | 71 | loop { |
9e0c209e SL |
72 | def_use_analysis.analyze(mir); |
73 | ||
abe05a73 XL |
74 | if eliminate_self_assignments(mir, &def_use_analysis) { |
75 | def_use_analysis.analyze(mir); | |
76 | } | |
77 | ||
9e0c209e | 78 | let mut changed = false; |
c30ab7b3 SL |
79 | for dest_local in mir.local_decls.indices() { |
80 | debug!("Considering destination local: {:?}", dest_local); | |
9e0c209e SL |
81 | |
82 | let action; | |
83 | let location; | |
84 | { | |
85 | // The destination must have exactly one def. | |
86 | let dest_use_info = def_use_analysis.local_info(dest_local); | |
87 | let dest_def_count = dest_use_info.def_count_not_including_drop(); | |
88 | if dest_def_count == 0 { | |
c30ab7b3 SL |
89 | debug!(" Can't copy-propagate local: dest {:?} undefined", |
90 | dest_local); | |
9e0c209e SL |
91 | continue |
92 | } | |
93 | if dest_def_count > 1 { | |
c30ab7b3 SL |
94 | debug!(" Can't copy-propagate local: dest {:?} defined {} times", |
95 | dest_local, | |
9e0c209e SL |
96 | dest_use_info.def_count()); |
97 | continue | |
98 | } | |
99 | if dest_use_info.use_count() == 0 { | |
c30ab7b3 SL |
100 | debug!(" Can't copy-propagate local: dest {:?} unused", |
101 | dest_local); | |
9e0c209e SL |
102 | continue |
103 | } | |
abe05a73 XL |
104 | // Conservatively gives up if the dest is an argument, |
105 | // because there may be uses of the original argument value. | |
106 | if mir.local_kind(dest_local) == LocalKind::Arg { | |
107 | debug!(" Can't copy-propagate local: dest {:?} (argument)", | |
108 | dest_local); | |
109 | continue; | |
110 | } | |
111 | let dest_lvalue_def = dest_use_info.defs_not_including_drop().next().unwrap(); | |
9e0c209e SL |
112 | location = dest_lvalue_def.location; |
113 | ||
114 | let basic_block = &mir[location.block]; | |
115 | let statement_index = location.statement_index; | |
116 | let statement = match basic_block.statements.get(statement_index) { | |
117 | Some(statement) => statement, | |
118 | None => { | |
119 | debug!(" Can't copy-propagate local: used in terminator"); | |
120 | continue | |
121 | } | |
122 | }; | |
123 | ||
124 | // That use of the source must be an assignment. | |
125 | match statement.kind { | |
c30ab7b3 SL |
126 | StatementKind::Assign(Lvalue::Local(local), Rvalue::Use(ref operand)) if |
127 | local == dest_local => { | |
9e0c209e SL |
128 | let maybe_action = match *operand { |
129 | Operand::Consume(ref src_lvalue) => { | |
476ff2be | 130 | Action::local_copy(&mir, &def_use_analysis, src_lvalue) |
9e0c209e SL |
131 | } |
132 | Operand::Constant(ref src_constant) => { | |
133 | Action::constant(src_constant) | |
134 | } | |
135 | }; | |
136 | match maybe_action { | |
137 | Some(this_action) => action = this_action, | |
138 | None => continue, | |
139 | } | |
140 | } | |
141 | _ => { | |
142 | debug!(" Can't copy-propagate local: source use is not an \ | |
143 | assignment"); | |
144 | continue | |
145 | } | |
146 | } | |
147 | } | |
148 | ||
149 | changed = action.perform(mir, &def_use_analysis, dest_local, location) || changed; | |
150 | // FIXME(pcwalton): Update the use-def chains to delete the instructions instead of | |
151 | // regenerating the chains. | |
152 | break | |
153 | } | |
154 | if !changed { | |
155 | break | |
156 | } | |
157 | } | |
158 | } | |
159 | } | |
160 | ||
abe05a73 XL |
161 | fn eliminate_self_assignments<'tcx>( |
162 | mir: &mut Mir<'tcx>, | |
163 | def_use_analysis: &DefUseAnalysis<'tcx>, | |
164 | ) -> bool { | |
165 | let mut changed = false; | |
166 | ||
167 | for dest_local in mir.local_decls.indices() { | |
168 | let dest_use_info = def_use_analysis.local_info(dest_local); | |
169 | ||
170 | for def in dest_use_info.defs_not_including_drop() { | |
171 | let location = def.location; | |
172 | if let Some(stmt) = mir[location.block].statements.get(location.statement_index) { | |
173 | match stmt.kind { | |
174 | StatementKind::Assign( | |
175 | Lvalue::Local(local), | |
176 | Rvalue::Use(Operand::Consume(Lvalue::Local(src_local))), | |
177 | ) if local == dest_local && dest_local == src_local => {} | |
178 | _ => { | |
179 | continue; | |
180 | } | |
181 | } | |
182 | } else { | |
183 | continue; | |
184 | } | |
185 | debug!("Deleting a self-assignment for {:?}", dest_local); | |
186 | mir.make_statement_nop(location); | |
187 | changed = true; | |
188 | } | |
189 | } | |
190 | ||
191 | changed | |
192 | } | |
193 | ||
9e0c209e SL |
194 | enum Action<'tcx> { |
195 | PropagateLocalCopy(Local), | |
196 | PropagateConstant(Constant<'tcx>), | |
197 | } | |
198 | ||
199 | impl<'tcx> Action<'tcx> { | |
476ff2be | 200 | fn local_copy(mir: &Mir<'tcx>, def_use_analysis: &DefUseAnalysis, src_lvalue: &Lvalue<'tcx>) |
9e0c209e SL |
201 | -> Option<Action<'tcx>> { |
202 | // The source must be a local. | |
c30ab7b3 SL |
203 | let src_local = if let Lvalue::Local(local) = *src_lvalue { |
204 | local | |
205 | } else { | |
206 | debug!(" Can't copy-propagate local: source is not a local"); | |
207 | return None; | |
9e0c209e SL |
208 | }; |
209 | ||
210 | // We're trying to copy propagate a local. | |
211 | // There must be exactly one use of the source used in a statement (not in a terminator). | |
212 | let src_use_info = def_use_analysis.local_info(src_local); | |
213 | let src_use_count = src_use_info.use_count(); | |
214 | if src_use_count == 0 { | |
215 | debug!(" Can't copy-propagate local: no uses"); | |
216 | return None | |
217 | } | |
218 | if src_use_count != 1 { | |
219 | debug!(" Can't copy-propagate local: {} uses", src_use_info.use_count()); | |
220 | return None | |
221 | } | |
222 | ||
223 | // Verify that the source doesn't change in between. This is done conservatively for now, | |
224 | // by ensuring that the source has exactly one mutation. The goal is to prevent things | |
225 | // like: | |
226 | // | |
227 | // DEST = SRC; | |
228 | // SRC = X; | |
229 | // USE(DEST); | |
230 | // | |
231 | // From being misoptimized into: | |
232 | // | |
233 | // SRC = X; | |
234 | // USE(SRC); | |
235 | let src_def_count = src_use_info.def_count_not_including_drop(); | |
476ff2be SL |
236 | // allow function arguments to be propagated |
237 | if src_def_count > 1 || | |
238 | (src_def_count == 0 && mir.local_kind(src_local) != LocalKind::Arg) { | |
9e0c209e SL |
239 | debug!(" Can't copy-propagate local: {} defs of src", |
240 | src_use_info.def_count_not_including_drop()); | |
241 | return None | |
242 | } | |
243 | ||
244 | Some(Action::PropagateLocalCopy(src_local)) | |
245 | } | |
246 | ||
247 | fn constant(src_constant: &Constant<'tcx>) -> Option<Action<'tcx>> { | |
248 | Some(Action::PropagateConstant((*src_constant).clone())) | |
249 | } | |
250 | ||
251 | fn perform(self, | |
252 | mir: &mut Mir<'tcx>, | |
253 | def_use_analysis: &DefUseAnalysis<'tcx>, | |
254 | dest_local: Local, | |
255 | location: Location) | |
256 | -> bool { | |
257 | match self { | |
258 | Action::PropagateLocalCopy(src_local) => { | |
259 | // Eliminate the destination and the assignment. | |
260 | // | |
261 | // First, remove all markers. | |
262 | // | |
263 | // FIXME(pcwalton): Don't do this. Merge live ranges instead. | |
c30ab7b3 SL |
264 | debug!(" Replacing all uses of {:?} with {:?} (local)", |
265 | dest_local, | |
266 | src_local); | |
9e0c209e SL |
267 | for lvalue_use in &def_use_analysis.local_info(dest_local).defs_and_uses { |
268 | if lvalue_use.context.is_storage_marker() { | |
269 | mir.make_statement_nop(lvalue_use.location) | |
270 | } | |
271 | } | |
272 | for lvalue_use in &def_use_analysis.local_info(src_local).defs_and_uses { | |
273 | if lvalue_use.context.is_storage_marker() { | |
274 | mir.make_statement_nop(lvalue_use.location) | |
275 | } | |
276 | } | |
277 | ||
278 | // Replace all uses of the destination local with the source local. | |
ea8adc8c | 279 | def_use_analysis.replace_all_defs_and_uses_with(dest_local, mir, src_local); |
9e0c209e SL |
280 | |
281 | // Finally, zap the now-useless assignment instruction. | |
282 | debug!(" Deleting assignment"); | |
283 | mir.make_statement_nop(location); | |
284 | ||
285 | true | |
286 | } | |
287 | Action::PropagateConstant(src_constant) => { | |
288 | // First, remove all markers. | |
289 | // | |
290 | // FIXME(pcwalton): Don't do this. Merge live ranges instead. | |
c30ab7b3 SL |
291 | debug!(" Replacing all uses of {:?} with {:?} (constant)", |
292 | dest_local, | |
9e0c209e SL |
293 | src_constant); |
294 | let dest_local_info = def_use_analysis.local_info(dest_local); | |
295 | for lvalue_use in &dest_local_info.defs_and_uses { | |
296 | if lvalue_use.context.is_storage_marker() { | |
297 | mir.make_statement_nop(lvalue_use.location) | |
298 | } | |
299 | } | |
300 | ||
301 | // Replace all uses of the destination local with the constant. | |
c30ab7b3 | 302 | let mut visitor = ConstantPropagationVisitor::new(dest_local, |
9e0c209e SL |
303 | src_constant); |
304 | for dest_lvalue_use in &dest_local_info.defs_and_uses { | |
305 | visitor.visit_location(mir, dest_lvalue_use.location) | |
306 | } | |
307 | ||
308 | // Zap the assignment instruction if we eliminated all the uses. We won't have been | |
309 | // able to do that if the destination was used in a projection, because projections | |
310 | // must have lvalues on their LHS. | |
311 | let use_count = dest_local_info.use_count(); | |
312 | if visitor.uses_replaced == use_count { | |
313 | debug!(" {} of {} use(s) replaced; deleting assignment", | |
314 | visitor.uses_replaced, | |
315 | use_count); | |
316 | mir.make_statement_nop(location); | |
317 | true | |
318 | } else if visitor.uses_replaced == 0 { | |
319 | debug!(" No uses replaced; not deleting assignment"); | |
320 | false | |
321 | } else { | |
322 | debug!(" {} of {} use(s) replaced; not deleting assignment", | |
323 | visitor.uses_replaced, | |
324 | use_count); | |
325 | true | |
326 | } | |
327 | } | |
328 | } | |
329 | } | |
330 | } | |
331 | ||
332 | struct ConstantPropagationVisitor<'tcx> { | |
333 | dest_local: Local, | |
334 | constant: Constant<'tcx>, | |
9e0c209e SL |
335 | uses_replaced: usize, |
336 | } | |
337 | ||
338 | impl<'tcx> ConstantPropagationVisitor<'tcx> { | |
c30ab7b3 | 339 | fn new(dest_local: Local, constant: Constant<'tcx>) |
9e0c209e SL |
340 | -> ConstantPropagationVisitor<'tcx> { |
341 | ConstantPropagationVisitor { | |
3b2f2976 XL |
342 | dest_local, |
343 | constant, | |
9e0c209e SL |
344 | uses_replaced: 0, |
345 | } | |
346 | } | |
347 | } | |
348 | ||
349 | impl<'tcx> MutVisitor<'tcx> for ConstantPropagationVisitor<'tcx> { | |
350 | fn visit_operand(&mut self, operand: &mut Operand<'tcx>, location: Location) { | |
351 | self.super_operand(operand, location); | |
352 | ||
353 | match *operand { | |
c30ab7b3 SL |
354 | Operand::Consume(Lvalue::Local(local)) if local == self.dest_local => {} |
355 | _ => return, | |
9e0c209e SL |
356 | } |
357 | ||
cc61c64b | 358 | *operand = Operand::Constant(box self.constant.clone()); |
9e0c209e SL |
359 | self.uses_replaced += 1 |
360 | } | |
361 | } |