GitLab will be upgraded to the 12.10.14-ce.0 on 28 Sept 2020 at 2.00pm (AEDT) to 2.30pm (AEDT). During the update, GitLab and Mattermost services will not be available. If you have any concerns with this, please talk to us at N110 (b) CSIT building.

inlining.rs 18.5 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
use ast::ir::*;
use ast::ptr::*;
use ast::inst::*;
use vm::VM;

use compiler::CompilerPass;
use std::any::Any;
use std::sync::RwLock;
use std::collections::HashMap;

pub struct Inlining {
    name: &'static str,

    // whether a function version should be inlined
    should_inline: HashMap<MuID, bool>
}

impl Inlining {
    pub fn new() -> Inlining {
        Inlining{
            name: "Inlining",
            should_inline: HashMap::new()
        }
    }

    fn check(&mut self, vm: &VM, func: &mut MuFunctionVersion) -> bool {
qinsoon's avatar
qinsoon committed
27
        debug!("check inline");
28 29
        self.should_inline.clear();

qinsoon's avatar
qinsoon committed
30 31 32
        let mut inline_something = false;

        for func_id in func.get_static_call_edges().values() {
33
            let should_inline_this = self.check_should_inline_func(*func_id, func.func_id, vm);
qinsoon's avatar
qinsoon committed
34 35 36 37 38 39 40 41

            inline_something = inline_something || should_inline_this;
        }

        inline_something
    }

    #[allow(unused_variables)]
42 43 44 45 46 47
    fn check_should_inline_func(&mut self, callee: MuID, caller: MuID, vm: &VM) -> bool {
        // recursive call, do not inline
        if callee == caller {
            return false;
        }

qinsoon's avatar
qinsoon committed
48
        let funcs_guard = vm.funcs().read().unwrap();
49
        let func = match funcs_guard.get(&callee) {
qinsoon's avatar
qinsoon committed
50
            Some(func) => func.read().unwrap(),
51
            None => panic!("callee {} is undeclared", callee)
qinsoon's avatar
qinsoon committed
52 53 54 55 56 57 58 59 60 61 62 63 64
        };

        let fv_id = match func.cur_ver {
            Some(fv_id) => fv_id,
            None => {
                // the funtion is not defined
                info!("the function is undefined, we cannot inline it. ");
                return false;
            }
        };

        match self.should_inline.get(&fv_id) {
            Some(flag) => {
65
                trace!("func {} should be inlined (checked before)", callee);
qinsoon's avatar
qinsoon committed
66 67 68 69 70 71 72 73 74 75
                return *flag;
            }
            None => {}
        }

        let fv_guard = vm.func_vers().read().unwrap();
        let fv = fv_guard.get(&fv_id).unwrap().read().unwrap();

        // if the function is forced inline, then we inline it
        if fv.force_inline {
76
            trace!("func {} is forced as inline function", callee);
qinsoon's avatar
qinsoon committed
77 78 79 80 81 82
            return true;
        }

        // some heuristics here to decide if we should inline the function
        // to be more precise. we should be target specific
        let n_params = fv.sig.arg_tys.len();
83
        let n_insts  = estimate_insts(&fv);
qinsoon's avatar
qinsoon committed
84 85 86 87 88
        let out_calls = fv.get_static_call_edges();
        let has_throw = fv.has_throw();

        // now we use a simple heuristic here:
        // insts fewer than 10, no static out calls, no throw
89
        let should_inline = n_insts <= 25 && out_calls.len() == 0 && !has_throw;
qinsoon's avatar
qinsoon committed
90

91
        trace!("func {} has {} insts (estimated)", callee, n_insts);
qinsoon's avatar
qinsoon committed
92 93 94 95
        trace!("     has {} out calls", out_calls.len());
        trace!("     has throws? {}", has_throw);
        trace!("SO func should be inlined? {}", should_inline);

96
        self.should_inline.insert(callee, should_inline);
qinsoon's avatar
qinsoon committed
97 98

        should_inline
99 100 101
    }

