src/librustc_mir/transform/inline.rs

   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.
   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
  11 //! Inlining pass for MIR functions
  12
  13 use rustc::hir::def_id::DefId;
  14
  15 use rustc_data_structures::bitvec::BitVector;
  16 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
  17 use rustc_data_structures::graph;
  18
  19 use rustc::dep_graph::DepNode;
  20 use rustc::mir::*;
  21 use rustc::mir::transform::{MirMapPass, MirPassHook, MirSource, Pass};
  22 use rustc::mir::visit::*;
  23 use rustc::traits;
  24 use rustc::ty::{self, Ty, TyCtxt};
  25 use rustc::ty::subst::{Subst,Substs};
  26 use rustc::util::nodemap::{DefIdSet};
  27
  28 use super::simplify::{remove_dead_blocks, CfgSimplifier};
  29
  30 use syntax::{attr};
  31 use syntax::abi::Abi;
  32
  33 use callgraph;
  34
  35 const DEFAULT_THRESHOLD: usize = 50;
  36 const HINT_THRESHOLD: usize = 100;
  37
  38 const INSTR_COST: usize = 5;
  39 const CALL_PENALTY: usize = 25;
  40
  41 const UNKNOWN_SIZE_COST: usize = 10;
  42
  43 pub struct Inline;
  44
  45 impl<'tcx> MirMapPass<'tcx> for Inline {
  46     fn run_pass<'a>(
  47         &mut self,
  48         tcx: TyCtxt<'a, 'tcx, 'tcx>,
  49         hooks: &mut [Box<for<'s> MirPassHook<'s>>]) {
  50
  51         if tcx.sess.opts.debugging_opts.mir_opt_level < 2 { return; }
  52
  53         let _ignore = tcx.dep_graph.in_ignore();
  54
  55         let callgraph = callgraph::CallGraph::build(tcx);
  56
  57         let mut inliner = Inliner {
  58             tcx: tcx,
  59         };
  60
  61         let def_ids = tcx.maps.mir.borrow().keys();
  62         for &def_id in &def_ids {
  63             if !def_id.is_local() { continue; }
  64
  65             let _task = tcx.dep_graph.in_task(DepNode::Mir(def_id));
  66             let mut mir = if let Some(mir) = tcx.maps.mir.borrow().get(&def_id) {
  67                 mir.borrow_mut()
  68             } else {
  69                 continue;
  70             };
  71
  72             tcx.dep_graph.write(DepNode::Mir(def_id));
  73
  74             let id = tcx.hir.as_local_node_id(def_id).unwrap();
  75             let src = MirSource::from_node(tcx, id);
  76
  77             for hook in &mut *hooks {
  78                 hook.on_mir_pass(tcx, src, &mut mir, self, false);
  79             }
  80         }
  81
  82         for scc in callgraph.scc_iter() {
  83             inliner.inline_scc(&callgraph, &scc);
  84         }
  85
  86         for def_id in def_ids {
  87             if !def_id.is_local() { continue; }
  88
  89             let _task = tcx.dep_graph.in_task(DepNode::Mir(def_id));
  90             let mut mir = tcx.maps.mir.borrow()[&def_id].borrow_mut();
  91             tcx.dep_graph.write(DepNode::Mir(def_id));
  92
  93             let id = tcx.hir.as_local_node_id(def_id).unwrap();
  94             let src = MirSource::from_node(tcx, id);
  95
  96             for hook in &mut *hooks {
  97                 hook.on_mir_pass(tcx, src, &mut mir, self, true);
  98             }
  99         }
 100     }
 101 }
 102
 103 impl<'tcx> Pass for Inline { }
 104
 105 struct Inliner<'a, 'tcx: 'a> {
 106     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 107 }
 108
 109 #[derive(Copy, Clone)]
 110 struct CallSite<'tcx> {
 111     caller: DefId,
 112     callee: DefId,
 113     substs: &'tcx Substs<'tcx>,
 114     bb: BasicBlock,
 115     location: SourceInfo,
 116 }
 117
 118 impl<'a, 'tcx> Inliner<'a, 'tcx> {
 119     fn inline_scc(&mut self, callgraph: &callgraph::CallGraph, scc: &[graph::NodeIndex]) -> bool {
 120         let mut callsites = Vec::new();
 121         let mut in_scc = DefIdSet();
 122
 123         let mut inlined_into = DefIdSet();
 124
 125         for &node in scc {
 126             let def_id = callgraph.def_id(node);
 127
 128             // Don't inspect functions from other crates
 129             let id = if let Some(id) = self.tcx.hir.as_local_node_id(def_id) {
 130                 id
 131             } else {
 132                 continue;
 133             };
 134             let src = MirSource::from_node(self.tcx, id);
 135             if let MirSource::Fn(_) = src {
 136                 if let Some(mir) = self.tcx.maybe_item_mir(def_id) {
 137                     for (bb, bb_data) in mir.basic_blocks().iter_enumerated() {
 138                         // Don't inline calls that are in cleanup blocks.
 139                         if bb_data.is_cleanup { continue; }
 140
 141                         // Only consider direct calls to functions
 142                         let terminator = bb_data.terminator();
 143                         if let TerminatorKind::Call {
 144                             func: Operand::Constant(ref f), .. } = terminator.kind {
 145                             if let ty::TyFnDef(callee_def_id, substs, _) = f.ty.sty {
 146                                 callsites.push(CallSite {
 147                                     caller: def_id,
 148                                     callee: callee_def_id,
 149                                     substs: substs,
 150                                     bb: bb,
 151                                     location: terminator.source_info
 152                                 });
 153                             }
 154                         }
 155                     }
 156
 157                     in_scc.insert(def_id);
 158                 }
 159             }
 160         }
 161
 162         // Move callsites that are in the the SCC to the end so
 163         // they're inlined after calls to outside the SCC
 164         let mut first_call_in_scc = callsites.len();
 165
 166         let mut i = 0;
 167         while i < first_call_in_scc {
 168             let f = callsites[i].caller;
 169             if in_scc.contains(&f) {
 170                 first_call_in_scc -= 1;
 171                 callsites.swap(i, first_call_in_scc);
 172             } else {
 173                 i += 1;
 174             }
 175         }
 176
 177         let mut local_change;
 178         let mut changed = false;
 179
 180         loop {
 181             local_change = false;
 182             let mut csi = 0;
 183             while csi < callsites.len() {
 184                 let callsite = callsites[csi];
 185                 csi += 1;
 186
 187                 let _task = self.tcx.dep_graph.in_task(DepNode::Mir(callsite.caller));
 188                 self.tcx.dep_graph.write(DepNode::Mir(callsite.caller));
 189
 190                 let callee_mir = {
 191                     if let Some(callee_mir) = self.tcx.maybe_item_mir(callsite.callee) {
 192                         if !self.should_inline(callsite, &callee_mir) {
 193                             continue;
 194                         }
 195
 196                         callee_mir.subst(self.tcx, callsite.substs)
 197                     } else {
 198                         continue;
 199                     }
 200
 201                 };
 202
 203                 let mut caller_mir = {
 204                     let map = self.tcx.maps.mir.borrow();
 205                     let mir = map.get(&callsite.caller).unwrap();
 206                     mir.borrow_mut()
 207                 };
 208
 209                 let start = caller_mir.basic_blocks().len();
 210
 211                 if !self.inline_call(callsite, &mut caller_mir, callee_mir) {
 212                     continue;
 213                 }
 214
 215                 inlined_into.insert(callsite.caller);
 216
 217                 // Add callsites from inlined function
 218                 for (bb, bb_data) in caller_mir.basic_blocks().iter_enumerated().skip(start) {
 219                     // Only consider direct calls to functions
 220                     let terminator = bb_data.terminator();
 221                     if let TerminatorKind::Call {
 222                         func: Operand::Constant(ref f), .. } = terminator.kind {
 223                         if let ty::TyFnDef(callee_def_id, substs, _) = f.ty.sty {
 224                             // Don't inline the same function multiple times.
 225                             if callsite.callee != callee_def_id {
 226                                 callsites.push(CallSite {
 227                                     caller: callsite.caller,
 228                                     callee: callee_def_id,
 229                                     substs: substs,
 230                                     bb: bb,
 231                                     location: terminator.source_info
 232                                 });
 233                             }
 234                         }
 235                     }
 236                 }
 237
 238                 csi -= 1;
 239                 if scc.len() == 1 {
 240                     callsites.swap_remove(csi);
 241                 } else {
 242                     callsites.remove(csi);
 243                 }
 244
 245                 local_change = true;
 246                 changed = true;
 247             }
 248
 249             if !local_change {
 250                 break;
 251             }
 252         }
 253
 254         // Simplify functions we inlined into.
 255         for def_id in inlined_into {
 256             let _task = self.tcx.dep_graph.in_task(DepNode::Mir(def_id));
 257             self.tcx.dep_graph.write(DepNode::Mir(def_id));
 258
 259             let mut caller_mir = {
 260                 let map = self.tcx.maps.mir.borrow();
 261                 let mir = map.get(&def_id).unwrap();
 262                 mir.borrow_mut()
 263             };
 264
 265             debug!("Running simplify cfg on {:?}", def_id);
 266             CfgSimplifier::new(&mut caller_mir).simplify();
 267             remove_dead_blocks(&mut caller_mir);
 268         }
 269         changed
 270     }
 271
 272     fn should_inline(&self, callsite: CallSite<'tcx>,
 273                      callee_mir: &'a Mir<'tcx>) -> bool {
 274
 275         let tcx = self.tcx;
 276
 277         // Don't inline closures that have captures
 278         // FIXME: Handle closures better
 279         if callee_mir.upvar_decls.len() > 0 {
 280             return false;
 281         }
 282
 283
 284         let attrs = tcx.get_attrs(callsite.callee);
 285         let hint = attr::find_inline_attr(None, &attrs[..]);
 286
 287         let hinted = match hint {
 288             // Just treat inline(always) as a hint for now,
 289             // there are cases that prevent inlining that we
 290             // need to check for first.
 291             attr::InlineAttr::Always => true,
 292             attr::InlineAttr::Never => return false,
 293             attr::InlineAttr::Hint => true,
 294             attr::InlineAttr::None => false,
 295         };
 296
 297         // Only inline local functions if they would be eligible for cross-crate
 298         // inlining. This is to ensure that the final crate doesn't have MIR that
 299         // reference unexported symbols
 300         if callsite.callee.is_local() {
 301             if callsite.substs.types().count() == 0 && !hinted {
 302                 return false;
 303             }
 304         }
 305
 306         let mut threshold = if hinted {
 307             HINT_THRESHOLD
 308         } else {
 309             DEFAULT_THRESHOLD
 310         };
 311
 312         // Significantly lower the threshold for inlining cold functions
 313         if attr::contains_name(&attrs[..], "cold") {
 314             threshold /= 5;
 315         }
 316
 317         // Give a bonus functions with a small number of blocks,
 318         // We normally have two or three blocks for even
 319         // very small functions.
 320         if callee_mir.basic_blocks().len() <= 3 {
 321             threshold += threshold / 4;
 322         }
 323
 324         // FIXME: Give a bonus to functions with only a single caller
 325
 326         let id = tcx.hir.as_local_node_id(callsite.caller).expect("Caller not local");
 327         let param_env = ty::ParameterEnvironment::for_item(tcx, id);
 328
 329         let mut first_block = true;
 330         let mut cost = 0;
 331
 332         // Traverse the MIR manually so we can account for the effects of
 333         // inlining on the CFG.
 334         let mut work_list = vec![START_BLOCK];
 335         let mut visited = BitVector::new(callee_mir.basic_blocks().len());
 336         while let Some(bb) = work_list.pop() {
 337             if !visited.insert(bb.index()) { continue; }
 338             let blk = &callee_mir.basic_blocks()[bb];
 339
 340             for stmt in &blk.statements {
 341                 // Don't count StorageLive/StorageDead in the inlining cost.
 342                 match stmt.kind {
 343                     StatementKind::StorageLive(_) |
 344                     StatementKind::StorageDead(_) |
 345                     StatementKind::Nop => {}
 346                     _ => cost += INSTR_COST
 347                 }
 348             }
 349             let term = blk.terminator();
 350             let mut is_drop = false;
 351             match term.kind {
 352                 TerminatorKind::Drop { ref location, target, unwind } |
 353                 TerminatorKind::DropAndReplace { ref location, target, unwind, .. } => {
 354                     is_drop = true;
 355                     work_list.push(target);
 356                     // If the location doesn't actually need dropping, treat it like
 357                     // a regular goto.
 358                     let ty = location.ty(&callee_mir, tcx).subst(tcx, callsite.substs);
 359                     let ty = ty.to_ty(tcx);
 360                     if tcx.type_needs_drop_given_env(ty, &param_env) {
 361                         cost += CALL_PENALTY;
 362                         if let Some(unwind) = unwind {
 363                             work_list.push(unwind);
 364                         }
 365                     } else {
 366                         cost += INSTR_COST;
 367                     }
 368                 }
 369
 370                 TerminatorKind::Unreachable |
 371                 TerminatorKind::Call { destination: None, .. } if first_block => {
 372                     // If the function always diverges, don't inline
 373                     // unless the cost is zero
 374                     threshold = 0;
 375                 }
 376
 377                 TerminatorKind::Call {func: Operand::Constant(ref f), .. } => {
 378                     if let ty::TyFnDef(.., f) = f.ty.sty {
 379                         // Don't give intrinsics the extra penalty for calls
 380                         if f.abi() == Abi::RustIntrinsic || f.abi() == Abi::PlatformIntrinsic {
 381                             cost += INSTR_COST;
 382                         } else {
 383                             cost += CALL_PENALTY;
 384                         }
 385                     }
 386                 }
 387                 TerminatorKind::Assert { .. } => cost += CALL_PENALTY,
 388                 _ => cost += INSTR_COST
 389             }
 390
 391             if !is_drop {
 392                 for &succ in &term.successors()[..] {
 393                     work_list.push(succ);
 394                 }
 395             }
 396
 397             first_block = false;
 398         }
 399
 400         // Count up the cost of local variables and temps, if we know the size
 401         // use that, otherwise we use a moderately-large dummy cost.
 402
 403         let ptr_size = tcx.data_layout.pointer_size.bytes();
 404
 405         for v in callee_mir.vars_and_temps_iter() {
 406             let v = &callee_mir.local_decls[v];
 407             let ty = v.ty.subst(tcx, callsite.substs);
 408             // Cost of the var is the size in machine-words, if we know
 409             // it.
 410             if let Some(size) = type_size_of(tcx, param_env.clone(), ty) {
 411                 cost += (size / ptr_size) as usize;
 412             } else {
 413                 cost += UNKNOWN_SIZE_COST;
 414             }
 415         }
 416
 417         debug!("Inline cost for {:?} is {}", callsite.callee, cost);
 418
 419         if let attr::InlineAttr::Always = hint {
 420             true
 421         } else {
 422             cost <= threshold
 423         }
 424     }
 425
 426
 427     fn inline_call(&self, callsite: CallSite<'tcx>,
 428                              caller_mir: &mut Mir<'tcx>, mut callee_mir: Mir<'tcx>) -> bool {
 429
 430         // Don't inline a function into itself
 431         if callsite.caller == callsite.callee { return false; }
 432
 433         let _task = self.tcx.dep_graph.in_task(DepNode::Mir(callsite.caller));
 434
 435
 436         let terminator = caller_mir[callsite.bb].terminator.take().unwrap();
 437         match terminator.kind {
 438             // FIXME: Handle inlining of diverging calls
 439             TerminatorKind::Call { args, destination: Some(destination), cleanup, .. } => {
 440
 441                 debug!("Inlined {:?} into {:?}", callsite.callee, callsite.caller);
 442
 443                 let is_box_free = Some(callsite.callee) == self.tcx.lang_items.box_free_fn();
 444
 445                 let mut local_map = IndexVec::with_capacity(callee_mir.local_decls.len());
 446                 let mut scope_map = IndexVec::with_capacity(callee_mir.visibility_scopes.len());
 447                 let mut promoted_map = IndexVec::with_capacity(callee_mir.promoted.len());
 448
 449                 for mut scope in callee_mir.visibility_scopes.iter().cloned() {
 450                     if scope.parent_scope.is_none() {
 451                         scope.parent_scope = Some(callsite.location.scope);
 452                         scope.span = callee_mir.span;
 453                     }
 454
 455                     scope.span = callsite.location.span;
 456
 457                     let idx = caller_mir.visibility_scopes.push(scope);
 458                     scope_map.push(idx);
 459                 }
 460
 461                 for loc in callee_mir.vars_and_temps_iter() {
 462                     let mut local = callee_mir.local_decls[loc].clone();
 463
 464                     local.source_info.scope = scope_map[local.source_info.scope];
 465                     local.source_info.span = callsite.location.span;
 466
 467                     let idx = caller_mir.local_decls.push(local);
 468                     local_map.push(idx);
 469                 }
 470
 471                 for p in callee_mir.promoted.iter().cloned() {
 472                     let idx = caller_mir.promoted.push(p);
 473                     promoted_map.push(idx);
 474                 }
 475
 476                 // If the call is something like `a[*i] = f(i)`, where
 477                 // `i : &mut usize`, then just duplicating the `a[*i]`
 478                 // Lvalue could result in two different locations if `f`
 479                 // writes to `i`. To prevent this we need to create a temporary
 480                 // borrow of the lvalue and pass the destination as `*temp` instead.
 481                 fn dest_needs_borrow(lval: &Lvalue) -> bool {
 482                     match *lval {
 483                         Lvalue::Projection(ref p) => {
 484                             match p.elem {
 485                                 ProjectionElem::Deref |
 486                                 ProjectionElem::Index(_) => true,
 487                                 _ => dest_needs_borrow(&p.base)
 488                             }
 489                         }
 490                         // Static variables need a borrow because the callee
 491                         // might modify the same static.
 492                         Lvalue::Static(_) => true,
 493                         _ => false
 494                     }
 495                 }
 496
 497                 let dest = if dest_needs_borrow(&destination.0) {
 498                     debug!("Creating temp for return destination");
 499                     let dest = Rvalue::Ref(
 500                         self.tcx.mk_region(ty::ReErased),
 501                         BorrowKind::Mut,
 502                         destination.0);
 503
 504                     let ty = dest.ty(caller_mir, self.tcx);
 505
 506                     let temp = LocalDecl::new_temp(ty, callsite.location.span);
 507
 508                     let tmp = caller_mir.local_decls.push(temp);
 509                     let tmp = Lvalue::Local(tmp);
 510
 511                     let stmt = Statement {
 512                         source_info: callsite.location,
 513                         kind: StatementKind::Assign(tmp.clone(), dest)
 514                     };
 515                     caller_mir[callsite.bb]
 516                         .statements.push(stmt);
 517                     tmp.deref()
 518                 } else {
 519                     destination.0
 520                 };
 521
 522                 let return_block = destination.1;
 523
 524                 let args : Vec<_> = if is_box_free {
 525                     assert!(args.len() == 1);
 526                     // box_free takes a Box, but is defined with a *mut T, inlining
 527                     // needs to generate the cast.
 528                     // FIXME: we should probably just generate correct MIR in the first place...
 529
 530                     let arg = if let Operand::Consume(ref lval) = args[0] {
 531                         lval.clone()
 532                     } else {
 533                         bug!("Constant arg to \"box_free\"");
 534                     };
 535
 536                     let ptr_ty = args[0].ty(caller_mir, self.tcx);
 537                     vec![self.cast_box_free_arg(arg, ptr_ty, &callsite, caller_mir)]
 538                 } else {
 539                     // Copy the arguments if needed.
 540                     self.make_call_args(args, &callsite, caller_mir)
 541                 };
 542
 543                 let bb_len = caller_mir.basic_blocks().len();
 544                 let mut integrator = Integrator {
 545                     block_idx: bb_len,
 546                     args: &args,
 547                     local_map: local_map,
 548                     scope_map: scope_map,
 549                     promoted_map: promoted_map,
 550                     _callsite: callsite,
 551                     destination: dest,
 552                     return_block: return_block,
 553                     cleanup_block: cleanup,
 554                     in_cleanup_block: false
 555                 };
 556
 557
 558                 for (bb, mut block) in callee_mir.basic_blocks_mut().drain_enumerated(..) {
 559                     integrator.visit_basic_block_data(bb, &mut block);
 560                     caller_mir.basic_blocks_mut().push(block);
 561                 }
 562
 563                 let terminator = Terminator {
 564                     source_info: callsite.location,
 565                     kind: TerminatorKind::Goto { target: BasicBlock::new(bb_len) }
 566                 };
 567
 568                 caller_mir[callsite.bb].terminator = Some(terminator);
 569
 570                 true
 571             }
 572             kind => {
 573                 caller_mir[callsite.bb].terminator = Some(Terminator {
 574                     source_info: terminator.source_info,
 575                     kind: kind
 576                 });
 577                 false
 578             }
 579         }
 580     }
 581
 582     fn cast_box_free_arg(&self, arg: Lvalue<'tcx>, ptr_ty: Ty<'tcx>,
 583                          callsite: &CallSite<'tcx>, caller_mir: &mut Mir<'tcx>) -> Operand<'tcx> {
 584         let arg = Rvalue::Ref(
 585             self.tcx.mk_region(ty::ReErased),
 586             BorrowKind::Mut,
 587             arg.deref());
 588
 589         let ty = arg.ty(caller_mir, self.tcx);
 590         let ref_tmp = LocalDecl::new_temp(ty, callsite.location.span);
 591         let ref_tmp = caller_mir.local_decls.push(ref_tmp);
 592         let ref_tmp = Lvalue::Local(ref_tmp);
 593
 594         let ref_stmt = Statement {
 595             source_info: callsite.location,
 596             kind: StatementKind::Assign(ref_tmp.clone(), arg)
 597         };
 598
 599         caller_mir[callsite.bb]
 600             .statements.push(ref_stmt);
 601
 602         let pointee_ty = match ptr_ty.sty {
 603             ty::TyRawPtr(tm) | ty::TyRef(_, tm) => tm.ty,
 604             _ if ptr_ty.is_box() => ptr_ty.boxed_ty(),
 605             _ => bug!("Invalid type `{:?}` for call to box_free", ptr_ty)
 606         };
 607         let ptr_ty = self.tcx.mk_mut_ptr(pointee_ty);
 608
 609         let raw_ptr = Rvalue::Cast(CastKind::Misc, Operand::Consume(ref_tmp), ptr_ty);
 610
 611         let cast_tmp = LocalDecl::new_temp(ptr_ty, callsite.location.span);
 612         let cast_tmp = caller_mir.local_decls.push(cast_tmp);
 613         let cast_tmp = Lvalue::Local(cast_tmp);
 614
 615         let cast_stmt = Statement {
 616             source_info: callsite.location,
 617             kind: StatementKind::Assign(cast_tmp.clone(), raw_ptr)
 618         };
 619
 620         caller_mir[callsite.bb]
 621             .statements.push(cast_stmt);
 622
 623         Operand::Consume(cast_tmp)
 624     }
 625
 626     fn make_call_args(&self, args: Vec<Operand<'tcx>>,
 627                       callsite: &CallSite<'tcx>, caller_mir: &mut Mir<'tcx>) -> Vec<Operand<'tcx>> {
 628         let tcx = self.tcx;
 629         // FIXME: Analysis of the usage of the arguments to avoid
 630         // unnecessary temporaries.
 631         args.into_iter().map(|a| {
 632             if let Operand::Consume(Lvalue::Local(local)) = a {
 633                 if caller_mir.local_kind(local) == LocalKind::Temp {
 634                     // Reuse the operand if it's a temporary already
 635                     return a;
 636                 }
 637             }
 638
 639             debug!("Creating temp for argument");
 640             // Otherwise, create a temporary for the arg
 641             let arg = Rvalue::Use(a);
 642
 643             let ty = arg.ty(caller_mir, tcx);
 644
 645             let arg_tmp = LocalDecl::new_temp(ty, callsite.location.span);
 646             let arg_tmp = caller_mir.local_decls.push(arg_tmp);
 647             let arg_tmp = Lvalue::Local(arg_tmp);
 648
 649             let stmt = Statement {
 650                 source_info: callsite.location,
 651                 kind: StatementKind::Assign(arg_tmp.clone(), arg)
 652             };
 653             caller_mir[callsite.bb].statements.push(stmt);
 654             Operand::Consume(arg_tmp)
 655         }).collect()
 656     }
 657 }
 658
 659 fn type_size_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, param_env: ty::ParameterEnvironment<'tcx>,
 660                           ty: Ty<'tcx>) -> Option<u64> {
 661     tcx.infer_ctxt(param_env, traits::Reveal::All).enter(|infcx| {
 662         ty.layout(&infcx).ok().map(|layout| {
 663             layout.size(&tcx.data_layout).bytes()
 664         })
 665     })
 666 }
 667
 668 /**
 669  * Integrator.
 670  *
 671  * Integrates blocks from the callee function into the calling function.
 672  * Updates block indices, references to locals and other control flow
 673  * stuff.
 674  */
 675 struct Integrator<'a, 'tcx: 'a> {
 676     block_idx: usize,
 677     args: &'a [Operand<'tcx>],
 678     local_map: IndexVec<Local, Local>,
 679     scope_map: IndexVec<VisibilityScope, VisibilityScope>,
 680     promoted_map: IndexVec<Promoted, Promoted>,
 681     _callsite: CallSite<'tcx>,
 682     destination: Lvalue<'tcx>,
 683     return_block: BasicBlock,
 684     cleanup_block: Option<BasicBlock>,
 685     in_cleanup_block: bool,
 686 }
 687
 688 impl<'a, 'tcx> Integrator<'a, 'tcx> {
 689     fn update_target(&self, tgt: BasicBlock) -> BasicBlock {
 690         let new = BasicBlock::new(tgt.index() + self.block_idx);
 691         debug!("Updating target `{:?}`, new: `{:?}`", tgt, new);
 692         new
 693     }
 694
 695     fn update_local(&self, local: Local) -> Option<Local> {
 696         let idx = local.index();
 697         if idx < (self.args.len() + 1) {
 698             return None;
 699         }
 700         let idx = idx - (self.args.len() + 1);
 701         let local = Local::new(idx);
 702         self.local_map.get(local).cloned()
 703     }
 704
 705     fn arg_index(&self, arg: Local) -> Option<usize> {
 706         let idx = arg.index();
 707         if idx > 0 && idx <= self.args.len() {
 708             Some(idx - 1)
 709         } else {
 710             None
 711         }
 712     }
 713 }
 714
 715 impl<'a, 'tcx> MutVisitor<'tcx> for Integrator<'a, 'tcx> {
 716     fn visit_lvalue(&mut self,
 717                     lvalue: &mut Lvalue<'tcx>,
 718                     _ctxt: LvalueContext<'tcx>,
 719                     _location: Location) {
 720         if let Lvalue::Local(ref mut local) = *lvalue {
 721             if let Some(l) = self.update_local(*local) {
 722                 // Temp or Var; update the local reference
 723                 *local = l;
 724                 return;
 725             }
 726         }
 727         if let Lvalue::Local(local) = *lvalue {
 728             if local == RETURN_POINTER {
 729                 // Return pointer; update the lvalue itself
 730                 *lvalue = self.destination.clone();
 731             } else if local.index() < (self.args.len() + 1) {
 732                 // Argument, once again update the the lvalue itself
 733                 let idx = local.index() - 1;
 734                 if let Operand::Consume(ref lval) = self.args[idx] {
 735                     *lvalue = lval.clone();
 736                 } else {
 737                     bug!("Arg operand `{:?}` is not an Lvalue use.", idx)
 738                 }
 739             }
 740         } else {
 741             self.super_lvalue(lvalue, _ctxt, _location)
 742         }
 743     }
 744
 745     fn visit_operand(&mut self, operand: &mut Operand<'tcx>, location: Location) {
 746         if let Operand::Consume(Lvalue::Local(arg)) = *operand {
 747             if let Some(idx) = self.arg_index(arg) {
 748                 let new_arg = self.args[idx].clone();
 749                 *operand = new_arg;
 750                 return;
 751             }
 752         }
 753         self.super_operand(operand, location);
 754     }
 755
 756     fn visit_basic_block_data(&mut self, block: BasicBlock, data: &mut BasicBlockData<'tcx>) {
 757         self.in_cleanup_block = data.is_cleanup;
 758         self.super_basic_block_data(block, data);
 759         self.in_cleanup_block = false;
 760     }
 761
 762     fn visit_terminator_kind(&mut self, block: BasicBlock,
 763                              kind: &mut TerminatorKind<'tcx>, loc: Location) {
 764         self.super_terminator_kind(block, kind, loc);
 765
 766         match *kind {
 767             TerminatorKind::Goto { ref mut target} => {
 768                 *target = self.update_target(*target);
 769             }
 770             TerminatorKind::SwitchInt { ref mut targets, .. } => {
 771                 for tgt in targets {
 772                     *tgt = self.update_target(*tgt);
 773                 }
 774             }
 775             TerminatorKind::Drop { ref mut target, ref mut unwind, .. } |
 776             TerminatorKind::DropAndReplace { ref mut target, ref mut unwind, .. } => {
 777                 *target = self.update_target(*target);
 778                 if let Some(tgt) = *unwind {
 779                     *unwind = Some(self.update_target(tgt));
 780                 } else if !self.in_cleanup_block {
 781                     // Unless this drop is in a cleanup block, add an unwind edge to
 782                     // the orignal call's cleanup block
 783                     *unwind = self.cleanup_block;
 784                 }
 785             }
 786             TerminatorKind::Call { ref mut destination, ref mut cleanup, .. } => {
 787                 if let Some((_, ref mut tgt)) = *destination {
 788                     *tgt = self.update_target(*tgt);
 789                 }
 790                 if let Some(tgt) = *cleanup {
 791                     *cleanup = Some(self.update_target(tgt));
 792                 } else if !self.in_cleanup_block {
 793                     // Unless this call is in a cleanup block, add an unwind edge to
 794                     // the orignal call's cleanup block
 795                     *cleanup = self.cleanup_block;
 796                 }
 797             }
 798             TerminatorKind::Assert { ref mut target, ref mut cleanup, .. } => {
 799                 *target = self.update_target(*target);
 800                 if let Some(tgt) = *cleanup {
 801                     *cleanup = Some(self.update_target(tgt));
 802                 } else if !self.in_cleanup_block {
 803                     // Unless this assert is in a cleanup block, add an unwind edge to
 804                     // the orignal call's cleanup block
 805                     *cleanup = self.cleanup_block;
 806                 }
 807             }
 808             TerminatorKind::Return => {
 809                 *kind = TerminatorKind::Goto { target: self.return_block };
 810             }
 811             TerminatorKind::Resume => {
 812                 if let Some(tgt) = self.cleanup_block {
 813                     *kind = TerminatorKind::Goto { target: tgt }
 814                 }
 815             }
 816             TerminatorKind::Unreachable => { }
 817         }
 818     }
 819
 820     fn visit_visibility_scope(&mut self, scope: &mut VisibilityScope) {
 821         *scope = self.scope_map[*scope];
 822     }
 823
 824     fn visit_literal(&mut self, literal: &mut Literal<'tcx>, loc: Location) {
 825         if let Literal::Promoted { ref mut index } = *literal {
 826             if let Some(p) = self.promoted_map.get(*index).cloned() {
 827                 *index = p;
 828             }
 829         } else {
 830             self.super_literal(literal, loc);
 831         }
 832     }
 833 }