src/librustc_mir/transform/inline.rs

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