1 //! Propagates assignment destinations backwards in the CFG to eliminate redundant assignments.
2 //!
3 //! # Motivation
4 //!
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.
9 //!
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.
15 //!
16 //! # The Optimization
17 //!
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:
22 //!
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
25 //! backwards).
26 //! 3) Delete the `dest = src;` statement (by making it a `nop`).
27 //!
28 //! Step 1) is by far the hardest, so it is explained in more detail below.
29 //!
30 //! ## Soundness
31 //!
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:
34 //!
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.
37 //!
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.
40 //!
41 //! Subtle case: If `dest` is a, or projects through a union, then we have to make sure that there
42 //! remains an assignment to it, since that sets the "active field" of the union. But if `src` is
43 //! a ZST, it might not be initialized, so there might not be any use of it before the assignment,
44 //! and performing the optimization would simply delete the assignment, leaving `dest`
45 //! uninitialized.
46 //!
47 //! * `src` must be a bare `Local` without any indirections or field projections (FIXME: Is this a
48 //! fundamental restriction or just current impl state?). It can be copied or moved by the
49 //! assignment.
50 //!
51 //! * The `dest` and `src` locals must never be [*live*][liveness] at the same time. If they are, it
52 //! means that they both hold a (potentially different) value that is needed by a future use of
53 //! the locals. Unifying them would overwrite one of the values.
54 //!
55 //! Note that computing liveness of locals that have had their address taken is more difficult:
56 //! Short of doing full escape analysis on the address/pointer/reference, the pass would need to
57 //! assume that any operation that can potentially involve opaque user code (such as function
58 //! calls, destructors, and inline assembly) may access any local that had its address taken
59 //! before that point.
60 //!
61 //! Here, the first two conditions are simple structural requirements on the `Assign` statements
62 //! that can be trivially checked. The liveness requirement however is more difficult and costly to
63 //! check.
64 //!
65 //! ## Previous Work
66 //!
67 //! A [previous attempt] at implementing an optimization like this turned out to be a significant
68 //! regression in compiler performance. Fixing the regressions introduced a lot of undesirable
69 //! complexity to the implementation.
70 //!
71 //! A [subsequent approach] tried to avoid the costly computation by limiting itself to acyclic
72 //! CFGs, but still turned out to be far too costly to run due to suboptimal performance within
73 //! individual basic blocks, requiring a walk across the entire block for every assignment found
74 //! within the block. For the `tuple-stress` benchmark, which has 458745 statements in a single
75 //! block, this proved to be far too costly.
76 //!
77 //! Since the first attempt at this, the compiler has improved dramatically, and new analysis
78 //! frameworks have been added that should make this approach viable without requiring a limited
79 //! approach that only works for some classes of CFGs:
80 //! - rustc now has a powerful dataflow analysis framework that can handle forwards and backwards
81 //! analyses efficiently.
82 //! - Layout optimizations for generators have been added to improve code generation for
83 //! async/await, which are very similar in spirit to what this optimization does. Both walk the
84 //! MIR and record conflicting uses of locals in a `BitMatrix`.
85 //!
86 //! Also, rustc now has a simple NRVO pass (see `nrvo.rs`), which handles a subset of the cases that
87 //! this destination propagation pass handles, proving that similar optimizations can be performed
88 //! on MIR.
89 //!
90 //! ## Pre/Post Optimization
91 //!
92 //! It is recommended to run `SimplifyCfg` and then `SimplifyLocals` some time after this pass, as
93 //! it replaces the eliminated assign statements with `nop`s and leaves unused locals behind.
94 //!
95 //! [liveness]: https://en.wikipedia.org/wiki/Live_variable_analysis
96 //! [previous attempt]: https://github.com/rust-lang/rust/pull/47954
97 //! [subsequent approach]: https://github.com/rust-lang/rust/pull/71003
98
99 use crate::MirPass;
100 use itertools::Itertools;
101 use rustc_data_structures::unify::{InPlaceUnificationTable, UnifyKey};
102 use rustc_index::{
103 bit_set::{BitMatrix, BitSet},
104 vec::IndexVec,
105 };
106 use rustc_middle::mir::tcx::PlaceTy;
107 use rustc_middle::mir::visit::{MutVisitor, PlaceContext, Visitor};
108 use rustc_middle::mir::{dump_mir, PassWhere};
109 use rustc_middle::mir::{
110 traversal, Body, InlineAsmOperand, Local, LocalKind, Location, Operand, Place, PlaceElem,
111 Rvalue, Statement, StatementKind, Terminator, TerminatorKind,
112 };
113 use rustc_middle::ty::TyCtxt;
114 use rustc_mir_dataflow::impls::{MaybeInitializedLocals, MaybeLiveLocals};
115 use rustc_mir_dataflow::Analysis;
116
117 // Empirical measurements have resulted in some observations:
118 // - Running on a body with a single block and 500 locals takes barely any time
119 // - Running on a body with ~400 blocks and ~300 relevant locals takes "too long"
120 // ...so we just limit both to somewhat reasonable-ish looking values.
121 const MAX_LOCALS: usize = 500;
122 const MAX_BLOCKS: usize = 250;
123
124 pub struct DestinationPropagation;
125
126 impl<'tcx> MirPass<'tcx> for DestinationPropagation {
run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>)127 fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
128 // FIXME(#79191, #82678)
129 if !tcx.sess.opts.debugging_opts.unsound_mir_opts {
130 return;
131 }
132
133 // Only run at mir-opt-level=3 or higher for now (we don't fix up debuginfo and remove
134 // storage statements at the moment).
135 if tcx.sess.mir_opt_level() < 3 {
136 return;
137 }
138
139 let def_id = body.source.def_id();
140
141 let candidates = find_candidates(tcx, body);
142 if candidates.is_empty() {
143 debug!("{:?}: no dest prop candidates, done", def_id);
144 return;
145 }
146
147 // Collect all locals we care about. We only compute conflicts for these to save time.
148 let mut relevant_locals = BitSet::new_empty(body.local_decls.len());
149 for CandidateAssignment { dest, src, loc: _ } in &candidates {
150 relevant_locals.insert(dest.local);
151 relevant_locals.insert(*src);
152 }
153
154 // This pass unfortunately has `O(l² * s)` performance, where `l` is the number of locals
155 // and `s` is the number of statements and terminators in the function.
156 // To prevent blowing up compile times too much, we bail out when there are too many locals.
157 let relevant = relevant_locals.count();
158 debug!(
159 "{:?}: {} locals ({} relevant), {} blocks",
160 def_id,
161 body.local_decls.len(),
162 relevant,
163 body.basic_blocks().len()
164 );
165 if relevant > MAX_LOCALS {
166 warn!(
167 "too many candidate locals in {:?} ({}, max is {}), not optimizing",
168 def_id, relevant, MAX_LOCALS
169 );
170 return;
171 }
172 if body.basic_blocks().len() > MAX_BLOCKS {
173 warn!(
174 "too many blocks in {:?} ({}, max is {}), not optimizing",
175 def_id,
176 body.basic_blocks().len(),
177 MAX_BLOCKS
178 );
179 return;
180 }
181
182 let mut conflicts = Conflicts::build(tcx, body, &relevant_locals);
183
184 let mut replacements = Replacements::new(body.local_decls.len());
185 for candidate @ CandidateAssignment { dest, src, loc } in candidates {
186 // Merge locals that don't conflict.
187 if !conflicts.can_unify(dest.local, src) {
188 debug!("at assignment {:?}, conflict {:?} vs. {:?}", loc, dest.local, src);
189 continue;
190 }
191
192 if replacements.for_src(candidate.src).is_some() {
193 debug!("src {:?} already has replacement", candidate.src);
194 continue;
195 }
196
197 if !tcx.consider_optimizing(|| {
198 format!("DestinationPropagation {:?} {:?}", def_id, candidate)
199 }) {
200 break;
201 }
202
203 replacements.push(candidate);
204 conflicts.unify(candidate.src, candidate.dest.local);
205 }
206
207 replacements.flatten(tcx);
208
209 debug!("replacements {:?}", replacements.map);
210
211 Replacer { tcx, replacements, place_elem_cache: Vec::new() }.visit_body(body);
212
213 // FIXME fix debug info
214 }
215 }
216
217 #[derive(Debug, Eq, PartialEq, Copy, Clone)]
218 struct UnifyLocal(Local);
219
220 impl From<Local> for UnifyLocal {
from(l: Local) -> Self221 fn from(l: Local) -> Self {
222 Self(l)
223 }
224 }
225
226 impl UnifyKey for UnifyLocal {
227 type Value = ();
index(&self) -> u32228 fn index(&self) -> u32 {
229 self.0.as_u32()
230 }
from_index(u: u32) -> Self231 fn from_index(u: u32) -> Self {
232 Self(Local::from_u32(u))
233 }
tag() -> &'static str234 fn tag() -> &'static str {
235 "UnifyLocal"
236 }
237 }
238
239 struct Replacements<'tcx> {
240 /// Maps locals to their replacement.
241 map: IndexVec<Local, Option<Place<'tcx>>>,
242
243 /// Whose locals' live ranges to kill.
244 kill: BitSet<Local>,
245 }
246
247 impl Replacements<'tcx> {
new(locals: usize) -> Self248 fn new(locals: usize) -> Self {
249 Self { map: IndexVec::from_elem_n(None, locals), kill: BitSet::new_empty(locals) }
250 }
251
push(&mut self, candidate: CandidateAssignment<'tcx>)252 fn push(&mut self, candidate: CandidateAssignment<'tcx>) {
253 trace!("Replacements::push({:?})", candidate);
254 let entry = &mut self.map[candidate.src];
255 assert!(entry.is_none());
256
257 *entry = Some(candidate.dest);
258 self.kill.insert(candidate.src);
259 self.kill.insert(candidate.dest.local);
260 }
261
262 /// Applies the stored replacements to all replacements, until no replacements would result in
263 /// locals that need further replacements when applied.
flatten(&mut self, tcx: TyCtxt<'tcx>)264 fn flatten(&mut self, tcx: TyCtxt<'tcx>) {
265 // Note: This assumes that there are no cycles in the replacements, which is enforced via
266 // `self.unified_locals`. Otherwise this can cause an infinite loop.
267
268 for local in self.map.indices() {
269 if let Some(replacement) = self.map[local] {
270 // Substitute the base local of `replacement` until fixpoint.
271 let mut base = replacement.local;
272 let mut reversed_projection_slices = Vec::with_capacity(1);
273 while let Some(replacement_for_replacement) = self.map[base] {
274 base = replacement_for_replacement.local;
275 reversed_projection_slices.push(replacement_for_replacement.projection);
276 }
277
278 let projection: Vec<_> = reversed_projection_slices
279 .iter()
280 .rev()
281 .flat_map(|projs| projs.iter())
282 .chain(replacement.projection.iter())
283 .collect();
284 let projection = tcx.intern_place_elems(&projection);
285
286 // Replace with the final `Place`.
287 self.map[local] = Some(Place { local: base, projection });
288 }
289 }
290 }
291
for_src(&self, src: Local) -> Option<Place<'tcx>>292 fn for_src(&self, src: Local) -> Option<Place<'tcx>> {
293 self.map[src]
294 }
295 }
296
297 struct Replacer<'tcx> {
298 tcx: TyCtxt<'tcx>,
299 replacements: Replacements<'tcx>,
300 place_elem_cache: Vec<PlaceElem<'tcx>>,
301 }
302
303 impl<'tcx> MutVisitor<'tcx> for Replacer<'tcx> {
tcx<'a>(&'a self) -> TyCtxt<'tcx>304 fn tcx<'a>(&'a self) -> TyCtxt<'tcx> {
305 self.tcx
306 }
307
visit_local(&mut self, local: &mut Local, context: PlaceContext, location: Location)308 fn visit_local(&mut self, local: &mut Local, context: PlaceContext, location: Location) {
309 if context.is_use() && self.replacements.for_src(*local).is_some() {
310 bug!(
311 "use of local {:?} should have been replaced by visit_place; context={:?}, loc={:?}",
312 local,
313 context,
314 location,
315 );
316 }
317 }
318
process_projection_elem( &mut self, elem: PlaceElem<'tcx>, _: Location, ) -> Option<PlaceElem<'tcx>>319 fn process_projection_elem(
320 &mut self,
321 elem: PlaceElem<'tcx>,
322 _: Location,
323 ) -> Option<PlaceElem<'tcx>> {
324 match elem {
325 PlaceElem::Index(local) => {
326 if let Some(replacement) = self.replacements.for_src(local) {
327 bug!(
328 "cannot replace {:?} with {:?} in index projection {:?}",
329 local,
330 replacement,
331 elem,
332 );
333 } else {
334 None
335 }
336 }
337 _ => None,
338 }
339 }
340
visit_place(&mut self, place: &mut Place<'tcx>, context: PlaceContext, location: Location)341 fn visit_place(&mut self, place: &mut Place<'tcx>, context: PlaceContext, location: Location) {
342 if let Some(replacement) = self.replacements.for_src(place.local) {
343 // Rebase `place`s projections onto `replacement`'s.
344 self.place_elem_cache.clear();
345 self.place_elem_cache.extend(replacement.projection.iter().chain(place.projection));
346 let projection = self.tcx.intern_place_elems(&self.place_elem_cache);
347 let new_place = Place { local: replacement.local, projection };
348
349 debug!("Replacer: {:?} -> {:?}", place, new_place);
350 *place = new_place;
351 }
352
353 self.super_place(place, context, location);
354 }
355
visit_statement(&mut self, statement: &mut Statement<'tcx>, location: Location)356 fn visit_statement(&mut self, statement: &mut Statement<'tcx>, location: Location) {
357 self.super_statement(statement, location);
358
359 match &statement.kind {
360 // FIXME: Don't delete storage statements, merge the live ranges instead
361 StatementKind::StorageDead(local) | StatementKind::StorageLive(local)
362 if self.replacements.kill.contains(*local) =>
363 {
364 statement.make_nop()
365 }
366
367 StatementKind::Assign(box (dest, rvalue)) => {
368 match rvalue {
369 Rvalue::Use(Operand::Copy(place) | Operand::Move(place)) => {
370 // These might've been turned into self-assignments by the replacement
371 // (this includes the original statement we wanted to eliminate).
372 if dest == place {
373 debug!("{:?} turned into self-assignment, deleting", location);
374 statement.make_nop();
375 }
376 }
377 _ => {}
378 }
379 }
380
381 _ => {}
382 }
383 }
384 }
385
386 struct Conflicts<'a> {
387 relevant_locals: &'a BitSet<Local>,
388
389 /// The conflict matrix. It is always symmetric and the adjacency matrix of the corresponding
390 /// conflict graph.
391 matrix: BitMatrix<Local, Local>,
392
393 /// Preallocated `BitSet` used by `unify`.
394 unify_cache: BitSet<Local>,
395
396 /// Tracks locals that have been merged together to prevent cycles and propagate conflicts.
397 unified_locals: InPlaceUnificationTable<UnifyLocal>,
398 }
399
400 impl Conflicts<'a> {
build<'tcx>( tcx: TyCtxt<'tcx>, body: &'_ Body<'tcx>, relevant_locals: &'a BitSet<Local>, ) -> Self401 fn build<'tcx>(
402 tcx: TyCtxt<'tcx>,
403 body: &'_ Body<'tcx>,
404 relevant_locals: &'a BitSet<Local>,
405 ) -> Self {
406 // We don't have to look out for locals that have their address taken, since
407 // `find_candidates` already takes care of that.
408
409 let conflicts = BitMatrix::from_row_n(
410 &BitSet::new_empty(body.local_decls.len()),
411 body.local_decls.len(),
412 );
413
414 let mut init = MaybeInitializedLocals
415 .into_engine(tcx, body)
416 .iterate_to_fixpoint()
417 .into_results_cursor(body);
418 let mut live =
419 MaybeLiveLocals.into_engine(tcx, body).iterate_to_fixpoint().into_results_cursor(body);
420
421 let mut reachable = None;
422 dump_mir(tcx, None, "DestinationPropagation-dataflow", &"", body, |pass_where, w| {
423 let reachable = reachable.get_or_insert_with(|| traversal::reachable_as_bitset(body));
424
425 match pass_where {
426 PassWhere::BeforeLocation(loc) if reachable.contains(loc.block) => {
427 init.seek_before_primary_effect(loc);
428 live.seek_after_primary_effect(loc);
429
430 writeln!(w, " // init: {:?}", init.get())?;
431 writeln!(w, " // live: {:?}", live.get())?;
432 }
433 PassWhere::AfterTerminator(bb) if reachable.contains(bb) => {
434 let loc = body.terminator_loc(bb);
435 init.seek_after_primary_effect(loc);
436 live.seek_before_primary_effect(loc);
437
438 writeln!(w, " // init: {:?}", init.get())?;
439 writeln!(w, " // live: {:?}", live.get())?;
440 }
441
442 PassWhere::BeforeBlock(bb) if reachable.contains(bb) => {
443 init.seek_to_block_start(bb);
444 live.seek_to_block_start(bb);
445
446 writeln!(w, " // init: {:?}", init.get())?;
447 writeln!(w, " // live: {:?}", live.get())?;
448 }
449
450 PassWhere::BeforeCFG | PassWhere::AfterCFG | PassWhere::AfterLocation(_) => {}
451
452 PassWhere::BeforeLocation(_) | PassWhere::AfterTerminator(_) => {
453 writeln!(w, " // init: <unreachable>")?;
454 writeln!(w, " // live: <unreachable>")?;
455 }
456
457 PassWhere::BeforeBlock(_) => {
458 writeln!(w, " // init: <unreachable>")?;
459 writeln!(w, " // live: <unreachable>")?;
460 }
461 }
462
463 Ok(())
464 });
465
466 let mut this = Self {
467 relevant_locals,
468 matrix: conflicts,
469 unify_cache: BitSet::new_empty(body.local_decls.len()),
470 unified_locals: {
471 let mut table = InPlaceUnificationTable::new();
472 // Pre-fill table with all locals (this creates N nodes / "connected" components,
473 // "graph"-ically speaking).
474 for local in 0..body.local_decls.len() {
475 assert_eq!(table.new_key(()), UnifyLocal(Local::from_usize(local)));
476 }
477 table
478 },
479 };
480
481 let mut live_and_init_locals = Vec::new();
482
483 // Visit only reachable basic blocks. The exact order is not important.
484 for (block, data) in traversal::preorder(body) {
485 // We need to observe the dataflow state *before* all possible locations (statement or
486 // terminator) in each basic block, and then observe the state *after* the terminator
487 // effect is applied. As long as neither `init` nor `borrowed` has a "before" effect,
488 // we will observe all possible dataflow states.
489
490 // Since liveness is a backwards analysis, we need to walk the results backwards. To do
491 // that, we first collect in the `MaybeInitializedLocals` results in a forwards
492 // traversal.
493
494 live_and_init_locals.resize_with(data.statements.len() + 1, || {
495 BitSet::new_empty(body.local_decls.len())
496 });
497
498 // First, go forwards for `MaybeInitializedLocals` and apply intra-statement/terminator
499 // conflicts.
500 for (i, statement) in data.statements.iter().enumerate() {
501 this.record_statement_conflicts(statement);
502
503 let loc = Location { block, statement_index: i };
504 init.seek_before_primary_effect(loc);
505
506 live_and_init_locals[i].clone_from(init.get());
507 }
508
509 this.record_terminator_conflicts(data.terminator());
510 let term_loc = Location { block, statement_index: data.statements.len() };
511 init.seek_before_primary_effect(term_loc);
512 live_and_init_locals[term_loc.statement_index].clone_from(init.get());
513
514 // Now, go backwards and union with the liveness results.
515 for statement_index in (0..=data.statements.len()).rev() {
516 let loc = Location { block, statement_index };
517 live.seek_after_primary_effect(loc);
518
519 live_and_init_locals[statement_index].intersect(live.get());
520
521 trace!("record conflicts at {:?}", loc);
522
523 this.record_dataflow_conflicts(&mut live_and_init_locals[statement_index]);
524 }
525
526 init.seek_to_block_end(block);
527 live.seek_to_block_end(block);
528 let mut conflicts = init.get().clone();
529 conflicts.intersect(live.get());
530 trace!("record conflicts at end of {:?}", block);
531
532 this.record_dataflow_conflicts(&mut conflicts);
533 }
534
535 this
536 }
537
record_dataflow_conflicts(&mut self, new_conflicts: &mut BitSet<Local>)538 fn record_dataflow_conflicts(&mut self, new_conflicts: &mut BitSet<Local>) {
539 // Remove all locals that are not candidates.
540 new_conflicts.intersect(self.relevant_locals);
541
542 for local in new_conflicts.iter() {
543 self.matrix.union_row_with(&new_conflicts, local);
544 }
545 }
546
record_local_conflict(&mut self, a: Local, b: Local, why: &str)547 fn record_local_conflict(&mut self, a: Local, b: Local, why: &str) {
548 trace!("conflict {:?} <-> {:?} due to {}", a, b, why);
549 self.matrix.insert(a, b);
550 self.matrix.insert(b, a);
551 }
552
553 /// Records locals that must not overlap during the evaluation of `stmt`. These locals conflict
554 /// and must not be merged.
record_statement_conflicts(&mut self, stmt: &Statement<'_>)555 fn record_statement_conflicts(&mut self, stmt: &Statement<'_>) {
556 match &stmt.kind {
557 // While the left and right sides of an assignment must not overlap, we do not mark
558 // conflicts here as that would make this optimization useless. When we optimize, we
559 // eliminate the resulting self-assignments automatically.
560 StatementKind::Assign(_) => {}
561
562 StatementKind::LlvmInlineAsm(asm) => {
563 // Inputs and outputs must not overlap.
564 for (_, input) in &*asm.inputs {
565 if let Some(in_place) = input.place() {
566 if !in_place.is_indirect() {
567 for out_place in &*asm.outputs {
568 if !out_place.is_indirect() && !in_place.is_indirect() {
569 self.record_local_conflict(
570 in_place.local,
571 out_place.local,
572 "aliasing llvm_asm! operands",
573 );
574 }
575 }
576 }
577 }
578 }
579 }
580
581 StatementKind::SetDiscriminant { .. }
582 | StatementKind::StorageLive(..)
583 | StatementKind::StorageDead(..)
584 | StatementKind::Retag(..)
585 | StatementKind::FakeRead(..)
586 | StatementKind::AscribeUserType(..)
587 | StatementKind::Coverage(..)
588 | StatementKind::CopyNonOverlapping(..)
589 | StatementKind::Nop => {}
590 }
591 }
592
record_terminator_conflicts(&mut self, term: &Terminator<'_>)593 fn record_terminator_conflicts(&mut self, term: &Terminator<'_>) {
594 match &term.kind {
595 TerminatorKind::DropAndReplace {
596 place: dropped_place,
597 value,
598 target: _,
599 unwind: _,
600 } => {
601 if let Some(place) = value.place() {
602 if !place.is_indirect() && !dropped_place.is_indirect() {
603 self.record_local_conflict(
604 place.local,
605 dropped_place.local,
606 "DropAndReplace operand overlap",
607 );
608 }
609 }
610 }
611 TerminatorKind::Yield { value, resume: _, resume_arg, drop: _ } => {
612 if let Some(place) = value.place() {
613 if !place.is_indirect() && !resume_arg.is_indirect() {
614 self.record_local_conflict(
615 place.local,
616 resume_arg.local,
617 "Yield operand overlap",
618 );
619 }
620 }
621 }
622 TerminatorKind::Call {
623 func,
624 args,
625 destination: Some((dest_place, _)),
626 cleanup: _,
627 from_hir_call: _,
628 fn_span: _,
629 } => {
630 // No arguments may overlap with the destination.
631 for arg in args.iter().chain(Some(func)) {
632 if let Some(place) = arg.place() {
633 if !place.is_indirect() && !dest_place.is_indirect() {
634 self.record_local_conflict(
635 dest_place.local,
636 place.local,
637 "call dest/arg overlap",
638 );
639 }
640 }
641 }
642 }
643 TerminatorKind::InlineAsm {
644 template: _,
645 operands,
646 options: _,
647 line_spans: _,
648 destination: _,
649 } => {
650 // The intended semantics here aren't documented, we just assume that nothing that
651 // could be written to by the assembly may overlap with any other operands.
652 for op in operands {
653 match op {
654 InlineAsmOperand::Out { reg: _, late: _, place: Some(dest_place) }
655 | InlineAsmOperand::InOut {
656 reg: _,
657 late: _,
658 in_value: _,
659 out_place: Some(dest_place),
660 } => {
661 // For output place `place`, add all places accessed by the inline asm.
662 for op in operands {
663 match op {
664 InlineAsmOperand::In { reg: _, value } => {
665 if let Some(p) = value.place() {
666 if !p.is_indirect() && !dest_place.is_indirect() {
667 self.record_local_conflict(
668 p.local,
669 dest_place.local,
670 "asm! operand overlap",
671 );
672 }
673 }
674 }
675 InlineAsmOperand::Out {
676 reg: _,
677 late: _,
678 place: Some(place),
679 } => {
680 if !place.is_indirect() && !dest_place.is_indirect() {
681 self.record_local_conflict(
682 place.local,
683 dest_place.local,
684 "asm! operand overlap",
685 );
686 }
687 }
688 InlineAsmOperand::InOut {
689 reg: _,
690 late: _,
691 in_value,
692 out_place,
693 } => {
694 if let Some(place) = in_value.place() {
695 if !place.is_indirect() && !dest_place.is_indirect() {
696 self.record_local_conflict(
697 place.local,
698 dest_place.local,
699 "asm! operand overlap",
700 );
701 }
702 }
703
704 if let Some(place) = out_place {
705 if !place.is_indirect() && !dest_place.is_indirect() {
706 self.record_local_conflict(
707 place.local,
708 dest_place.local,
709 "asm! operand overlap",
710 );
711 }
712 }
713 }
714 InlineAsmOperand::Out { reg: _, late: _, place: None }
715 | InlineAsmOperand::Const { value: _ }
716 | InlineAsmOperand::SymFn { value: _ }
717 | InlineAsmOperand::SymStatic { def_id: _ } => {}
718 }
719 }
720 }
721 InlineAsmOperand::InOut {
722 reg: _,
723 late: _,
724 in_value: _,
725 out_place: None,
726 }
727 | InlineAsmOperand::In { reg: _, value: _ }
728 | InlineAsmOperand::Out { reg: _, late: _, place: None }
729 | InlineAsmOperand::Const { value: _ }
730 | InlineAsmOperand::SymFn { value: _ }
731 | InlineAsmOperand::SymStatic { def_id: _ } => {}
732 }
733 }
734 }
735
736 TerminatorKind::Goto { .. }
737 | TerminatorKind::Call { destination: None, .. }
738 | TerminatorKind::SwitchInt { .. }
739 | TerminatorKind::Resume
740 | TerminatorKind::Abort
741 | TerminatorKind::Return
742 | TerminatorKind::Unreachable
743 | TerminatorKind::Drop { .. }
744 | TerminatorKind::Assert { .. }
745 | TerminatorKind::GeneratorDrop
746 | TerminatorKind::FalseEdge { .. }
747 | TerminatorKind::FalseUnwind { .. } => {}
748 }
749 }
750
751 /// Checks whether `a` and `b` may be merged. Returns `false` if there's a conflict.
can_unify(&mut self, a: Local, b: Local) -> bool752 fn can_unify(&mut self, a: Local, b: Local) -> bool {
753 // After some locals have been unified, their conflicts are only tracked in the root key,
754 // so look that up.
755 let a = self.unified_locals.find(a).0;
756 let b = self.unified_locals.find(b).0;
757
758 if a == b {
759 // Already merged (part of the same connected component).
760 return false;
761 }
762
763 if self.matrix.contains(a, b) {
764 // Conflict (derived via dataflow, intra-statement conflicts, or inherited from another
765 // local during unification).
766 return false;
767 }
768
769 true
770 }
771
772 /// Merges the conflicts of `a` and `b`, so that each one inherits all conflicts of the other.
773 ///
774 /// `can_unify` must have returned `true` for the same locals, or this may panic or lead to
775 /// miscompiles.
776 ///
777 /// This is called when the pass makes the decision to unify `a` and `b` (or parts of `a` and
778 /// `b`) and is needed to ensure that future unification decisions take potentially newly
779 /// introduced conflicts into account.
780 ///
781 /// For an example, assume we have locals `_0`, `_1`, `_2`, and `_3`. There are these conflicts:
782 ///
783 /// * `_0` <-> `_1`
784 /// * `_1` <-> `_2`
785 /// * `_3` <-> `_0`
786 ///
787 /// We then decide to merge `_2` with `_3` since they don't conflict. Then we decide to merge
788 /// `_2` with `_0`, which also doesn't have a conflict in the above list. However `_2` is now
789 /// `_3`, which does conflict with `_0`.
unify(&mut self, a: Local, b: Local)790 fn unify(&mut self, a: Local, b: Local) {
791 trace!("unify({:?}, {:?})", a, b);
792
793 // Get the root local of the connected components. The root local stores the conflicts of
794 // all locals in the connected component (and *is stored* as the conflicting local of other
795 // locals).
796 let a = self.unified_locals.find(a).0;
797 let b = self.unified_locals.find(b).0;
798 assert_ne!(a, b);
799
800 trace!("roots: a={:?}, b={:?}", a, b);
801 trace!("{:?} conflicts: {:?}", a, self.matrix.iter(a).format(", "));
802 trace!("{:?} conflicts: {:?}", b, self.matrix.iter(b).format(", "));
803
804 self.unified_locals.union(a, b);
805
806 let root = self.unified_locals.find(a).0;
807 assert!(root == a || root == b);
808
809 // Make all locals that conflict with `a` also conflict with `b`, and vice versa.
810 self.unify_cache.clear();
811 for conflicts_with_a in self.matrix.iter(a) {
812 self.unify_cache.insert(conflicts_with_a);
813 }
814 for conflicts_with_b in self.matrix.iter(b) {
815 self.unify_cache.insert(conflicts_with_b);
816 }
817 for conflicts_with_a_or_b in self.unify_cache.iter() {
818 // Set both `a` and `b` for this local's row.
819 self.matrix.insert(conflicts_with_a_or_b, a);
820 self.matrix.insert(conflicts_with_a_or_b, b);
821 }
822
823 // Write the locals `a` conflicts with to `b`'s row.
824 self.matrix.union_rows(a, b);
825 // Write the locals `b` conflicts with to `a`'s row.
826 self.matrix.union_rows(b, a);
827 }
828 }
829
830 /// A `dest = {move} src;` statement at `loc`.
831 ///
832 /// We want to consider merging `dest` and `src` due to this assignment.
833 #[derive(Debug, Copy, Clone)]
834 struct CandidateAssignment<'tcx> {
835 /// Does not contain indirection or indexing (so the only local it contains is the place base).
836 dest: Place<'tcx>,
837 src: Local,
838 loc: Location,
839 }
840
841 /// Scans the MIR for assignments between locals that we might want to consider merging.
842 ///
843 /// This will filter out assignments that do not match the right form (as described in the top-level
844 /// comment) and also throw out assignments that involve a local that has its address taken or is
845 /// otherwise ineligible (eg. locals used as array indices are ignored because we cannot propagate
846 /// arbitrary places into array indices).
find_candidates<'a, 'tcx>( tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, ) -> Vec<CandidateAssignment<'tcx>>847 fn find_candidates<'a, 'tcx>(
848 tcx: TyCtxt<'tcx>,
849 body: &'a Body<'tcx>,
850 ) -> Vec<CandidateAssignment<'tcx>> {
851 let mut visitor = FindAssignments {
852 tcx,
853 body,
854 candidates: Vec::new(),
855 ever_borrowed_locals: ever_borrowed_locals(body),
856 locals_used_as_array_index: locals_used_as_array_index(body),
857 };
858 visitor.visit_body(body);
859 visitor.candidates
860 }
861
862 struct FindAssignments<'a, 'tcx> {
863 tcx: TyCtxt<'tcx>,
864 body: &'a Body<'tcx>,
865 candidates: Vec<CandidateAssignment<'tcx>>,
866 ever_borrowed_locals: BitSet<Local>,
867 locals_used_as_array_index: BitSet<Local>,
868 }
869
870 impl<'a, 'tcx> Visitor<'tcx> for FindAssignments<'a, 'tcx> {
visit_statement(&mut self, statement: &Statement<'tcx>, location: Location)871 fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
872 if let StatementKind::Assign(box (
873 dest,
874 Rvalue::Use(Operand::Copy(src) | Operand::Move(src)),
875 )) = &statement.kind
876 {
877 // `dest` must not have pointer indirection.
878 if dest.is_indirect() {
879 return;
880 }
881
882 // `src` must be a plain local.
883 if !src.projection.is_empty() {
884 return;
885 }
886
887 // Since we want to replace `src` with `dest`, `src` must not be required.
888 if is_local_required(src.local, self.body) {
889 return;
890 }
891
892 // Can't optimize if both locals ever have their address taken (can introduce
893 // aliasing).
894 // FIXME: This can be smarter and take `StorageDead` into account (which
895 // invalidates borrows).
896 if self.ever_borrowed_locals.contains(dest.local)
897 || self.ever_borrowed_locals.contains(src.local)
898 {
899 return;
900 }
901
902 assert_ne!(dest.local, src.local, "self-assignments are UB");
903
904 // We can't replace locals occurring in `PlaceElem::Index` for now.
905 if self.locals_used_as_array_index.contains(src.local) {
906 return;
907 }
908
909 // Handle the "subtle case" described above by rejecting any `dest` that is or
910 // projects through a union.
911 let mut place_ty = PlaceTy::from_ty(self.body.local_decls[dest.local].ty);
912 if place_ty.ty.is_union() {
913 return;
914 }
915 for elem in dest.projection {
916 if let PlaceElem::Index(_) = elem {
917 // `dest` contains an indexing projection.
918 return;
919 }
920
921 place_ty = place_ty.projection_ty(self.tcx, elem);
922 if place_ty.ty.is_union() {
923 return;
924 }
925 }
926
927 self.candidates.push(CandidateAssignment {
928 dest: *dest,
929 src: src.local,
930 loc: location,
931 });
932 }
933 }
934 }
935
936 /// Some locals are part of the function's interface and can not be removed.
937 ///
938 /// Note that these locals *can* still be merged with non-required locals by removing that other
939 /// local.
is_local_required(local: Local, body: &Body<'_>) -> bool940 fn is_local_required(local: Local, body: &Body<'_>) -> bool {
941 match body.local_kind(local) {
942 LocalKind::Arg | LocalKind::ReturnPointer => true,
943 LocalKind::Var | LocalKind::Temp => false,
944 }
945 }
946
947 /// Walks MIR to find all locals that have their address taken anywhere.
ever_borrowed_locals(body: &Body<'_>) -> BitSet<Local>948 fn ever_borrowed_locals(body: &Body<'_>) -> BitSet<Local> {
949 let mut visitor = BorrowCollector { locals: BitSet::new_empty(body.local_decls.len()) };
950 visitor.visit_body(body);
951 visitor.locals
952 }
953
954 struct BorrowCollector {
955 locals: BitSet<Local>,
956 }
957
958 impl<'tcx> Visitor<'tcx> for BorrowCollector {
visit_rvalue(&mut self, rvalue: &Rvalue<'tcx>, location: Location)959 fn visit_rvalue(&mut self, rvalue: &Rvalue<'tcx>, location: Location) {
960 self.super_rvalue(rvalue, location);
961
962 match rvalue {
963 Rvalue::AddressOf(_, borrowed_place) | Rvalue::Ref(_, _, borrowed_place) => {
964 if !borrowed_place.is_indirect() {
965 self.locals.insert(borrowed_place.local);
966 }
967 }
968
969 Rvalue::Cast(..)
970 | Rvalue::ShallowInitBox(..)
971 | Rvalue::Use(..)
972 | Rvalue::Repeat(..)
973 | Rvalue::Len(..)
974 | Rvalue::BinaryOp(..)
975 | Rvalue::CheckedBinaryOp(..)
976 | Rvalue::NullaryOp(..)
977 | Rvalue::UnaryOp(..)
978 | Rvalue::Discriminant(..)
979 | Rvalue::Aggregate(..)
980 | Rvalue::ThreadLocalRef(..) => {}
981 }
982 }
983
visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location)984 fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location) {
985 self.super_terminator(terminator, location);
986
987 match terminator.kind {
988 TerminatorKind::Drop { place: dropped_place, .. }
989 | TerminatorKind::DropAndReplace { place: dropped_place, .. } => {
990 self.locals.insert(dropped_place.local);
991 }
992
993 TerminatorKind::Abort
994 | TerminatorKind::Assert { .. }
995 | TerminatorKind::Call { .. }
996 | TerminatorKind::FalseEdge { .. }
997 | TerminatorKind::FalseUnwind { .. }
998 | TerminatorKind::GeneratorDrop
999 | TerminatorKind::Goto { .. }
1000 | TerminatorKind::Resume
1001 | TerminatorKind::Return
1002 | TerminatorKind::SwitchInt { .. }
1003 | TerminatorKind::Unreachable
1004 | TerminatorKind::Yield { .. }
1005 | TerminatorKind::InlineAsm { .. } => {}
1006 }
1007 }
1008 }
1009
1010 /// `PlaceElem::Index` only stores a `Local`, so we can't replace that with a full `Place`.
1011 ///
1012 /// Collect locals used as indices so we don't generate candidates that are impossible to apply
1013 /// later.
locals_used_as_array_index(body: &Body<'_>) -> BitSet<Local>1014 fn locals_used_as_array_index(body: &Body<'_>) -> BitSet<Local> {
1015 let mut visitor = IndexCollector { locals: BitSet::new_empty(body.local_decls.len()) };
1016 visitor.visit_body(body);
1017 visitor.locals
1018 }
1019
1020 struct IndexCollector {
1021 locals: BitSet<Local>,
1022 }
1023
1024 impl<'tcx> Visitor<'tcx> for IndexCollector {
visit_projection_elem( &mut self, local: Local, proj_base: &[PlaceElem<'tcx>], elem: PlaceElem<'tcx>, context: PlaceContext, location: Location, )1025 fn visit_projection_elem(
1026 &mut self,
1027 local: Local,
1028 proj_base: &[PlaceElem<'tcx>],
1029 elem: PlaceElem<'tcx>,
1030 context: PlaceContext,
1031 location: Location,
1032 ) {
1033 if let PlaceElem::Index(i) = elem {
1034 self.locals.insert(i);
1035 }
1036 self.super_projection_elem(local, proj_base, elem, context, location);
1037 }
1038 }
1039