control_flow.rs 11.3 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// Copyright 2017 The Australian National University
// 
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// 
//     http://www.apache.org/licenses/LICENSE-2.0
// 
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

15 16
use ast::ir::*;
use ast::inst::Instruction_::*;
17
use utils::vec_utils::as_str as vector_as_str;
qinsoon's avatar
qinsoon committed
18
use vm::VM;
19
use compiler::CompilerPass;
20
use utils::LinkedHashMap;
21
use utils::LinkedHashSet;
qinsoon's avatar
qinsoon committed
22 23
use std::any::Any;

24 25 26 27 28 29 30 31 32 33
pub struct ControlFlowAnalysis {
    name: &'static str
}

impl ControlFlowAnalysis {
    pub fn new() -> ControlFlowAnalysis {
        ControlFlowAnalysis{name: "Control Flow Analysis"}
    }
}

qinsoon's avatar
qinsoon committed
34
fn check_edge_kind(target: MuID, stack: &Vec<MuID>) -> EdgeKind {
35 36 37 38 39 40 41
    if stack.contains(&target) {
        EdgeKind::Backward
    } else {
        EdgeKind::Forward
    }
}

qinsoon's avatar
qinsoon committed
42
fn new_edge(cur: MuID, edge: BlockEdge, stack: &mut Vec<MuID>, visited: &mut Vec<MuID>, func: &mut MuFunctionVersion) {
43 44
    // add current block to target's predecessors
    {
qinsoon's avatar
qinsoon committed
45
        let target = func.content.as_mut().unwrap().get_block_mut(edge.target);
46 47
        target.control_flow.preds.push(cur);
    }
48

qinsoon's avatar
qinsoon committed
49 50
    // add target as current block's successors and start dfs
    let succ = edge.target;
51
    {
qinsoon's avatar
qinsoon committed
52
        let cur = func.content.as_mut().unwrap().get_block_mut(cur);
53 54
        cur.control_flow.succs.push(edge);
    }
qinsoon's avatar
qinsoon committed
55 56 57
    if !visited.contains(&succ) {
        dfs(succ, stack, visited, func);
    }
58

59 60 61 62 63 64 65
}

const WATCHPOINT_DISABLED_CHANCE : f32 = 0.9f32;

const NORMAL_RESUME_CHANCE       : f32 = 0.6f32;
const EXN_RESUME_CHANCE          : f32 = 1f32 - NORMAL_RESUME_CHANCE;

