1 //! This pass finds basic blocks that are completely equal,
2 //! and replaces all uses with just one of them.
4 use std::{collections::hash_map::Entry, hash::Hash, hash::Hasher, iter};
8 use rustc_data_structures::fx::FxHashMap;
9 use rustc_middle::mir::visit::MutVisitor;
10 use rustc_middle::mir::*;
11 use rustc_middle::ty::TyCtxt;
13 use super::simplify::simplify_cfg;
15 pub struct DeduplicateBlocks;
17 impl<'tcx> MirPass<'tcx> for DeduplicateBlocks {
18 fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
19 sess.mir_opt_level() >= 4
22 fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
23 debug!("Running DeduplicateBlocks on `{:?}`", body.source);
24 let duplicates = find_duplicates(body);
25 let has_opts_to_apply = !duplicates.is_empty();
27 if has_opts_to_apply {
28 let mut opt_applier = OptApplier { tcx, duplicates };
29 opt_applier.visit_body(body);
30 simplify_cfg(tcx, body);
35 struct OptApplier<'tcx> {
37 duplicates: FxHashMap<BasicBlock, BasicBlock>,
40 impl<'tcx> MutVisitor<'tcx> for OptApplier<'tcx> {
41 fn tcx(&self) -> TyCtxt<'tcx> {
45 fn visit_terminator(&mut self, terminator: &mut Terminator<'tcx>, location: Location) {
46 for target in terminator.successors_mut() {
47 if let Some(replacement) = self.duplicates.get(target) {
48 debug!("SUCCESS: Replacing: `{:?}` with `{:?}`", target, replacement);
49 *target = *replacement;
53 self.super_terminator(terminator, location);
57 fn find_duplicates(body: &Body<'_>) -> FxHashMap<BasicBlock, BasicBlock> {
58 let mut duplicates = FxHashMap::default();
60 let bbs_to_go_through =
61 body.basic_blocks.iter_enumerated().filter(|(_, bbd)| !bbd.is_cleanup).count();
64 FxHashMap::with_capacity_and_hasher(bbs_to_go_through, Default::default());
66 // Go through the basic blocks backwards. This means that in case of duplicates,
67 // we can use the basic block with the highest index as the replacement for all lower ones.
68 // For example, if bb1, bb2 and bb3 are duplicates, we will first insert bb3 in same_hashes.
69 // Then we will see that bb2 is a duplicate of bb3,
70 // and insert bb2 with the replacement bb3 in the duplicates list.
71 // When we see bb1, we see that it is a duplicate of bb3, and therefore insert it in the duplicates list
72 // with replacement bb3.
73 // When the duplicates are removed, we will end up with only bb3.
74 for (bb, bbd) in body.basic_blocks.iter_enumerated().rev().filter(|(_, bbd)| !bbd.is_cleanup) {
75 // Basic blocks can get really big, so to avoid checking for duplicates in basic blocks
76 // that are unlikely to have duplicates, we stop early. The early bail number has been
77 // found experimentally by eprintln while compiling the crates in the rustc-perf suite.
78 if bbd.statements.len() > 10 {
82 let to_hash = BasicBlockHashable { basic_block_data: bbd };
83 let entry = same_hashes.entry(to_hash);
85 Entry::Occupied(occupied) => {
86 // The basic block was already in the hashmap, which means we have a duplicate
87 let value = *occupied.get();
88 debug!("Inserting {:?} -> {:?}", bb, value);
89 duplicates.try_insert(bb, value).expect("key was already inserted");
91 Entry::Vacant(vacant) => {
100 struct BasicBlockHashable<'tcx, 'a> {
101 basic_block_data: &'a BasicBlockData<'tcx>,
104 impl Hash for BasicBlockHashable<'_, '_> {
105 fn hash<H: Hasher>(&self, state: &mut H) {
106 hash_statements(state, self.basic_block_data.statements.iter());
107 // Note that since we only hash the kind, we lose span information if we deduplicate the blocks
108 self.basic_block_data.terminator().kind.hash(state);
112 impl Eq for BasicBlockHashable<'_, '_> {}
114 impl PartialEq for BasicBlockHashable<'_, '_> {
115 fn eq(&self, other: &Self) -> bool {
116 self.basic_block_data.statements.len() == other.basic_block_data.statements.len()
117 && &self.basic_block_data.terminator().kind == &other.basic_block_data.terminator().kind
118 && iter::zip(&self.basic_block_data.statements, &other.basic_block_data.statements)
119 .all(|(x, y)| statement_eq(&x.kind, &y.kind))
123 fn hash_statements<'a, 'tcx, H: Hasher>(
125 iter: impl Iterator<Item = &'a Statement<'tcx>>,
130 statement_hash(hasher, &stmt.kind);
134 fn statement_hash<H: Hasher>(hasher: &mut H, stmt: &StatementKind<'_>) {
136 StatementKind::Assign(box (place, rvalue)) => {
138 rvalue_hash(hasher, rvalue)
144 fn rvalue_hash<H: Hasher>(hasher: &mut H, rvalue: &Rvalue<'_>) {
146 Rvalue::Use(op) => operand_hash(hasher, op),
151 fn operand_hash<H: Hasher>(hasher: &mut H, operand: &Operand<'_>) {
153 Operand::Constant(box Constant { user_ty: _, literal, span: _ }) => literal.hash(hasher),
158 fn statement_eq<'tcx>(lhs: &StatementKind<'tcx>, rhs: &StatementKind<'tcx>) -> bool {
159 let res = match (lhs, rhs) {
161 StatementKind::Assign(box (place, rvalue)),
162 StatementKind::Assign(box (place2, rvalue2)),
163 ) => place == place2 && rvalue_eq(rvalue, rvalue2),
166 debug!("statement_eq lhs: `{:?}` rhs: `{:?}` result: {:?}", lhs, rhs, res);
170 fn rvalue_eq<'tcx>(lhs: &Rvalue<'tcx>, rhs: &Rvalue<'tcx>) -> bool {
171 let res = match (lhs, rhs) {
172 (Rvalue::Use(op1), Rvalue::Use(op2)) => operand_eq(op1, op2),
175 debug!("rvalue_eq lhs: `{:?}` rhs: `{:?}` result: {:?}", lhs, rhs, res);
179 fn operand_eq<'tcx>(lhs: &Operand<'tcx>, rhs: &Operand<'tcx>) -> bool {
180 let res = match (lhs, rhs) {
182 Operand::Constant(box Constant { user_ty: _, literal, span: _ }),
183 Operand::Constant(box Constant { user_ty: _, literal: literal2, span: _ }),
184 ) => literal == literal2,
187 debug!("operand_eq lhs: `{:?}` rhs: `{:?}` result: {:?}", lhs, rhs, res);