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;
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>(
15 (root, target): (ty::Instance<'tcx>, LocalDefId),
17 trace!(%root, target = %tcx.def_path_str(target.to_def_id()));
18 let param_env = tcx.param_env_reveal_all_normalized(target);
20 root.def_id().expect_local(),
22 "you should not call `mir_callgraph_reachable` on immediate self recursion"
25 matches!(root.def, InstanceDef::Item(_)),
26 "you should not call `mir_callgraph_reachable` on shims"
29 !tcx.is_constructor(root.def_id()),
30 "you should not call `mir_callgraph_reachable` on enum/struct constructor functions"
34 skip(tcx, param_env, target, stack, seen, recursion_limiter, caller, recursion_limit)
38 param_env: ty::ParamEnv<'tcx>,
39 caller: ty::Instance<'tcx>,
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,
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,
52 trace!(?callee, "cannot resolve, skipping");
58 if callee.def_id() == target.to_def_id() {
62 if tcx.is_constructor(callee.def_id()) {
63 trace!("constructors always have MIR");
64 // Constructor functions cannot cause a query cycle.
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");
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
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.definitely_needs_subst(tcx) {
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) {
104 let found_recursion = ensure_sufficient_stack(|| {
121 // Pessimistically assume that there could be recursion.
134 &mut FxHashSet::default(),
135 &mut FxHashMap::default(),
136 tcx.recursion_limit(),
140 crate fn mir_inliner_callees<'tcx>(
142 instance: ty::InstanceDef<'tcx>,
143 ) -> &'tcx [(DefId, SubstsRef<'tcx>)] {
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();
153 // Functions from other crates and MIR shims
154 _ => tcx.instance_mir(instance),
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),
168 tcx.arena.alloc_from_iter(calls.iter().copied())