1use std::borrow::Cow;
2
3use rustc_data_structures::fx::FxHashSet;
4use rustc_index::IndexVec;
5use rustc_index::bit_set::DenseBitSet;
6use rustc_middle::bug;
7use rustc_middle::mir::visit::*;
8use rustc_middle::mir::*;
9use rustc_middle::ty::TyCtxt;
10use rustc_mir_dataflow::Analysis;
11use rustc_mir_dataflow::impls::{MaybeStorageDead, always_storage_live_locals};
12use tracing::{debug, instrument};
13
14use crate::ssa::{SsaLocals, StorageLiveLocals};
15
16pub(super) struct ReferencePropagation;
73
74impl<'tcx> crate::MirPass<'tcx> for ReferencePropagation {
75 fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
76 sess.mir_opt_level() >= 2
77 }
78
79 #[instrument(level = "trace", skip(self, tcx, body))]
80 fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
81 debug!(def_id = ?body.source.def_id());
82 move_to_copy_pointers(tcx, body);
83 while propagate_ssa(tcx, body) {}
84 }
85
86 fn is_required(&self) -> bool {
87 false
88 }
89}
90
91fn move_to_copy_pointers<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
97 let mut visitor = MoveToCopyVisitor { tcx, local_decls: &body.local_decls };
98 for (bb, data) in body.basic_blocks.as_mut_preserves_cfg().iter_enumerated_mut() {
99 visitor.visit_basic_block_data(bb, data);
100 }
101
102 struct MoveToCopyVisitor<'a, 'tcx> {
103 tcx: TyCtxt<'tcx>,
104 local_decls: &'a IndexVec<Local, LocalDecl<'tcx>>,
105 }
106
107 impl<'a, 'tcx> MutVisitor<'tcx> for MoveToCopyVisitor<'a, 'tcx> {
108 fn tcx(&self) -> TyCtxt<'tcx> {
109 self.tcx
110 }
111
112 fn visit_operand(&mut self, operand: &mut Operand<'tcx>, loc: Location) {
113 if let Operand::Move(place) = *operand {
114 if place.ty(self.local_decls, self.tcx).ty.is_any_ptr() {
115 *operand = Operand::Copy(place);
116 }
117 }
118 self.super_operand(operand, loc);
119 }
120 }
121}
122
123fn propagate_ssa<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) -> bool {
124 let typing_env = body.typing_env(tcx);
125 let ssa = SsaLocals::new(tcx, body, typing_env);
126
127 let mut replacer = compute_replacement(tcx, body, ssa);
128 debug!(?replacer.targets);
129 debug!(?replacer.allowed_replacements);
130 debug!(?replacer.storage_to_remove);
131
132 replacer.visit_body_preserves_cfg(body);
133
134 if replacer.any_replacement {
135 crate::simplify::remove_unused_definitions(body);
136 }
137
138 replacer.any_replacement
139}
140
141#[derive(Copy, Clone, Debug, PartialEq, Eq)]
142enum Value<'tcx> {
143 Unknown,
145 Pointer(Place<'tcx>, bool),
148}
149
150#[instrument(level = "trace", skip(tcx, body, ssa))]
152fn compute_replacement<'tcx>(
153 tcx: TyCtxt<'tcx>,
154 body: &Body<'tcx>,
155 ssa: SsaLocals,
156) -> Replacer<'tcx> {
157 let always_live_locals = always_storage_live_locals(body);
158
159 let storage_live = StorageLiveLocals::new(body, &always_live_locals);
161
162 let mut maybe_dead = MaybeStorageDead::new(Cow::Owned(always_live_locals))
165 .iterate_to_fixpoint(tcx, body, None)
166 .into_results_cursor(body);
167
168 let mut targets = IndexVec::from_elem(Value::Unknown, &body.local_decls);
170 let mut storage_to_remove = DenseBitSet::new_empty(body.local_decls.len());
173
174 let fully_replaceable_locals = fully_replaceable_locals(&ssa);
175
176 let is_constant_place = |place: Place<'_>| {
197 if let Some((&PlaceElem::Deref, rest)) = place.projection.split_first() {
199 ssa.is_ssa(place.local) && rest.iter().all(PlaceElem::is_stable_offset)
202 } else {
203 storage_live.has_single_storage(place.local)
204 && place.projection[..].iter().all(PlaceElem::is_stable_offset)
205 }
206 };
207
208 let mut can_perform_opt = |target: Place<'tcx>, loc: Location| {
209 if target.is_indirect_first_projection() {
210 storage_to_remove.insert(target.local);
213 true
214 } else {
215 maybe_dead.seek_after_primary_effect(loc);
217 let maybe_dead = maybe_dead.get().contains(target.local);
218 !maybe_dead
219 }
220 };
221
222 for (local, rvalue, location) in ssa.assignments(body) {
223 debug!(?local);
224
225 let Value::Unknown = targets[local] else { bug!() };
227
228 let ty = body.local_decls[local].ty;
229
230 if !ty.is_any_ptr() {
232 debug!("not a reference or pointer");
233 continue;
234 }
235
236 let needs_unique = ty.is_mutable_ptr();
238
239 if needs_unique && !fully_replaceable_locals.contains(local) {
241 debug!("not fully replaceable");
242 continue;
243 }
244
245 debug!(?rvalue);
246 match rvalue {
247 Rvalue::Use(Operand::Copy(place) | Operand::Move(place)) => {
251 if let Some(rhs) = place.as_local()
252 && ssa.is_ssa(rhs)
253 {
254 let target = targets[rhs];
255 if !needs_unique && matches!(target, Value::Pointer(..)) {
258 targets[local] = target;
259 } else {
260 targets[local] =
261 Value::Pointer(tcx.mk_place_deref(rhs.into()), needs_unique);
262 }
263 }
264 }
265 Rvalue::Ref(_, _, place) | Rvalue::RawPtr(_, place) => {
266 let mut place = *place;
267 if let Some((&PlaceElem::Deref, rest)) = place.projection.split_first()
269 && let Value::Pointer(target, inner_needs_unique) = targets[place.local]
270 && !inner_needs_unique
273 && can_perform_opt(target, location)
275 {
276 place = target.project_deeper(rest, tcx);
277 }
278 assert_ne!(place.local, local);
279 if is_constant_place(place) {
280 targets[local] = Value::Pointer(place, needs_unique);
281 }
282 }
283 _ => {}
285 }
286 }
287
288 debug!(?targets);
289
290 let mut finder =
291 ReplacementFinder { targets, can_perform_opt, allowed_replacements: FxHashSet::default() };
292 let reachable_blocks = traversal::reachable_as_bitset(body);
293 for (bb, bbdata) in body.basic_blocks.iter_enumerated() {
294 if reachable_blocks.contains(bb) {
296 finder.visit_basic_block_data(bb, bbdata);
297 }
298 }
299
300 let allowed_replacements = finder.allowed_replacements;
301 return Replacer {
302 tcx,
303 targets: finder.targets,
304 remap_var_debug_infos: IndexVec::from_elem(None, body.local_decls()),
305 storage_to_remove,
306 allowed_replacements,
307 any_replacement: false,
308 };
309
310 struct ReplacementFinder<'tcx, F> {
311 targets: IndexVec<Local, Value<'tcx>>,
312 can_perform_opt: F,
313 allowed_replacements: FxHashSet<(Local, Location)>,
314 }
315
316 impl<'tcx, F> Visitor<'tcx> for ReplacementFinder<'tcx, F>
317 where
318 F: FnMut(Place<'tcx>, Location) -> bool,
319 {
320 fn visit_place(&mut self, place: &Place<'tcx>, ctxt: PlaceContext, loc: Location) {
321 if matches!(ctxt, PlaceContext::NonUse(_)) {
322 return;
324 }
325
326 if !place.is_indirect_first_projection() {
327 return;
329 }
330
331 let mut place = place.as_ref();
332 loop {
333 if let Value::Pointer(target, needs_unique) = self.targets[place.local] {
334 let perform_opt = (self.can_perform_opt)(target, loc);
335 debug!(?place, ?target, ?needs_unique, ?perform_opt);
336
337 if let &[PlaceElem::Deref] = &target.projection[..] {
342 assert!(perform_opt);
343 self.allowed_replacements.insert((target.local, loc));
344 place.local = target.local;
345 continue;
346 } else if perform_opt {
347 self.allowed_replacements.insert((target.local, loc));
348 } else if needs_unique {
349 self.targets[place.local] = Value::Unknown;
351 }
352 }
353
354 break;
355 }
356 }
357 }
358}
359
360fn fully_replaceable_locals(ssa: &SsaLocals) -> DenseBitSet<Local> {
365 let mut replaceable = DenseBitSet::new_empty(ssa.num_locals());
366
367 for local in ssa.locals() {
369 if ssa.num_direct_uses(local) == 0 {
370 replaceable.insert(local);
371 }
372 }
373
374 ssa.meet_copy_equivalence(&mut replaceable);
376
377 replaceable
378}
379
380struct Replacer<'tcx> {
382 tcx: TyCtxt<'tcx>,
383 targets: IndexVec<Local, Value<'tcx>>,
384 remap_var_debug_infos: IndexVec<Local, Option<Local>>,
385 storage_to_remove: DenseBitSet<Local>,
386 allowed_replacements: FxHashSet<(Local, Location)>,
387 any_replacement: bool,
388}
389
390impl<'tcx> MutVisitor<'tcx> for Replacer<'tcx> {
391 fn tcx(&self) -> TyCtxt<'tcx> {
392 self.tcx
393 }
394
395 fn visit_var_debug_info(&mut self, debuginfo: &mut VarDebugInfo<'tcx>) {
396 if let VarDebugInfoContents::Place(ref mut place) = debuginfo.value
397 && place.projection.is_empty()
398 {
399 let mut new_local = place.local;
400
401 while let Value::Pointer(target, _) = self.targets[new_local]
404 && let &[PlaceElem::Deref] = &target.projection[..]
405 {
406 new_local = target.local;
407 }
408 if place.local != new_local {
409 self.remap_var_debug_infos[place.local] = Some(new_local);
410 place.local = new_local;
411
412 self.any_replacement = true;
413 }
414 }
415
416 self.super_var_debug_info(debuginfo);
418 }
419
420 fn visit_statement_debuginfo(
421 &mut self,
422 stmt_debuginfo: &mut StmtDebugInfo<'tcx>,
423 location: Location,
424 ) {
425 let local = match stmt_debuginfo {
426 StmtDebugInfo::AssignRef(local, _) | StmtDebugInfo::InvalidAssign(local) => local,
427 };
428 if let Some(target) = self.remap_var_debug_infos[*local] {
429 *local = target;
430 self.any_replacement = true;
431 }
432 self.super_statement_debuginfo(stmt_debuginfo, location);
433 }
434
435 fn visit_place(&mut self, place: &mut Place<'tcx>, ctxt: PlaceContext, loc: Location) {
436 loop {
437 let Some((&PlaceElem::Deref, rest)) = place.projection.split_first() else { return };
438
439 let Value::Pointer(target, _) = self.targets[place.local] else { return };
440
441 let perform_opt = match ctxt {
442 PlaceContext::NonUse(NonUseContext::VarDebugInfo) => {
443 target.projection.iter().all(|p| p.can_use_in_debuginfo())
444 }
445 PlaceContext::NonUse(_) => true,
446 _ => self.allowed_replacements.contains(&(target.local, loc)),
447 };
448
449 if !perform_opt {
450 return;
451 }
452
453 *place = target.project_deeper(rest, self.tcx);
454 self.any_replacement = true;
455 }
456 }
457
458 fn visit_statement(&mut self, stmt: &mut Statement<'tcx>, loc: Location) {
459 match stmt.kind {
460 StatementKind::StorageLive(l) | StatementKind::StorageDead(l)
461 if self.storage_to_remove.contains(l) =>
462 {
463 stmt.make_nop(true);
464 }
465 _ => {}
466 }
467 self.super_statement(stmt, loc);
469 }
470}