]> git.proxmox.com Git - rustc.git/blame - src/librustc_mir/transform/simplify_cfg.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc_mir / transform / simplify_cfg.rs
CommitLineData
92a42be0
SL
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
54a0048b
SL
11use rustc::middle::const_val::ConstVal;
12use rustc::ty::TyCtxt;
92a42be0 13use rustc::mir::repr::*;
54a0048b
SL
14use rustc::mir::transform::{MirPass, Pass};
15use pretty;
16use syntax::ast::NodeId;
17
18use super::remove_dead_blocks::RemoveDeadBlocks;
92a42be0
SL
19
20pub struct SimplifyCfg;
21
22impl SimplifyCfg {
23 pub fn new() -> SimplifyCfg {
24 SimplifyCfg
25 }
26
92a42be0 27 fn remove_goto_chains(&self, mir: &mut Mir) -> bool {
92a42be0
SL
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() {
54a0048b
SL
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;
92a42be0 45 }
54a0048b 46 _ => break
92a42be0 47 }
54a0048b
SL
48 } else {
49 break
92a42be0
SL
50 }
51 }
52
53 Some(target)
54 }
55
56 let mut changed = false;
57 for bb in mir.all_basic_blocks() {
9cc50fc6
SL
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");
92a42be0 61
54a0048b
SL
62 debug!("remove_goto_chains: bb={:?} terminator={:?}", bb, terminator);
63
92a42be0
SL
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 }
9cc50fc6 73 mir.basic_block_data_mut(bb).terminator = Some(terminator);
92a42be0 74 }
92a42be0
SL
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() {
9cc50fc6
SL
82 let basic_block = mir.basic_block_data_mut(bb);
83 let mut terminator = basic_block.terminator_mut();
54a0048b
SL
84 terminator.kind = match terminator.kind {
85 TerminatorKind::If { ref targets, .. } if targets.0 == targets.1 => {
92a42be0 86 changed = true;
54a0048b 87 TerminatorKind::Goto { target: targets.0 }
92a42be0 88 }
7453a54e 89
54a0048b 90 TerminatorKind::If { ref targets, cond: Operand::Constant(Constant {
92a42be0
SL
91 literal: Literal::Value {
92 value: ConstVal::Bool(cond)
93 }, ..
94 }) } => {
95 changed = true;
9cc50fc6 96 if cond {
54a0048b 97 TerminatorKind::Goto { target: targets.0 }
9cc50fc6 98 } else {
54a0048b 99 TerminatorKind::Goto { target: targets.1 }
9cc50fc6 100 }
92a42be0 101 }
7453a54e 102
54a0048b
SL
103 TerminatorKind::SwitchInt { ref targets, .. } if targets.len() == 1 => {
104 TerminatorKind::Goto { target: targets[0] }
92a42be0 105 }
9cc50fc6 106 _ => continue
92a42be0
SL
107 }
108 }
109
110 changed
111 }
112}
113
54a0048b
SL
114impl<'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;
92a42be0
SL
117 let mut changed = true;
118 while changed {
54a0048b
SL
119 pretty::dump_mir(tcx, "simplify_cfg", &counter, id, mir, None);
120 counter += 1;
92a42be0
SL
121 changed = self.simplify_branches(mir);
122 changed |= self.remove_goto_chains(mir);
54a0048b 123 RemoveDeadBlocks.run_pass(tcx, id, mir);
92a42be0 124 }
92a42be0
SL
125 // FIXME: Should probably be moved into some kind of pass manager
126 mir.basic_blocks.shrink_to_fit();
127 }
128}
7453a54e 129
54a0048b 130impl Pass for SimplifyCfg {}