src/librustc_mir/transform/simplify_cfg.rs

   1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use rustc_data_structures::bitvec::BitVector;
  12 use rustc::middle::const_val::ConstVal;
  13 use rustc::ty::TyCtxt;
  14 use rustc::mir::repr::*;
  15 use rustc::mir::transform::{MirPass, MirSource, Pass};
  16 use pretty;
  17 use std::mem;
  18
  19 use super::remove_dead_blocks::RemoveDeadBlocks;
  20
  21 use traversal;
  22
  23 pub struct SimplifyCfg;
  24
  25 impl SimplifyCfg {
  26     pub fn new() -> SimplifyCfg {
  27         SimplifyCfg
  28     }
  29 }
  30
  31 impl<'tcx> MirPass<'tcx> for SimplifyCfg {
  32     fn run_pass<'a>(&mut self, tcx: TyCtxt<'a, 'tcx, 'tcx>, src: MirSource, mir: &mut Mir<'tcx>) {
  33         simplify_branches(mir);
  34         RemoveDeadBlocks.run_pass(tcx, src, mir);
  35         merge_consecutive_blocks(mir);
  36         RemoveDeadBlocks.run_pass(tcx, src, mir);
  37         pretty::dump_mir(tcx, "simplify_cfg", &0, src, mir, None);
  38
  39         // FIXME: Should probably be moved into some kind of pass manager
  40         mir.basic_blocks.shrink_to_fit();
  41     }
  42 }
  43
  44 impl Pass for SimplifyCfg {}
  45
  46 fn merge_consecutive_blocks(mir: &mut Mir) {
  47     // Build the precedecessor map for the MIR
  48     let mut pred_count = vec![0u32; mir.basic_blocks.len()];
  49     for (_, data) in traversal::preorder(mir) {
  50         if let Some(ref term) = data.terminator {
  51             for &tgt in term.successors().iter() {
  52                 pred_count[tgt.index()] += 1;
  53             }
  54         }
  55     }
  56
  57     loop {
  58         let mut changed = false;
  59         let mut seen = BitVector::new(mir.basic_blocks.len());
  60         let mut worklist = vec![START_BLOCK];
  61         while let Some(bb) = worklist.pop() {
  62             // Temporarily take ownership of the terminator we're modifying to keep borrowck happy
  63             let mut terminator = mir.basic_block_data_mut(bb).terminator.take()
  64                 .expect("invalid terminator state");
  65
  66             // See if we can merge the target block into this one
  67             loop {
  68                 let mut inner_change = false;
  69
  70                 if let TerminatorKind::Goto { target } = terminator.kind {
  71                     // Don't bother trying to merge a block into itself
  72                     if target == bb {
  73                         break;
  74                     }
  75
  76                     let num_insts = mir.basic_block_data(target).statements.len();
  77                     match mir.basic_block_data(target).terminator().kind {
  78                         TerminatorKind::Goto { target: new_target } if num_insts == 0 => {
  79                             inner_change = true;
  80                             terminator.kind = TerminatorKind::Goto { target: new_target };
  81                             pred_count[target.index()] -= 1;
  82                             pred_count[new_target.index()] += 1;
  83                         }
  84                         _ if pred_count[target.index()] == 1 => {
  85                             inner_change = true;
  86                             let mut stmts = Vec::new();
  87                             {
  88                                 let target_data = mir.basic_block_data_mut(target);
  89                                 mem::swap(&mut stmts, &mut target_data.statements);
  90                                 mem::swap(&mut terminator, target_data.terminator_mut());
  91                             }
  92
  93                             mir.basic_block_data_mut(bb).statements.append(&mut stmts);
  94                         }
  95                         _ => {}
  96                     };
  97                 }
  98
  99                 for target in terminator.successors_mut() {
 100                     let new_target = match final_target(mir, *target) {
 101                         Some(new_target) => new_target,
 102                         None if mir.basic_block_data(bb).statements.is_empty() => bb,
 103                         None => continue
 104                     };
 105                     if *target != new_target {
 106                         inner_change = true;
 107                         pred_count[target.index()] -= 1;
 108                         pred_count[new_target.index()] += 1;
 109                         *target = new_target;
 110                     }
 111                 }
 112
 113                 changed |= inner_change;
 114                 if !inner_change {
 115                     break;
 116                 }
 117             }
 118
 119             mir.basic_block_data_mut(bb).terminator = Some(terminator);
 120
 121             for succ in mir.basic_block_data(bb).terminator().successors().iter() {
 122                 if seen.insert(succ.index()) {
 123                     worklist.push(*succ);
 124                 }
 125             }
 126         }
 127
 128         if !changed {
 129             break;
 130         }
 131     }
 132 }
 133
 134 // Find the target at the end of the jump chain, return None if there is a loop
 135 fn final_target(mir: &Mir, mut target: BasicBlock) -> Option<BasicBlock> {
 136     // Keep track of already seen blocks to detect loops
 137     let mut seen: Vec<BasicBlock> = Vec::with_capacity(8);
 138
 139     while mir.basic_block_data(target).statements.is_empty() {
 140         // NB -- terminator may have been swapped with `None` in
 141         // merge_consecutive_blocks, in which case we have a cycle and just want
 142         // to stop
 143         match mir.basic_block_data(target).terminator {
 144             Some(Terminator { kind: TerminatorKind::Goto { target: next }, .. }) =>  {
 145                 if seen.contains(&next) {
 146                     return None;
 147                 }
 148                 seen.push(next);
 149                 target = next;
 150             }
 151             _ => break
 152         }
 153     }
 154
 155     Some(target)
 156 }
 157
 158 fn simplify_branches(mir: &mut Mir) {
 159     loop {
 160         let mut changed = false;
 161
 162         for bb in mir.all_basic_blocks() {
 163             let basic_block = mir.basic_block_data_mut(bb);
 164             let mut terminator = basic_block.terminator_mut();
 165             terminator.kind = match terminator.kind {
 166                 TerminatorKind::If { ref targets, .. } if targets.0 == targets.1 => {
 167                     changed = true;
 168                     TerminatorKind::Goto { target: targets.0 }
 169                 }
 170
 171                 TerminatorKind::If { ref targets, cond: Operand::Constant(Constant {
 172                     literal: Literal::Value {
 173                         value: ConstVal::Bool(cond)
 174                     }, ..
 175                 }) } => {
 176                     changed = true;
 177                     if cond {
 178                         TerminatorKind::Goto { target: targets.0 }
 179                     } else {
 180                         TerminatorKind::Goto { target: targets.1 }
 181                     }
 182                 }
 183
 184                 TerminatorKind::Assert { target, cond: Operand::Constant(Constant {
 185                     literal: Literal::Value {
 186                         value: ConstVal::Bool(cond)
 187                     }, ..
 188                 }), expected, .. } if cond == expected => {
 189                     changed = true;
 190                     TerminatorKind::Goto { target: target }
 191                 }
 192
 193                 TerminatorKind::SwitchInt { ref targets, .. } if targets.len() == 1 => {
 194                     changed = true;
 195                     TerminatorKind::Goto { target: targets[0] }
 196                 }
 197                 _ => continue
 198             }
 199         }
 200
 201         if !changed {
 202             break;
 203         }
 204     }
 205 }