    fn inline(&mut self, vm: &VM, func: &mut MuFunctionVersion) {
qinsoon's avatar
qinsoon committed
102 103 104 105 106 107 108 109 110
        debug!("inlining for Function {}", func);

        let call_edges = func.get_static_call_edges();

        let mut f_content = func.content.as_mut().unwrap();
        let ref mut f_context = func.context;

        let mut new_blocks : Vec<Block> = vec![];

111
        for (_, block) in f_content.blocks.iter() {
qinsoon's avatar
qinsoon committed
112 113 114 115
            // clone curent block, and clear its instructions
            let mut cur_block = block.clone();
            cur_block.content.as_mut().unwrap().body.clear();

116 117
            let block = block.clone();

qinsoon's avatar
qinsoon committed
118 119
            // iterate through instructions
            for inst in block.content.unwrap().body {
120
                trace!("check inst: {}", inst);
qinsoon's avatar
qinsoon committed
121 122
                let inst_id = inst.id();
                if call_edges.contains_key(&inst_id) {
123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
                    let call_target = call_edges.get(&inst_id).unwrap();
                    if self.should_inline.contains_key(call_target) && *self.should_inline.get(call_target).unwrap() {

                        trace!("inserting inlined function at {}", inst);

                        // from TreeNode into Inst (we do not need old TreeNode)
                        let inst = inst.into_inst().unwrap();

                        // (inline expansion)

                        let inlined_func = *call_edges.get(&inst.id()).unwrap();
                        trace!("function being inlined is {}", inlined_func);

                        let inlined_fvid = match vm.get_cur_version_of(inlined_func) {
                            Some(fvid) => fvid,
                            None => panic!("cannot resolve current version of Func {}, which is supposed to be inlined", inlined_func)
                        };

                        let inlined_fvs_guard = vm.func_vers().read().unwrap();
                        let inlined_fv_lock   = inlined_fvs_guard.get(&inlined_fvid).unwrap();
                        let inlined_fv_guard  = inlined_fv_lock.read().unwrap();

qinsoon's avatar
[wip]  
qinsoon committed
145 146 147
                        trace!("QINSOON_DEBUG: orig_content: {:?}", inlined_fv_guard.get_orig_ir().unwrap());
                        trace!("QINSOON_DEBUG: content     : {:?}", inlined_fv_guard.content.as_ref().unwrap());

148 149 150 151 152 153 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 194 195 196 197 198
                        let new_inlined_entry_id = vm.next_id();

                        // change current call insts to a branch
                        trace!("turning CALL instruction into a branch");
                        let ops = inst.ops.read().unwrap();

                        match inst.v {
                            Instruction_::ExprCall {ref data, ..} => {
                                let arg_nodes  : Vec<P<TreeNode>> = data.args.iter().map(|x| ops[*x].clone()).collect();
                                let arg_indices: Vec<OpIndex> = (0..arg_nodes.len()).collect();

                                let branch = TreeNode::new_boxed_inst(Instruction{
                                    hdr: inst.hdr.clone(),
                                    value: None,
                                    ops: RwLock::new(arg_nodes.clone()),
                                    v: Instruction_::Branch1(Destination{
                                        // this block doesnt exist yet, we will fix it later
                                        target: new_inlined_entry_id,
                                        args: arg_indices.iter().map(|x| DestArg::Normal(*x)).collect()
                                    })
                                });

                                trace!("branch inst: {}", branch);

                                // add branch to current block
                                cur_block.content.as_mut().unwrap().body.push(branch);

                                // finish current block
                                new_blocks.push(cur_block.clone());
                                let old_name = cur_block.name().unwrap();

                                // start a new block
                                cur_block = Block::new(vm.next_id());
                                cur_block.content = Some(BlockContent{
                                    args: {
                                        if inst.value.is_none() {
                                            vec![]
                                        } else {
                                            inst.value.unwrap()
                                        }
                                    },
                                    exn_arg: None,
                                    body: vec![],
                                    keepalives: None
                                });
                                let new_name = format!("{}_cont_after_inline_{}", old_name, inst_id);
                                trace!("create continue block for EXPRCALL/CCALL: {}", &new_name);
                                vm.set_name(cur_block.as_entity(), new_name);

                                // deal with the inlined function
                                copy_inline_blocks(&mut new_blocks, cur_block.id(),
qinsoon's avatar
[wip]  
qinsoon committed
199
                                                   inlined_fv_guard.get_orig_ir().unwrap(), new_inlined_entry_id,
200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230
                                                   vm);
                                copy_inline_context(f_context, &inlined_fv_guard.context);
                            },

                            Instruction_::Call {ref data, ref resume} => {
                                let arg_nodes  : Vec<P<TreeNode>> = data.args.iter().map(|x| ops[*x].clone()).collect();
                                let arg_indices: Vec<OpIndex> = (0..arg_nodes.len()).collect();

                                let branch = Instruction{
                                    hdr: inst.hdr.clone(),
                                    value: None,
                                    ops: RwLock::new(arg_nodes),
                                    v: Instruction_::Branch1(Destination{
                                        target: new_inlined_entry_id,
                                        args: arg_indices.iter().map(|x| DestArg::Normal(*x)).collect()
                                    })
                                };

                                // add branch to current block
                                cur_block.content.as_mut().unwrap().body.push(TreeNode::new_boxed_inst(branch));

                                // if normal_dest expects different number of arguments
                                // other than the inlined function returns, we need an intermediate block to pass extra arguments
                                if resume.normal_dest.args.len() != inlined_fv_guard.sig.ret_tys.len() {
                                    unimplemented!()
                                }

                                // deal with inlined function
                                let next_block = resume.normal_dest.target;

                                copy_inline_blocks(&mut new_blocks, next_block,
qinsoon's avatar
[wip]  
qinsoon committed
231
                                                   inlined_fv_guard.get_orig_ir().unwrap(), new_inlined_entry_id,
232 233 234 235 236 237 238 239
                                                   vm);
                                copy_inline_context(f_context, &inlined_fv_guard.context);
                            },

                            _ => panic!("unexpected callsite: {}", inst)
                        }
                    } else {
                        cur_block.content.as_mut().unwrap().body.push(inst.clone());
qinsoon's avatar
qinsoon committed
240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
                    }
                } else {
                    cur_block.content.as_mut().unwrap().body.push(inst.clone());
                }
            }

            new_blocks.push(cur_block);
        }

        f_content.blocks.clear();
        for blk in new_blocks {
            f_content.blocks.insert(blk.id(), blk);
        }
    }
}

