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