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 rustc_data_structures
::bit_set
::BitSet
;
31 use rustc_data_structures
::indexed_vec
::{Idx, IndexVec}
;
32 use rustc
::ty
::TyCtxt
;
34 use rustc
::mir
::visit
::{MutVisitor, Visitor, PlaceContext}
;
35 use rustc
::session
::config
::DebugInfo
;
37 use crate::transform
::{MirPass, MirSource}
;
39 pub struct SimplifyCfg { label: String }
42 pub fn new(label
: &str) -> Self {
43 SimplifyCfg { label: format!("SimplifyCfg-{}
", label) }
47 pub fn simplify_cfg(mir: &mut Mir<'_>) {
48 CfgSimplifier::new(mir).simplify();
49 remove_dead_blocks(mir);
51 // FIXME: Should probably be moved into some kind of pass manager
52 mir.basic_blocks_mut().raw.shrink_to_fit();
55 impl MirPass for SimplifyCfg {
56 fn name<'a>(&'a self) -> Cow<'a, str> {
57 Cow::Borrowed(&self.label)
60 fn run_pass<'a, 'tcx>(&self,
61 _tcx: TyCtxt<'a, 'tcx, 'tcx>,
62 _src: MirSource<'tcx>,
63 mir: &mut Mir<'tcx>) {
64 debug!("SimplifyCfg({:?}
) - simplifying {:?}
", self.label, mir);
69 pub struct CfgSimplifier<'a, 'tcx: 'a> {
70 basic_blocks: &'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>>,
71 pred_count: IndexVec<BasicBlock, u32>
74 impl<'a, 'tcx: 'a> CfgSimplifier<'a, 'tcx> {
75 pub fn new(mir: &'a mut Mir<'tcx>) -> Self {
76 let mut pred_count = IndexVec::from_elem(0u32, mir.basic_blocks());
78 // we can't use mir.predecessors() here because that counts
79 // dead blocks, which we don't want to.
80 pred_count[START_BLOCK] = 1;
82 for (_, data) in traversal::preorder(mir) {
83 if let Some(ref term) = data.terminator {
84 for &tgt in term.successors() {
90 let basic_blocks = mir.basic_blocks_mut();
98 pub fn simplify(mut self) {
101 let mut start = START_BLOCK;
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);
115 let mut terminator = self.basic_blocks[bb].terminator.take()
116 .expect("invalid terminator state
");
118 for successor in terminator.successors_mut() {
119 self.collapse_goto_chain(successor, &mut changed);
122 let mut new_stmts = vec![];
123 let mut inner_changed = true;
124 while inner_changed {
125 inner_changed = false;
126 inner_changed |= self.simplify_branch(&mut terminator);
127 inner_changed |= self.merge_successor(&mut new_stmts, &mut terminator);
128 changed |= inner_changed;
131 self.basic_blocks[bb].statements.extend(new_stmts);
132 self.basic_blocks[bb].terminator = Some(terminator);
134 changed |= inner_changed;
137 if !changed { break }
140 if start != START_BLOCK {
141 debug_assert!(self.pred_count[START_BLOCK] == 0);
142 self.basic_blocks.swap(START_BLOCK, start);
143 self.pred_count.swap(START_BLOCK, start);
145 // pred_count == 1 if the start block has no predecessor _blocks_.
146 if self.pred_count[START_BLOCK] > 1 {
147 for (bb, data) in self.basic_blocks.iter_enumerated_mut() {
148 if self.pred_count[bb] == 0 {
152 for target in data.terminator_mut().successors_mut() {
153 if *target == start {
154 *target = START_BLOCK;
162 // Collapse a goto chain starting from `start`
163 fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) {
164 let mut terminator = match self.basic_blocks[*start] {
167 terminator: ref mut terminator @ Some(Terminator {
168 kind: TerminatorKind::Goto { .. }, ..
170 } if statements.is_empty() => terminator.take(),
171 // if `terminator` is None, this means we are in a loop. In that
172 // case, let all the loop collapse to its entry.
176 let target = match terminator {
177 Some(Terminator { kind: TerminatorKind::Goto { ref mut target }, .. }) => {
178 self.collapse_goto_chain(target, changed);
183 self.basic_blocks[*start].terminator = terminator;
185 debug!("collapsing goto chain from {:?} to {:?}
", *start, target);
187 *changed |= *start != target;
189 if self.pred_count[*start] == 1 {
190 // This is the last reference to *start, so the pred-count to
191 // to target is moved into the current block.
192 self.pred_count[*start] = 0;
194 self.pred_count[target] += 1;
195 self.pred_count[*start] -= 1;
201 // merge a block with 1 `goto` predecessor to its parent
202 fn merge_successor(&mut self,
203 new_stmts: &mut Vec<Statement<'tcx>>,
204 terminator: &mut Terminator<'tcx>)
207 let target = match terminator.kind {
208 TerminatorKind::Goto { target }
209 if self.pred_count[target] == 1
214 debug!("merging block {:?} into {:?}
", target, terminator);
215 *terminator = match self.basic_blocks[target].terminator.take() {
216 Some(terminator) => terminator,
218 // unreachable loop - this should not be possible, as we
219 // don't strand blocks, but handle it correctly.
223 new_stmts.extend(self.basic_blocks[target].statements.drain(..));
224 self.pred_count[target] = 0;
229 // turn a branch with all successors identical to a goto
230 fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool {
231 match terminator.kind {
232 TerminatorKind::SwitchInt { .. } => {},
237 if let Some(&first_succ) = terminator.successors().nth(0) {
238 if terminator.successors().all(|s| *s == first_succ) {
239 let count = terminator.successors().count();
240 self.pred_count[first_succ] -= (count - 1) as u32;
250 debug!("simplifying branch {:?}
", terminator);
251 terminator.kind = TerminatorKind::Goto { target: first_succ };
255 fn strip_nops(&mut self) {
256 for blk in self.basic_blocks.iter_mut() {
257 blk.statements.retain(|stmt| if let StatementKind::Nop = stmt.kind {
266 pub fn remove_dead_blocks(mir: &mut Mir<'_>) {
267 let mut seen = BitSet::new_empty(mir.basic_blocks().len());
268 for (bb, _) in traversal::preorder(mir) {
269 seen.insert(bb.index());
272 let basic_blocks = mir.basic_blocks_mut();
274 let num_blocks = basic_blocks.len();
275 let mut replacements : Vec<_> = (0..num_blocks).map(BasicBlock::new).collect();
276 let mut used_blocks = 0;
277 for alive_index in seen.iter() {
278 replacements[alive_index] = BasicBlock::new(used_blocks);
279 if alive_index != used_blocks {
280 // Swap the next alive block data with the current available slot. Since alive_index is
281 // non-decreasing this is a valid operation.
282 basic_blocks.raw.swap(alive_index, used_blocks);
286 basic_blocks.raw.truncate(used_blocks);
288 for block in basic_blocks {
289 for target in block.terminator_mut().successors_mut() {
290 *target = replacements[target.index()];
296 pub struct SimplifyLocals;
298 impl MirPass for SimplifyLocals {
299 fn run_pass<'a, 'tcx>(&self,
300 tcx: TyCtxt<'a, 'tcx, 'tcx>,
302 mir: &mut Mir<'tcx>) {
303 let mut marker = DeclMarker { locals: BitSet::new_empty(mir.local_decls.len()) };
304 marker.visit_mir(mir);
305 // Return pointer and arguments are always live
306 marker.locals.insert(RETURN_PLACE);
307 for arg in mir.args_iter() {
308 marker.locals.insert(arg);
311 // We may need to keep dead user variables live for debuginfo.
312 if tcx.sess.opts.debuginfo == DebugInfo::Full {
313 for local in mir.vars_iter() {
314 marker.locals.insert(local);
318 let map = make_local_map(&mut mir.local_decls, marker.locals);
319 // Update references to all vars and tmps now
320 LocalUpdater { map }.visit_mir(mir);
321 mir.local_decls.shrink_to_fit();
325 /// Construct the mapping while swapping out unused stuff out from the `vec`.
326 fn make_local_map<'tcx, V>(
327 vec: &mut IndexVec<Local, V>,
329 ) -> IndexVec<Local, Option<Local>> {
330 let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, &*vec);
331 let mut used = Local::new(0);
332 for alive_index in mask.iter() {
333 map[alive_index] = Some(used);
334 if alive_index != used {
335 vec.swap(alive_index, used);
337 used.increment_by(1);
339 vec.truncate(used.index());
344 pub locals: BitSet<Local>,
347 impl<'tcx> Visitor<'tcx> for DeclMarker {
348 fn visit_local(&mut self, local: &Local, ctx: PlaceContext<'tcx>, _: Location) {
349 // Ignore storage markers altogether, they get removed along with their otherwise unused
351 // FIXME: Extend this to all non-uses.
352 if !ctx.is_storage_marker() {
353 self.locals.insert(*local);
358 struct LocalUpdater {
359 map: IndexVec<Local, Option<Local>>,
362 impl<'tcx> MutVisitor<'tcx> for LocalUpdater {
363 fn visit_basic_block_data(&mut self, block: BasicBlock, data: &mut BasicBlockData<'tcx>) {
364 // Remove unnecessary StorageLive and StorageDead annotations.
365 data.statements.retain(|stmt| {
367 StatementKind::StorageLive(l) | StatementKind::StorageDead(l) => {
368 self.map[l].is_some()
373 self.super_basic_block_data(block, data);
375 fn visit_local(&mut self, l: &mut Local, _: PlaceContext<'tcx>, _: Location) {
376 *l = self.map[*l].unwrap();