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};
17 use rustc_data_structures::graph;
19 use rustc::dep_graph::DepNode;
21 use rustc::mir::transform::{MirMapPass, MirPassHook, MirSource, Pass};
22 use rustc::mir::visit::*;
24 use rustc::ty::{self, Ty, TyCtxt};
25 use rustc::ty::subst::{Subst,Substs};
26 use rustc::util::nodemap::{DefIdSet};
28 use super::simplify::{remove_dead_blocks, CfgSimplifier};
35 const DEFAULT_THRESHOLD: usize = 50;
36 const HINT_THRESHOLD: usize = 100;
38 const INSTR_COST: usize = 5;
39 const CALL_PENALTY: usize = 25;
41 const UNKNOWN_SIZE_COST: usize = 10;
45 impl<'tcx> MirMapPass<'tcx> for Inline {
48 tcx: TyCtxt<'a, 'tcx, 'tcx>,
49 hooks: &mut [Box<for<'s> MirPassHook<'s>>]) {
51 if tcx.sess.opts.debugging_opts.mir_opt_level < 2 { return; }
53 let _ignore = tcx.dep_graph.in_ignore();
55 let callgraph = callgraph::CallGraph::build(tcx);
57 let mut inliner = Inliner {
61 let def_ids = tcx.maps.mir.borrow().keys();
62 for &def_id in &def_ids {
63 if !def_id.is_local() { continue; }
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) {
72 tcx.dep_graph.write(DepNode::Mir(def_id));
74 let id = tcx.hir.as_local_node_id(def_id).unwrap();
75 let src = MirSource::from_node(tcx, id);
77 for hook in &mut *hooks {
78 hook.on_mir_pass(tcx, src, &mut mir, self, false);
82 for scc in callgraph.scc_iter() {
83 inliner.inline_scc(&callgraph, &scc);
86 for def_id in def_ids {
87 if !def_id.is_local() { continue; }
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));
93 let id = tcx.hir.as_local_node_id(def_id).unwrap();
94 let src = MirSource::from_node(tcx, id);
96 for hook in &mut *hooks {
97 hook.on_mir_pass(tcx, src, &mut mir, self, true);
103 impl<'tcx> Pass for Inline { }
105 struct Inliner<'a, 'tcx: 'a> {
106 tcx: TyCtxt<'a, 'tcx, 'tcx>,
109 #[derive(Copy, Clone)]
110 struct CallSite<'tcx> {
113 substs: &'tcx Substs<'tcx>,
115 location: SourceInfo,
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();
123 let mut inlined_into = DefIdSet();
126 let def_id = callgraph.def_id(node);
128 // Don't inspect functions from other crates
129 let id = if let Some(id) = self.tcx.hir.as_local_node_id(def_id) {
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; }
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 {
148 callee: callee_def_id,
151 location: terminator.source_info
157 in_scc.insert(def_id);
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();
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);
177 let mut local_change;
178 let mut changed = false;
181 local_change = false;
183 while csi < callsites.len() {
184 let callsite = callsites[csi];
187 let _task = self.tcx.dep_graph.in_task(DepNode::Mir(callsite.caller));
188 self.tcx.dep_graph.write(DepNode::Mir(callsite.caller));
191 if let Some(callee_mir) = self.tcx.maybe_item_mir(callsite.callee) {
192 if !self.should_inline(callsite, &callee_mir) {
196 callee_mir.subst(self.tcx, callsite.substs)
203 let mut caller_mir = {
204 let map = self.tcx.maps.mir.borrow();
205 let mir = map.get(&callsite.caller).unwrap();
209 let start = caller_mir.basic_blocks().len();
211 if !self.inline_call(callsite, &mut caller_mir, callee_mir) {
215 inlined_into.insert(callsite.caller);
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,
231 location: terminator.source_info
240 callsites.swap_remove(csi);
242 callsites.remove(csi);
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));
259 let mut caller_mir = {
260 let map = self.tcx.maps.mir.borrow();
261 let mir = map.get(&def_id).unwrap();
265 debug!("Running simplify cfg on {:?}", def_id);
266 CfgSimplifier::new(&mut caller_mir).simplify();
267 remove_dead_blocks(&mut caller_mir);
272 fn should_inline(&self, callsite: CallSite<'tcx>,
273 callee_mir: &'a Mir<'tcx>) -> bool {
277 // Don't inline closures that have captures
278 // FIXME: Handle closures better
279 if callee_mir.upvar_decls.len() > 0 {
284 let attrs = tcx.get_attrs(callsite.callee);
285 let hint = attr::find_inline_attr(None, &attrs[..]);
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,
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 {
306 let mut threshold = if hinted {
312 // Significantly lower the threshold for inlining cold functions
313 if attr::contains_name(&attrs[..], "cold") {
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;
324 // FIXME: Give a bonus to functions with only a single caller
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);
329 let mut first_block = true;
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];
340 for stmt in &blk.statements {
341 // Don't count StorageLive/StorageDead in the inlining cost.
343 StatementKind::StorageLive(_) |
344 StatementKind::StorageDead(_) |
345 StatementKind::Nop => {}
346 _ => cost += INSTR_COST
349 let term = blk.terminator();
350 let mut is_drop = false;
352 TerminatorKind::Drop { ref location, target, unwind } |
353 TerminatorKind::DropAndReplace { ref location, target, unwind, .. } => {
355 work_list.push(target);
356 // If the location doesn't actually need dropping, treat it like
358 let ty = location.ty(&callee_mir, tcx).subst(tcx, callsite.substs);
359 let ty = ty.to_ty(tcx);
360 if ty.needs_drop(tcx, ¶m_env) {
361 cost += CALL_PENALTY;
362 if let Some(unwind) = unwind {
363 work_list.push(unwind);
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
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 {
383 cost += CALL_PENALTY;
387 TerminatorKind::Assert { .. } => cost += CALL_PENALTY,
388 _ => cost += INSTR_COST
392 for &succ in &term.successors()[..] {
393 work_list.push(succ);
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.
403 let ptr_size = tcx.data_layout.pointer_size.bytes();
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
410 if let Some(size) = type_size_of(tcx, param_env.clone(), ty) {
411 cost += (size / ptr_size) as usize;
413 cost += UNKNOWN_SIZE_COST;
417 debug!("Inline cost for {:?} is {}", callsite.callee, cost);
419 if let attr::InlineAttr::Always = hint {
427 fn inline_call(&self, callsite: CallSite<'tcx>,
428 caller_mir: &mut Mir<'tcx>, mut callee_mir: Mir<'tcx>) -> bool {
430 // Don't inline a function into itself
431 if callsite.caller == callsite.callee { return false; }
433 let _task = self.tcx.dep_graph.in_task(DepNode::Mir(callsite.caller));
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, .. } => {
441 debug!("Inlined {:?} into {:?}", callsite.callee, callsite.caller);
443 let is_box_free = Some(callsite.callee) == self.tcx.lang_items.box_free_fn();
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());
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;
455 scope.span = callsite.location.span;
457 let idx = caller_mir.visibility_scopes.push(scope);
461 for loc in callee_mir.vars_and_temps_iter() {
462 let mut local = callee_mir.local_decls[loc].clone();
464 local.source_info.scope = scope_map[local.source_info.scope];
465 local.source_info.span = callsite.location.span;
467 let idx = caller_mir.local_decls.push(local);
471 for p in callee_mir.promoted.iter().cloned() {
472 let idx = caller_mir.promoted.push(p);
473 promoted_map.push(idx);
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 {
483 Lvalue::Projection(ref p) => {
485 ProjectionElem::Deref |
486 ProjectionElem::Index(_) => true,
487 _ => dest_needs_borrow(&p.base)
490 // Static variables need a borrow because the callee
491 // might modify the same static.
492 Lvalue::Static(_) => true,
497 let dest = if dest_needs_borrow(&destination.0) {
498 debug!("Creating temp for return destination");
499 let dest = Rvalue::Ref(
500 self.tcx.types.re_erased,
504 let ty = dest.ty(caller_mir, self.tcx);
506 let temp = LocalDecl::new_temp(ty, callsite.location.span);
508 let tmp = caller_mir.local_decls.push(temp);
509 let tmp = Lvalue::Local(tmp);
511 let stmt = Statement {
512 source_info: callsite.location,
513 kind: StatementKind::Assign(tmp.clone(), dest)
515 caller_mir[callsite.bb]
516 .statements.push(stmt);
522 let return_block = destination.1;
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...
530 let arg = if let Operand::Consume(ref lval) = args[0] {
533 bug!("Constant arg to \"box_free\"");
536 let ptr_ty = args[0].ty(caller_mir, self.tcx);
537 vec![self.cast_box_free_arg(arg, ptr_ty, &callsite, caller_mir)]
539 // Copy the arguments if needed.
540 self.make_call_args(args, &callsite, caller_mir)
543 let bb_len = caller_mir.basic_blocks().len();
544 let mut integrator = Integrator {
547 local_map: local_map,
548 scope_map: scope_map,
549 promoted_map: promoted_map,
552 return_block: return_block,
553 cleanup_block: cleanup,
554 in_cleanup_block: false
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);
563 let terminator = Terminator {
564 source_info: callsite.location,
565 kind: TerminatorKind::Goto { target: BasicBlock::new(bb_len) }
568 caller_mir[callsite.bb].terminator = Some(terminator);
573 caller_mir[callsite.bb].terminator = Some(Terminator {
574 source_info: terminator.source_info,
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.types.re_erased,
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);
594 let ref_stmt = Statement {
595 source_info: callsite.location,
596 kind: StatementKind::Assign(ref_tmp.clone(), arg)
599 caller_mir[callsite.bb]
600 .statements.push(ref_stmt);
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)
607 let ptr_ty = self.tcx.mk_mut_ptr(pointee_ty);
609 let raw_ptr = Rvalue::Cast(CastKind::Misc, Operand::Consume(ref_tmp), ptr_ty);
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);
615 let cast_stmt = Statement {
616 source_info: callsite.location,
617 kind: StatementKind::Assign(cast_tmp.clone(), raw_ptr)
620 caller_mir[callsite.bb]
621 .statements.push(cast_stmt);
623 Operand::Consume(cast_tmp)
626 fn make_call_args(&self, args: Vec<Operand<'tcx>>,
627 callsite: &CallSite<'tcx>, caller_mir: &mut Mir<'tcx>) -> Vec<Operand<'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
639 debug!("Creating temp for argument");
640 // Otherwise, create a temporary for the arg
641 let arg = Rvalue::Use(a);
643 let ty = arg.ty(caller_mir, tcx);
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);
649 let stmt = Statement {
650 source_info: callsite.location,
651 kind: StatementKind::Assign(arg_tmp.clone(), arg)
653 caller_mir[callsite.bb].statements.push(stmt);
654 Operand::Consume(arg_tmp)
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()
671 * Integrates blocks from the callee function into the calling function.
672 * Updates block indices, references to locals and other control flow
675 struct Integrator<'a, 'tcx: 'a> {
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,
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);
695 fn update_local(&self, local: Local) -> Option<Local> {
696 let idx = local.index();
697 if idx < (self.args.len() + 1) {
700 let idx = idx - (self.args.len() + 1);
701 let local = Local::new(idx);
702 self.local_map.get(local).cloned()
705 fn arg_index(&self, arg: Local) -> Option<usize> {
706 let idx = arg.index();
707 if idx > 0 && idx <= self.args.len() {
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
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();
737 bug!("Arg operand `{:?}` is not an Lvalue use.", idx)
741 self.super_lvalue(lvalue, _ctxt, _location)
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();
753 self.super_operand(operand, location);
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;
762 fn visit_terminator_kind(&mut self, block: BasicBlock,
763 kind: &mut TerminatorKind<'tcx>, loc: Location) {
764 self.super_terminator_kind(block, kind, loc);
767 TerminatorKind::Goto { ref mut target} => {
768 *target = self.update_target(*target);
770 TerminatorKind::SwitchInt { ref mut targets, .. } => {
772 *tgt = self.update_target(*tgt);
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;
786 TerminatorKind::Call { ref mut destination, ref mut cleanup, .. } => {
787 if let Some((_, ref mut tgt)) = *destination {
788 *tgt = self.update_target(*tgt);
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;
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;
808 TerminatorKind::Return => {
809 *kind = TerminatorKind::Goto { target: self.return_block };
811 TerminatorKind::Resume => {
812 if let Some(tgt) = self.cleanup_block {
813 *kind = TerminatorKind::Goto { target: tgt }
816 TerminatorKind::Unreachable => { }
820 fn visit_visibility_scope(&mut self, scope: &mut VisibilityScope) {
821 *scope = self.scope_map[*scope];
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() {
830 self.super_literal(literal, loc);