]>
Commit | Line | Data |
---|---|---|
6a06907d XL |
1 | //! This pass finds basic blocks that are completely equal, |
2 | //! and replaces all uses with just one of them. | |
3 | ||
cdc7bbd5 | 4 | use std::{collections::hash_map::Entry, hash::Hash, hash::Hasher, iter}; |
6a06907d | 5 | |
c295e0f8 | 6 | use crate::MirPass; |
6a06907d XL |
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 { | |
a2a8927a XL |
18 | fn is_enabled(&self, sess: &rustc_session::Session) -> bool { |
19 | sess.mir_opt_level() >= 4 | |
20 | } | |
21 | ||
6a06907d | 22 | fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { |
6a06907d XL |
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); | |
17df50a5 | 30 | simplify_cfg(tcx, body); |
6a06907d XL |
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 | ||
a2a8927a | 57 | fn find_duplicates(body: &Body<'_>) -> FxHashMap<BasicBlock, BasicBlock> { |
6a06907d XL |
58 | let mut duplicates = FxHashMap::default(); |
59 | ||
60 | let bbs_to_go_through = | |
f2b60f7d | 61 | body.basic_blocks.iter_enumerated().filter(|(_, bbd)| !bbd.is_cleanup).count(); |
6a06907d XL |
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. | |
f2b60f7d | 74 | for (bb, bbd) in body.basic_blocks.iter_enumerated().rev().filter(|(_, bbd)| !bbd.is_cleanup) { |
6a06907d XL |
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 | ||
a2a8927a | 104 | impl Hash for BasicBlockHashable<'_, '_> { |
6a06907d XL |
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 | ||
a2a8927a | 112 | impl Eq for BasicBlockHashable<'_, '_> {} |
6a06907d | 113 | |
a2a8927a | 114 | impl PartialEq for BasicBlockHashable<'_, '_> { |
6a06907d XL |
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 | |
cdc7bbd5 | 118 | && iter::zip(&self.basic_block_data.statements, &other.basic_block_data.statements) |
6a06907d XL |
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 | ||
a2a8927a | 134 | fn statement_hash<H: Hasher>(hasher: &mut H, stmt: &StatementKind<'_>) { |
6a06907d XL |
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 | ||
a2a8927a | 144 | fn rvalue_hash<H: Hasher>(hasher: &mut H, rvalue: &Rvalue<'_>) { |
6a06907d XL |
145 | match rvalue { |
146 | Rvalue::Use(op) => operand_hash(hasher, op), | |
147 | x => x.hash(hasher), | |
148 | }; | |
149 | } | |
150 | ||
a2a8927a | 151 | fn operand_hash<H: Hasher>(hasher: &mut H, operand: &Operand<'_>) { |
6a06907d XL |
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 | ||
a2a8927a | 170 | fn rvalue_eq<'tcx>(lhs: &Rvalue<'tcx>, rhs: &Rvalue<'tcx>) -> bool { |
6a06907d XL |
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 | ||
a2a8927a | 179 | fn operand_eq<'tcx>(lhs: &Operand<'tcx>, rhs: &Operand<'tcx>) -> bool { |
6a06907d XL |
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 | } |