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.
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.
11 use rustc
::ty
::TyCtxt
;
12 use rustc
::mir
::repr
::*;
13 use rustc
::mir
::transform
::{MirPass, Pass}
;
14 use syntax
::ast
::NodeId
;
16 use rustc_data_structures
::bitvec
::BitVector
;
20 pub struct BreakCriticalEdges
;
23 * Breaks critical edges in the MIR.
25 * Critical edges are edges that are neither the only edge leaving a
26 * block, nor the only edge entering one.
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.
33 * This function will break those edges by inserting new blocks along them.
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
41 * NOTE: Simplify CFG will happily undo most of the work this pass does.
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
);
51 impl Pass
for BreakCriticalEdges {}
53 fn break_critical_edges(mir
: &mut Mir
) {
54 let mut pred_count
= vec
![0u32; mir
.basic_blocks
.len()];
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;
65 let cleanup_map
: BitVector
= mir
.basic_blocks
66 .iter().map(|bb
| bb
.is_cleanup
).collect();
68 // We need a place to store the new blocks generated
69 let mut new_blocks
= Vec
::new();
71 let bbs
= mir
.all_basic_blocks();
72 let cur_len
= mir
.basic_blocks
.len();
75 let data
= mir
.basic_block_data_mut(bb
);
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
) {
84 let num_preds
= pred_count
[tgt
.index()];
86 // It's a critical edge, break it
87 let goto
= Terminator
{
90 kind
: TerminatorKind
::Goto { target: *tgt }
92 let mut data
= BasicBlockData
::new(Some(goto
));
93 data
.is_cleanup
= cleanup_map
.contains(tgt
.index());
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
);
105 debug
!("Broke {} N edges", new_blocks
.len());
107 mir
.basic_blocks
.extend_from_slice(&new_blocks
);
110 // Returns true if the terminator would use an invoke in LLVM.
111 fn term_is_invoke(term
: &Terminator
) -> bool
{
113 TerminatorKind
::Call { cleanup: Some(_), .. }
|
114 TerminatorKind
::Drop { unwind: Some(_), .. }
=> true,