src/librustc_mir/transform/break_critical_edges.rs

   1 // Copyright 2016 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::ty::TyCtxt;
  12 use rustc::mir::repr::*;
  13 use rustc::mir::transform::{MirPass, Pass};
  14 use syntax::ast::NodeId;
  15
  16 use rustc_data_structures::bitvec::BitVector;
  17
  18 use traversal;
  19
  20 pub struct BreakCriticalEdges;
  21
  22 /**
  23  * Breaks critical edges in the MIR.
  24  *
  25  * Critical edges are edges that are neither the only edge leaving a
  26  * block, nor the only edge entering one.
  27  *
  28  * When you want something to happen "along" an edge, you can either
  29  * do at the end of the predecessor block, or at the start of the
  30  * successor block. Critical edges have to be broken in order to prevent
  31  * "edge actions" from affecting other edges.
  32  *
  33  * This function will break those edges by inserting new blocks along them.
  34  *
  35  * A special case is Drop and Call terminators with unwind/cleanup successors,
  36  * They use `invoke` in LLVM, which terminates a block, meaning that code cannot
  37  * be inserted after them, so even if an edge is the only edge leaving a block
  38  * like that, we still insert blocks if the edge is one of many entering the
  39  * target.
  40  *
  41  * NOTE: Simplify CFG will happily undo most of the work this pass does.
  42  *
  43  */
  44
  45 impl<'tcx> MirPass<'tcx> for BreakCriticalEdges {
  46     fn run_pass(&mut self, _: &TyCtxt<'tcx>, _: NodeId, mir: &mut Mir<'tcx>) {
  47         break_critical_edges(mir);
  48     }
  49 }
  50
  51 impl Pass for BreakCriticalEdges {}
  52
  53 fn break_critical_edges(mir: &mut Mir) {
  54     let mut pred_count = vec![0u32; mir.basic_blocks.len()];
  55
  56     // Build the precedecessor map for the MIR
  57     for (_, data) in traversal::preorder(mir) {
  58         if let Some(ref term) = data.terminator {
  59             for &tgt in term.successors().iter() {
  60                 pred_count[tgt.index()] += 1;
  61             }
  62         }
  63     }
  64
  65     let cleanup_map : BitVector = mir.basic_blocks
  66         .iter().map(|bb| bb.is_cleanup).collect();
  67
  68     // We need a place to store the new blocks generated
  69     let mut new_blocks = Vec::new();
  70
  71     let bbs = mir.all_basic_blocks();
  72     let cur_len = mir.basic_blocks.len();
  73
  74     for &bb in &bbs {
  75         let data = mir.basic_block_data_mut(bb);
  76
  77         if let Some(ref mut term) = data.terminator {
  78             let is_invoke = term_is_invoke(term);
  79             let term_span = term.span;
  80             let term_scope = term.scope;
  81             let succs = term.successors_mut();
  82             if succs.len() > 1 || (succs.len() > 0 && is_invoke) {
  83                 for tgt in succs {
  84                     let num_preds = pred_count[tgt.index()];
  85                     if num_preds > 1 {
  86                         // It's a critical edge, break it
  87                         let goto = Terminator {
  88                             span: term_span,
  89                             scope: term_scope,
  90                             kind: TerminatorKind::Goto { target: *tgt }
  91                         };
  92                         let mut data = BasicBlockData::new(Some(goto));
  93                         data.is_cleanup = cleanup_map.contains(tgt.index());
  94
  95                         // Get the index it will be when inserted into the MIR
  96                         let idx = cur_len + new_blocks.len();
  97                         new_blocks.push(data);
  98                         *tgt = BasicBlock::new(idx);
  99                     }
 100                 }
 101             }
 102         }
 103     }
 104
 105     debug!("Broke {} N edges", new_blocks.len());
 106
 107     mir.basic_blocks.extend_from_slice(&new_blocks);
 108 }
 109
 110 // Returns true if the terminator would use an invoke in LLVM.
 111 fn term_is_invoke(term: &Terminator) -> bool {
 112     match term.kind {
 113         TerminatorKind::Call { cleanup: Some(_), .. } |
 114         TerminatorKind::Drop { unwind: Some(_), .. } => true,
 115         _ => false
 116     }
 117 }