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, iter};
   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.try_insert(bb, value).expect("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             && iter::zip(&self.basic_block_data.statements, &other.basic_block_data.statements)
 119                 .all(|(x, y)| statement_eq(&x.kind, &y.kind))
 120     }
 121 }
 122
 123 fn hash_statements<'a, 'tcx, H: Hasher>(
 124     hasher: &mut H,
 125     iter: impl Iterator<Item = &'a Statement<'tcx>>,
 126 ) where
 127     'tcx: 'a,
 128 {
 129     for stmt in iter {
 130         statement_hash(hasher, &stmt.kind);
 131     }
 132 }
 133
 134 fn statement_hash<'tcx, H: Hasher>(hasher: &mut H, stmt: &StatementKind<'tcx>) {
 135     match stmt {
 136         StatementKind::Assign(box (place, rvalue)) => {
 137             place.hash(hasher);
 138             rvalue_hash(hasher, rvalue)
 139         }
 140         x => x.hash(hasher),
 141     };
 142 }
 143
 144 fn rvalue_hash<H: Hasher>(hasher: &mut H, rvalue: &Rvalue<'tcx>) {
 145     match rvalue {
 146         Rvalue::Use(op) => operand_hash(hasher, op),
 147         x => x.hash(hasher),
 148     };
 149 }
 150
 151 fn operand_hash<H: Hasher>(hasher: &mut H, operand: &Operand<'tcx>) {
 152     match operand {
 153         Operand::Constant(box Constant { user_ty: _, literal, span: _ }) => literal.hash(hasher),
 154         x => x.hash(hasher),
 155     };
 156 }
 157
 158 fn statement_eq<'tcx>(lhs: &StatementKind<'tcx>, rhs: &StatementKind<'tcx>) -> bool {
 159     let res = match (lhs, rhs) {
 160         (
 161             StatementKind::Assign(box (place, rvalue)),
 162             StatementKind::Assign(box (place2, rvalue2)),
 163         ) => place == place2 && rvalue_eq(rvalue, rvalue2),
 164         (x, y) => x == y,
 165     };
 166     debug!("statement_eq lhs: `{:?}` rhs: `{:?}` result: {:?}", lhs, rhs, res);
 167     res
 168 }
 169
 170 fn rvalue_eq(lhs: &Rvalue<'tcx>, rhs: &Rvalue<'tcx>) -> bool {
 171     let res = match (lhs, rhs) {
 172         (Rvalue::Use(op1), Rvalue::Use(op2)) => operand_eq(op1, op2),
 173         (x, y) => x == y,
 174     };
 175     debug!("rvalue_eq lhs: `{:?}` rhs: `{:?}` result: {:?}", lhs, rhs, res);
 176     res
 177 }
 178
 179 fn operand_eq(lhs: &Operand<'tcx>, rhs: &Operand<'tcx>) -> bool {
 180     let res = match (lhs, rhs) {
 181         (
 182             Operand::Constant(box Constant { user_ty: _, literal, span: _ }),
 183             Operand::Constant(box Constant { user_ty: _, literal: literal2, span: _ }),
 184         ) => literal == literal2,
 185         (x, y) => x == y,
 186     };
 187     debug!("operand_eq lhs: `{:?}` rhs: `{:?}` result: {:?}", lhs, rhs, res);
 188     res
 189 }