qinsoon's avatar
qinsoon committed
66
fn dfs(cur: MuID, stack: &mut Vec<MuID>, visited: &mut Vec<MuID>, func: &mut MuFunctionVersion) {
qinsoon's avatar
qinsoon committed
67 68 69
    trace!("dfs visiting block {}", cur);
    trace!("current stack: {:?}", stack);
    trace!("current visited: {:?}", visited);
70

71 72
    stack.push(cur);
    visited.push(cur);
73 74

    // find all the successors for current block, and push them to the stack
75
    let out_edges : Vec<BlockEdge> = {
76
        let cur = func.content.as_mut().unwrap().get_block_mut(cur);
77 78
        let ref body = cur.content.as_ref().unwrap().body;
        let last_inst = body.last().unwrap();
79

80 81 82 83 84 85 86 87 88 89
        match last_inst.v {
            TreeNode_::Instruction(ref inst) => {
                match inst.v {
                    // unconditional branch, definitely branch to the target
                    Branch1(ref dest) => vec![BlockEdge{
                        target: dest.target,
                        kind: check_edge_kind(dest.target, stack),
                        is_exception: false,
                        probability: 1.0f32
                    }],
90

91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
                    // conditional branch
                    Branch2{ref true_dest, ref false_dest, true_prob, ..} => vec![
                        BlockEdge{
                            target: true_dest.target,
                            kind: check_edge_kind(true_dest.target, stack),
                            is_exception: false,
                            probability: true_prob
                        },
                        BlockEdge{
                            target: false_dest.target,
                            kind: check_edge_kind(false_dest.target, stack),
                            is_exception: false,
                            probability: 1.0f32 - true_prob
                        }
                    ],
106

qinsoon's avatar
qinsoon committed
107 108 109 110 111
                    // switch
                    Switch{ref default, ref branches, ..} => {
                        const BRANCH_DEFAULT_PROB : f32 = 0.1;
                        let switch_prob = (1.0f32 - BRANCH_DEFAULT_PROB) / (branches.len() as f32);

112 113
                        let map : LinkedHashMap<MuID, BlockEdge> = {
                            let mut ret = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
114

115
                            let check_add_edge = |map: &mut LinkedHashMap<MuID, BlockEdge>, target: MuID, prob: f32| {
qinsoon's avatar
qinsoon committed
116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
                                if map.contains_key(&target) {
                                    let mut edge : &mut BlockEdge = map.get_mut(&target).unwrap();
                                    edge.probability += prob;
                                } else {
                                    map.insert(target, BlockEdge{
                                        target: target,
                                        kind: check_edge_kind(target, stack),
                                        is_exception: false,
                                        probability: prob
                                    });
                                }
                            };

                            for &(_, ref dest) in branches.iter() {
                                let target = dest.target;

                                check_add_edge(&mut ret, target, switch_prob);
                            }

                            check_add_edge(&mut ret, default.target, BRANCH_DEFAULT_PROB);

                            ret
                        };

                        let mut ret = vec![];

                        for edge in map.values() {
                            ret.push(*edge);
                        }
qinsoon's avatar
qinsoon committed
145 146 147 148

                        ret
                    }

149 150 151
                    // watchpoints
                    Watchpoint{ref id, ref disable_dest, ref resume} => {
                        let ref normal = resume.normal_dest;
152 153
                        let ref exn    = resume.exn_dest;

154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193
                        if id.is_none() {
                            // unconditional trap
                            vec![
                                BlockEdge{
                                    target: normal.target,
                                    kind: check_edge_kind(normal.target, stack),
                                    is_exception: false,
                                    probability: 1.0f32 * NORMAL_RESUME_CHANCE
                                },
                                BlockEdge{
                                    target: exn.target,
                                    kind: check_edge_kind(exn.target, stack),
                                    is_exception: true,
                                    probability: 1.0f32 * EXN_RESUME_CHANCE
                                }
                            ]
                        } else {
                            // watchpoint. jump to disable_dest when disabled. otherwise trap
                            vec![
                                BlockEdge{
                                    target: disable_dest.as_ref().unwrap().target,
                                    kind: check_edge_kind(disable_dest.as_ref().unwrap().target, stack),
                                    is_exception: false,
                                    probability: WATCHPOINT_DISABLED_CHANCE
                                },
                                BlockEdge{
                                    target: normal.target,
                                    kind: check_edge_kind(normal.target, stack),
                                    is_exception: false,
                                    probability: (1.0f32 - WATCHPOINT_DISABLED_CHANCE) * NORMAL_RESUME_CHANCE
                                },
                                BlockEdge{
                                    target: exn.target,
                                    kind: check_edge_kind(exn.target, stack),
                                    is_exception: true,
                                    probability: (1.0f32 - WATCHPOINT_DISABLED_CHANCE) * EXN_RESUME_CHANCE
                                }
                            ]
                        }
                    },
194

195 196 197 198 199 200 201 202 203 204 205 206 207 208 209
                    // wpbranch
                    WPBranch{ref disable_dest, ref enable_dest, ..} => vec![
                        BlockEdge{
                            target: disable_dest.target,
                            kind: check_edge_kind(disable_dest.target, stack),
                            is_exception: false,
                            probability: WATCHPOINT_DISABLED_CHANCE
                        },
                        BlockEdge{
                            target: enable_dest.target,
                            kind: check_edge_kind(enable_dest.target, stack),
                            is_exception: false,
                            probability: 1.0f32 - WATCHPOINT_DISABLED_CHANCE
                        }
                    ],
210

211
                    // call
212
                    Call{ref resume, ..}
qinsoon's avatar
qinsoon committed
213
                    | CCall{ref resume, ..}
214 215 216 217
                    | SwapStack{ref resume, ..}
                    | ExnInstruction{ref resume, ..} => {
                        let ref normal = resume.normal_dest;
                        let ref exn    = resume.exn_dest;
218

219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234
                        vec![
                                BlockEdge{
                                    target: normal.target,
                                    kind: check_edge_kind(normal.target, stack),
                                    is_exception: false,
                                    probability: 1.0f32 * NORMAL_RESUME_CHANCE
                                },
                                BlockEdge{
                                    target: exn.target,
                                    kind: check_edge_kind(exn.target, stack),
                                    is_exception: true,
                                    probability: 1.0f32 * EXN_RESUME_CHANCE
                                }

                        ]
                    },
235

236 237 238 239 240 241
                    _ => vec![]
                }
            },
            _ => panic!("expected an instruction")
        }
    };
242

qinsoon's avatar
qinsoon committed
243
    trace!("out edges for {}: {}", cur, vector_as_str(&out_edges));
244

245
    for edge in out_edges {
qinsoon's avatar
qinsoon committed
246
        new_edge(cur, edge, stack, visited, func);
247
    }
248

249 250 251 252 253 254 255
    stack.pop();
}

impl CompilerPass for ControlFlowAnalysis {
    fn name(&self) -> &'static str {
        self.name
    }
256

qinsoon's avatar
qinsoon committed
257 258 259 260
    fn as_any(&self) -> &Any {
        self
    }

261
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
262
    fn visit_function(&mut self, vm: &VM, func: &mut MuFunctionVersion) {
qinsoon's avatar
qinsoon committed
263 264
        let mut stack   : Vec<MuID> = vec![];
        let mut visited : Vec<MuID> = vec![];
265

266 267
        dfs(func.content.as_ref().unwrap().entry, &mut stack, &mut visited, func);
    }
268

269
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
270
    fn finish_function(&mut self, vm: &VM, func: &mut MuFunctionVersion) {
271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286
        {
            let mut exception_blocks = LinkedHashSet::new();

            for block in func.content.as_ref().unwrap().blocks.iter() {
                let ref control_flow = block.1.control_flow;

                for edge in control_flow.succs.iter() {
                    if edge.is_exception {
                        exception_blocks.insert(edge.target);
                    }
                }
            }

            func.content.as_mut().unwrap().exception_blocks.add_all(exception_blocks);
        }

qinsoon's avatar
qinsoon committed
287
        debug!("check control flow for {}", func);
288

289 290
        for entry in func.content.as_ref().unwrap().blocks.iter() {
            debug!("block {}", entry.0);
291

292 293 294
            debug!("{}", entry.1.control_flow);
        }
    }
295
}