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