rustc_mir_transform/inline/
cycle.rs

1use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexSet};
2use rustc_data_structures::unord::UnordSet;
3use rustc_hir::def_id::{DefId, LocalDefId};
4use rustc_middle::mir::TerminatorKind;
5use rustc_middle::ty::{self, GenericArgsRef, InstanceKind, ShimKind, TyCtxt, TypeVisitableExt};
6use rustc_span::sym;
7use rustc_structures::Limit;
8use tracing::{instrument, trace};
9
10#[instrument(level = "debug", skip(tcx), ret)]
11fn should_recurse<'tcx>(tcx: TyCtxt<'tcx>, callee: ty::Instance<'tcx>) -> bool {
12    match callee.def {
13        // If there is no MIR available (either because it was not in metadata or
14        // because it has no MIR because it's an extern function), then the inliner
15        // won't cause cycles on this.
16        InstanceKind::Item(_) => {
17            if !tcx.is_mir_available(callee.def_id()) {
18                return false;
19            }
20        }
21
22        // These have no own callable MIR.
23        InstanceKind::Intrinsic(_) | InstanceKind::LlvmIntrinsic(_) | InstanceKind::Virtual(..) => {
24            return false;
25        }
26
27        // These have MIR and if that MIR is inlined, instantiated and then inlining is run
28        // again, a function item can end up getting inlined. Thus we'll be able to cause
29        // a cycle that way
30        InstanceKind::Shim(ShimKind::VTable(_))
31        | InstanceKind::Shim(ShimKind::Reify(..))
32        | InstanceKind::Shim(ShimKind::FnPtr(..))
33        | InstanceKind::Shim(ShimKind::ClosureOnce { .. })
34        | InstanceKind::Shim(ShimKind::ConstructCoroutineInClosure { .. })
35        | InstanceKind::Shim(ShimKind::ThreadLocal { .. })
36        | InstanceKind::Shim(ShimKind::Clone(..)) => {}
37
38        // This shim does not call any other functions, thus there can be no recursion.
39        InstanceKind::Shim(ShimKind::FnPtrAsPtr(..) | ShimKind::FnPtrFromPtr(..)) => return false,
40
41        // FIXME: A not fully instantiated drop shim can cause ICEs if one attempts to
42        // have its MIR built. Likely oli-obk just screwed up the `ParamEnv`s, so this
43        // needs some more analysis.
44        InstanceKind::Shim(ShimKind::DropGlue(..))
45        | InstanceKind::Shim(ShimKind::FutureDropPoll(..))
46        | InstanceKind::Shim(ShimKind::AsyncDropGlue(..))
47        | InstanceKind::Shim(ShimKind::AsyncDropGlueCtor(..)) => {
48            if callee.has_param() {
49                return false;
50            }
51        }
52    }
53
54    crate::pm::should_run_pass(
55        &crate::inline::Inline,
56        &crate::pm::PassCtx::for_body(tcx, callee.def_id()),
57    ) || crate::inline::ForceInline::should_run_pass_for_callee(tcx, callee.def.def_id())
58}
59
60#[instrument(
61    level = "debug",
62    skip(tcx, typing_env, seen, involved, recursion_limiter, recursion_limit),
63    ret
64)]
65fn process<'tcx>(
66    tcx: TyCtxt<'tcx>,
67    typing_env: ty::TypingEnv<'tcx>,
68    caller: ty::Instance<'tcx>,
69    target: LocalDefId,
70    seen: &mut FxHashMap<ty::Instance<'tcx>, bool>,
71    involved: &mut FxHashSet<LocalDefId>,
72    recursion_limiter: &mut FxHashMap<DefId, usize>,
73    recursion_limit: Limit,
74) -> Option<bool> {
75    trace!(%caller);
76    let mut reaches_root = false;
77
78    for &(callee_def_id, args) in tcx.mir_inliner_callees(caller.def) {
79        let Ok(args) = caller.try_instantiate_mir_and_normalize_erasing_regions(
80            tcx,
81            typing_env,
82            ty::EarlyBinder::bind(tcx, args),
83        ) else {
84            trace!(?caller, ?typing_env, ?args, "cannot normalize, skipping");
85            continue;
86        };
87        let Ok(Some(callee)) = ty::Instance::try_resolve(tcx, typing_env, callee_def_id, args)
88        else {
89            trace!(?callee_def_id, "cannot resolve, skipping");
90            continue;
91        };
92
93        // Found a path.
94        if callee.def_id() == target.to_def_id() {
95            reaches_root = true;
96            seen.insert(callee, true);
97            continue;
98        }
99
100        if tcx.is_constructor(callee.def_id()) {
101            trace!("constructors always have MIR");
102            // Constructor functions cannot cause a query cycle.
103            continue;
104        }
105
106        if !should_recurse(tcx, callee) {
107            continue;
108        }
109
110        let callee_reaches_root = if let Some(&c) = seen.get(&callee) {
111            // Even if we have seen this callee before, and thus don't need
112            // to recurse into it, we still need to propagate whether it reaches
113            // the root so that we can mark all the involved callers, in case we
114            // end up reaching that same recursive callee through some *other* cycle.
115            c
116        } else {
117            seen.insert(callee, false);
118            let recursion = recursion_limiter.entry(callee.def_id()).or_default();
119            trace!(?callee, recursion = *recursion);
120            let callee_reaches_root = if recursion_limit.value_within_limit(*recursion) {
121                *recursion += 1;
122
123                process(
124                    tcx,
125                    typing_env,
126                    callee,
127                    target,
128                    seen,
129                    involved,
130                    recursion_limiter,
131                    recursion_limit,
132                )?
133            } else {
134                return None;
135            };
136            seen.insert(callee, callee_reaches_root);
137            callee_reaches_root
138        };
139        if callee_reaches_root {
140            if let Some(callee_def_id) = callee.def_id().as_local() {
141                // Calling `optimized_mir` of a non-local definition cannot cycle.
142                involved.insert(callee_def_id);
143            }
144            reaches_root = true;
145        }
146    }
147
148    Some(reaches_root)
149}
150
151#[instrument(level = "debug", skip(tcx), ret)]
152pub(crate) fn mir_callgraph_cyclic<'tcx>(
153    tcx: TyCtxt<'tcx>,
154    root: LocalDefId,
155) -> Option<&'tcx UnordSet<LocalDefId>> {
156    assert!(
157        !tcx.is_constructor(root.to_def_id()),
158        "you should not call `mir_callgraph_reachable` on enum/struct constructor functions"
159    );
160
161    // FIXME(-Znext-solver=no): Remove this hack when trait solver overflow can return an error.
162    // In code like that pointed out in #128887, the type complexity we ask the solver to deal with
163    // grows as we recurse into the call graph. If we use the same recursion limit here and in the
164    // solver, the solver hits the limit first and emits a fatal error. But if we use a reduced
165    // limit, we will hit the limit first and give up on looking for inlining. And in any case,
166    // the default recursion limits are quite generous for us. If we need to recurse 64 times
167    // into the call graph, we're probably not going to find any useful MIR inlining.
168    let recursion_limit = tcx.recursion_limit() / 8;
169    let mut involved = FxHashSet::default();
170    let typing_env = ty::TypingEnv::post_analysis(tcx, root);
171    let root_instance =
172        ty::Instance::new_raw(root.to_def_id(), ty::GenericArgs::identity_for_item(tcx, root));
173    if !should_recurse(tcx, root_instance) {
174        trace!("cannot walk, skipping");
175        return Some(tcx.arena.alloc(involved.into()));
176    }
177    match process(
178        tcx,
179        typing_env,
180        root_instance,
181        root,
182        &mut FxHashMap::default(),
183        &mut involved,
184        &mut FxHashMap::default(),
185        recursion_limit,
186    ) {
187        Some(_) => Some(tcx.arena.alloc(involved.into())),
188        _ => None,
189    }
190}
191
192pub(crate) fn mir_inliner_callees<'tcx>(
193    tcx: TyCtxt<'tcx>,
194    instance: ty::InstanceKind<'tcx>,
195) -> &'tcx [(DefId, GenericArgsRef<'tcx>)] {
196    let steal;
197    let guard;
198    let body = match (instance, instance.def_id().as_local()) {
199        (InstanceKind::Item(_), Some(def_id)) => {
200            steal = tcx.mir_promoted(def_id).0;
201            guard = steal.borrow();
202            &*guard
203        }
204        // Functions from other crates and MIR shims
205        _ => tcx.instance_mir(instance),
206    };
207    let mut calls = FxIndexSet::default();
208    for bb_data in body.basic_blocks.iter() {
209        let terminator = bb_data.terminator();
210        if let TerminatorKind::Call { func, args: call_args, .. } = &terminator.kind {
211            let ty = func.ty(&body.local_decls, tcx);
212            let ty::FnDef(def_id, generic_args) = ty.kind() else {
213                continue;
214            };
215            let call = if tcx.is_intrinsic(*def_id, sym::const_eval_select) {
216                let func = &call_args[2].node;
217                let ty = func.ty(&body.local_decls, tcx);
218                let ty::FnDef(def_id, generic_args) = ty.kind() else {
219                    continue;
220                };
221                (*def_id, *generic_args)
222            } else {
223                (*def_id, *generic_args)
224            };
225            calls.insert(call);
226        }
227    }
228    tcx.arena.alloc_from_iter(calls.iter().map(|(did, args)| (*did, args.no_bound_vars().unwrap())))
229}
rustc_mir_transform/inline/cycle.rs

rustc_mir_transform/inline/
cycle.rs
