inlining.rs 22.8 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
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 17 18 19 20 21 22 23 24 25 26 27 28 29 30
use ast::ir::*;
use ast::ptr::*;
use ast::inst::*;
use vm::VM;

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

pub struct Inlining {
    name: &'static str,

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

qinsoon's avatar
qinsoon committed
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
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) {
        if vm.vm_options.flag_disable_inline {
            info!("inlining is disabled");
            return;
        }

        if self.check(vm, func) {
            self.inline(vm, func);
            debug!("after inlining: {:?}", func);
        }
    }
}

53 54 55 56 57 58 59 60
impl Inlining {
    pub fn new() -> Inlining {
        Inlining{
            name: "Inlining",
            should_inline: HashMap::new()
        }
    }

qinsoon's avatar
qinsoon committed
61
    /// checks whether we need to rewrite the function because of inlining
62
    fn check(&mut self, vm: &VM, func: &mut MuFunctionVersion) -> bool {
qinsoon's avatar
qinsoon committed
63
        debug!("check inline");
qinsoon's avatar
qinsoon committed
64 65 66

        // should_inline will store all the calls from this function,
        // and whether they should be inlined
67 68
        self.should_inline.clear();

qinsoon's avatar
qinsoon committed
69 70
        let mut inline_something = false;

qinsoon's avatar
qinsoon committed
71
        // check each call from this function
qinsoon's avatar
qinsoon committed
72
        for func_id in func.get_static_call_edges().values() {
qinsoon's avatar
qinsoon committed
73 74
            // check a single callsite, whether it should be inlined
            // the result is returned as boolean, and also written into 'should_inline'
75
            let should_inline_this = self.check_should_inline_func(*func_id, func.func_id, vm);
qinsoon's avatar
qinsoon committed
76 77 78 79 80 81
            inline_something = inline_something || should_inline_this;
        }

        inline_something
    }

qinsoon's avatar
qinsoon committed
82
    /// checks whether we should inline the caller into the callee
83 84 85 86 87 88
    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
89
        let funcs_guard = vm.funcs().read().unwrap();
90
        let func = match funcs_guard.get(&callee) {
qinsoon's avatar
qinsoon committed
91
            Some(func) => func.read().unwrap(),
92
            None => panic!("callee {} is undeclared", callee)
qinsoon's avatar
qinsoon committed
93 94 95 96 97 98 99 100 101 102
        };
        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;
            }
        };

qinsoon's avatar
qinsoon committed
103 104 105 106
        // if we have checked this callee before, we use the same result
        // (this is not optimal though. The inline criteria we use at the moment
        // do not take caller size growth into consideration, so we will
        // get the same result anyway. )
qinsoon's avatar
qinsoon committed
107 108
        match self.should_inline.get(&fv_id) {
            Some(flag) => {
109
                trace!("func {} should be inlined (checked before)", callee);
qinsoon's avatar
qinsoon committed
110 111 112 113 114 115 116 117
                return *flag;
            }
            None => {}
        }

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

qinsoon's avatar
qinsoon committed
118
        // if the function is forced inline, we inline it
qinsoon's avatar
qinsoon committed
119
        if fv.force_inline {
120
            trace!("func {} is forced as inline function", callee);
qinsoon's avatar
qinsoon committed
121 122 123 124
            return true;
        }

        // some heuristics here to decide if we should inline the function
125
        let n_insts  = estimate_insts(&fv);
qinsoon's avatar
qinsoon committed
126 127
        let out_calls = fv.get_static_call_edges();
        let has_throw = fv.has_throw();
128
        let has_tailcall = fv.has_tailcall();
qinsoon's avatar
qinsoon committed
129

qinsoon's avatar
qinsoon committed
130 131 132 133
        // simple heuristic here:
        // * estimated machine insts are fewer than 10 insts
        // * leaf in call graph (no out calls)
        // * no throw (otherwise we will need to rearrange catch)
134
        let should_inline = n_insts <= 25 && out_calls.len() == 0 && !has_throw && !has_tailcall;
qinsoon's avatar
qinsoon committed
135

136
        trace!("func {} has {} insts (estimated)", callee, n_insts);
qinsoon's avatar
qinsoon committed
137 138 139 140
        trace!("     has {} out calls", out_calls.len());
        trace!("     has throws? {}", has_throw);
        trace!("SO func should be inlined? {}", should_inline);

141
        self.should_inline.insert(callee, should_inline);
qinsoon's avatar
qinsoon committed
142 143

        should_inline
144 145
    }

