compiler/rustc_mir_transform/src/inline/cycle.rs

   1 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
   2 use rustc_data_structures::sso::SsoHashSet;
   3 use rustc_data_structures::stack::ensure_sufficient_stack;
   4 use rustc_hir::def_id::{DefId, LocalDefId};
   5 use rustc_middle::mir::TerminatorKind;
   6 use rustc_middle::ty::TypeFoldable;
   7 use rustc_middle::ty::{self, subst::SubstsRef, InstanceDef, TyCtxt};
   8 use rustc_session::Limit;
   9
  10 // FIXME: check whether it is cheaper to precompute the entire call graph instead of invoking
  11 // this query riddiculously often.
  12 #[instrument(level = "debug", skip(tcx, root, target))]
  13 crate fn mir_callgraph_reachable<'tcx>(
  14     tcx: TyCtxt<'tcx>,
  15     (root, target): (ty::Instance<'tcx>, LocalDefId),
  16 ) -> bool {
  17     trace!(%root, target = %tcx.def_path_str(target.to_def_id()));
  18     let param_env = tcx.param_env_reveal_all_normalized(target);
  19     assert_ne!(
  20         root.def_id().expect_local(),
  21         target,
  22         "you should not call `mir_callgraph_reachable` on immediate self recursion"
  23     );
  24     assert!(
  25         matches!(root.def, InstanceDef::Item(_)),
  26         "you should not call `mir_callgraph_reachable` on shims"
  27     );
  28     assert!(
  29         !tcx.is_constructor(root.def_id()),
  30         "you should not call `mir_callgraph_reachable` on enum/struct constructor functions"
  31     );
  32     #[instrument(
  33         level = "debug",
  34         skip(tcx, param_env, target, stack, seen, recursion_limiter, caller, recursion_limit)
  35     )]
  36     fn process<'tcx>(
  37         tcx: TyCtxt<'tcx>,
  38         param_env: ty::ParamEnv<'tcx>,
  39         caller: ty::Instance<'tcx>,
  40         target: LocalDefId,
  41         stack: &mut Vec<ty::Instance<'tcx>>,
  42         seen: &mut FxHashSet<ty::Instance<'tcx>>,
  43         recursion_limiter: &mut FxHashMap<DefId, usize>,
  44         recursion_limit: Limit,
  45     ) -> bool {
  46         trace!(%caller);
  47         for &(callee, substs) in tcx.mir_inliner_callees(caller.def) {
  48             let substs = caller.subst_mir_and_normalize_erasing_regions(tcx, param_env, substs);
  49             let callee = match ty::Instance::resolve(tcx, param_env, callee, substs).unwrap() {
  50                 Some(callee) => callee,
  51                 None => {
  52                     trace!(?callee, "cannot resolve, skipping");
  53                     continue;
  54                 }
  55             };
  56
  57             // Found a path.
  58             if callee.def_id() == target.to_def_id() {
  59                 return true;
  60             }
  61
  62             if tcx.is_constructor(callee.def_id()) {
  63                 trace!("constructors always have MIR");
  64                 // Constructor functions cannot cause a query cycle.
  65                 continue;
  66             }
  67
  68             match callee.def {
  69                 InstanceDef::Item(_) => {
  70                     // If there is no MIR available (either because it was not in metadata or
  71                     // because it has no MIR because it's an extern function), then the inliner
  72                     // won't cause cycles on this.
  73                     if !tcx.is_mir_available(callee.def_id()) {
  74                         trace!(?callee, "no mir available, skipping");
  75                         continue;
  76                     }
  77                 }
  78                 // These have no own callable MIR.
  79                 InstanceDef::Intrinsic(_) | InstanceDef::Virtual(..) => continue,
  80                 // These have MIR and if that MIR is inlined, substituted and then inlining is run
  81                 // again, a function item can end up getting inlined. Thus we'll be able to cause
  82                 // a cycle that way
  83                 InstanceDef::VtableShim(_)
  84                 | InstanceDef::ReifyShim(_)
  85                 | InstanceDef::FnPtrShim(..)
  86                 | InstanceDef::ClosureOnceShim { .. }
  87                 | InstanceDef::CloneShim(..) => {}
  88                 InstanceDef::DropGlue(..) => {
  89                     // FIXME: A not fully substituted drop shim can cause ICEs if one attempts to
  90                     // have its MIR built. Likely oli-obk just screwed up the `ParamEnv`s, so this
  91                     // needs some more analysis.
  92                     if callee.needs_subst() {
  93                         continue;
  94                     }
  95                 }
  96             }
  97
  98             if seen.insert(callee) {
  99                 let recursion = recursion_limiter.entry(callee.def_id()).or_default();
 100                 trace!(?callee, recursion = *recursion);
 101                 if recursion_limit.value_within_limit(*recursion) {
 102                     *recursion += 1;
 103                     stack.push(callee);
 104                     let found_recursion = ensure_sufficient_stack(|| {
 105                         process(
 106                             tcx,
 107                             param_env,
 108                             callee,
 109                             target,
 110                             stack,
 111                             seen,
 112                             recursion_limiter,
 113                             recursion_limit,
 114                         )
 115                     });
 116                     if found_recursion {
 117                         return true;
 118                     }
 119                     stack.pop();
 120                 } else {
 121                     // Pessimistically assume that there could be recursion.
 122                     return true;
 123                 }
 124             }
 125         }
 126         false
 127     }
 128     process(
 129         tcx,
 130         param_env,
 131         root,
 132         target,
 133         &mut Vec::new(),
 134         &mut FxHashSet::default(),
 135         &mut FxHashMap::default(),
 136         tcx.recursion_limit(),
 137     )
 138 }
 139
 140 crate fn mir_inliner_callees<'tcx>(
 141     tcx: TyCtxt<'tcx>,
 142     instance: ty::InstanceDef<'tcx>,
 143 ) -> &'tcx [(DefId, SubstsRef<'tcx>)] {
 144     let steal;
 145     let guard;
 146     let body = match (instance, instance.def_id().as_local()) {
 147         (InstanceDef::Item(_), Some(def_id)) => {
 148             let def = ty::WithOptConstParam::unknown(def_id);
 149             steal = tcx.mir_promoted(def).0;
 150             guard = steal.borrow();
 151             &*guard
 152         }
 153         // Functions from other crates and MIR shims
 154         _ => tcx.instance_mir(instance),
 155     };
 156     let mut calls = SsoHashSet::new();
 157     for bb_data in body.basic_blocks() {
 158         let terminator = bb_data.terminator();
 159         if let TerminatorKind::Call { func, .. } = &terminator.kind {
 160             let ty = func.ty(&body.local_decls, tcx);
 161             let call = match ty.kind() {
 162                 ty::FnDef(def_id, substs) => (*def_id, *substs),
 163                 _ => continue,
 164             };
 165             calls.insert(call);
 166         }
 167     }
 168     tcx.arena.alloc_from_iter(calls.iter().copied())
 169 }