compiler/rustc_mir_transform/src/inline/cycle.rs

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