compiler/rustc_mir_transform/src/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, iter};
   5
   6 use crate::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 is_enabled(&self, sess: &rustc_session::Session) -> bool {
  19         sess.mir_opt_level() >= 4
  20     }
  21
  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();
  26
  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);
  31         }
  32     }
  33 }
  34
  35 struct OptApplier<'tcx> {
  36     tcx: TyCtxt<'tcx>,
  37     duplicates: FxHashMap<BasicBlock, BasicBlock>,
  38 }
  39
  40 impl<'tcx> MutVisitor<'tcx> for OptApplier<'tcx> {
  41     fn tcx(&self) -> TyCtxt<'tcx> {
  42         self.tcx
  43     }
  44
  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;
  50             }
  51         }
  52
  53         self.super_terminator(terminator, location);
  54     }
  55 }
  56
  57 fn find_duplicates(body: &Body<'_>) -> FxHashMap<BasicBlock, BasicBlock> {
  58     let mut duplicates = FxHashMap::default();
  59
  60     let bbs_to_go_through =
  61         body.basic_blocks().iter_enumerated().filter(|(_, bbd)| !bbd.is_cleanup).count();
  62
  63     let mut same_hashes =
  64         FxHashMap::with_capacity_and_hasher(bbs_to_go_through, Default::default());
  65
  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     {
  76         // Basic blocks can get really big, so to avoid checking for duplicates in basic blocks
  77         // that are unlikely to have duplicates, we stop early. The early bail number has been
  78         // found experimentally by eprintln while compiling the crates in the rustc-perf suite.
  79         if bbd.statements.len() > 10 {
  80             continue;
  81         }
  82
  83         let to_hash = BasicBlockHashable { basic_block_data: bbd };
  84         let entry = same_hashes.entry(to_hash);
  85         match entry {
  86             Entry::Occupied(occupied) => {
  87                 // The basic block was already in the hashmap, which means we have a duplicate
  88                 let value = *occupied.get();
  89                 debug!("Inserting {:?} -> {:?}", bb, value);
  90                 duplicates.try_insert(bb, value).expect("key was already inserted");
  91             }
  92             Entry::Vacant(vacant) => {
  93                 vacant.insert(bb);
  94             }
  95         }
  96     }
  97
  98     duplicates
  99 }
 100
 101 struct BasicBlockHashable<'tcx, 'a> {
 102     basic_block_data: &'a BasicBlockData<'tcx>,
 103 }
 104
 105 impl Hash for BasicBlockHashable<'_, '_> {
 106     fn hash<H: Hasher>(&self, state: &mut H) {
 107         hash_statements(state, self.basic_block_data.statements.iter());
 108         // Note that since we only hash the kind, we lose span information if we deduplicate the blocks
 109         self.basic_block_data.terminator().kind.hash(state);
 110     }
 111 }
 112
 113 impl Eq for BasicBlockHashable<'_, '_> {}
 114
 115 impl PartialEq for BasicBlockHashable<'_, '_> {
 116     fn eq(&self, other: &Self) -> bool {
 117         self.basic_block_data.statements.len() == other.basic_block_data.statements.len()
 118             && &self.basic_block_data.terminator().kind == &other.basic_block_data.terminator().kind
 119             && iter::zip(&self.basic_block_data.statements, &other.basic_block_data.statements)
 120                 .all(|(x, y)| statement_eq(&x.kind, &y.kind))
 121     }
 122 }
 123
 124 fn hash_statements<'a, 'tcx, H: Hasher>(
 125     hasher: &mut H,
 126     iter: impl Iterator<Item = &'a Statement<'tcx>>,
 127 ) where
 128     'tcx: 'a,
 129 {
 130     for stmt in iter {
 131         statement_hash(hasher, &stmt.kind);
 132     }
 133 }
 134
 135 fn statement_hash<H: Hasher>(hasher: &mut H, stmt: &StatementKind<'_>) {
 136     match stmt {
 137         StatementKind::Assign(box (place, rvalue)) => {
 138             place.hash(hasher);
 139             rvalue_hash(hasher, rvalue)
 140         }
 141         x => x.hash(hasher),
 142     };
 143 }
 144
 145 fn rvalue_hash<H: Hasher>(hasher: &mut H, rvalue: &Rvalue<'_>) {
 146     match rvalue {
 147         Rvalue::Use(op) => operand_hash(hasher, op),
 148         x => x.hash(hasher),
 149     };
 150 }
 151
 152 fn operand_hash<H: Hasher>(hasher: &mut H, operand: &Operand<'_>) {
 153     match operand {
 154         Operand::Constant(box Constant { user_ty: _, literal, span: _ }) => literal.hash(hasher),
 155         x => x.hash(hasher),
 156     };
 157 }
 158
 159 fn statement_eq<'tcx>(lhs: &StatementKind<'tcx>, rhs: &StatementKind<'tcx>) -> bool {
 160     let res = match (lhs, rhs) {
 161         (
 162             StatementKind::Assign(box (place, rvalue)),
 163             StatementKind::Assign(box (place2, rvalue2)),
 164         ) => place == place2 && rvalue_eq(rvalue, rvalue2),
 165         (x, y) => x == y,
 166     };
 167     debug!("statement_eq lhs: `{:?}` rhs: `{:?}` result: {:?}", lhs, rhs, res);
 168     res
 169 }
 170
 171 fn rvalue_eq<'tcx>(lhs: &Rvalue<'tcx>, rhs: &Rvalue<'tcx>) -> bool {
 172     let res = match (lhs, rhs) {
 173         (Rvalue::Use(op1), Rvalue::Use(op2)) => operand_eq(op1, op2),
 174         (x, y) => x == y,
 175     };
 176     debug!("rvalue_eq lhs: `{:?}` rhs: `{:?}` result: {:?}", lhs, rhs, res);
 177     res
 178 }
 179
 180 fn operand_eq<'tcx>(lhs: &Operand<'tcx>, rhs: &Operand<'tcx>) -> bool {
 181     let res = match (lhs, rhs) {
 182         (
 183             Operand::Constant(box Constant { user_ty: _, literal, span: _ }),
 184             Operand::Constant(box Constant { user_ty: _, literal: literal2, span: _ }),
 185         ) => literal == literal2,
 186         (x, y) => x == y,
 187     };
 188     debug!("operand_eq lhs: `{:?}` rhs: `{:?}` result: {:?}", lhs, rhs, res);
 189     res
 190 }