256
fn copy_inline_blocks(caller: &mut Vec<Block>, ret_block: MuID, callee: &FunctionContent, entry_block: MuID, vm: &VM) {
257
    trace!("trying to copy inlined function blocks to caller");
258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283

    // old id -> new id
    let mut block_map : HashMap<MuID, MuID> = HashMap::new();

    for block in callee.blocks.values() {
        if block.id() == callee.entry {
            block_map.insert(block.id(), entry_block);
        } else {
            block_map.insert(block.id(), vm.next_id());
        }
    }

    let fix_dest = |dest : Destination| {
        Destination {
            target: *block_map.get(&dest.target).unwrap(),
            args: dest.args
        }
    };

    let fix_resume = |resume : ResumptionData| {
        ResumptionData {
            normal_dest: fix_dest(resume.normal_dest),
            exn_dest: fix_dest(resume.exn_dest)
        }
    };

qinsoon's avatar
qinsoon committed
284
    for block in callee.blocks.values() {
qinsoon's avatar
[wip]  
qinsoon committed
285
        let old_id = block.id();
286 287 288 289 290 291
        let new_id = *block_map.get(&block.id()).unwrap();
        let mut block = Block {
            hdr: MuEntityHeader::named(new_id, format!("IB{}_for_{}", new_id, block.id())),
            content: block.content.clone(),
            control_flow: ControlFlow::default()
        };
qinsoon's avatar
qinsoon committed
292

qinsoon's avatar
[wip]  
qinsoon committed
293 294
        trace!("starts copying instruction from {} to {}", old_id, new_id);

qinsoon's avatar
qinsoon committed
295 296 297 298 299 300 301 302
        // check its last instruction
        {
            let block_content = block.content.as_mut().unwrap();
            let last_inst = block_content.body.pop().unwrap();
            let last_inst_clone = last_inst.clone();

            match last_inst.v {
                TreeNode_::Instruction(inst) => {
qinsoon's avatar
[wip]  
qinsoon committed
303 304
                    trace!("last instruction: {}", inst);

qinsoon's avatar
qinsoon committed
305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322
                    let hdr = inst.hdr;
                    let value = inst.value;
                    let ops = inst.ops;
                    let v = inst.v;

                    match v {
                        Instruction_::Return(vec) => {
                            // change RET to a branch
                            let branch = Instruction {
                                hdr: hdr,
                                value: value,
                                ops: ops,
                                v: Instruction_::Branch1(Destination {
                                    target: ret_block,
                                    args: vec.iter().map(|x| DestArg::Normal(*x)).collect()
                                })
                            };

qinsoon's avatar
[wip]  
qinsoon committed
323
                            trace!("rewrite to: {}", branch);
qinsoon's avatar
qinsoon committed
324 325
                            block_content.body.push(TreeNode::new_boxed_inst(branch));
                        },
326 327 328 329 330 331 332 333 334 335

                        // fix destination
                        Instruction_::Branch1(dest) => {
                            let branch = Instruction {
                                hdr: hdr,
                                value: value,
                                ops: ops,
                                v: Instruction_::Branch1(fix_dest(dest))
                            };

qinsoon's avatar
[wip]  
qinsoon committed
336
                            trace!("rewrite to: {}", branch);
337 338 339 340 341 342 343 344 345 346 347 348 349 350 351
                            block_content.body.push(TreeNode::new_boxed_inst(branch));
                        }
                        Instruction_::Branch2{cond, true_dest, false_dest, true_prob} => {
                            let branch2 = Instruction {
                                hdr: hdr,
                                value: value,
                                ops: ops,
                                v: Instruction_::Branch2 {
                                    cond: cond,
                                    true_dest: fix_dest(true_dest),
                                    false_dest: fix_dest(false_dest),
                                    true_prob: true_prob
                                }
                            };

qinsoon's avatar
[wip]  
qinsoon committed
352
                            trace!("rewrite to: {}", branch2);
353 354 355 356 357 358 359 360 361 362 363 364 365
                            block_content.body.push(TreeNode::new_boxed_inst(branch2));
                        }
                        Instruction_::Call{data, resume} => {
                            let call = Instruction{
                                hdr: hdr,
                                value: value,
                                ops: ops,
                                v: Instruction_::Call {
                                    data: data,
                                    resume: fix_resume(resume)
                                }
                            };

qinsoon's avatar
[wip]  
qinsoon committed
366
                            trace!("rewrite to: {}", call);
367 368 369 370 371 372 373 374 375 376 377 378 379
                            block_content.body.push(TreeNode::new_boxed_inst(call));
                        }
                        Instruction_::CCall{data, resume} => {
                            let call = Instruction{
                                hdr: hdr,
                                value: value,
                                ops: ops,
                                v: Instruction_::CCall {
                                    data: data,
                                    resume: fix_resume(resume)
                                }
                            };

qinsoon's avatar
[wip]  
qinsoon committed
380
                            trace!("rewrite to: {}", call);
381 382 383 384 385 386 387 388 389 390 391 392 393 394
                            block_content.body.push(TreeNode::new_boxed_inst(call));
                        }
                        Instruction_::Switch {cond, default, mut branches} => {
                            let switch = Instruction {
                                hdr: hdr,
                                value: value,
                                ops: ops,
                                v: Instruction_::Switch {
                                    cond: cond,
                                    default: fix_dest(default),
                                    branches: branches.drain(..).map(|(op, dest)| (op, fix_dest(dest))).collect()
                                }
                            };

qinsoon's avatar
[wip]  
qinsoon committed
395
                            trace!("rewrite to: {}", switch);
396 397 398 399 400 401 402 403
                            block_content.body.push(TreeNode::new_boxed_inst(switch));
                        }

                        Instruction_::Watchpoint{..}
                        | Instruction_::WPBranch{..}
                        | Instruction_::SwapStack{..}
                        | Instruction_::ExnInstruction{..} => unimplemented!(),

qinsoon's avatar
qinsoon committed
404 405 406 407 408 409 410 411 412 413 414 415 416 417 418
                        _ => {block_content.body.push(last_inst_clone);}
                    }
                },
                _ => {
                    // do nothing, and directly push the instruction back
                    block_content.body.push(last_inst_clone)
                }
            }
        }

        caller.push(block);
    }
}

