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 with values for `dest` and `src` whose storage can soundly
25 //! 2) Replace all mentions of `src` with `dest` ("unifying" them and propagating the destination
27 //! 3) Delete the `dest = src;` statement (by making it a `nop`).
29 //! Step 1) is by far the hardest, so it is explained in more detail below.
33 //! We have a pair of places `p` and `q`, whose memory we would like to merge. In order for this to
34 //! be sound, we need to check a number of conditions:
36 //! * `p` and `q` must both be *constant* - it does not make much sense to talk about merging them
37 //! if they do not consistently refer to the same place in memory. This is satisfied if they do
38 //! not contain any indirection through a pointer or any indexing projections.
40 //! * We need to make sure that the goal of "merging the memory" is actually structurally possible
41 //! in MIR. For example, even if all the other conditions are satisfied, there is no way to
42 //! "merge" `_5.foo` and `_6.bar`. For now, we ensure this by requiring that both `p` and `q` are
43 //! locals with no further projections. Future iterations of this pass should improve on this.
45 //! * Finally, we want `p` and `q` to use the same memory - however, we still need to make sure that
46 //! each of them has enough "ownership" of that memory to continue "doing its job." More
47 //! precisely, what we will check is that whenever the program performs a write to `p`, then it
48 //! does not currently care about what the value in `q` is (and vice versa). We formalize the
49 //! notion of "does not care what the value in `q` is" by checking the *liveness* of `q`.
51 //! Because of the difficulty of computing liveness of places that have their address taken, we do
52 //! not even attempt to do it. Any places that are in a local that has its address taken is
53 //! excluded from the optimization.
55 //! The first two conditions are simple structural requirements on the `Assign` statements that can
56 //! be trivially checked. The third requirement however is more difficult and costly to check.
58 //! ## Future Improvements
60 //! There are a number of ways in which this pass could be improved in the future:
62 //! * Merging storage liveness ranges instead of removing storage statements completely. This may
63 //! improve stack usage.
65 //! * Allow merging locals into places with projections, eg `_5` into `_6.foo`.
67 //! * Liveness analysis with more precision than whole locals at a time. The smaller benefit of this
68 //! is that it would allow us to dest prop at "sub-local" levels in some cases. The bigger benefit
69 //! of this is that such liveness analysis can report more accurate results about whole locals at
70 //! a time. For example, consider:
72 //! ```ignore (syntax-highliting-only)
79 //! Because the current analysis only thinks in terms of locals, it does not have enough
80 //! information to report that `_1` is dead in the "unrelated code" section.
82 //! * Liveness analysis enabled by alias analysis. This would allow us to not just bail on locals
83 //! that ever have their address taken. Of course that requires actually having alias analysis
84 //! (and a model to build it on), so this might be a bit of a ways off.
86 //! * Various perf improvents. There are a bunch of comments in here marked `PERF` with ideas for
87 //! how to do things more efficiently. However, the complexity of the pass as a whole should be
92 //! A [previous attempt][attempt 1] at implementing an optimization like this turned out to be a
93 //! significant regression in compiler performance. Fixing the regressions introduced a lot of
94 //! undesirable complexity to the implementation.
96 //! A [subsequent approach][attempt 2] tried to avoid the costly computation by limiting itself to
97 //! acyclic CFGs, but still turned out to be far too costly to run due to suboptimal performance
98 //! within individual basic blocks, requiring a walk across the entire block for every assignment
99 //! found within the block. For the `tuple-stress` benchmark, which has 458745 statements in a
100 //! single block, this proved to be far too costly.
102 //! [Another approach after that][attempt 3] was much closer to correct, but had some soundness
103 //! issues - it was failing to consider stores outside live ranges, and failed to uphold some of the
104 //! requirements that MIR has for non-overlapping places within statements. However, it also had
105 //! performance issues caused by `O(l² * s)` runtime, where `l` is the number of locals and `s` is
106 //! the number of statements and terminators.
108 //! Since the first attempt at this, the compiler has improved dramatically, and new analysis
109 //! frameworks have been added that should make this approach viable without requiring a limited
110 //! approach that only works for some classes of CFGs:
111 //! - rustc now has a powerful dataflow analysis framework that can handle forwards and backwards
112 //! analyses efficiently.
113 //! - Layout optimizations for generators have been added to improve code generation for
114 //! async/await, which are very similar in spirit to what this optimization does.
116 //! Also, rustc now has a simple NRVO pass (see `nrvo.rs`), which handles a subset of the cases that
117 //! this destination propagation pass handles, proving that similar optimizations can be performed
120 //! ## Pre/Post Optimization
122 //! It is recommended to run `SimplifyCfg` and then `SimplifyLocals` some time after this pass, as
123 //! it replaces the eliminated assign statements with `nop`s and leaves unused locals behind.
125 //! [liveness]: https://en.wikipedia.org/wiki/Live_variable_analysis
126 //! [attempt 1]: https://github.com/rust-lang/rust/pull/47954
127 //! [attempt 2]: https://github.com/rust-lang/rust/pull/71003
128 //! [attempt 3]: https://github.com/rust-lang/rust/pull/72632
130 use std::collections::hash_map::{Entry, OccupiedEntry};
133 use rustc_data_structures::fx::FxHashMap;
134 use rustc_index::bit_set::BitSet;
135 use rustc_middle::mir::{dump_mir, PassWhere};
136 use rustc_middle::mir::{
137 traversal, BasicBlock, Body, InlineAsmOperand, Local, LocalKind, Location, Operand, Place,
138 Rvalue, Statement, StatementKind, TerminatorKind,
140 use rustc_middle::mir::{
141 visit::{MutVisitor, PlaceContext, Visitor},
144 use rustc_middle::ty::TyCtxt;
145 use rustc_mir_dataflow::impls::MaybeLiveLocals;
146 use rustc_mir_dataflow::{Analysis, ResultsCursor};
148 pub struct DestinationPropagation;
150 impl<'tcx> MirPass<'tcx> for DestinationPropagation {
151 fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
152 // For now, only run at MIR opt level 3. Two things need to be changed before this can be
153 // turned on by default:
154 // 1. Because of the overeager removal of storage statements, this can cause stack space
155 // regressions. This opt is not the place to fix this though, it's a more general
157 // 2. Despite being an overall perf improvement, this still causes a 30% regression in
158 // keccak. We can temporarily fix this by bounding function size, but in the long term
159 // we should fix this by being smarter about invalidating analysis results.
160 sess.mir_opt_level() >= 3
163 fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
164 let def_id = body.source.def_id();
165 let mut allocations = Allocations::default();
166 trace!(func = ?tcx.def_path_str(def_id));
168 let borrowed = rustc_mir_dataflow::impls::borrowed_locals(body);
170 // In order to avoid having to collect data for every single pair of locals in the body, we
171 // do not allow doing more than one merge for places that are derived from the same local at
172 // once. To avoid missed opportunities, we instead iterate to a fixed point - we'll refer to
173 // each of these iterations as a "round."
175 // Reaching a fixed point could in theory take up to `min(l, s)` rounds - however, we do not
176 // expect to see MIR like that. To verify this, a test was run against `[rust-lang/regex]` -
177 // the average MIR body saw 1.32 full iterations of this loop. The most that was hit were 30
178 // for a single function. Only 80/2801 (2.9%) of functions saw at least 5.
180 // [rust-lang/regex]:
181 // https://github.com/rust-lang/regex/tree/b5372864e2df6a2f5e543a556a62197f50ca3650
182 let mut round_count = 0;
184 // PERF: Can we do something smarter than recalculating the candidates and liveness
186 let mut candidates = find_candidates(
189 &mut allocations.candidates,
190 &mut allocations.candidates_reverse,
193 let mut live = MaybeLiveLocals
194 .into_engine(tcx, body)
195 .iterate_to_fixpoint()
196 .into_results_cursor(body);
197 dest_prop_mir_dump(tcx, body, &mut live, round_count);
199 FilterInformation::filter_liveness(
202 &mut allocations.write_info,
206 // Because we do not update liveness information, it is unsound to use a local for more
207 // than one merge operation within a single round of optimizations. We store here which
208 // ones we have already used.
209 let mut merged_locals: BitSet<Local> = BitSet::new_empty(body.local_decls.len());
211 // This is the set of merges we will apply this round. It is a subset of the candidates.
212 let mut merges = FxHashMap::default();
214 for (src, candidates) in candidates.c.iter() {
215 if merged_locals.contains(*src) {
219 candidates.iter().find(|dest| !merged_locals.contains(**dest)) else {
222 if !tcx.consider_optimizing(|| {
223 format!("{} round {}", tcx.def_path_str(def_id), round_count)
227 merges.insert(*src, *dest);
228 merged_locals.insert(*src);
229 merged_locals.insert(*dest);
231 trace!(merging = ?merges);
233 if merges.is_empty() {
238 apply_merges(body, tcx, &merges, &merged_locals);
245 /// Container for the various allocations that we need.
247 /// We store these here and hand out `&mut` access to them, instead of dropping and recreating them
248 /// frequently. Everything with a `&'alloc` lifetime points into here.
251 candidates: FxHashMap<Local, Vec<Local>>,
252 candidates_reverse: FxHashMap<Local, Vec<Local>>,
253 write_info: WriteInfo,
254 // PERF: Do this for `MaybeLiveLocals` allocations too.
258 struct Candidates<'alloc> {
259 /// The set of candidates we are considering in this optimization.
261 /// We will always merge the key into at most one of its values.
263 /// Whether a place ends up in the key or the value does not correspond to whether it appears as
264 /// the lhs or rhs of any assignment. As a matter of fact, the places in here might never appear
265 /// in an assignment at all. This happens because if we see an assignment like this:
267 /// ```ignore (syntax-highlighting-only)
271 /// We will still report that we would like to merge `_1` and `_2` in an attempt to allow us to
272 /// remove that assignment.
273 c: &'alloc mut FxHashMap<Local, Vec<Local>>,
274 /// A reverse index of the `c` set; if the `c` set contains `a => Place { local: b, proj }`,
275 /// then this contains `b => a`.
276 // PERF: Possibly these should be `SmallVec`s?
277 reverse: &'alloc mut FxHashMap<Local, Vec<Local>>,
280 //////////////////////////////////////////////////////////
283 // Applies the actual optimization
285 fn apply_merges<'tcx>(
286 body: &mut Body<'tcx>,
288 merges: &FxHashMap<Local, Local>,
289 merged_locals: &BitSet<Local>,
291 let mut merger = Merger { tcx, merges, merged_locals };
292 merger.visit_body_preserves_cfg(body);
295 struct Merger<'a, 'tcx> {
297 merges: &'a FxHashMap<Local, Local>,
298 merged_locals: &'a BitSet<Local>,
301 impl<'a, 'tcx> MutVisitor<'tcx> for Merger<'a, 'tcx> {
302 fn tcx(&self) -> TyCtxt<'tcx> {
306 fn visit_local(&mut self, local: &mut Local, _: PlaceContext, _location: Location) {
307 if let Some(dest) = self.merges.get(local) {
312 fn visit_statement(&mut self, statement: &mut Statement<'tcx>, location: Location) {
313 match &statement.kind {
314 // FIXME: Don't delete storage statements, but "merge" the storage ranges instead.
315 StatementKind::StorageDead(local) | StatementKind::StorageLive(local)
316 if self.merged_locals.contains(*local) =>
318 statement.make_nop();
323 self.super_statement(statement, location);
324 match &statement.kind {
325 StatementKind::Assign(box (dest, rvalue)) => {
327 Rvalue::Use(Operand::Copy(place) | Operand::Move(place)) => {
328 // These might've been turned into self-assignments by the replacement
329 // (this includes the original statement we wanted to eliminate).
331 debug!("{:?} turned into self-assignment, deleting", location);
332 statement.make_nop();
344 //////////////////////////////////////////////////////////
345 // Liveness filtering
347 // This section enforces bullet point 2
349 struct FilterInformation<'a, 'body, 'alloc, 'tcx> {
350 body: &'body Body<'tcx>,
351 live: &'a mut ResultsCursor<'body, 'tcx, MaybeLiveLocals>,
352 candidates: &'a mut Candidates<'alloc>,
353 write_info: &'alloc mut WriteInfo,
357 // We first implement some utility functions which we will expose removing candidates according to
358 // different needs. Throughout the livenss filtering, the `candidates` are only ever accessed
359 // through these methods, and not directly.
360 impl<'alloc> Candidates<'alloc> {
361 /// Just `Vec::retain`, but the condition is inverted and we add debugging output
365 mut f: impl FnMut(Local) -> bool,
369 let remove = f(*dest);
371 trace!("eliminating {:?} => {:?} due to conflict at {:?}", src, dest, at);
377 /// `vec_remove_debug` but for an `Entry`
379 mut entry: OccupiedEntry<'_, Local, Vec<Local>>,
381 f: impl FnMut(Local) -> bool,
384 let candidates = entry.get_mut();
385 Self::vec_remove_debug(p, candidates, f, at);
386 if candidates.len() == 0 {
391 /// Removes all candidates `(p, q)` or `(q, p)` where `p` is the indicated local and `f(q)` is true.
392 fn remove_candidates_if(&mut self, p: Local, mut f: impl FnMut(Local) -> bool, at: Location) {
393 // Cover the cases where `p` appears as a `src`
394 if let Entry::Occupied(entry) = self.c.entry(p) {
395 Self::entry_remove(entry, p, &mut f, at);
397 // And the cases where `p` appears as a `dest`
398 let Some(srcs) = self.reverse.get_mut(&p) else {
401 // We use `retain` here to remove the elements from the reverse set if we've removed the
402 // matching candidate in the forward set.
407 let Entry::Occupied(entry) = self.c.entry(*src) else {
410 Self::entry_remove(entry, *src, |dest| dest == p, at);
416 impl<'a, 'body, 'alloc, 'tcx> FilterInformation<'a, 'body, 'alloc, 'tcx> {
417 /// Filters the set of candidates to remove those that conflict.
419 /// The steps we take are exactly those that are outlined at the top of the file. For each
420 /// statement/terminator, we collect the set of locals that are written to in that
421 /// statement/terminator, and then we remove all pairs of candidates that contain one such local
422 /// and another one that is live.
424 /// We need to be careful about the ordering of operations within each statement/terminator
425 /// here. Many statements might write and read from more than one place, and we need to consider
426 /// them all. The strategy for doing this is as follows: We first gather all the places that are
427 /// written to within the statement/terminator via `WriteInfo`. Then, we use the liveness
428 /// analysis from *before* the statement/terminator (in the control flow sense) to eliminate
429 /// candidates - this is because we want to conservatively treat a pair of locals that is both
430 /// read and written in the statement/terminator to be conflicting, and the liveness analysis
431 /// before the statement/terminator will correctly report locals that are read in the
432 /// statement/terminator to be live. We are additionally conservative by treating all written to
433 /// locals as also being read from.
434 fn filter_liveness<'b>(
435 candidates: &mut Candidates<'alloc>,
436 live: &mut ResultsCursor<'b, 'tcx, MaybeLiveLocals>,
437 write_info_alloc: &'alloc mut WriteInfo,
438 body: &'b Body<'tcx>,
440 let mut this = FilterInformation {
444 // We don't actually store anything at this scope, we just keep things here to be able
445 // to reuse the allocation.
446 write_info: write_info_alloc,
447 // Doesn't matter what we put here, will be overwritten before being used
448 at: Location { block: BasicBlock::from_u32(0), statement_index: 0 },
450 this.internal_filter_liveness();
453 fn internal_filter_liveness(&mut self) {
454 for (block, data) in traversal::preorder(self.body) {
455 self.at = Location { block, statement_index: data.statements.len() };
456 self.live.seek_after_primary_effect(self.at);
457 self.write_info.for_terminator(&data.terminator().kind);
458 self.apply_conflicts();
460 for (i, statement) in data.statements.iter().enumerate().rev() {
461 self.at = Location { block, statement_index: i };
462 self.live.seek_after_primary_effect(self.at);
463 self.get_statement_write_info(&statement.kind);
464 self.apply_conflicts();
469 fn apply_conflicts(&mut self) {
470 let writes = &self.write_info.writes;
472 self.candidates.remove_candidates_if(
474 // It is possible that a local may be live for less than the
475 // duration of a statement This happens in the case of function
476 // calls or inline asm. Because of this, we also mark locals as
477 // conflicting when both of them are written to in the same
479 |q| self.live.contains(q) || writes.contains(&q),
485 /// Gets the write info for the `statement`.
486 fn get_statement_write_info(&mut self, statement: &StatementKind<'tcx>) {
487 self.write_info.writes.clear();
489 StatementKind::Assign(box (lhs, rhs)) => match rhs {
491 if !lhs.is_indirect() {
492 self.get_assign_use_write_info(*lhs, op);
501 self.write_info.for_statement(statement);
504 fn get_assign_use_write_info(&mut self, lhs: Place<'tcx>, rhs: &Operand<'tcx>) {
505 // We register the writes for the operand unconditionally
506 self.write_info.add_operand(rhs);
507 // However, we cannot do the same thing for the `lhs` as that would always block the
508 // optimization. Instead, we consider removing candidates manually.
509 let Some(rhs) = rhs.place() else {
510 self.write_info.add_place(lhs);
513 // Find out which candidate pair we should skip, if any
514 let Some((src, dest)) = places_to_candidate_pair(lhs, rhs, self.body) else {
515 self.write_info.add_place(lhs);
518 self.candidates.remove_candidates_if(
521 // Check if this is the candidate pair that should not be removed
522 if (lhs.local == src && other == dest) || (lhs.local == dest && other == src) {
525 // Otherwise, do the "standard" thing
526 self.live.contains(other)
533 /// Describes where a statement/terminator writes to
534 #[derive(Default, Debug)]
540 fn for_statement<'tcx>(&mut self, statement: &StatementKind<'tcx>) {
542 StatementKind::Assign(box (lhs, rhs)) => {
543 self.add_place(*lhs);
545 Rvalue::Use(op) | Rvalue::Repeat(op, _) => {
546 self.add_operand(op);
548 Rvalue::Cast(_, op, _)
549 | Rvalue::UnaryOp(_, op)
550 | Rvalue::ShallowInitBox(op, _) => {
551 self.add_operand(op);
553 Rvalue::BinaryOp(_, ops) | Rvalue::CheckedBinaryOp(_, ops) => {
554 for op in [&ops.0, &ops.1] {
555 self.add_operand(op);
558 Rvalue::Aggregate(_, ops) => {
560 self.add_operand(op);
563 Rvalue::ThreadLocalRef(_)
564 | Rvalue::NullaryOp(_, _)
565 | Rvalue::Ref(_, _, _)
566 | Rvalue::AddressOf(_, _)
568 | Rvalue::Discriminant(_)
569 | Rvalue::CopyForDeref(_) => (),
572 // Retags are technically also reads, but reporting them as a write suffices
573 StatementKind::SetDiscriminant { place, .. }
574 | StatementKind::Deinit(place)
575 | StatementKind::Retag(_, place) => {
576 self.add_place(**place);
578 StatementKind::Intrinsic(_)
580 | StatementKind::Coverage(_)
581 | StatementKind::StorageLive(_)
582 | StatementKind::StorageDead(_) => (),
583 StatementKind::FakeRead(_) | StatementKind::AscribeUserType(_, _) => {
584 bug!("{:?} not found in this MIR phase", statement)
589 fn for_terminator<'tcx>(&mut self, terminator: &TerminatorKind<'tcx>) {
592 TerminatorKind::SwitchInt { discr: op, .. }
593 | TerminatorKind::Assert { cond: op, .. } => {
594 self.add_operand(op);
596 TerminatorKind::Call { destination, func, args, .. } => {
597 self.add_place(*destination);
598 self.add_operand(func);
600 self.add_operand(arg);
603 TerminatorKind::InlineAsm { operands, .. } => {
604 for asm_operand in operands {
606 InlineAsmOperand::In { value, .. } => {
607 self.add_operand(value);
609 InlineAsmOperand::Out { place, .. } => {
610 if let Some(place) = place {
611 self.add_place(*place);
614 // Note that the `late` field in `InOut` is about whether the registers used
615 // for these things overlap, and is of absolutely no interest to us.
616 InlineAsmOperand::InOut { in_value, out_place, .. } => {
617 if let Some(place) = out_place {
618 self.add_place(*place);
620 self.add_operand(in_value);
622 InlineAsmOperand::Const { .. }
623 | InlineAsmOperand::SymFn { .. }
624 | InlineAsmOperand::SymStatic { .. } => (),
628 TerminatorKind::Goto { .. }
629 | TerminatorKind::Resume { .. }
630 | TerminatorKind::Abort { .. }
631 | TerminatorKind::Return
632 | TerminatorKind::Unreachable { .. } => (),
633 TerminatorKind::Drop { .. } => {
634 // `Drop`s create a `&mut` and so are not considered
636 TerminatorKind::DropAndReplace { .. }
637 | TerminatorKind::Yield { .. }
638 | TerminatorKind::GeneratorDrop
639 | TerminatorKind::FalseEdge { .. }
640 | TerminatorKind::FalseUnwind { .. } => {
641 bug!("{:?} not found in this MIR phase", terminator)
646 fn add_place<'tcx>(&mut self, place: Place<'tcx>) {
647 self.writes.push(place.local);
650 fn add_operand<'tcx>(&mut self, op: &Operand<'tcx>) {
652 // FIXME(JakobDegen): In a previous version, the `Move` case was incorrectly treated as
653 // being a read only. This was unsound, however we cannot add a regression test because
654 // it is not possible to set this off with current MIR. Once we have that ability, a
655 // regression test should be added.
656 Operand::Move(p) => self.add_place(*p),
657 Operand::Copy(_) | Operand::Constant(_) => (),
662 /////////////////////////////////////////////////////
663 // Candidate accumulation
665 fn is_constant<'tcx>(place: Place<'tcx>) -> bool {
666 place.projection.iter().all(|p| !matches!(p, ProjectionElem::Deref | ProjectionElem::Index(_)))
669 /// If the pair of places is being considered for merging, returns the candidate which would be
670 /// merged in order to accomplish this.
672 /// The contract here is in one direction - there is a guarantee that merging the locals that are
673 /// outputted by this function would result in an assignment between the inputs becoming a
674 /// self-assignment. However, there is no guarantee that the returned pair is actually suitable for
675 /// merging - candidate collection must still check this independently.
677 /// This output is unique for each unordered pair of input places.
678 fn places_to_candidate_pair<'tcx>(
682 ) -> Option<(Local, Local)> {
683 let (mut a, mut b) = if a.projection.len() == 0 && b.projection.len() == 0 {
689 // By sorting, we make sure we're input order independent
691 std::mem::swap(&mut a, &mut b);
694 // We could now return `(a, b)`, but then we miss some candidates in the case where `a` can't be
696 if is_local_required(a, body) {
697 std::mem::swap(&mut a, &mut b);
699 // We could check `is_local_required` again here, but there's no need - after all, we make no
700 // promise that the candidate pair is actually valid
704 /// Collects the candidates for merging
706 /// This is responsible for enforcing the first and third bullet point.
707 fn find_candidates<'alloc, 'tcx>(
709 borrowed: &BitSet<Local>,
710 candidates: &'alloc mut FxHashMap<Local, Vec<Local>>,
711 candidates_reverse: &'alloc mut FxHashMap<Local, Vec<Local>>,
712 ) -> Candidates<'alloc> {
714 candidates_reverse.clear();
715 let mut visitor = FindAssignments { body, candidates, borrowed };
716 visitor.visit_body(body);
717 // Deduplicate candidates
718 for (_, cands) in candidates.iter_mut() {
722 // Generate the reverse map
723 for (src, cands) in candidates.iter() {
724 for dest in cands.iter().copied() {
725 candidates_reverse.entry(dest).or_default().push(*src);
728 Candidates { c: candidates, reverse: candidates_reverse }
731 struct FindAssignments<'a, 'alloc, 'tcx> {
732 body: &'a Body<'tcx>,
733 candidates: &'alloc mut FxHashMap<Local, Vec<Local>>,
734 borrowed: &'a BitSet<Local>,
737 impl<'tcx> Visitor<'tcx> for FindAssignments<'_, '_, 'tcx> {
738 fn visit_statement(&mut self, statement: &Statement<'tcx>, _: Location) {
739 if let StatementKind::Assign(box (
741 Rvalue::Use(Operand::Copy(rhs) | Operand::Move(rhs)),
744 if !is_constant(*lhs) || !is_constant(*rhs) {
748 let Some((src, dest)) = places_to_candidate_pair(*lhs, *rhs, self.body) else {
752 // As described at the top of the file, we do not go near things that have their address
754 if self.borrowed.contains(src) || self.borrowed.contains(dest) {
758 // Also, we need to make sure that MIR actually allows the `src` to be removed
759 if is_local_required(src, self.body) {
763 // We may insert duplicates here, but that's fine
764 self.candidates.entry(src).or_default().push(dest);
769 /// Some locals are part of the function's interface and can not be removed.
771 /// Note that these locals *can* still be merged with non-required locals by removing that other
773 fn is_local_required(local: Local, body: &Body<'_>) -> bool {
774 match body.local_kind(local) {
775 LocalKind::Arg | LocalKind::ReturnPointer => true,
776 LocalKind::Var | LocalKind::Temp => false,
780 /////////////////////////////////////////////////////////
783 fn dest_prop_mir_dump<'body, 'tcx>(
785 body: &'body Body<'tcx>,
786 live: &mut ResultsCursor<'body, 'tcx, MaybeLiveLocals>,
789 let mut reachable = None;
790 dump_mir(tcx, false, "DestinationPropagation-dataflow", &round, body, |pass_where, w| {
791 let reachable = reachable.get_or_insert_with(|| traversal::reachable_as_bitset(body));
794 PassWhere::BeforeLocation(loc) if reachable.contains(loc.block) => {
795 live.seek_after_primary_effect(loc);
796 writeln!(w, " // live: {:?}", live.get())?;
798 PassWhere::AfterTerminator(bb) if reachable.contains(bb) => {
799 let loc = body.terminator_loc(bb);
800 live.seek_before_primary_effect(loc);
801 writeln!(w, " // live: {:?}", live.get())?;
804 PassWhere::BeforeBlock(bb) if reachable.contains(bb) => {
805 live.seek_to_block_start(bb);
806 writeln!(w, " // live: {:?}", live.get())?;
809 PassWhere::BeforeCFG | PassWhere::AfterCFG | PassWhere::AfterLocation(_) => {}
811 PassWhere::BeforeLocation(_) | PassWhere::AfterTerminator(_) => {
812 writeln!(w, " // live: <unreachable>")?;
815 PassWhere::BeforeBlock(_) => {
816 writeln!(w, " // live: <unreachable>")?;