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 {
run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>)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(tcx, 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> {
tcx(&self) -> TyCtxt<'tcx>40 fn tcx(&self) -> TyCtxt<'tcx> {
41 self.tcx
42 }
43
visit_terminator(&mut self, terminator: &mut Terminator<'tcx>, location: Location)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
find_duplicates<'a, 'tcx>(body: &'a Body<'tcx>) -> FxHashMap<BasicBlock, BasicBlock>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> {
hash<H: Hasher>(&self, state: &mut H)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> {
eq(&self, other: &Self) -> bool115 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
hash_statements<'a, 'tcx, H: Hasher>( hasher: &mut H, iter: impl Iterator<Item = &'a Statement<'tcx>>, ) where 'tcx: 'a,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
statement_hash<'tcx, H: Hasher>(hasher: &mut H, stmt: &StatementKind<'tcx>)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
rvalue_hash<H: Hasher>(hasher: &mut H, rvalue: &Rvalue<'tcx>)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
operand_hash<H: Hasher>(hasher: &mut H, operand: &Operand<'tcx>)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
statement_eq<'tcx>(lhs: &StatementKind<'tcx>, rhs: &StatementKind<'tcx>) -> bool158 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
rvalue_eq(lhs: &Rvalue<'tcx>, rhs: &Rvalue<'tcx>) -> bool170 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
operand_eq(lhs: &Operand<'tcx>, rhs: &Operand<'tcx>) -> bool179 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 }
190