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::mir::visit::{MutVisitor, MutatingUseContext, PlaceContext, Visitor};
33 use rustc::ty::{self, TyCtxt};
34 use rustc_index::bit_set::BitSet;
35 use rustc_index::vec::{Idx, IndexVec};
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;
99 let mut changed = false;
101 self.collapse_goto_chain(&mut start, &mut changed);
103 for bb in self.basic_blocks.indices() {
104 if self.pred_count[bb] == 0 {
108 debug!("simplifying {:?}", bb);
111 self.basic_blocks[bb].terminator.take().expect("invalid terminator state");
113 for successor in terminator.successors_mut() {
114 self.collapse_goto_chain(successor, &mut changed);
117 let mut new_stmts = vec![];
118 let mut inner_changed = true;
119 while inner_changed {
120 inner_changed = false;
121 inner_changed |= self.simplify_branch(&mut terminator);
122 inner_changed |= self.merge_successor(&mut new_stmts, &mut terminator);
123 changed |= inner_changed;
126 let data = &mut self.basic_blocks[bb];
127 data.statements.extend(new_stmts);
128 data.terminator = Some(terminator);
130 changed |= inner_changed;
138 if start != START_BLOCK {
139 debug_assert!(self.pred_count[START_BLOCK] == 0);
140 self.basic_blocks.swap(START_BLOCK, start);
141 self.pred_count.swap(START_BLOCK, start);
143 // pred_count == 1 if the start block has no predecessor _blocks_.
144 if self.pred_count[START_BLOCK] > 1 {
145 for (bb, data) in self.basic_blocks.iter_enumerated_mut() {
146 if self.pred_count[bb] == 0 {
150 for target in data.terminator_mut().successors_mut() {
151 if *target == start {
152 *target = START_BLOCK;
160 // Collapse a goto chain starting from `start`
161 fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) {
162 let mut terminator = match self.basic_blocks[*start] {
166 ref mut terminator @ Some(Terminator { kind: TerminatorKind::Goto { .. }, .. }),
168 } if statements.is_empty() => terminator.take(),
169 // if `terminator` is None, this means we are in a loop. In that
170 // case, let all the loop collapse to its entry.
174 let target = match terminator {
175 Some(Terminator { kind: TerminatorKind::Goto { ref mut target }, .. }) => {
176 self.collapse_goto_chain(target, changed);
181 self.basic_blocks[*start].terminator = terminator;
183 debug!("collapsing goto chain from {:?} to {:?}", *start, target);
185 *changed |= *start != target;
187 if self.pred_count[*start] == 1 {
188 // This is the last reference to *start, so the pred-count to
189 // to target is moved into the current block.
190 self.pred_count[*start] = 0;
192 self.pred_count[target] += 1;
193 self.pred_count[*start] -= 1;
199 // merge a block with 1 `goto` predecessor to its parent
202 new_stmts: &mut Vec<Statement<'tcx>>,
203 terminator: &mut Terminator<'tcx>,
205 let target = match terminator.kind {
206 TerminatorKind::Goto { target } if self.pred_count[target] == 1 => target,
210 debug!("merging block {:?} into {:?}", target, terminator);
211 *terminator = match self.basic_blocks[target].terminator.take() {
212 Some(terminator) => terminator,
214 // unreachable loop - this should not be possible, as we
215 // don't strand blocks, but handle it correctly.
219 new_stmts.extend(self.basic_blocks[target].statements.drain(..));
220 self.pred_count[target] = 0;
225 // turn a branch with all successors identical to a goto
226 fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool {
227 match terminator.kind {
228 TerminatorKind::SwitchInt { .. } => {}
233 if let Some(&first_succ) = terminator.successors().next() {
234 if terminator.successors().all(|s| *s == first_succ) {
235 let count = terminator.successors().count();
236 self.pred_count[first_succ] -= (count - 1) as u32;
246 debug!("simplifying branch {:?}", terminator);
247 terminator.kind = TerminatorKind::Goto { target: first_succ };
251 fn strip_nops(&mut self) {
252 for blk in self.basic_blocks.iter_mut() {
254 .retain(|stmt| if let StatementKind::Nop = stmt.kind { false } else { true })
259 pub fn remove_dead_blocks(body: &mut BodyAndCache<'_>) {
260 let mut seen = BitSet::new_empty(body.basic_blocks().len());
261 for (bb, _) in traversal::preorder(body) {
262 seen.insert(bb.index());
265 let basic_blocks = body.basic_blocks_mut();
267 let num_blocks = basic_blocks.len();
268 let mut replacements: Vec<_> = (0..num_blocks).map(BasicBlock::new).collect();
269 let mut used_blocks = 0;
270 for alive_index in seen.iter() {
271 replacements[alive_index] = BasicBlock::new(used_blocks);
272 if alive_index != used_blocks {
273 // Swap the next alive block data with the current available slot. Since
274 // alive_index is non-decreasing this is a valid operation.
275 basic_blocks.raw.swap(alive_index, used_blocks);
279 basic_blocks.raw.truncate(used_blocks);
281 for block in basic_blocks {
282 for target in block.terminator_mut().successors_mut() {
283 *target = replacements[target.index()];
288 pub struct SimplifyLocals;
290 impl<'tcx> MirPass<'tcx> for SimplifyLocals {
291 fn run_pass(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut BodyAndCache<'tcx>) {
292 trace!("running SimplifyLocals on {:?}", source);
294 let read_only_cache = read_only!(body);
295 let mut marker = DeclMarker { locals: BitSet::new_empty(body.local_decls.len()), body };
296 marker.visit_body(read_only_cache);
297 // Return pointer and arguments are always live
298 marker.locals.insert(RETURN_PLACE);
299 for arg in body.args_iter() {
300 marker.locals.insert(arg);
306 let map = make_local_map(&mut body.local_decls, locals);
307 // Update references to all vars and tmps now
308 LocalUpdater { map, tcx }.visit_body(body);
309 body.local_decls.shrink_to_fit();
313 /// Construct the mapping while swapping out unused stuff out from the `vec`.
314 fn make_local_map<V>(
315 vec: &mut IndexVec<Local, V>,
317 ) -> IndexVec<Local, Option<Local>> {
318 let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, &*vec);
319 let mut used = Local::new(0);
320 for alive_index in mask.iter() {
321 map[alive_index] = Some(used);
322 if alive_index != used {
323 vec.swap(alive_index, used);
325 used.increment_by(1);
327 vec.truncate(used.index());
331 struct DeclMarker<'a, 'tcx> {
332 pub locals: BitSet<Local>,
333 pub body: &'a Body<'tcx>,
336 impl<'a, 'tcx> Visitor<'tcx> for DeclMarker<'a, 'tcx> {
337 fn visit_local(&mut self, local: &Local, ctx: PlaceContext, location: Location) {
338 // Ignore storage markers altogether, they get removed along with their otherwise unused
340 // FIXME: Extend this to all non-uses.
341 if ctx.is_storage_marker() {
345 // Ignore stores of constants because `ConstProp` and `CopyProp` can remove uses of many
346 // of these locals. However, if the local is still needed, then it will be referenced in
347 // another place and we'll mark it as being used there.
348 if ctx == PlaceContext::MutatingUse(MutatingUseContext::Store)
349 || ctx == PlaceContext::MutatingUse(MutatingUseContext::Projection)
351 let block = &self.body.basic_blocks()[location.block];
352 if location.statement_index != block.statements.len() {
353 let stmt = &block.statements[location.statement_index];
355 if let StatementKind::Assign(box (p, Rvalue::Use(Operand::Constant(c)))) =
358 match c.literal.val {
359 // Keep assignments from unevaluated constants around, since the evaluation
360 // may report errors, even if the use of the constant is dead code.
361 ty::ConstKind::Unevaluated(..) => {}
363 if !p.is_indirect() {
364 trace!("skipping store of const value {:?} to {:?}", c, p);
373 self.locals.insert(*local);
377 struct LocalUpdater<'tcx> {
378 map: IndexVec<Local, Option<Local>>,
382 impl<'tcx> MutVisitor<'tcx> for LocalUpdater<'tcx> {
383 fn tcx(&self) -> TyCtxt<'tcx> {
387 fn visit_basic_block_data(&mut self, block: BasicBlock, data: &mut BasicBlockData<'tcx>) {
388 // Remove unnecessary StorageLive and StorageDead annotations.
389 data.statements.retain(|stmt| match &stmt.kind {
390 StatementKind::StorageLive(l) | StatementKind::StorageDead(l) => self.map[*l].is_some(),
391 StatementKind::Assign(box (place, _)) => self.map[place.local].is_some(),
394 self.super_basic_block_data(block, data);
397 fn visit_local(&mut self, l: &mut Local, _: PlaceContext, _: Location) {
398 *l = self.map[*l].unwrap();
401 fn process_projection_elem(&mut self, elem: &PlaceElem<'tcx>) -> Option<PlaceElem<'tcx>> {
403 PlaceElem::Index(local) => Some(PlaceElem::Index(self.map[*local].unwrap())),