]> git.proxmox.com Git - rustc.git/blob - src/librustc_mir/transform/break_critical_edges.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / 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 }