1use itertools::Itertools as _;
38use rustc_data_structures::thin_vec::ThinVec;
39use rustc_index::bit_set::DenseBitSet;
40use rustc_index::{Idx, IndexSlice, IndexVec};
41use rustc_middle::mir::visit::{MutVisitor, MutatingUseContext, PlaceContext, Visitor};
42use rustc_middle::mir::*;
43use rustc_middle::ty::TyCtxt;
44use rustc_mir_dataflow::debuginfo::debuginfo_locals;
45use rustc_span::DUMMY_SP;
46use smallvec::SmallVec;
47use tracing::{debug, trace};
48
49use crate::PassPolicy;
50
51pub(super) enum SimplifyCfg {
52 Initial,
53 PromoteConsts,
54 RemoveFalseEdges,
55 PostAnalysis,
57 PreOptimizations,
60 Final,
61 MakeShim,
62 AfterUnreachableEnumBranching,
63}
64
65impl SimplifyCfg {
66 fn name(&self) -> &'static str {
67 match self {
68 SimplifyCfg::Initial => "SimplifyCfg-initial",
69 SimplifyCfg::PromoteConsts => "SimplifyCfg-promote-consts",
70 SimplifyCfg::RemoveFalseEdges => "SimplifyCfg-remove-false-edges",
71 SimplifyCfg::PostAnalysis => "SimplifyCfg-post-analysis",
72 SimplifyCfg::PreOptimizations => "SimplifyCfg-pre-optimizations",
73 SimplifyCfg::Final => "SimplifyCfg-final",
74 SimplifyCfg::MakeShim => "SimplifyCfg-make_shim",
75 SimplifyCfg::AfterUnreachableEnumBranching => {
76 "SimplifyCfg-after-unreachable-enum-branching"
77 }
78 }
79 }
80}
81
82pub(super) fn simplify_cfg<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
83 if CfgSimplifier::new(tcx, body).simplify() {
84 body.basic_blocks.invalidate_cfg_cache();
87 }
88 remove_dead_blocks(body);
89
90 body.basic_blocks.as_mut_preserves_cfg().shrink_to_fit();
92}
93
94impl<'tcx> crate::MirPass<'tcx> for SimplifyCfg {
95 fn name(&self) -> &'static str {
96 self.name()
97 }
98
99 fn policy(&self, _ctx: &crate::PassCtx<'_>) -> PassPolicy {
100 PassPolicy::optional(true)
101 }
102
103 fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
104 debug!("SimplifyCfg({:?}) - simplifying {:?}", self.name(), body.source);
105 simplify_cfg(tcx, body);
106 }
107}
108
109struct CfgSimplifier<'a, 'tcx> {
110 preserve_switch_reads: bool,
111 basic_blocks: &'a mut IndexSlice<BasicBlock, BasicBlockData<'tcx>>,
112 pred_count: IndexVec<BasicBlock, u32>,
113}
114
115impl<'a, 'tcx> CfgSimplifier<'a, 'tcx> {
116 fn new(tcx: TyCtxt<'tcx>, body: &'a mut Body<'tcx>) -> Self {
117 let mut pred_count = IndexVec::from_elem(0u32, &body.basic_blocks);
118
119 pred_count[START_BLOCK] = 1;
122
123 for (_, data) in traversal::preorder(body) {
124 if let Some(ref term) = data.terminator {
125 for tgt in term.successors() {
126 pred_count[tgt] += 1;
127 }
128 }
129 }
130
131 let preserve_switch_reads = matches!(body.phase, MirPhase::Built | MirPhase::Analysis(_))
133 || tcx.sess.opts.unstable_opts.mir_preserve_ub;
134 let basic_blocks = body.basic_blocks.as_mut_preserves_cfg();
136
137 CfgSimplifier { preserve_switch_reads, basic_blocks, pred_count }
138 }
139
140 #[must_use]
143 fn simplify(mut self) -> bool {
144 self.strip_nops();
145
146 let mut merged_blocks: Vec<BasicBlock> = Vec::new();
151 let mut outer_changed = false;
152 loop {
153 let mut changed = false;
154
155 for bb in self.basic_blocks.indices() {
156 if self.pred_count[bb] == 0 {
157 continue;
158 }
159
160 debug!("simplifying {:?}", bb);
161
162 let mut terminator = self.take_terminator(bb).expect("invalid terminator state");
163
164 terminator.successors_mut(|successor| {
165 self.collapse_goto_chain(successor, &mut changed);
166 });
167
168 let mut inner_changed = true;
169 merged_blocks.clear();
170 while inner_changed {
171 inner_changed = false;
172 inner_changed |= self.simplify_branch(&mut terminator);
173 inner_changed |= self.merge_successor(&mut merged_blocks, &mut terminator);
174 changed |= inner_changed;
175 }
176
177 let statements_to_merge =
178 merged_blocks.iter().map(|&i| self.basic_blocks[i].statements.len()).sum();
179
180 if statements_to_merge > 0 {
181 let mut statements = std::mem::take(&mut self.basic_blocks[bb].statements);
182 statements.reserve(statements_to_merge);
183 let mut parent_bb_last_debuginfos =
184 std::mem::take(&mut self.basic_blocks[bb].after_last_stmt_debuginfos);
185 for &from in &merged_blocks {
186 if let Some(stmt) = self.basic_blocks[from].statements.first_mut() {
187 stmt.debuginfos.prepend(&mut parent_bb_last_debuginfos);
188 }
189 statements.append(&mut self.basic_blocks[from].statements);
190 parent_bb_last_debuginfos =
191 std::mem::take(&mut self.basic_blocks[from].after_last_stmt_debuginfos);
192 }
193 self.basic_blocks[bb].statements = statements;
194 self.basic_blocks[bb].after_last_stmt_debuginfos = parent_bb_last_debuginfos;
195 }
196
197 self.basic_blocks[bb].terminator = Some(terminator);
198 }
199
200 if !changed {
201 break;
202 }
203
204 outer_changed = true;
205 }
206
207 outer_changed
208 }
209
210 fn take_terminator(&mut self, bb: BasicBlock) -> Option<Terminator<'tcx>> {
212 if has_dummy_terminator(&self.basic_blocks[bb]) {
213 return None;
214 }
215 let dummy_terminator = Terminator {
216 source_info: SourceInfo { span: DUMMY_SP, scope: SourceScope::ZERO },
217 kind: TerminatorKind::Goto { target: BasicBlock::MAX, loop_hint_attrs: ThinVec::new() },
218 };
219 std::mem::replace(&mut self.basic_blocks[bb].terminator, Some(dummy_terminator))
220 }
221
222 fn take_terminator_if_simple_goto(&mut self, bb: BasicBlock) -> Option<Terminator<'tcx>> {
227 match self.basic_blocks[bb] {
228 BasicBlockData {
229 ref statements,
230 terminator:
231 ref mut terminator @ Some(Terminator { kind: TerminatorKind::Goto { .. }, .. }),
232 ..
233 } if statements.is_empty() => self.take_terminator(bb),
234 _ => None,
237 }
238 }
239
240 fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) {
242 let mut terminators: SmallVec<[_; 1]> = Default::default();
245 let mut current = *start;
246 let mut trivial_goto_chain = true;
249 while let Some(terminator) = self.take_terminator_if_simple_goto(current) {
250 let Terminator { kind: TerminatorKind::Goto { target, .. }, .. } = terminator else {
251 unreachable!();
252 };
253 trivial_goto_chain &= self.pred_count[target] == 1;
254 terminators.push((current, terminator));
255 current = target;
256 }
257 let last = current;
258 *changed |= *start != last;
259 *start = last;
260 while let Some((current, mut terminator)) = terminators.pop() {
261 let Terminator { kind: TerminatorKind::Goto { ref mut target, .. }, .. } = terminator
262 else {
263 unreachable!();
264 };
265 if trivial_goto_chain {
266 let mut pred_debuginfos =
267 std::mem::take(&mut self.basic_blocks[current].after_last_stmt_debuginfos);
268 let debuginfos = if let Some(stmt) = self.basic_blocks[last].statements.first_mut()
269 {
270 &mut stmt.debuginfos
271 } else {
272 &mut self.basic_blocks[last].after_last_stmt_debuginfos
273 };
274 debuginfos.prepend(&mut pred_debuginfos);
275 }
276 *changed |= *target != last;
277 *target = last;
278 debug!("collapsing goto chain from {:?} to {:?}", current, target);
279
280 if self.pred_count[current] == 1 {
281 self.pred_count[current] = 0;
284 } else {
285 self.pred_count[*target] += 1;
286 self.pred_count[current] -= 1;
287 }
288 self.basic_blocks[current].terminator = Some(terminator);
289 }
290 }
291
292 fn merge_successor(
294 &mut self,
295 merged_blocks: &mut Vec<BasicBlock>,
296 terminator: &mut Terminator<'tcx>,
297 ) -> bool {
298 let target = match terminator.kind {
299 TerminatorKind::Goto { target, .. } if self.pred_count[target] == 1 => target,
300 _ => return false,
301 };
302
303 debug!("merging block {:?} into {:?}", target, terminator);
304 *terminator = match self.take_terminator(target) {
305 Some(terminator) => terminator,
306 None => {
307 return false;
310 }
311 };
312
313 merged_blocks.push(target);
314 self.pred_count[target] = 0;
315
316 true
317 }
318
319 fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool {
321 if self.preserve_switch_reads {
325 return false;
326 }
327
328 let TerminatorKind::SwitchInt { .. } = terminator.kind else {
329 return false;
330 };
331
332 let Ok(first_succ) = terminator.successors().all_equal_value() else {
333 return false;
334 };
335
336 let count = terminator.successors().count();
337 self.pred_count[first_succ] -= (count - 1) as u32;
338
339 debug!("simplifying branch {:?}", terminator);
340 terminator.kind = TerminatorKind::goto(first_succ);
341 true
342 }
343
344 fn strip_nops(&mut self) {
345 for blk in self.basic_blocks.iter_mut() {
346 blk.strip_nops();
347 }
348 }
349}
350
351pub(super) fn simplify_duplicate_switch_targets(terminator: &mut Terminator<'_>) {
352 if let TerminatorKind::SwitchInt { targets, .. } = &mut terminator.kind {
353 let otherwise = targets.otherwise();
354 if targets.iter().any(|t| t.1 == otherwise) {
355 *targets = SwitchTargets::new(
356 targets.iter().filter(|t| t.1 != otherwise),
357 targets.otherwise(),
358 );
359 }
360 }
361}
362
363pub(super) fn remove_dead_blocks(body: &mut Body<'_>) {
364 let should_deduplicate_unreachable = |bbdata: &BasicBlockData<'_>| {
365 !has_dummy_terminator(bbdata) && bbdata.is_empty_unreachable() && !bbdata.is_cleanup
371 };
372
373 let reachable = traversal::reachable_as_bitset(body);
374 let empty_unreachable_blocks = body
375 .basic_blocks
376 .iter_enumerated()
377 .filter(|(bb, bbdata)| should_deduplicate_unreachable(bbdata) && reachable.contains(*bb))
378 .count();
379
380 let num_blocks = body.basic_blocks.len();
381 if num_blocks == reachable.count() && empty_unreachable_blocks <= 1 {
382 return;
383 }
384
385 let basic_blocks = body.basic_blocks.as_mut();
386
387 let mut replacements: Vec<_> = (0..num_blocks).map(BasicBlock::new).collect();
388 let mut orig_index = 0;
389 let mut used_index = 0;
390 let mut kept_unreachable = None;
391 let mut deduplicated_unreachable = false;
392 basic_blocks.raw.retain(|bbdata| {
393 let orig_bb = BasicBlock::new(orig_index);
394 if !reachable.contains(orig_bb) {
395 orig_index += 1;
396 return false;
397 }
398
399 let used_bb = BasicBlock::new(used_index);
400 if should_deduplicate_unreachable(bbdata) {
401 let kept_unreachable = *kept_unreachable.get_or_insert(used_bb);
402 if kept_unreachable != used_bb {
403 replacements[orig_index] = kept_unreachable;
404 deduplicated_unreachable = true;
405 orig_index += 1;
406 return false;
407 }
408 }
409
410 replacements[orig_index] = used_bb;
411 used_index += 1;
412 orig_index += 1;
413 true
414 });
415
416 if deduplicated_unreachable {
420 basic_blocks[kept_unreachable.unwrap()].terminator_mut().source_info =
421 SourceInfo { span: DUMMY_SP, scope: OUTERMOST_SOURCE_SCOPE };
422 }
423
424 for block in basic_blocks {
425 block.terminator_mut().successors_mut(|target| *target = replacements[target.index()]);
426 }
427}
428
429fn has_dummy_terminator(bbdata: &BasicBlockData<'_>) -> bool {
430 match bbdata.terminator().kind {
431 TerminatorKind::Goto { target, .. } => target == BasicBlock::MAX,
432 _ => false,
433 }
434}
435
436pub(super) enum SimplifyLocals {
437 BeforeConstProp,
438 AfterGVN,
439 Final,
440}
441
442impl<'tcx> crate::MirPass<'tcx> for SimplifyLocals {
443 fn name(&self) -> &'static str {
444 match &self {
445 SimplifyLocals::BeforeConstProp => "SimplifyLocals-before-const-prop",
446 SimplifyLocals::AfterGVN => "SimplifyLocals-after-value-numbering",
447 SimplifyLocals::Final => "SimplifyLocals-final",
448 }
449 }
450
451 fn policy(&self, ctx: &crate::PassCtx<'_>) -> PassPolicy {
452 PassPolicy::optional(ctx.mir_opt_level() >= 1)
453 }
454
455 fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
456 trace!("running SimplifyLocals on {:?}", body.source);
457
458 let mut used_locals = UsedLocals::new(body);
460
461 remove_unused_definitions_helper(&mut used_locals, body);
467
468 let map = make_local_map(&mut body.local_decls, &used_locals);
471
472 if map.iter().any(Option::is_none) {
474 let mut updater = LocalUpdater { map, tcx };
476 updater.visit_body_preserves_cfg(body);
477
478 body.local_decls.shrink_to_fit();
479 }
480 }
481}
482
483pub(super) fn remove_unused_definitions<'tcx>(body: &mut Body<'tcx>) {
484 let mut used_locals = UsedLocals::new(body);
486
487 remove_unused_definitions_helper(&mut used_locals, body);
493}
494
495fn make_local_map<V>(
497 local_decls: &mut IndexVec<Local, V>,
498 used_locals: &UsedLocals,
499) -> IndexVec<Local, Option<Local>> {
500 let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, local_decls);
501 let mut used = Local::ZERO;
502
503 for alive_index in local_decls.indices() {
504 if !used_locals.is_used(alive_index) {
506 continue;
507 }
508
509 map[alive_index] = Some(used);
510 if alive_index != used {
511 local_decls.swap(alive_index, used);
512 }
513 used.increment_by(1);
514 }
515 local_decls.truncate(used.index());
516 map
517}
518
519struct UsedLocals {
521 increment: bool,
522 use_count: IndexVec<Local, u32>,
523 always_used: DenseBitSet<Local>,
524}
525
526impl UsedLocals {
527 fn new(body: &Body<'_>) -> Self {
529 let mut always_used = debuginfo_locals(body);
530 always_used.insert(RETURN_PLACE);
531 for arg in body.args_iter() {
532 always_used.insert(arg);
533 }
534 let mut this = Self {
535 increment: true,
536 use_count: IndexVec::from_elem(0, &body.local_decls),
537 always_used,
538 };
539 this.visit_body(body);
540 this
541 }
542
543 fn is_used(&self, local: Local) -> bool {
547 trace!(
548 "is_used({:?}): use_count: {:?}, always_used: {}",
549 local,
550 self.use_count[local],
551 self.always_used.contains(local)
552 );
553 self.always_used.contains(local) || self.use_count[local] != 0
555 }
556
557 fn statement_removed(&mut self, statement: &Statement<'_>) {
559 self.increment = false;
560
561 let location = Location::START;
563 self.visit_statement(statement, location);
564 }
565
566 fn visit_lhs(&mut self, place: &Place<'_>, location: Location) {
568 if place.is_indirect() {
569 self.visit_place(place, PlaceContext::MutatingUse(MutatingUseContext::Store), location);
571 } else {
572 self.super_projection(
576 place.as_ref(),
577 PlaceContext::MutatingUse(MutatingUseContext::Projection),
578 location,
579 );
580 }
581 }
582}
583
584impl<'tcx> Visitor<'tcx> for UsedLocals {
585 fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
586 match statement.kind {
587 StatementKind::Intrinsic(..)
588 | StatementKind::Coverage(..)
589 | StatementKind::FakeRead(..)
590 | StatementKind::PlaceMention(..)
591 | StatementKind::AscribeUserType(..) => {
592 self.super_statement(statement, location);
593 }
594
595 StatementKind::ConstEvalCounter
596 | StatementKind::Nop
597 | StatementKind::StorageLive(..)
598 | StatementKind::StorageDead(..) => {}
599 StatementKind::Assign((ref place, ref rvalue)) => {
600 if rvalue.is_safe_to_remove() {
601 self.visit_lhs(place, location);
602 self.visit_rvalue(rvalue, location);
603 } else {
604 self.super_statement(statement, location);
605 }
606 }
607
608 StatementKind::SetDiscriminant { ref place, variant_index: _ }
609 | StatementKind::BackwardIncompatibleDropHint { ref place, reason: _ } => {
610 self.visit_lhs(place, location);
611 }
612 }
613 }
614
615 fn visit_local(&mut self, local: Local, ctx: PlaceContext, _location: Location) {
616 if matches!(ctx, PlaceContext::NonUse(_)) {
617 return;
618 }
619 if self.increment {
620 self.use_count[local] += 1;
621 } else {
622 assert_ne!(self.use_count[local], 0);
623 self.use_count[local] -= 1;
624 }
625 }
626}
627
628fn remove_unused_definitions_helper(used_locals: &mut UsedLocals, body: &mut Body<'_>) {
630 let mut modified = true;
636 while modified {
637 modified = false;
638
639 for data in body.basic_blocks.as_mut_preserves_cfg() {
640 for statement in data.statements.iter_mut() {
642 let keep_statement = match &statement.kind {
643 StatementKind::StorageLive(local) | StatementKind::StorageDead(local) => {
644 used_locals.is_used(*local)
645 }
646 StatementKind::Assign((place, _)) => used_locals.is_used(place.local),
647 StatementKind::SetDiscriminant { place, .. }
648 | StatementKind::BackwardIncompatibleDropHint { place, .. } => {
649 used_locals.is_used(place.local)
650 }
651 _ => continue,
652 };
653 if keep_statement {
654 continue;
655 }
656 trace!("removing statement {:?}", statement);
657 modified = true;
658 used_locals.statement_removed(statement);
659 statement.make_nop(true);
660 }
661 data.strip_nops();
662 }
663 }
664}
665
666struct LocalUpdater<'tcx> {
667 map: IndexVec<Local, Option<Local>>,
668 tcx: TyCtxt<'tcx>,
669}
670
671impl<'tcx> MutVisitor<'tcx> for LocalUpdater<'tcx> {
672 fn tcx(&self) -> TyCtxt<'tcx> {
673 self.tcx
674 }
675
676 fn visit_statement_debuginfo(
677 &mut self,
678 stmt_debuginfo: &mut StmtDebugInfo<'tcx>,
679 location: Location,
680 ) {
681 match stmt_debuginfo {
682 StmtDebugInfo::AssignRef(local, place) => {
683 if place.as_ref().accessed_locals().any(|local| self.map[local].is_none()) {
684 *stmt_debuginfo = StmtDebugInfo::InvalidAssign(*local);
685 }
686 }
687 StmtDebugInfo::InvalidAssign(_) => {}
688 }
689 self.super_statement_debuginfo(stmt_debuginfo, location);
690 }
691
692 fn visit_local(&mut self, l: &mut Local, _: PlaceContext, _: Location) {
693 *l = self.map[*l].unwrap();
694 }
695}
696
697pub(crate) struct UsedInStmtLocals {
698 pub(crate) locals: DenseBitSet<Local>,
699}
700
701impl UsedInStmtLocals {
702 pub(crate) fn new(body: &Body<'_>) -> Self {
703 let mut this = Self { locals: DenseBitSet::new_empty(body.local_decls.len()) };
704 this.visit_body(body);
705 this
706 }
707
708 pub(crate) fn remove_unused_storage_annotations<'tcx>(&self, body: &mut Body<'tcx>) {
709 for data in body.basic_blocks.as_mut_preserves_cfg() {
710 for statement in data.statements.iter_mut() {
712 let keep_statement = match &statement.kind {
713 StatementKind::StorageLive(local) | StatementKind::StorageDead(local) => {
714 self.locals.contains(*local)
715 }
716 _ => continue,
717 };
718 if keep_statement {
719 continue;
720 }
721 statement.make_nop(true);
722 }
723 }
724 }
725}
726
727impl<'tcx> Visitor<'tcx> for UsedInStmtLocals {
728 fn visit_local(&mut self, local: Local, context: PlaceContext, _: Location) {
729 if matches!(context, PlaceContext::NonUse(_)) {
730 return;
731 }
732 self.locals.insert(local);
733 }
734}