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