qinsoon's avatar
qinsoon committed
146
    /// inlines the callee that are marked as 'should inline'
147
    fn inline(&mut self, vm: &VM, func: &mut MuFunctionVersion) {
qinsoon's avatar
qinsoon committed
148 149 150 151 152 153 154 155 156
        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![];

157
        for (_, block) in f_content.blocks.iter() {
qinsoon's avatar
qinsoon committed
158 159 160 161
            // clone curent block, and clear its instructions
            let mut cur_block = block.clone();
            cur_block.content.as_mut().unwrap().body.clear();

162 163
            let block = block.clone();

qinsoon's avatar
qinsoon committed
164 165
            // iterate through instructions
            for inst in block.content.unwrap().body {
166
                trace!("check inst: {}", inst);
qinsoon's avatar
qinsoon committed
167 168
                let inst_id = inst.id();
                if call_edges.contains_key(&inst_id) {
169 170 171 172 173 174 175
                    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();

qinsoon's avatar
qinsoon committed
176
                        // inline expansion starts here
177

qinsoon's avatar
qinsoon committed
178
                        // getting the function being inlined
179 180
                        let inlined_func = *call_edges.get(&inst.id()).unwrap();
                        trace!("function being inlined is {}", inlined_func);
qinsoon's avatar
vm.rs  
qinsoon committed
181
                        let inlined_fvid = match vm.get_cur_version_for_func(inlined_func) {
182 183 184 185 186 187
                            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();
188 189
                        trace!("orig_content: {:?}", inlined_fv_guard.get_orig_ir().unwrap());
                        trace!("content     : {:?}", inlined_fv_guard.content.as_ref().unwrap());
qinsoon's avatar
[wip]  
qinsoon committed
190

qinsoon's avatar
qinsoon committed
191
                        // creates a new block ID which will be the entry block for the inlined function
192 193
                        let new_inlined_entry_id = vm.next_id();

qinsoon's avatar
qinsoon committed
194
                        // change current call instruction to a branch
195
                        trace!("turning CALL instruction into a branch");
196
                        let ref ops = inst.ops;
197 198 199 200 201 202 203 204
                        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,
205
                                    ops: arg_nodes.clone(),
206
                                    v: Instruction_::Branch1(Destination{
qinsoon's avatar
qinsoon committed
207
                                        // this block doesnt exist yet, we will create it later
208 209 210 211 212 213 214 215 216 217 218 219
                                        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());

220 221 222
                                // creates a new block after inlined part,
                                // which will receive results from inlined function
                                let old_name = cur_block.name();
223 224 225
                                let new_name = format!("{}_cont_after_inline_{}", old_name, inst_id);
                                trace!("create continue block for EXPRCALL/CCALL: {}", &new_name);
                                cur_block = Block::new(MuEntityHeader::named(vm.next_id(), new_name));
226 227 228 229 230 231 232 233 234 235 236 237
                                cur_block.content = Some(BlockContent{
                                    args: {
                                        if inst.value.is_none() {
                                            vec![]
                                        } else {
                                            inst.value.unwrap()
                                        }
                                    },
                                    exn_arg: None,
                                    body: vec![],
                                    keepalives: None
                                });
238
                                vm.set_name(cur_block.as_entity());
239 240 241

                                // deal with the inlined function
                                copy_inline_blocks(&mut new_blocks, cur_block.id(),
qinsoon's avatar
[wip]  
qinsoon committed
242
                                                   inlined_fv_guard.get_orig_ir().unwrap(), new_inlined_entry_id,
243 244 245 246 247 248 249 250 251 252 253
                                                   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,
254
                                    ops: arg_nodes,
255 256 257 258 259 260 261 262 263
                                    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));

264 265 266
                                // next block
                                let mut next_block = resume.normal_dest.target;

267 268 269
                                // 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() {
270
                                    debug!("need an extra block for passing normal dest arguments");
271 272 273
                                    let int_block_name = format!("inline_{}_arg_pass", inst_id);
                                    let mut intermediate_block = Block::new(MuEntityHeader::named(vm.next_id(), int_block_name));
                                    vm.set_name(intermediate_block.as_entity());
274 275 276 277 278 279 280 281

                                    // branch to normal_dest with normal_dest arguments
                                    let normal_dest_args = resume.normal_dest.get_arguments_as_node(&ops);
                                    let normal_dest_args_len = normal_dest_args.len();

                                    let branch = Instruction {
                                        hdr: MuEntityHeader::unnamed(vm.next_id()),
                                        value: None,
282
                                        ops: normal_dest_args,
283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304
                                        v: Instruction_::Branch1(Destination {
                                            target: resume.normal_dest.target,
                                            args: (0..normal_dest_args_len).map(|x| DestArg::Normal(x)).collect()
                                        })
                                    };

                                    intermediate_block.content = Some(BlockContent {
                                        args: {
                                            match inst.value {
                                                Some(ref vec) => vec.clone(),
                                                None => vec![]
                                            }
                                        },
                                        exn_arg: None,
                                        body: vec![TreeNode::new_boxed_inst(branch)],
                                        keepalives: None
                                    });

                                    trace!("extra block: {:?}", intermediate_block);

                                    next_block = intermediate_block.id();
                                    new_blocks.push(intermediate_block);
305 306 307 308
                                }

                                // deal with inlined function
                                copy_inline_blocks(&mut new_blocks, next_block,
qinsoon's avatar
[wip]  
qinsoon committed
309
                                                   inlined_fv_guard.get_orig_ir().unwrap(), new_inlined_entry_id,
310 311 312 313 314 315 316 317
                                                   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
318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333
                    }
                } 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);
        }
    }
}

