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.
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.
11 //! Inlining pass for MIR functions
13 use rustc::hir::def_id::DefId;
15 use rustc_data_structures::bitvec::BitVector;
16 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
19 use rustc::mir::transform::{MirPass, MirSource};
20 use rustc::mir::visit::*;
22 use rustc::ty::{self, Ty, TyCtxt};
23 use rustc::ty::subst::{Subst,Substs};
25 use std::collections::VecDeque;
26 use super::simplify::{remove_dead_blocks, CfgSimplifier};
31 const DEFAULT_THRESHOLD: usize = 50;
32 const HINT_THRESHOLD: usize = 100;
34 const INSTR_COST: usize = 5;
35 const CALL_PENALTY: usize = 25;
37 const UNKNOWN_SIZE_COST: usize = 10;
41 #[derive(Copy, Clone)]
42 struct CallSite<'tcx> {
44 substs: &'tcx Substs<'tcx>,
49 impl MirPass for Inline {
50 fn run_pass<'a, 'tcx>(&self,
51 tcx: TyCtxt<'a, 'tcx, 'tcx>,
53 mir: &mut Mir<'tcx>) {
54 if tcx.sess.opts.debugging_opts.mir_opt_level >= 2 {
55 Inliner { tcx, source }.run_pass(mir);
60 struct Inliner<'a, 'tcx: 'a> {
61 tcx: TyCtxt<'a, 'tcx, 'tcx>,
65 impl<'a, 'tcx> Inliner<'a, 'tcx> {
66 fn run_pass(&self, caller_mir: &mut Mir<'tcx>) {
67 // Keep a queue of callsites to try inlining on. We take
68 // advantage of the fact that queries detect cycles here to
69 // allow us to try and fetch the fully optimized MIR of a
70 // call; if it succeeds, we can inline it and we know that
71 // they do not call us. Otherwise, we just don't try to
74 // We use a queue so that we inline "broadly" before we inline
75 // in depth. It is unclear if this is the current heuristic.
77 let mut callsites = VecDeque::new();
79 // Only do inlining into fn bodies.
80 if let MirSource::Fn(_) = self.source {
81 for (bb, bb_data) in caller_mir.basic_blocks().iter_enumerated() {
82 // Don't inline calls that are in cleanup blocks.
83 if bb_data.is_cleanup { continue; }
85 // Only consider direct calls to functions
86 let terminator = bb_data.terminator();
87 if let TerminatorKind::Call {
88 func: Operand::Constant(ref f), .. } = terminator.kind {
89 if let ty::TyFnDef(callee_def_id, substs, _) = f.ty.sty {
90 callsites.push_back(CallSite {
91 callee: callee_def_id,
94 location: terminator.source_info
101 let mut local_change;
102 let mut changed = false;
105 local_change = false;
106 while let Some(callsite) = callsites.pop_front() {
107 if !self.tcx.is_item_mir_available(callsite.callee) {
111 let callee_mir = match ty::queries::optimized_mir::try_get(self.tcx,
112 callsite.location.span,
114 Ok(ref callee_mir) if self.should_inline(callsite, callee_mir) => {
115 callee_mir.subst(self.tcx, callsite.substs)
121 let start = caller_mir.basic_blocks().len();
123 if !self.inline_call(callsite, caller_mir, callee_mir) {
127 // Add callsites from inlined function
128 for (bb, bb_data) in caller_mir.basic_blocks().iter_enumerated().skip(start) {
129 // Only consider direct calls to functions
130 let terminator = bb_data.terminator();
131 if let TerminatorKind::Call {
132 func: Operand::Constant(ref f), .. } = terminator.kind {
133 if let ty::TyFnDef(callee_def_id, substs, _) = f.ty.sty {
134 // Don't inline the same function multiple times.
135 if callsite.callee != callee_def_id {
136 callsites.push_back(CallSite {
137 callee: callee_def_id,
140 location: terminator.source_info
156 // Simplify if we inlined anything.
158 debug!("Running simplify cfg on {:?}", self.source);
159 CfgSimplifier::new(caller_mir).simplify();
160 remove_dead_blocks(caller_mir);
164 fn should_inline(&self,
165 callsite: CallSite<'tcx>,
166 callee_mir: &Mir<'tcx>)
171 // Don't inline closures that have captures
172 // FIXME: Handle closures better
173 if callee_mir.upvar_decls.len() > 0 {
178 let attrs = tcx.get_attrs(callsite.callee);
179 let hint = attr::find_inline_attr(None, &attrs[..]);
181 let hinted = match hint {
182 // Just treat inline(always) as a hint for now,
183 // there are cases that prevent inlining that we
184 // need to check for first.
185 attr::InlineAttr::Always => true,
186 attr::InlineAttr::Never => return false,
187 attr::InlineAttr::Hint => true,
188 attr::InlineAttr::None => false,
191 // Only inline local functions if they would be eligible for cross-crate
192 // inlining. This is to ensure that the final crate doesn't have MIR that
193 // reference unexported symbols
194 if callsite.callee.is_local() {
195 if callsite.substs.types().count() == 0 && !hinted {
200 let mut threshold = if hinted {
206 // Significantly lower the threshold for inlining cold functions
207 if attr::contains_name(&attrs[..], "cold") {
211 // Give a bonus functions with a small number of blocks,
212 // We normally have two or three blocks for even
213 // very small functions.
214 if callee_mir.basic_blocks().len() <= 3 {
215 threshold += threshold / 4;
218 // FIXME: Give a bonus to functions with only a single caller
220 let param_env = ty::ParameterEnvironment::for_item(tcx, self.source.item_id());
222 let mut first_block = true;
225 // Traverse the MIR manually so we can account for the effects of
226 // inlining on the CFG.
227 let mut work_list = vec![START_BLOCK];
228 let mut visited = BitVector::new(callee_mir.basic_blocks().len());
229 while let Some(bb) = work_list.pop() {
230 if !visited.insert(bb.index()) { continue; }
231 let blk = &callee_mir.basic_blocks()[bb];
233 for stmt in &blk.statements {
234 // Don't count StorageLive/StorageDead in the inlining cost.
236 StatementKind::StorageLive(_) |
237 StatementKind::StorageDead(_) |
238 StatementKind::Nop => {}
239 _ => cost += INSTR_COST
242 let term = blk.terminator();
243 let mut is_drop = false;
245 TerminatorKind::Drop { ref location, target, unwind } |
246 TerminatorKind::DropAndReplace { ref location, target, unwind, .. } => {
248 work_list.push(target);
249 // If the location doesn't actually need dropping, treat it like
251 let ty = location.ty(&callee_mir, tcx).subst(tcx, callsite.substs);
252 let ty = ty.to_ty(tcx);
253 if ty.needs_drop(tcx, ¶m_env) {
254 cost += CALL_PENALTY;
255 if let Some(unwind) = unwind {
256 work_list.push(unwind);
263 TerminatorKind::Unreachable |
264 TerminatorKind::Call { destination: None, .. } if first_block => {
265 // If the function always diverges, don't inline
266 // unless the cost is zero
270 TerminatorKind::Call {func: Operand::Constant(ref f), .. } => {
271 if let ty::TyFnDef(.., f) = f.ty.sty {
272 // Don't give intrinsics the extra penalty for calls
273 if f.abi() == Abi::RustIntrinsic || f.abi() == Abi::PlatformIntrinsic {
276 cost += CALL_PENALTY;
280 TerminatorKind::Assert { .. } => cost += CALL_PENALTY,
281 _ => cost += INSTR_COST
285 for &succ in &term.successors()[..] {
286 work_list.push(succ);
293 // Count up the cost of local variables and temps, if we know the size
294 // use that, otherwise we use a moderately-large dummy cost.
296 let ptr_size = tcx.data_layout.pointer_size.bytes();
298 for v in callee_mir.vars_and_temps_iter() {
299 let v = &callee_mir.local_decls[v];
300 let ty = v.ty.subst(tcx, callsite.substs);
301 // Cost of the var is the size in machine-words, if we know
303 if let Some(size) = type_size_of(tcx, param_env.clone(), ty) {
304 cost += (size / ptr_size) as usize;
306 cost += UNKNOWN_SIZE_COST;
310 debug!("Inline cost for {:?} is {}", callsite.callee, cost);
312 if let attr::InlineAttr::Always = hint {
319 fn inline_call(&self,
320 callsite: CallSite<'tcx>,
321 caller_mir: &mut Mir<'tcx>,
322 mut callee_mir: Mir<'tcx>) -> bool {
323 let terminator = caller_mir[callsite.bb].terminator.take().unwrap();
324 match terminator.kind {
325 // FIXME: Handle inlining of diverging calls
326 TerminatorKind::Call { args, destination: Some(destination), cleanup, .. } => {
327 debug!("Inlined {:?} into {:?}", callsite.callee, self.source);
329 let is_box_free = Some(callsite.callee) == self.tcx.lang_items.box_free_fn();
331 let mut local_map = IndexVec::with_capacity(callee_mir.local_decls.len());
332 let mut scope_map = IndexVec::with_capacity(callee_mir.visibility_scopes.len());
333 let mut promoted_map = IndexVec::with_capacity(callee_mir.promoted.len());
335 for mut scope in callee_mir.visibility_scopes.iter().cloned() {
336 if scope.parent_scope.is_none() {
337 scope.parent_scope = Some(callsite.location.scope);
338 scope.span = callee_mir.span;
341 scope.span = callsite.location.span;
343 let idx = caller_mir.visibility_scopes.push(scope);
347 for loc in callee_mir.vars_and_temps_iter() {
348 let mut local = callee_mir.local_decls[loc].clone();
350 local.source_info.scope = scope_map[local.source_info.scope];
351 local.source_info.span = callsite.location.span;
353 let idx = caller_mir.local_decls.push(local);
357 for p in callee_mir.promoted.iter().cloned() {
358 let idx = caller_mir.promoted.push(p);
359 promoted_map.push(idx);
362 // If the call is something like `a[*i] = f(i)`, where
363 // `i : &mut usize`, then just duplicating the `a[*i]`
364 // Lvalue could result in two different locations if `f`
365 // writes to `i`. To prevent this we need to create a temporary
366 // borrow of the lvalue and pass the destination as `*temp` instead.
367 fn dest_needs_borrow(lval: &Lvalue) -> bool {
369 Lvalue::Projection(ref p) => {
371 ProjectionElem::Deref |
372 ProjectionElem::Index(_) => true,
373 _ => dest_needs_borrow(&p.base)
376 // Static variables need a borrow because the callee
377 // might modify the same static.
378 Lvalue::Static(_) => true,
383 let dest = if dest_needs_borrow(&destination.0) {
384 debug!("Creating temp for return destination");
385 let dest = Rvalue::Ref(
386 self.tcx.types.re_erased,
390 let ty = dest.ty(caller_mir, self.tcx);
392 let temp = LocalDecl::new_temp(ty, callsite.location.span);
394 let tmp = caller_mir.local_decls.push(temp);
395 let tmp = Lvalue::Local(tmp);
397 let stmt = Statement {
398 source_info: callsite.location,
399 kind: StatementKind::Assign(tmp.clone(), dest)
401 caller_mir[callsite.bb]
402 .statements.push(stmt);
408 let return_block = destination.1;
410 let args : Vec<_> = if is_box_free {
411 assert!(args.len() == 1);
412 // box_free takes a Box, but is defined with a *mut T, inlining
413 // needs to generate the cast.
414 // FIXME: we should probably just generate correct MIR in the first place...
416 let arg = if let Operand::Consume(ref lval) = args[0] {
419 bug!("Constant arg to \"box_free\"");
422 let ptr_ty = args[0].ty(caller_mir, self.tcx);
423 vec![self.cast_box_free_arg(arg, ptr_ty, &callsite, caller_mir)]
425 // Copy the arguments if needed.
426 self.make_call_args(args, &callsite, caller_mir)
429 let bb_len = caller_mir.basic_blocks().len();
430 let mut integrator = Integrator {
433 local_map: local_map,
434 scope_map: scope_map,
435 promoted_map: promoted_map,
438 return_block: return_block,
439 cleanup_block: cleanup,
440 in_cleanup_block: false
444 for (bb, mut block) in callee_mir.basic_blocks_mut().drain_enumerated(..) {
445 integrator.visit_basic_block_data(bb, &mut block);
446 caller_mir.basic_blocks_mut().push(block);
449 let terminator = Terminator {
450 source_info: callsite.location,
451 kind: TerminatorKind::Goto { target: BasicBlock::new(bb_len) }
454 caller_mir[callsite.bb].terminator = Some(terminator);
459 caller_mir[callsite.bb].terminator = Some(Terminator {
460 source_info: terminator.source_info,
468 fn cast_box_free_arg(&self, arg: Lvalue<'tcx>, ptr_ty: Ty<'tcx>,
469 callsite: &CallSite<'tcx>, caller_mir: &mut Mir<'tcx>) -> Operand<'tcx> {
470 let arg = Rvalue::Ref(
471 self.tcx.types.re_erased,
475 let ty = arg.ty(caller_mir, self.tcx);
476 let ref_tmp = LocalDecl::new_temp(ty, callsite.location.span);
477 let ref_tmp = caller_mir.local_decls.push(ref_tmp);
478 let ref_tmp = Lvalue::Local(ref_tmp);
480 let ref_stmt = Statement {
481 source_info: callsite.location,
482 kind: StatementKind::Assign(ref_tmp.clone(), arg)
485 caller_mir[callsite.bb]
486 .statements.push(ref_stmt);
488 let pointee_ty = match ptr_ty.sty {
489 ty::TyRawPtr(tm) | ty::TyRef(_, tm) => tm.ty,
490 _ if ptr_ty.is_box() => ptr_ty.boxed_ty(),
491 _ => bug!("Invalid type `{:?}` for call to box_free", ptr_ty)
493 let ptr_ty = self.tcx.mk_mut_ptr(pointee_ty);
495 let raw_ptr = Rvalue::Cast(CastKind::Misc, Operand::Consume(ref_tmp), ptr_ty);
497 let cast_tmp = LocalDecl::new_temp(ptr_ty, callsite.location.span);
498 let cast_tmp = caller_mir.local_decls.push(cast_tmp);
499 let cast_tmp = Lvalue::Local(cast_tmp);
501 let cast_stmt = Statement {
502 source_info: callsite.location,
503 kind: StatementKind::Assign(cast_tmp.clone(), raw_ptr)
506 caller_mir[callsite.bb]
507 .statements.push(cast_stmt);
509 Operand::Consume(cast_tmp)
512 fn make_call_args(&self, args: Vec<Operand<'tcx>>,
513 callsite: &CallSite<'tcx>, caller_mir: &mut Mir<'tcx>) -> Vec<Operand<'tcx>> {
515 // FIXME: Analysis of the usage of the arguments to avoid
516 // unnecessary temporaries.
517 args.into_iter().map(|a| {
518 if let Operand::Consume(Lvalue::Local(local)) = a {
519 if caller_mir.local_kind(local) == LocalKind::Temp {
520 // Reuse the operand if it's a temporary already
525 debug!("Creating temp for argument");
526 // Otherwise, create a temporary for the arg
527 let arg = Rvalue::Use(a);
529 let ty = arg.ty(caller_mir, tcx);
531 let arg_tmp = LocalDecl::new_temp(ty, callsite.location.span);
532 let arg_tmp = caller_mir.local_decls.push(arg_tmp);
533 let arg_tmp = Lvalue::Local(arg_tmp);
535 let stmt = Statement {
536 source_info: callsite.location,
537 kind: StatementKind::Assign(arg_tmp.clone(), arg)
539 caller_mir[callsite.bb].statements.push(stmt);
540 Operand::Consume(arg_tmp)
545 fn type_size_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, param_env: ty::ParameterEnvironment<'tcx>,
546 ty: Ty<'tcx>) -> Option<u64> {
547 tcx.infer_ctxt(param_env, traits::Reveal::All).enter(|infcx| {
548 ty.layout(&infcx).ok().map(|layout| {
549 layout.size(&tcx.data_layout).bytes()
557 * Integrates blocks from the callee function into the calling function.
558 * Updates block indices, references to locals and other control flow
561 struct Integrator<'a, 'tcx: 'a> {
563 args: &'a [Operand<'tcx>],
564 local_map: IndexVec<Local, Local>,
565 scope_map: IndexVec<VisibilityScope, VisibilityScope>,
566 promoted_map: IndexVec<Promoted, Promoted>,
567 _callsite: CallSite<'tcx>,
568 destination: Lvalue<'tcx>,
569 return_block: BasicBlock,
570 cleanup_block: Option<BasicBlock>,
571 in_cleanup_block: bool,
574 impl<'a, 'tcx> Integrator<'a, 'tcx> {
575 fn update_target(&self, tgt: BasicBlock) -> BasicBlock {
576 let new = BasicBlock::new(tgt.index() + self.block_idx);
577 debug!("Updating target `{:?}`, new: `{:?}`", tgt, new);
581 fn update_local(&self, local: Local) -> Option<Local> {
582 let idx = local.index();
583 if idx < (self.args.len() + 1) {
586 let idx = idx - (self.args.len() + 1);
587 let local = Local::new(idx);
588 self.local_map.get(local).cloned()
591 fn arg_index(&self, arg: Local) -> Option<usize> {
592 let idx = arg.index();
593 if idx > 0 && idx <= self.args.len() {
601 impl<'a, 'tcx> MutVisitor<'tcx> for Integrator<'a, 'tcx> {
602 fn visit_lvalue(&mut self,
603 lvalue: &mut Lvalue<'tcx>,
604 _ctxt: LvalueContext<'tcx>,
605 _location: Location) {
606 if let Lvalue::Local(ref mut local) = *lvalue {
607 if let Some(l) = self.update_local(*local) {
608 // Temp or Var; update the local reference
613 if let Lvalue::Local(local) = *lvalue {
614 if local == RETURN_POINTER {
615 // Return pointer; update the lvalue itself
616 *lvalue = self.destination.clone();
617 } else if local.index() < (self.args.len() + 1) {
618 // Argument, once again update the the lvalue itself
619 let idx = local.index() - 1;
620 if let Operand::Consume(ref lval) = self.args[idx] {
621 *lvalue = lval.clone();
623 bug!("Arg operand `{:?}` is not an Lvalue use.", idx)
627 self.super_lvalue(lvalue, _ctxt, _location)
631 fn visit_operand(&mut self, operand: &mut Operand<'tcx>, location: Location) {
632 if let Operand::Consume(Lvalue::Local(arg)) = *operand {
633 if let Some(idx) = self.arg_index(arg) {
634 let new_arg = self.args[idx].clone();
639 self.super_operand(operand, location);
642 fn visit_basic_block_data(&mut self, block: BasicBlock, data: &mut BasicBlockData<'tcx>) {
643 self.in_cleanup_block = data.is_cleanup;
644 self.super_basic_block_data(block, data);
645 self.in_cleanup_block = false;
648 fn visit_terminator_kind(&mut self, block: BasicBlock,
649 kind: &mut TerminatorKind<'tcx>, loc: Location) {
650 self.super_terminator_kind(block, kind, loc);
653 TerminatorKind::Goto { ref mut target} => {
654 *target = self.update_target(*target);
656 TerminatorKind::SwitchInt { ref mut targets, .. } => {
658 *tgt = self.update_target(*tgt);
661 TerminatorKind::Drop { ref mut target, ref mut unwind, .. } |
662 TerminatorKind::DropAndReplace { ref mut target, ref mut unwind, .. } => {
663 *target = self.update_target(*target);
664 if let Some(tgt) = *unwind {
665 *unwind = Some(self.update_target(tgt));
666 } else if !self.in_cleanup_block {
667 // Unless this drop is in a cleanup block, add an unwind edge to
668 // the orignal call's cleanup block
669 *unwind = self.cleanup_block;
672 TerminatorKind::Call { ref mut destination, ref mut cleanup, .. } => {
673 if let Some((_, ref mut tgt)) = *destination {
674 *tgt = self.update_target(*tgt);
676 if let Some(tgt) = *cleanup {
677 *cleanup = Some(self.update_target(tgt));
678 } else if !self.in_cleanup_block {
679 // Unless this call is in a cleanup block, add an unwind edge to
680 // the orignal call's cleanup block
681 *cleanup = self.cleanup_block;
684 TerminatorKind::Assert { ref mut target, ref mut cleanup, .. } => {
685 *target = self.update_target(*target);
686 if let Some(tgt) = *cleanup {
687 *cleanup = Some(self.update_target(tgt));
688 } else if !self.in_cleanup_block {
689 // Unless this assert is in a cleanup block, add an unwind edge to
690 // the orignal call's cleanup block
691 *cleanup = self.cleanup_block;
694 TerminatorKind::Return => {
695 *kind = TerminatorKind::Goto { target: self.return_block };
697 TerminatorKind::Resume => {
698 if let Some(tgt) = self.cleanup_block {
699 *kind = TerminatorKind::Goto { target: tgt }
702 TerminatorKind::Unreachable => { }
706 fn visit_visibility_scope(&mut self, scope: &mut VisibilityScope) {
707 *scope = self.scope_map[*scope];
710 fn visit_literal(&mut self, literal: &mut Literal<'tcx>, loc: Location) {
711 if let Literal::Promoted { ref mut index } = *literal {
712 if let Some(p) = self.promoted_map.get(*index).cloned() {
716 self.super_literal(literal, loc);