compiler/rustc_mir/src/transform/deduplicate_blocks.rs

   1 //! This pass finds basic blocks that are completely equal,
   2 //! and replaces all uses with just one of them.
   3
   4 use std::{collections::hash_map::Entry, hash::Hash, hash::Hasher};
   5
   6 use crate::transform::MirPass;
   7
   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;
  12
  13 use super::simplify::simplify_cfg;
  14
  15 pub struct DeduplicateBlocks;
  16
  17 impl<'tcx> MirPass<'tcx> for DeduplicateBlocks {
  18     fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
  19         if tcx.sess.mir_opt_level() < 4 {
  20             return;
  21         }
  22         debug!("Running DeduplicateBlocks on `{:?}`", body.source);
  23         let duplicates = find_duplicates(body);
  24         let has_opts_to_apply = !duplicates.is_empty();
  25
  26         if has_opts_to_apply {
  27             let mut opt_applier = OptApplier { tcx, duplicates };
  28             opt_applier.visit_body(body);
  29             simplify_cfg(body);
  30         }
  31     }
  32 }
  33
  34 struct OptApplier<'tcx> {
  35     tcx: TyCtxt<'tcx>,
  36     duplicates: FxHashMap<BasicBlock, BasicBlock>,
  37 }
  38
  39 impl<'tcx> MutVisitor<'tcx> for OptApplier<'tcx> {
  40     fn tcx(&self) -> TyCtxt<'tcx> {
  41         self.tcx
  42     }
  43
  44     fn visit_terminator(&mut self, terminator: &mut Terminator<'tcx>, location: Location) {
  45         for target in terminator.successors_mut() {
  46             if let Some(replacement) = self.duplicates.get(target) {
  47                 debug!("SUCCESS: Replacing: `{:?}` with `{:?}`", target, replacement);
  48                 *target = *replacement;
  49             }
  50         }
  51
  52         self.super_terminator(terminator, location);
  53     }
  54 }
  55
  56 fn find_duplicates<'a, 'tcx>(body: &'a Body<'tcx>) -> FxHashMap<BasicBlock, BasicBlock> {
  57     let mut duplicates = FxHashMap::default();
  58
  59     let bbs_to_go_through =
  60         body.basic_blocks().iter_enumerated().filter(|(_, bbd)| !bbd.is_cleanup).count();
  61
  62     let mut same_hashes =
  63         FxHashMap::with_capacity_and_hasher(bbs_to_go_through, Default::default());
  64
  65     // Go through the basic blocks backwards. This means that in case of duplicates,
  66     // we can use the basic block with the highest index as the replacement for all lower ones.
  67     // For example, if bb1, bb2 and bb3 are duplicates, we will first insert bb3 in same_hashes.
  68     // Then we will see that bb2 is a duplicate of bb3,
  69     // and insert bb2 with the replacement bb3 in the duplicates list.
  70     // When we see bb1, we see that it is a duplicate of bb3, and therefore insert it in the duplicates list
  71     // with replacement bb3.
  72     // When the duplicates are removed, we will end up with only bb3.
  73     for (bb, bbd) in body.basic_blocks().iter_enumerated().rev().filter(|(_, bbd)| !bbd.is_cleanup)
  74     {
  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 {
  79             continue;
  80         }
  81
  82         let to_hash = BasicBlockHashable { basic_block_data: bbd };
  83         let entry = same_hashes.entry(to_hash);
  84         match entry {
  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.insert(bb, value).expect_none("key was already inserted");
  90             }
  91             Entry::Vacant(vacant) => {
  92                 vacant.insert(bb);
  93             }
  94         }
  95     }
  96
  97     duplicates
  98 }
  99
 100 struct BasicBlockHashable<'tcx, 'a> {
 101     basic_block_data: &'a BasicBlockData<'tcx>,
 102 }
 103
 104 impl<'tcx, 'a> Hash for BasicBlockHashable<'tcx, 'a> {
 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);
 109     }
 110 }
 111
 112 impl<'tcx, 'a> Eq for BasicBlockHashable<'tcx, 'a> {}
 113
 114 impl<'tcx, 'a> PartialEq for BasicBlockHashable<'tcx, 'a> {
 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             && self
 119                 .basic_block_data
 120                 .statements
 121                 .iter()
 122                 .zip(&other.basic_block_data.statements)
 123                 .all(|(x, y)| statement_eq(&x.kind, &y.kind))
 124     }
 125 }
 126
 127 fn hash_statements<'a, 'tcx, H: Hasher>(
 128     hasher: &mut H,
 129     iter: impl Iterator<Item = &'a Statement<'tcx>>,
 130 ) where
 131     'tcx: 'a,
 132 {
 133     for stmt in iter {
 134         statement_hash(hasher, &stmt.kind);
 135     }
 136 }
 137
 138 fn statement_hash<'tcx, H: Hasher>(hasher: &mut H, stmt: &StatementKind<'tcx>) {
 139     match stmt {
 140         StatementKind::Assign(box (place, rvalue)) => {
 141             place.hash(hasher);
 142             rvalue_hash(hasher, rvalue)
 143         }
 144         x => x.hash(hasher),
 145     };
 146 }
 147
 148 fn rvalue_hash<H: Hasher>(hasher: &mut H, rvalue: &Rvalue<'tcx>) {
 149     match rvalue {
 150         Rvalue::Use(op) => operand_hash(hasher, op),
 151         x => x.hash(hasher),
 152     };
 153 }
 154
 155 fn operand_hash<H: Hasher>(hasher: &mut H, operand: &Operand<'tcx>) {
 156     match operand {
 157         Operand::Constant(box Constant { user_ty: _, literal, span: _ }) => literal.hash(hasher),
 158         x => x.hash(hasher),
 159     };
 160 }
 161
 162 fn statement_eq<'tcx>(lhs: &StatementKind<'tcx>, rhs: &StatementKind<'tcx>) -> bool {
 163     let res = match (lhs, rhs) {
 164         (
 165             StatementKind::Assign(box (place, rvalue)),
 166             StatementKind::Assign(box (place2, rvalue2)),
 167         ) => place == place2 && rvalue_eq(rvalue, rvalue2),
 168         (x, y) => x == y,
 169     };
 170     debug!("statement_eq lhs: `{:?}` rhs: `{:?}` result: {:?}", lhs, rhs, res);
 171     res
 172 }
 173
 174 fn rvalue_eq(lhs: &Rvalue<'tcx>, rhs: &Rvalue<'tcx>) -> bool {
 175     let res = match (lhs, rhs) {
 176         (Rvalue::Use(op1), Rvalue::Use(op2)) => operand_eq(op1, op2),
 177         (x, y) => x == y,
 178     };
 179     debug!("rvalue_eq lhs: `{:?}` rhs: `{:?}` result: {:?}", lhs, rhs, res);
 180     res
 181 }
 182
 183 fn operand_eq(lhs: &Operand<'tcx>, rhs: &Operand<'tcx>) -> bool {
 184     let res = match (lhs, rhs) {
 185         (
 186             Operand::Constant(box Constant { user_ty: _, literal, span: _ }),
 187             Operand::Constant(box Constant { user_ty: _, literal: literal2, span: _ }),
 188         ) => literal == literal2,
 189         (x, y) => x == y,
 190     };
 191     debug!("operand_eq lhs: `{:?}` rhs: `{:?}` result: {:?}", lhs, rhs, res);
 192     res
 193 }