1 //! A number of passes which remove various redundancies in the CFG.
3 //! The `SimplifyCfg` pass gets rid of unnecessary blocks in the CFG, whereas the `SimplifyLocals`
4 //! gets rid of all the unnecessary local variable declarations.
6 //! The `SimplifyLocals` pass is kinda expensive and therefore not very suitable to be run often.
7 //! Most of the passes should not care or be impacted in meaningful ways due to extra locals
8 //! either, so running the pass once, right before codegen, should suffice.
10 //! On the other side of the spectrum, the `SimplifyCfg` pass is considerably cheap to run, thus
11 //! one should run it after every pass which may modify CFG in significant ways. This pass must
12 //! also be run before any analysis passes because it removes dead blocks, and some of these can be
15 //! The cause of this typing issue is typeck allowing most blocks whose end is not reachable have
16 //! an arbitrary return type, rather than having the usual () return type (as a note, typeck's
17 //! notion of reachability is in fact slightly weaker than MIR CFG reachability - see #31617). A
18 //! standard example of the situation is:
22 //! let _a: char = { return; };
26 //! Here the block (`{ return; }`) has the return type `char`, rather than `()`, but the MIR we
27 //! naively generate still contains the `_a = ()` write in the unreachable block "after" the
30 use crate::transform::{MirPass, MirSource};
31 use rustc_index::bit_set::BitSet;
32 use rustc_index::vec::{Idx, IndexVec};
33 use rustc_middle::mir::visit::{MutVisitor, MutatingUseContext, PlaceContext, Visitor};
34 use rustc_middle::mir::*;
35 use rustc_middle::ty::{self, TyCtxt};
38 pub struct SimplifyCfg {
43 pub fn new(label: &str) -> Self {
44 SimplifyCfg { label: format!("SimplifyCfg-{}", label) }
48 pub fn simplify_cfg(body: &mut BodyAndCache<'_>) {
49 CfgSimplifier::new(body).simplify();
50 remove_dead_blocks(body);
52 // FIXME: Should probably be moved into some kind of pass manager
53 body.basic_blocks_mut().raw.shrink_to_fit();
56 impl<'tcx> MirPass<'tcx> for SimplifyCfg {
57 fn name(&self) -> Cow<'_, str> {
58 Cow::Borrowed(&self.label)
61 fn run_pass(&self, _tcx: TyCtxt<'tcx>, _src: MirSource<'tcx>, body: &mut BodyAndCache<'tcx>) {
62 debug!("SimplifyCfg({:?}) - simplifying {:?}", self.label, body);
67 pub struct CfgSimplifier<'a, 'tcx> {
68 basic_blocks: &'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>>,
69 pred_count: IndexVec<BasicBlock, u32>,
72 impl<'a, 'tcx> CfgSimplifier<'a, 'tcx> {
73 pub fn new(body: &'a mut BodyAndCache<'tcx>) -> Self {
74 let mut pred_count = IndexVec::from_elem(0u32, body.basic_blocks());
76 // we can't use mir.predecessors() here because that counts
77 // dead blocks, which we don't want to.
78 pred_count[START_BLOCK] = 1;
80 for (_, data) in traversal::preorder(body) {
81 if let Some(ref term) = data.terminator {
82 for &tgt in term.successors() {
88 let basic_blocks = body.basic_blocks_mut();
90 CfgSimplifier { basic_blocks, pred_count }
93 pub fn simplify(mut self) {
96 let mut start = START_BLOCK;
98 // Vec of the blocks that should be merged. We store the indices here, instead of the
99 // statements itself to avoid moving the (relatively) large statements twice.
100 // We do not push the statements directly into the target block (`bb`) as that is slower
101 // due to additional reallocations
102 let mut merged_blocks = Vec::new();
104 let mut changed = false;
106 self.collapse_goto_chain(&mut start, &mut changed);
108 for bb in self.basic_blocks.indices() {
109 if self.pred_count[bb] == 0 {
113 debug!("simplifying {:?}", bb);
116 self.basic_blocks[bb].terminator.take().expect("invalid terminator state");
118 for successor in terminator.successors_mut() {
119 self.collapse_goto_chain(successor, &mut changed);
122 let mut inner_changed = true;
123 merged_blocks.clear();
124 while inner_changed {
125 inner_changed = false;
126 inner_changed |= self.simplify_branch(&mut terminator);
127 inner_changed |= self.merge_successor(&mut merged_blocks, &mut terminator);
128 changed |= inner_changed;
131 let statements_to_merge =
132 merged_blocks.iter().map(|&i| self.basic_blocks[i].statements.len()).sum();
134 if statements_to_merge > 0 {
135 let mut statements = std::mem::take(&mut self.basic_blocks[bb].statements);
136 statements.reserve(statements_to_merge);
137 for &from in &merged_blocks {
138 statements.append(&mut self.basic_blocks[from].statements);
140 self.basic_blocks[bb].statements = statements;
143 self.basic_blocks[bb].terminator = Some(terminator);
145 changed |= inner_changed;
153 if start != START_BLOCK {
154 debug_assert!(self.pred_count[START_BLOCK] == 0);
155 self.basic_blocks.swap(START_BLOCK, start);
156 self.pred_count.swap(START_BLOCK, start);
158 // pred_count == 1 if the start block has no predecessor _blocks_.
159 if self.pred_count[START_BLOCK] > 1 {
160 for (bb, data) in self.basic_blocks.iter_enumerated_mut() {
161 if self.pred_count[bb] == 0 {
165 for target in data.terminator_mut().successors_mut() {
166 if *target == start {
167 *target = START_BLOCK;
175 // Collapse a goto chain starting from `start`
176 fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) {
177 let mut terminator = match self.basic_blocks[*start] {
181 ref mut terminator @ Some(Terminator { kind: TerminatorKind::Goto { .. }, .. }),
183 } if statements.is_empty() => terminator.take(),
184 // if `terminator` is None, this means we are in a loop. In that
185 // case, let all the loop collapse to its entry.
189 let target = match terminator {
190 Some(Terminator { kind: TerminatorKind::Goto { ref mut target }, .. }) => {
191 self.collapse_goto_chain(target, changed);
196 self.basic_blocks[*start].terminator = terminator;
198 debug!("collapsing goto chain from {:?} to {:?}", *start, target);
200 *changed |= *start != target;
202 if self.pred_count[*start] == 1 {
203 // This is the last reference to *start, so the pred-count to
204 // to target is moved into the current block.
205 self.pred_count[*start] = 0;
207 self.pred_count[target] += 1;
208 self.pred_count[*start] -= 1;
214 // merge a block with 1 `goto` predecessor to its parent
217 merged_blocks: &mut Vec<BasicBlock>,
218 terminator: &mut Terminator<'tcx>,
220 let target = match terminator.kind {
221 TerminatorKind::Goto { target } if self.pred_count[target] == 1 => target,
225 debug!("merging block {:?} into {:?}", target, terminator);
226 *terminator = match self.basic_blocks[target].terminator.take() {
227 Some(terminator) => terminator,
229 // unreachable loop - this should not be possible, as we
230 // don't strand blocks, but handle it correctly.
235 merged_blocks.push(target);
236 self.pred_count[target] = 0;
241 // turn a branch with all successors identical to a goto
242 fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool {
243 match terminator.kind {
244 TerminatorKind::SwitchInt { .. } => {}
249 if let Some(&first_succ) = terminator.successors().next() {
250 if terminator.successors().all(|s| *s == first_succ) {
251 let count = terminator.successors().count();
252 self.pred_count[first_succ] -= (count - 1) as u32;
262 debug!("simplifying branch {:?}", terminator);
263 terminator.kind = TerminatorKind::Goto { target: first_succ };
267 fn strip_nops(&mut self) {
268 for blk in self.basic_blocks.iter_mut() {
270 .retain(|stmt| if let StatementKind::Nop = stmt.kind { false } else { true })
275 pub fn remove_dead_blocks(body: &mut BodyAndCache<'_>) {
276 let mut seen = BitSet::new_empty(body.basic_blocks().len());
277 for (bb, _) in traversal::preorder(body) {
278 seen.insert(bb.index());
281 let basic_blocks = body.basic_blocks_mut();
283 let num_blocks = basic_blocks.len();
284 let mut replacements: Vec<_> = (0..num_blocks).map(BasicBlock::new).collect();
285 let mut used_blocks = 0;
286 for alive_index in seen.iter() {
287 replacements[alive_index] = BasicBlock::new(used_blocks);
288 if alive_index != used_blocks {
289 // Swap the next alive block data with the current available slot. Since
290 // alive_index is non-decreasing this is a valid operation.
291 basic_blocks.raw.swap(alive_index, used_blocks);
295 basic_blocks.raw.truncate(used_blocks);
297 for block in basic_blocks {
298 for target in block.terminator_mut().successors_mut() {
299 *target = replacements[target.index()];
304 pub struct SimplifyLocals;
306 impl<'tcx> MirPass<'tcx> for SimplifyLocals {
307 fn run_pass(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut BodyAndCache<'tcx>) {
308 trace!("running SimplifyLocals on {:?}", source);
310 // First, we're going to get a count of *actual* uses for every `Local`.
311 // Take a look at `DeclMarker::visit_local()` to see exactly what is ignored.
312 let mut used_locals = {
313 let read_only_cache = read_only!(body);
314 let mut marker = DeclMarker::new(body);
315 marker.visit_body(&read_only_cache);
320 let arg_count = body.arg_count;
322 // Next, we're going to remove any `Local` with zero actual uses. When we remove those
323 // `Locals`, we're also going to subtract any uses of other `Locals` from the `used_locals`
324 // count. For example, if we removed `_2 = discriminant(_1)`, then we'll subtract one from
325 // `use_counts[_1]`. That in turn might make `_1` unused, so we loop until we hit a
326 // fixedpoint where there are no more unused locals.
328 let mut remove_statements = RemoveStatements::new(&mut used_locals, arg_count, tcx);
329 remove_statements.visit_body(body);
331 if !remove_statements.modified {
336 // Finally, we'll actually do the work of shrinking `body.local_decls` and remapping the `Local`s.
337 let map = make_local_map(&mut body.local_decls, used_locals, arg_count);
339 // Only bother running the `LocalUpdater` if we actually found locals to remove.
340 if map.iter().any(Option::is_none) {
341 // Update references to all vars and tmps now
342 let mut updater = LocalUpdater { map, tcx };
343 updater.visit_body(body);
345 body.local_decls.shrink_to_fit();
350 /// Construct the mapping while swapping out unused stuff out from the `vec`.
351 fn make_local_map<V>(
352 local_decls: &mut IndexVec<Local, V>,
353 used_locals: IndexVec<Local, usize>,
355 ) -> IndexVec<Local, Option<Local>> {
356 let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, &*local_decls);
357 let mut used = Local::new(0);
358 for (alive_index, count) in used_locals.iter_enumerated() {
359 // The `RETURN_PLACE` and arguments are always live.
360 if alive_index.as_usize() > arg_count && *count == 0 {
364 map[alive_index] = Some(used);
365 if alive_index != used {
366 local_decls.swap(alive_index, used);
368 used.increment_by(1);
370 local_decls.truncate(used.index());
374 struct DeclMarker<'a, 'tcx> {
375 pub local_counts: IndexVec<Local, usize>,
376 pub body: &'a Body<'tcx>,
379 impl<'a, 'tcx> DeclMarker<'a, 'tcx> {
380 pub fn new(body: &'a Body<'tcx>) -> Self {
381 Self { local_counts: IndexVec::from_elem(0, &body.local_decls), body }
385 impl<'a, 'tcx> Visitor<'tcx> for DeclMarker<'a, 'tcx> {
386 fn visit_local(&mut self, local: &Local, ctx: PlaceContext, location: Location) {
387 // Ignore storage markers altogether, they get removed along with their otherwise unused
389 // FIXME: Extend this to all non-uses.
390 if ctx.is_storage_marker() {
394 // Ignore stores of constants because `ConstProp` and `CopyProp` can remove uses of many
395 // of these locals. However, if the local is still needed, then it will be referenced in
396 // another place and we'll mark it as being used there.
397 if ctx == PlaceContext::MutatingUse(MutatingUseContext::Store)
398 || ctx == PlaceContext::MutatingUse(MutatingUseContext::Projection)
400 let block = &self.body.basic_blocks()[location.block];
401 if location.statement_index != block.statements.len() {
402 let stmt = &block.statements[location.statement_index];
404 fn can_skip_constant(c: &ty::Const<'tcx>) -> bool {
405 // Keep assignments from unevaluated constants around, since the
406 // evaluation may report errors, even if the use of the constant
408 !matches!(c.val, ty::ConstKind::Unevaluated(..))
411 fn can_skip_operand(o: &Operand<'_>) -> bool {
413 Operand::Copy(_) | Operand::Move(_) => true,
414 Operand::Constant(c) => can_skip_constant(c.literal),
418 if let StatementKind::Assign(box (dest, rvalue)) = &stmt.kind {
419 if !dest.is_indirect() && dest.local == *local {
420 let can_skip = match rvalue {
421 Rvalue::Use(op) => can_skip_operand(op),
422 Rvalue::Discriminant(_) => true,
423 Rvalue::BinaryOp(_, l, r) | Rvalue::CheckedBinaryOp(_, l, r) => {
424 can_skip_operand(l) && can_skip_operand(r)
426 Rvalue::Repeat(op, c) => can_skip_operand(op) && can_skip_constant(c),
427 Rvalue::AddressOf(_, _) => true,
428 Rvalue::Len(_) => true,
429 Rvalue::UnaryOp(_, op) => can_skip_operand(op),
430 Rvalue::Aggregate(_, operands) => operands.iter().all(can_skip_operand),
436 trace!("skipping store of {:?} to {:?}", rvalue, dest);
444 self.local_counts[*local] += 1;
448 struct StatementDeclMarker<'a, 'tcx> {
449 used_locals: &'a mut IndexVec<Local, usize>,
450 statement: &'a Statement<'tcx>,
453 impl<'a, 'tcx> StatementDeclMarker<'a, 'tcx> {
455 used_locals: &'a mut IndexVec<Local, usize>,
456 statement: &'a Statement<'tcx>,
458 Self { used_locals, statement }
462 impl<'a, 'tcx> Visitor<'tcx> for StatementDeclMarker<'a, 'tcx> {
463 fn visit_local(&mut self, local: &Local, context: PlaceContext, _location: Location) {
464 // Skip the lvalue for assignments
465 if let StatementKind::Assign(box (p, _)) = self.statement.kind {
466 if p.local == *local && context.is_place_assignment() {
471 let use_count = &mut self.used_locals[*local];
472 // If this is the local we're removing...
479 struct RemoveStatements<'a, 'tcx> {
480 used_locals: &'a mut IndexVec<Local, usize>,
486 impl<'a, 'tcx> RemoveStatements<'a, 'tcx> {
488 used_locals: &'a mut IndexVec<Local, usize>,
492 Self { used_locals, arg_count, tcx, modified: false }
495 fn keep_local(&self, l: Local) -> bool {
496 trace!("keep_local({:?}): count: {:?}", l, self.used_locals[l]);
497 l.as_usize() <= self.arg_count || self.used_locals[l] != 0
501 impl<'a, 'tcx> MutVisitor<'tcx> for RemoveStatements<'a, 'tcx> {
502 fn tcx(&self) -> TyCtxt<'tcx> {
506 fn visit_basic_block_data(&mut self, block: BasicBlock, data: &mut BasicBlockData<'tcx>) {
507 // Remove unnecessary StorageLive and StorageDead annotations.
509 data.statements.retain(|stmt| {
510 let keep = match &stmt.kind {
511 StatementKind::StorageLive(l) | StatementKind::StorageDead(l) => {
514 StatementKind::Assign(box (place, _)) => self.keep_local(place.local),
519 trace!("removing statement {:?}", stmt);
520 self.modified = true;
522 let mut visitor = StatementDeclMarker::new(self.used_locals, stmt);
523 visitor.visit_statement(stmt, Location { block, statement_index: i });
531 self.super_basic_block_data(block, data);
535 struct LocalUpdater<'tcx> {
536 map: IndexVec<Local, Option<Local>>,
540 impl<'tcx> MutVisitor<'tcx> for LocalUpdater<'tcx> {
541 fn tcx(&self) -> TyCtxt<'tcx> {
545 fn visit_local(&mut self, l: &mut Local, _: PlaceContext, _: Location) {
546 *l = self.map[*l].unwrap();