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