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::middle::const_val::ConstVal;
  12 use rustc::ty::TyCtxt;
  13 use rustc::mir::repr::*;
  14 use rustc::mir::transform::{MirPass, Pass};
  15 use pretty;
  16 use syntax::ast::NodeId;
  17
  18 use super::remove_dead_blocks::RemoveDeadBlocks;
  19
  20 pub struct SimplifyCfg;
  21
  22 impl SimplifyCfg {
  23     pub fn new() -> SimplifyCfg {
  24         SimplifyCfg
  25     }
  26
  27     fn remove_goto_chains(&self, mir: &mut Mir) -> bool {
  28         // Find the target at the end of the jump chain, return None if there is a loop
  29         fn final_target(mir: &Mir, mut target: BasicBlock) -> Option<BasicBlock> {
  30             // Keep track of already seen blocks to detect loops
  31             let mut seen: Vec<BasicBlock> = Vec::with_capacity(8);
  32
  33             while mir.basic_block_data(target).statements.is_empty() {
  34                 // NB -- terminator may have been swapped with `None`
  35                 // below, in which case we have a cycle and just want
  36                 // to stop
  37                 if let Some(ref terminator) = mir.basic_block_data(target).terminator {
  38                     match terminator.kind {
  39                         TerminatorKind::Goto { target: next } => {
  40                             if seen.contains(&next) {
  41                                 return None;
  42                             }
  43                             seen.push(next);
  44                             target = next;
  45                         }
  46                         _ => break
  47                     }
  48                 } else {
  49                     break
  50                 }
  51             }
  52
  53             Some(target)
  54         }
  55
  56         let mut changed = false;
  57         for bb in mir.all_basic_blocks() {
  58             // Temporarily take ownership of the terminator we're modifying to keep borrowck happy
  59             let mut terminator = mir.basic_block_data_mut(bb).terminator.take()
  60                                     .expect("invalid terminator state");
  61
  62             debug!("remove_goto_chains: bb={:?} terminator={:?}", bb, terminator);
  63
  64             for target in terminator.successors_mut() {
  65                 let new_target = match final_target(mir, *target) {
  66                     Some(new_target) => new_target,
  67                     None if mir.basic_block_data(bb).statements.is_empty() => bb,
  68                     None => continue
  69                 };
  70                 changed |= *target != new_target;
  71                 *target = new_target;
  72             }
  73             mir.basic_block_data_mut(bb).terminator = Some(terminator);
  74         }
  75         changed
  76     }
  77
  78     fn simplify_branches(&self, mir: &mut Mir) -> bool {
  79         let mut changed = false;
  80
  81         for bb in mir.all_basic_blocks() {
  82             let basic_block = mir.basic_block_data_mut(bb);
  83             let mut terminator = basic_block.terminator_mut();
  84             terminator.kind = match terminator.kind {
  85                 TerminatorKind::If { ref targets, .. } if targets.0 == targets.1 => {
  86                     changed = true;
  87                     TerminatorKind::Goto { target: targets.0 }
  88                 }
  89
  90                 TerminatorKind::If { ref targets, cond: Operand::Constant(Constant {
  91                     literal: Literal::Value {
  92                         value: ConstVal::Bool(cond)
  93                     }, ..
  94                 }) } => {
  95                     changed = true;
  96                     if cond {
  97                         TerminatorKind::Goto { target: targets.0 }
  98                     } else {
  99                         TerminatorKind::Goto { target: targets.1 }
 100                     }
 101                 }
 102
 103                 TerminatorKind::SwitchInt { ref targets, .. } if targets.len() == 1 => {
 104                     TerminatorKind::Goto { target: targets[0] }
 105                 }
 106                 _ => continue
 107             }
 108         }
 109
 110         changed
 111     }
 112 }
 113
 114 impl<'tcx> MirPass<'tcx> for SimplifyCfg {
 115     fn run_pass(&mut self, tcx: &TyCtxt<'tcx>, id: NodeId, mir: &mut Mir<'tcx>) {
 116         let mut counter = 0;
 117         let mut changed = true;
 118         while changed {
 119             pretty::dump_mir(tcx, "simplify_cfg", &counter, id, mir, None);
 120             counter += 1;
 121             changed = self.simplify_branches(mir);
 122             changed |= self.remove_goto_chains(mir);
 123             RemoveDeadBlocks.run_pass(tcx, id, mir);
 124         }
 125         // FIXME: Should probably be moved into some kind of pass manager
 126         mir.basic_blocks.shrink_to_fit();
 127     }
 128 }
 129
 130 impl Pass for SimplifyCfg {}