fn copy_inline_context(caller: &mut FunctionContext, callee: &FunctionContext) {
419
    trace!("trying to copy inlined function context to caller");
qinsoon's avatar
qinsoon committed
420 421
    for (id, entry) in callee.values.iter() {
        caller.values.insert(*id, SSAVarEntry::new(entry.value().clone()));
422 423 424
    }
}

425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445
fn estimate_insts(fv: &MuFunctionVersion) -> usize {
    let f_content = fv.content.as_ref().unwrap();

    let mut insts = 0;

    for block in f_content.blocks.values() {
        let ref body = block.content.as_ref().unwrap().body;

        for inst in body.iter() {
            use compiler::backend;

            match inst.v {
                TreeNode_::Value(_) => unreachable!(),
                TreeNode_::Instruction(ref inst) => {insts += backend::estimate_insts_for_ir(inst);}
            }
        }
    }

    insts
}

446 447 448 449 450 451 452 453 454 455
impl CompilerPass for Inlining {
    fn name(&self) -> &'static str {
        self.name
    }

    fn as_any(&self) -> &Any {
        self
    }

    fn visit_function(&mut self, vm: &VM, func: &mut MuFunctionVersion) {
456
        if vm.vm_options.flag_disable_inline {
457 458 459 460
            info!("inlining is disabled");
            return;
        }

461 462
        if self.check(vm, func) {
            self.inline(vm, func);
463 464

            debug!("after inlining: {:?}", func);
465 466
        }
    }
467
}