qinsoon's avatar
qinsoon committed
334
/// copies blocks from callee to caller, with specified entry block and return block
335
fn copy_inline_blocks(caller: &mut Vec<Block>, ret_block: MuID, callee: &FunctionContent, entry_block: MuID, vm: &VM) {
336
    trace!("trying to copy inlined function blocks to caller");
337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362

    // 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
363
    for block in callee.blocks.values() {
qinsoon's avatar
[wip]  
qinsoon committed
364
        let old_id = block.id();
365 366
        let new_id = *block_map.get(&block.id()).unwrap();
        let mut block = Block {
367
            hdr: MuEntityHeader::named(new_id, format!("{}:inlinedblock.#{}", block.name(), new_id)),
368
            content: block.content.clone(),
369
            trace_hint: TraceHint::None,
370 371
            control_flow: ControlFlow::default()
        };
qinsoon's avatar
qinsoon committed
372

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

qinsoon's avatar
qinsoon committed
375 376 377 378
        // check its last instruction
        {
            let block_content = block.content.as_mut().unwrap();
            let last_inst = block_content.body.pop().unwrap();
379 380 381 382 383 384 385 386 387

            // every inst should have a unique ID
            let inst_new_id = vm.next_id();
            let last_inst_clone = match last_inst.v {
                TreeNode_::Instruction(ref inst) => {
                    TreeNode::new_boxed_inst(inst.clone_with_id(inst_new_id))
                }
                _ => panic!("expect instruction as block body")
            };
qinsoon's avatar
qinsoon committed
388 389 390

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

393
                    let hdr = inst.hdr.clone_with_id(inst_new_id);
qinsoon's avatar
qinsoon committed
394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410
                    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
411
                            trace!("rewrite to: {}", branch);
qinsoon's avatar
qinsoon committed
412 413
                            block_content.body.push(TreeNode::new_boxed_inst(branch));
                        },
414 415 416 417 418 419 420 421 422 423

                        // 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
424
                            trace!("rewrite to: {}", branch);
425 426 427 428 429 430 431 432 433 434 435 436 437 438 439
                            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
440
                            trace!("rewrite to: {}", branch2);
441 442 443 444 445 446 447 448 449 450 451 452 453
                            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
454
                            trace!("rewrite to: {}", call);
455 456 457 458 459 460 461 462 463 464 465 466 467
                            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
468
                            trace!("rewrite to: {}", call);
469 470 471 472 473 474 475 476 477 478 479 480 481 482
                            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
483
                            trace!("rewrite to: {}", switch);
484 485 486 487 488 489 490 491
                            block_content.body.push(TreeNode::new_boxed_inst(switch));
                        }

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

qinsoon's avatar
qinsoon committed
492 493 494 495 496 497 498 499 500 501 502 503 504 505
                        _ => {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);
    }
}

qinsoon's avatar
qinsoon committed
506
/// copies inlined function context into caller
qinsoon's avatar
qinsoon committed
507
fn copy_inline_context(caller: &mut FunctionContext, callee: &FunctionContext) {
508
    trace!("trying to copy inlined function context to caller");
qinsoon's avatar
qinsoon committed
509 510
    for (id, entry) in callee.values.iter() {
        caller.values.insert(*id, SSAVarEntry::new(entry.value().clone()));
511 512 513
    }
}

qinsoon's avatar
qinsoon committed
514
/// calculate estimate machine instruction for a Mu function
515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533
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
qinsoon's avatar
qinsoon committed
534
}