The Call Graph From the Wrong MIR: How rustc's Inliner Avoids a Query Cycle

TL;DR: Before inlining, rustc asks “could inlining this callee create a query cycle?”. To answer it needs a call graph — but computing the call graph from optimized MIR would itself be a query cycle. So the inliner computes it from mir_promoted, the pre-optimization MIR, which sits lower in the query DAG. The answer is conservative (it may see calls that optimization later removes) but it never deadlocks.

The problem

rustc’s query system is a DAG. optimized_mir(F) depends on optimized_mir(G) for every G that F calls, because the inliner may inline G into F. But that inlining decision depends on knowing the call graph, which is derived from the MIR…

So: to decide whether to inline G into F, the inliner wants to know whether G (transitively) calls F. If it does, inlining G into F would create a query cycle, and the query system would report a cycle error rather than a compile.

The naive implementation — compute the call graph from optimized_mir — builds exactly the cycle it is trying to avoid:

optimized_mir(F)
  -> inline(F)
    -> mir_inliner_callees(F)
      -> optimized_mir(G)
        -> inline(G)
          -> ...

The fix: use an earlier MIR

// compiler/rustc_mir_transform/src/inline/cycle.rs:192-229

pub(crate) fn mir_inliner_callees<'tcx>(
    tcx: TyCtxt<'tcx>,
    instance: ty::InstanceKind<'tcx>,
) -> &'tcx [(DefId, GenericArgsRef<'tcx>)] {
    let steal;
    let guard;
    let body = match (instance, instance.def_id().as_local()) {
        (InstanceKind::Item(_), Some(def_id)) => {
            steal = tcx.mir_promoted(def_id).0;
            guard = steal.borrow();
            &*guard
        }
        // Functions from other crates and MIR shims
        _ => tcx.instance_mir(instance),
    };
    let mut calls = FxIndexSet::default();
    for bb_data in body.basic_blocks.iter() {
        let terminator = bb_data.terminator();
        let TerminatorKind::Call { func, args: call_args, .. } = &terminator.kind {
            let ty = func.ty(&body.local_decls, tcx);
            let ty::FnDef(def_id, generic_args) = ty.kind() else {
                continue;
            };
            let call = if tcx.is_intrinsic(*def_id, sym::const_eval_select) {
                // `const_eval_select` takes the real callee as an argument.
                let func = &call_args[2].node;
                let ty = func.ty(&body.local_decls, tcx);
                let ty::FnDef(def_id, generic_args) = ty.kind() else {
                    continue;
                };
                (*def_id, *generic_args)
            } else {
                (*def_id, *generic_args)
            };
            calls.insert(call);
        }
    }
    tcx.arena.alloc_from_iter(calls.iter().map(|(did, args)| (did, args.no_bound_vars().unwrap())))
}

Two details:

1. The MIR source is mir_promoted — the MIR before optimization, before inlining, before constant propagation. It sits lower in the query DAG, so asking for it cannot create a cycle.
2. The const_eval_select special case. That intrinsic takes the real callee as an argument, so a naive scan of call terminators would miss the edge. The code digs into call_args[2] to find it.

The trade-off, stated plainly

The call graph computed from mir_promoted is a superset of the real call graph: optimization might remove a call entirely (a Call to a function whose result is unused and which has no side effects can be deleted), but mir_promoted still shows it.

That means rustc will sometimes refuse to inline something it could have inlined. The trade is deliberate: a conservative refusal costs a little optimization; a cycle costs a failed compile with a confusing error.

How the answer is used

// compiler/rustc_mir_transform/src/inline.rs:776-788

if let Some(callee_def_id) = callee_def_id.as_local()
    && !inliner.tcx().is_lang_item(inliner.tcx().parent(caller_def_id), LangItem::FnOnce)
{
    // If we know for sure that the function we're calling will itself try to
    // call us, then we avoid inlining that function.
    let Some(cyclic_callees) = inliner.tcx().mir_callgraph_cyclic(caller_def_id.expect_local())
    else {
        return Err("call graph cycle detection bailed due to recursion limit");
    };
    if cyclic_callees.contains(&callee_def_id) {
        debug!("query cycle avoidance");
        return Err("caller might be reachable from callee");
    }

mir_callgraph_cyclic is a query, so the answer is memoized per function and shared across the whole compilation.

The recursion limit hack, with the best comment in the file

// compiler/rustc_mir_transform/src/inline/cycle.rs:161-168

// FIXME(-Znext-solver=no): Remove this hack when trait solver overflow can return an error.
// In code like that pointed out in #128887, the type complexity we ask the solver to deal with
// grows as we recurse into the call graph. If we use the same recursion limit here and in the
// solver, the solver hits the limit first and emits a fatal error. But if we use a reduced
// limit, we will hit the limit first and give up on looking for inlining. And in any case,
// the default recursion limits are quite generous for us. If we need to recurse 64 times
// into the call graph, we're probably not going to find any useful MIR inlining.
let recursion_limit = tcx.recursion_limit() / 8;

This is a genuinely instructive pattern: the cheap analysis should fail before the expensive one. The trait solver’s recursion limit and the call-graph walker’s recursion limit are the same number, and both can be hit by the same pathological code. If the call-graph walker used the same limit, it would hit the limit at the same time as the solver, and the solver’s failure would be a hard error. By using an eighth of the limit, the call-graph walker gives up first, inlining is simply not attempted, and the compile succeeds with slightly worse code.

The other anti-explosion machinery

While we are in the inliner, the other protections are worth mentioning:

// compiler/rustc_mir_transform/src/inline.rs:30-31
const HISTORY_DEPTH_LIMIT: usize = 20;
const TOP_DOWN_DEPTH_LIMIT: usize = 5;

• history is a stack of DefIds (not full instances). Because the number of DefIds is finite, checking “have I already inlined this function” is enough to break cycles — and it deliberately still allows polymorphic recursion (f::<u8> calling f::<u32>) to be inlined.
• top_down_counter caps how many multi-call sites are inlined at the top level, bounding super-linear MIR growth.

And the cost model itself:

// compiler/rustc_mir_transform/src/inline.rs:364-381

let mut threshold = if self.caller_is_inline_forwarder || self.past_depth_limit() {
    tcx.sess.opts.unstable_opts.inline_mir_forwarder_threshold.unwrap_or(30)
} else if tcx.cross_crate_inlinable(callsite.callee.def_id()) {
    tcx.sess.opts.unstable_opts.inline_mir_hint_threshold.unwrap_or(100)
} else {
    tcx.sess.opts.unstable_opts.inline_mir_threshold.unwrap_or(50)
};

// Give a bonus functions with a small number of blocks,
// We normally have two or three blocks for even
// very small functions.
if callee_body.basic_blocks.len() <= 3 {
    threshold += threshold / 4;
}

The 25% bonus for small bodies is a heuristic about fixed overhead: even a tiny function has two or three basic blocks, and the per-block cost dominates the per-statement cost.

Where it lives

• compiler/rustc_mir_transform/src/inline/cycle.rs — mir_inliner_callees, mir_callgraph_cyclic, the /8 recursion limit.
• compiler/rustc_mir_transform/src/inline.rs — the cycle-avoidance check and the cost thresholds.
• compiler/rustc_mir_transform/src/inline/cost_checker.rs — the cost model.

Takeaway

When a system with a dependency DAG needs to ask a question about that DAG while computing it, you have to answer the question from a different, earlier version of the data. Here that is “the MIR before we optimized it”. The result is conservative, and the comment in the code says so — but a conservative answer that never deadlocks beats a precise answer that sometimes hangs the compiler.