1 //! Propagates assignment destinations backwards in the CFG to eliminate redundant assignments.
5 //! MIR building can insert a lot of redundant copies, and Rust code in general often tends to move
6 //! values around a lot. The result is a lot of assignments of the form `dest = {move} src;` in MIR.
7 //! MIR building for constants in particular tends to create additional locals that are only used
8 //! inside a single block to shuffle a value around unnecessarily.
10 //! LLVM by itself is not good enough at eliminating these redundant copies (eg. see
11 //! <https://github.com/rust-lang/rust/issues/32966>), so this leaves some performance on the table
12 //! that we can regain by implementing an optimization for removing these assign statements in rustc
13 //! itself. When this optimization runs fast enough, it can also speed up the constant evaluation
14 //! and code generation phases of rustc due to the reduced number of statements and locals.
16 //! # The Optimization
18 //! Conceptually, this optimization is "destination propagation". It is similar to the Named Return
19 //! Value Optimization, or NRVO, known from the C++ world, except that it isn't limited to return
20 //! values or the return place `_0`. On a very high level, independent of the actual implementation
21 //! details, it does the following:
23 //! 1) Identify `dest = src;` statements that can be soundly eliminated.
24 //! 2) Replace all mentions of `src` with `dest` ("unifying" them and propagating the destination
26 //! 3) Delete the `dest = src;` statement (by making it a `nop`).
28 //! Step 1) is by far the hardest, so it is explained in more detail below.
32 //! Given an `Assign` statement `dest = src;`, where `dest` is a `Place` and `src` is an `Rvalue`,
33 //! there are a few requirements that must hold for the optimization to be sound:
35 //! * `dest` must not contain any *indirection* through a pointer. It must access part of the base
36 //! local. Otherwise it might point to arbitrary memory that is hard to track.
38 //! It must also not contain any indexing projections, since those take an arbitrary `Local` as
39 //! the index, and that local might only be initialized shortly before `dest` is used.
41 //! * `src` must be a bare `Local` without any indirections or field projections (FIXME: Is this a
42 //! fundamental restriction or just current impl state?). It can be copied or moved by the
45 //! * The `dest` and `src` locals must never be [*live*][liveness] at the same time. If they are, it
46 //! means that they both hold a (potentially different) value that is needed by a future use of
47 //! the locals. Unifying them would overwrite one of the values.
49 //! Note that computing liveness of locals that have had their address taken is more difficult:
50 //! Short of doing full escape analysis on the address/pointer/reference, the pass would need to
51 //! assume that any operation that can potentially involve opaque user code (such as function
52 //! calls, destructors, and inline assembly) may access any local that had its address taken
53 //! before that point.
55 //! Here, the first two conditions are simple structural requirements on the `Assign` statements
56 //! that can be trivially checked. The liveness requirement however is more difficult and costly to
61 //! A [previous attempt] at implementing an optimization like this turned out to be a significant
62 //! regression in compiler performance. Fixing the regressions introduced a lot of undesirable
63 //! complexity to the implementation.
65 //! A [subsequent approach] tried to avoid the costly computation by limiting itself to acyclic
66 //! CFGs, but still turned out to be far too costly to run due to suboptimal performance within
67 //! individual basic blocks, requiring a walk across the entire block for every assignment found
68 //! within the block. For the `tuple-stress` benchmark, which has 458745 statements in a single
69 //! block, this proved to be far too costly.
71 //! Since the first attempt at this, the compiler has improved dramatically, and new analysis
72 //! frameworks have been added that should make this approach viable without requiring a limited
73 //! approach that only works for some classes of CFGs:
74 //! - rustc now has a powerful dataflow analysis framework that can handle forwards and backwards
75 //! analyses efficiently.
76 //! - Layout optimizations for generators have been added to improve code generation for
77 //! async/await, which are very similar in spirit to what this optimization does. Both walk the
78 //! MIR and record conflicting uses of locals in a `BitMatrix`.
80 //! Also, rustc now has a simple NRVO pass (see `nrvo.rs`), which handles a subset of the cases that
81 //! this destination propagation pass handles, proving that similar optimizations can be performed
84 //! ## Pre/Post Optimization
86 //! It is recommended to run `SimplifyCfg` and then `SimplifyLocals` some time after this pass, as
87 //! it replaces the eliminated assign statements with `nop`s and leaves unused locals behind.
89 //! [liveness]: https://en.wikipedia.org/wiki/Live_variable_analysis
90 //! [previous attempt]: https://github.com/rust-lang/rust/pull/47954
91 //! [subsequent approach]: https://github.com/rust-lang/rust/pull/71003
94 use itertools::Itertools;
95 use rustc_data_structures::unify::{InPlaceUnificationTable, UnifyKey};
97 bit_set::{BitMatrix, BitSet},
100 use rustc_middle::mir::visit::{MutVisitor, PlaceContext, Visitor};
101 use rustc_middle::mir::{dump_mir, PassWhere};
102 use rustc_middle::mir::{
103 traversal, Body, InlineAsmOperand, Local, LocalKind, Location, Operand, Place, PlaceElem,
104 Rvalue, Statement, StatementKind, Terminator, TerminatorKind,
106 use rustc_middle::ty::TyCtxt;
107 use rustc_mir_dataflow::impls::{borrowed_locals, MaybeInitializedLocals, MaybeLiveLocals};
108 use rustc_mir_dataflow::Analysis;
110 // Empirical measurements have resulted in some observations:
111 // - Running on a body with a single block and 500 locals takes barely any time
112 // - Running on a body with ~400 blocks and ~300 relevant locals takes "too long"
113 // ...so we just limit both to somewhat reasonable-ish looking values.
114 const MAX_LOCALS: usize = 500;
115 const MAX_BLOCKS: usize = 250;
117 pub struct DestinationPropagation;
119 impl<'tcx> MirPass<'tcx> for DestinationPropagation {
120 fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
121 // FIXME(#79191, #82678): This is unsound.
123 // Only run at mir-opt-level=3 or higher for now (we don't fix up debuginfo and remove
124 // storage statements at the moment).
125 sess.opts.unstable_opts.unsound_mir_opts && sess.mir_opt_level() >= 3
128 fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
129 let def_id = body.source.def_id();
131 let candidates = find_candidates(body);
132 if candidates.is_empty() {
133 debug!("{:?}: no dest prop candidates, done", def_id);
137 // Collect all locals we care about. We only compute conflicts for these to save time.
138 let mut relevant_locals = BitSet::new_empty(body.local_decls.len());
139 for CandidateAssignment { dest, src, loc: _ } in &candidates {
140 relevant_locals.insert(dest.local);
141 relevant_locals.insert(*src);
144 // This pass unfortunately has `O(l² * s)` performance, where `l` is the number of locals
145 // and `s` is the number of statements and terminators in the function.
146 // To prevent blowing up compile times too much, we bail out when there are too many locals.
147 let relevant = relevant_locals.count();
149 "{:?}: {} locals ({} relevant), {} blocks",
151 body.local_decls.len(),
153 body.basic_blocks.len()
155 if relevant > MAX_LOCALS {
157 "too many candidate locals in {:?} ({}, max is {}), not optimizing",
158 def_id, relevant, MAX_LOCALS
162 if body.basic_blocks.len() > MAX_BLOCKS {
164 "too many blocks in {:?} ({}, max is {}), not optimizing",
166 body.basic_blocks.len(),
172 let mut conflicts = Conflicts::build(tcx, body, &relevant_locals);
174 let mut replacements = Replacements::new(body.local_decls.len());
175 for candidate @ CandidateAssignment { dest, src, loc } in candidates {
176 // Merge locals that don't conflict.
177 if !conflicts.can_unify(dest.local, src) {
178 debug!("at assignment {:?}, conflict {:?} vs. {:?}", loc, dest.local, src);
182 if replacements.for_src(candidate.src).is_some() {
183 debug!("src {:?} already has replacement", candidate.src);
187 if !tcx.consider_optimizing(|| {
188 format!("DestinationPropagation {:?} {:?}", def_id, candidate)
193 replacements.push(candidate);
194 conflicts.unify(candidate.src, candidate.dest.local);
197 replacements.flatten(tcx);
199 debug!("replacements {:?}", replacements.map);
201 Replacer { tcx, replacements, place_elem_cache: Vec::new() }.visit_body(body);
203 // FIXME fix debug info
207 #[derive(Debug, Eq, PartialEq, Copy, Clone)]
208 struct UnifyLocal(Local);
210 impl From<Local> for UnifyLocal {
211 fn from(l: Local) -> Self {
216 impl UnifyKey for UnifyLocal {
219 fn index(&self) -> u32 {
223 fn from_index(u: u32) -> Self {
224 Self(Local::from_u32(u))
226 fn tag() -> &'static str {
231 struct Replacements<'tcx> {
232 /// Maps locals to their replacement.
233 map: IndexVec<Local, Option<Place<'tcx>>>,
235 /// Whose locals' live ranges to kill.
239 impl<'tcx> Replacements<'tcx> {
240 fn new(locals: usize) -> Self {
241 Self { map: IndexVec::from_elem_n(None, locals), kill: BitSet::new_empty(locals) }
244 fn push(&mut self, candidate: CandidateAssignment<'tcx>) {
245 trace!("Replacements::push({:?})", candidate);
246 let entry = &mut self.map[candidate.src];
247 assert!(entry.is_none());
249 *entry = Some(candidate.dest);
250 self.kill.insert(candidate.src);
251 self.kill.insert(candidate.dest.local);
254 /// Applies the stored replacements to all replacements, until no replacements would result in
255 /// locals that need further replacements when applied.
256 fn flatten(&mut self, tcx: TyCtxt<'tcx>) {
257 // Note: This assumes that there are no cycles in the replacements, which is enforced via
258 // `self.unified_locals`. Otherwise this can cause an infinite loop.
260 for local in self.map.indices() {
261 if let Some(replacement) = self.map[local] {
262 // Substitute the base local of `replacement` until fixpoint.
263 let mut base = replacement.local;
264 let mut reversed_projection_slices = Vec::with_capacity(1);
265 while let Some(replacement_for_replacement) = self.map[base] {
266 base = replacement_for_replacement.local;
267 reversed_projection_slices.push(replacement_for_replacement.projection);
270 let projection: Vec<_> = reversed_projection_slices
273 .flat_map(|projs| projs.iter())
274 .chain(replacement.projection.iter())
276 let projection = tcx.intern_place_elems(&projection);
278 // Replace with the final `Place`.
279 self.map[local] = Some(Place { local: base, projection });
284 fn for_src(&self, src: Local) -> Option<Place<'tcx>> {
289 struct Replacer<'tcx> {
291 replacements: Replacements<'tcx>,
292 place_elem_cache: Vec<PlaceElem<'tcx>>,
295 impl<'tcx> MutVisitor<'tcx> for Replacer<'tcx> {
296 fn tcx(&self) -> TyCtxt<'tcx> {
300 fn visit_local(&mut self, local: &mut Local, context: PlaceContext, location: Location) {
301 if context.is_use() && self.replacements.for_src(*local).is_some() {
303 "use of local {:?} should have been replaced by visit_place; context={:?}, loc={:?}",
311 fn visit_place(&mut self, place: &mut Place<'tcx>, context: PlaceContext, location: Location) {
312 if let Some(replacement) = self.replacements.for_src(place.local) {
313 // Rebase `place`s projections onto `replacement`'s.
314 self.place_elem_cache.clear();
315 self.place_elem_cache.extend(replacement.projection.iter().chain(place.projection));
316 let projection = self.tcx.intern_place_elems(&self.place_elem_cache);
317 let new_place = Place { local: replacement.local, projection };
319 debug!("Replacer: {:?} -> {:?}", place, new_place);
323 self.super_place(place, context, location);
326 fn visit_statement(&mut self, statement: &mut Statement<'tcx>, location: Location) {
327 self.super_statement(statement, location);
329 match &statement.kind {
330 // FIXME: Don't delete storage statements, merge the live ranges instead
331 StatementKind::StorageDead(local) | StatementKind::StorageLive(local)
332 if self.replacements.kill.contains(*local) =>
337 StatementKind::Assign(box (dest, rvalue)) => {
339 Rvalue::Use(Operand::Copy(place) | Operand::Move(place)) => {
340 // These might've been turned into self-assignments by the replacement
341 // (this includes the original statement we wanted to eliminate).
343 debug!("{:?} turned into self-assignment, deleting", location);
344 statement.make_nop();
356 struct Conflicts<'a> {
357 relevant_locals: &'a BitSet<Local>,
359 /// The conflict matrix. It is always symmetric and the adjacency matrix of the corresponding
361 matrix: BitMatrix<Local, Local>,
363 /// Preallocated `BitSet` used by `unify`.
364 unify_cache: BitSet<Local>,
366 /// Tracks locals that have been merged together to prevent cycles and propagate conflicts.
367 unified_locals: InPlaceUnificationTable<UnifyLocal>,
370 impl<'a> Conflicts<'a> {
373 body: &'_ Body<'tcx>,
374 relevant_locals: &'a BitSet<Local>,
376 // We don't have to look out for locals that have their address taken, since
377 // `find_candidates` already takes care of that.
379 let conflicts = BitMatrix::from_row_n(
380 &BitSet::new_empty(body.local_decls.len()),
381 body.local_decls.len(),
384 let mut init = MaybeInitializedLocals
385 .into_engine(tcx, body)
386 .iterate_to_fixpoint()
387 .into_results_cursor(body);
389 MaybeLiveLocals.into_engine(tcx, body).iterate_to_fixpoint().into_results_cursor(body);
391 let mut reachable = None;
392 dump_mir(tcx, None, "DestinationPropagation-dataflow", &"", body, |pass_where, w| {
393 let reachable = reachable.get_or_insert_with(|| traversal::reachable_as_bitset(body));
396 PassWhere::BeforeLocation(loc) if reachable.contains(loc.block) => {
397 init.seek_before_primary_effect(loc);
398 live.seek_after_primary_effect(loc);
400 writeln!(w, " // init: {:?}", init.get())?;
401 writeln!(w, " // live: {:?}", live.get())?;
403 PassWhere::AfterTerminator(bb) if reachable.contains(bb) => {
404 let loc = body.terminator_loc(bb);
405 init.seek_after_primary_effect(loc);
406 live.seek_before_primary_effect(loc);
408 writeln!(w, " // init: {:?}", init.get())?;
409 writeln!(w, " // live: {:?}", live.get())?;
412 PassWhere::BeforeBlock(bb) if reachable.contains(bb) => {
413 init.seek_to_block_start(bb);
414 live.seek_to_block_start(bb);
416 writeln!(w, " // init: {:?}", init.get())?;
417 writeln!(w, " // live: {:?}", live.get())?;
420 PassWhere::BeforeCFG | PassWhere::AfterCFG | PassWhere::AfterLocation(_) => {}
422 PassWhere::BeforeLocation(_) | PassWhere::AfterTerminator(_) => {
423 writeln!(w, " // init: <unreachable>")?;
424 writeln!(w, " // live: <unreachable>")?;
427 PassWhere::BeforeBlock(_) => {
428 writeln!(w, " // init: <unreachable>")?;
429 writeln!(w, " // live: <unreachable>")?;
436 let mut this = Self {
439 unify_cache: BitSet::new_empty(body.local_decls.len()),
441 let mut table = InPlaceUnificationTable::new();
442 // Pre-fill table with all locals (this creates N nodes / "connected" components,
443 // "graph"-ically speaking).
444 for local in 0..body.local_decls.len() {
445 assert_eq!(table.new_key(()), UnifyLocal(Local::from_usize(local)));
451 let mut live_and_init_locals = Vec::new();
453 // Visit only reachable basic blocks. The exact order is not important.
454 for (block, data) in traversal::preorder(body) {
455 // We need to observe the dataflow state *before* all possible locations (statement or
456 // terminator) in each basic block, and then observe the state *after* the terminator
457 // effect is applied. As long as neither `init` nor `borrowed` has a "before" effect,
458 // we will observe all possible dataflow states.
460 // Since liveness is a backwards analysis, we need to walk the results backwards. To do
461 // that, we first collect in the `MaybeInitializedLocals` results in a forwards
464 live_and_init_locals.resize_with(data.statements.len() + 1, || {
465 BitSet::new_empty(body.local_decls.len())
468 // First, go forwards for `MaybeInitializedLocals` and apply intra-statement/terminator
470 for (i, statement) in data.statements.iter().enumerate() {
471 this.record_statement_conflicts(statement);
473 let loc = Location { block, statement_index: i };
474 init.seek_before_primary_effect(loc);
476 live_and_init_locals[i].clone_from(init.get());
479 this.record_terminator_conflicts(data.terminator());
480 let term_loc = Location { block, statement_index: data.statements.len() };
481 init.seek_before_primary_effect(term_loc);
482 live_and_init_locals[term_loc.statement_index].clone_from(init.get());
484 // Now, go backwards and union with the liveness results.
485 for statement_index in (0..=data.statements.len()).rev() {
486 let loc = Location { block, statement_index };
487 live.seek_after_primary_effect(loc);
489 live_and_init_locals[statement_index].intersect(live.get());
491 trace!("record conflicts at {:?}", loc);
493 this.record_dataflow_conflicts(&mut live_and_init_locals[statement_index]);
496 init.seek_to_block_end(block);
497 live.seek_to_block_end(block);
498 let mut conflicts = init.get().clone();
499 conflicts.intersect(live.get());
500 trace!("record conflicts at end of {:?}", block);
502 this.record_dataflow_conflicts(&mut conflicts);
508 fn record_dataflow_conflicts(&mut self, new_conflicts: &mut BitSet<Local>) {
509 // Remove all locals that are not candidates.
510 new_conflicts.intersect(self.relevant_locals);
512 for local in new_conflicts.iter() {
513 self.matrix.union_row_with(&new_conflicts, local);
517 fn record_local_conflict(&mut self, a: Local, b: Local, why: &str) {
518 trace!("conflict {:?} <-> {:?} due to {}", a, b, why);
519 self.matrix.insert(a, b);
520 self.matrix.insert(b, a);
523 /// Records locals that must not overlap during the evaluation of `stmt`. These locals conflict
524 /// and must not be merged.
525 fn record_statement_conflicts(&mut self, stmt: &Statement<'_>) {
527 // While the left and right sides of an assignment must not overlap, we do not mark
528 // conflicts here as that would make this optimization useless. When we optimize, we
529 // eliminate the resulting self-assignments automatically.
530 StatementKind::Assign(_) => {}
532 StatementKind::SetDiscriminant { .. }
533 | StatementKind::Deinit(..)
534 | StatementKind::StorageLive(..)
535 | StatementKind::StorageDead(..)
536 | StatementKind::Retag(..)
537 | StatementKind::FakeRead(..)
538 | StatementKind::AscribeUserType(..)
539 | StatementKind::Coverage(..)
540 | StatementKind::CopyNonOverlapping(..)
541 | StatementKind::Nop => {}
545 fn record_terminator_conflicts(&mut self, term: &Terminator<'_>) {
547 TerminatorKind::DropAndReplace {
548 place: dropped_place,
553 if let Some(place) = value.place()
554 && !place.is_indirect()
555 && !dropped_place.is_indirect()
557 self.record_local_conflict(
560 "DropAndReplace operand overlap",
564 TerminatorKind::Yield { value, resume: _, resume_arg, drop: _ } => {
565 if let Some(place) = value.place() {
566 if !place.is_indirect() && !resume_arg.is_indirect() {
567 self.record_local_conflict(
570 "Yield operand overlap",
575 TerminatorKind::Call {
584 // No arguments may overlap with the destination.
585 for arg in args.iter().chain(Some(func)) {
586 if let Some(place) = arg.place() {
587 if !place.is_indirect() && !destination.is_indirect() {
588 self.record_local_conflict(
591 "call dest/arg overlap",
597 TerminatorKind::InlineAsm {
605 // The intended semantics here aren't documented, we just assume that nothing that
606 // could be written to by the assembly may overlap with any other operands.
609 InlineAsmOperand::Out { reg: _, late: _, place: Some(dest_place) }
610 | InlineAsmOperand::InOut {
614 out_place: Some(dest_place),
616 // For output place `place`, add all places accessed by the inline asm.
619 InlineAsmOperand::In { reg: _, value } => {
620 if let Some(p) = value.place()
622 && !dest_place.is_indirect()
624 self.record_local_conflict(
627 "asm! operand overlap",
631 InlineAsmOperand::Out {
636 if !place.is_indirect() && !dest_place.is_indirect() {
637 self.record_local_conflict(
640 "asm! operand overlap",
644 InlineAsmOperand::InOut {
650 if let Some(place) = in_value.place()
651 && !place.is_indirect()
652 && !dest_place.is_indirect()
654 self.record_local_conflict(
657 "asm! operand overlap",
661 if let Some(place) = out_place
662 && !place.is_indirect()
663 && !dest_place.is_indirect()
665 self.record_local_conflict(
668 "asm! operand overlap",
672 InlineAsmOperand::Out { reg: _, late: _, place: None }
673 | InlineAsmOperand::Const { value: _ }
674 | InlineAsmOperand::SymFn { value: _ }
675 | InlineAsmOperand::SymStatic { def_id: _ } => {}
679 InlineAsmOperand::InOut {
685 | InlineAsmOperand::In { reg: _, value: _ }
686 | InlineAsmOperand::Out { reg: _, late: _, place: None }
687 | InlineAsmOperand::Const { value: _ }
688 | InlineAsmOperand::SymFn { value: _ }
689 | InlineAsmOperand::SymStatic { def_id: _ } => {}
694 TerminatorKind::Goto { .. }
695 | TerminatorKind::SwitchInt { .. }
696 | TerminatorKind::Resume
697 | TerminatorKind::Abort
698 | TerminatorKind::Return
699 | TerminatorKind::Unreachable
700 | TerminatorKind::Drop { .. }
701 | TerminatorKind::Assert { .. }
702 | TerminatorKind::GeneratorDrop
703 | TerminatorKind::FalseEdge { .. }
704 | TerminatorKind::FalseUnwind { .. } => {}
708 /// Checks whether `a` and `b` may be merged. Returns `false` if there's a conflict.
709 fn can_unify(&mut self, a: Local, b: Local) -> bool {
710 // After some locals have been unified, their conflicts are only tracked in the root key,
712 let a = self.unified_locals.find(a).0;
713 let b = self.unified_locals.find(b).0;
716 // Already merged (part of the same connected component).
720 if self.matrix.contains(a, b) {
721 // Conflict (derived via dataflow, intra-statement conflicts, or inherited from another
722 // local during unification).
729 /// Merges the conflicts of `a` and `b`, so that each one inherits all conflicts of the other.
731 /// `can_unify` must have returned `true` for the same locals, or this may panic or lead to
734 /// This is called when the pass makes the decision to unify `a` and `b` (or parts of `a` and
735 /// `b`) and is needed to ensure that future unification decisions take potentially newly
736 /// introduced conflicts into account.
738 /// For an example, assume we have locals `_0`, `_1`, `_2`, and `_3`. There are these conflicts:
744 /// We then decide to merge `_2` with `_3` since they don't conflict. Then we decide to merge
745 /// `_2` with `_0`, which also doesn't have a conflict in the above list. However `_2` is now
746 /// `_3`, which does conflict with `_0`.
747 fn unify(&mut self, a: Local, b: Local) {
748 trace!("unify({:?}, {:?})", a, b);
750 // Get the root local of the connected components. The root local stores the conflicts of
751 // all locals in the connected component (and *is stored* as the conflicting local of other
753 let a = self.unified_locals.find(a).0;
754 let b = self.unified_locals.find(b).0;
757 trace!("roots: a={:?}, b={:?}", a, b);
758 trace!("{:?} conflicts: {:?}", a, self.matrix.iter(a).format(", "));
759 trace!("{:?} conflicts: {:?}", b, self.matrix.iter(b).format(", "));
761 self.unified_locals.union(a, b);
763 let root = self.unified_locals.find(a).0;
764 assert!(root == a || root == b);
766 // Make all locals that conflict with `a` also conflict with `b`, and vice versa.
767 self.unify_cache.clear();
768 for conflicts_with_a in self.matrix.iter(a) {
769 self.unify_cache.insert(conflicts_with_a);
771 for conflicts_with_b in self.matrix.iter(b) {
772 self.unify_cache.insert(conflicts_with_b);
774 for conflicts_with_a_or_b in self.unify_cache.iter() {
775 // Set both `a` and `b` for this local's row.
776 self.matrix.insert(conflicts_with_a_or_b, a);
777 self.matrix.insert(conflicts_with_a_or_b, b);
780 // Write the locals `a` conflicts with to `b`'s row.
781 self.matrix.union_rows(a, b);
782 // Write the locals `b` conflicts with to `a`'s row.
783 self.matrix.union_rows(b, a);
787 /// A `dest = {move} src;` statement at `loc`.
789 /// We want to consider merging `dest` and `src` due to this assignment.
790 #[derive(Debug, Copy, Clone)]
791 struct CandidateAssignment<'tcx> {
792 /// Does not contain indirection or indexing (so the only local it contains is the place base).
798 /// Scans the MIR for assignments between locals that we might want to consider merging.
800 /// This will filter out assignments that do not match the right form (as described in the top-level
801 /// comment) and also throw out assignments that involve a local that has its address taken or is
802 /// otherwise ineligible (eg. locals used as array indices are ignored because we cannot propagate
803 /// arbitrary places into array indices).
804 fn find_candidates<'tcx>(body: &Body<'tcx>) -> Vec<CandidateAssignment<'tcx>> {
805 let mut visitor = FindAssignments {
807 candidates: Vec::new(),
808 ever_borrowed_locals: borrowed_locals(body),
809 locals_used_as_array_index: locals_used_as_array_index(body),
811 visitor.visit_body(body);
815 struct FindAssignments<'a, 'tcx> {
816 body: &'a Body<'tcx>,
817 candidates: Vec<CandidateAssignment<'tcx>>,
818 ever_borrowed_locals: BitSet<Local>,
819 locals_used_as_array_index: BitSet<Local>,
822 impl<'tcx> Visitor<'tcx> for FindAssignments<'_, 'tcx> {
823 fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
824 if let StatementKind::Assign(box (
826 Rvalue::Use(Operand::Copy(src) | Operand::Move(src)),
829 // `dest` must not have pointer indirection.
830 if dest.is_indirect() {
834 // `src` must be a plain local.
835 if !src.projection.is_empty() {
839 // Since we want to replace `src` with `dest`, `src` must not be required.
840 if is_local_required(src.local, self.body) {
844 // Can't optimize if either local ever has their address taken. This optimization does
845 // liveness analysis only based on assignments, and a local can be live even if its
846 // never assigned to again, because a reference to it might be live.
847 // FIXME: This can be smarter and take `StorageDead` into account (which invalidates
849 if self.ever_borrowed_locals.contains(dest.local)
850 || self.ever_borrowed_locals.contains(src.local)
855 assert_ne!(dest.local, src.local, "self-assignments are UB");
857 // We can't replace locals occurring in `PlaceElem::Index` for now.
858 if self.locals_used_as_array_index.contains(src.local) {
862 for elem in dest.projection {
863 if let PlaceElem::Index(_) = elem {
864 // `dest` contains an indexing projection.
869 self.candidates.push(CandidateAssignment {
878 /// Some locals are part of the function's interface and can not be removed.
880 /// Note that these locals *can* still be merged with non-required locals by removing that other
882 fn is_local_required(local: Local, body: &Body<'_>) -> bool {
883 match body.local_kind(local) {
884 LocalKind::Arg | LocalKind::ReturnPointer => true,
885 LocalKind::Var | LocalKind::Temp => false,
889 /// `PlaceElem::Index` only stores a `Local`, so we can't replace that with a full `Place`.
891 /// Collect locals used as indices so we don't generate candidates that are impossible to apply
893 fn locals_used_as_array_index(body: &Body<'_>) -> BitSet<Local> {
894 let mut visitor = IndexCollector { locals: BitSet::new_empty(body.local_decls.len()) };
895 visitor.visit_body(body);
899 struct IndexCollector {
900 locals: BitSet<Local>,
903 impl<'tcx> Visitor<'tcx> for IndexCollector {
904 fn visit_projection_elem(
907 proj_base: &[PlaceElem<'tcx>],
908 elem: PlaceElem<'tcx>,
909 context: PlaceContext,
912 if let PlaceElem::Index(i) = elem {
913 self.locals.insert(i);
915 self.super_projection_elem(local, proj_base, elem, context, location);