rustc_passes/
reachable.rs

1//! Finds local items that are "reachable", which means that other crates need access to their
2//! compiled code or their *runtime* MIR. (Compile-time MIR is always encoded anyway, so we don't
3//! worry about that here.)
4//!
5//! An item is "reachable" if codegen that happens in downstream crates can end up referencing this
6//! item. This obviously includes all public items. However, some of these items cannot be codegen'd
7//! (because they are generic), and for some the compiled code is not sufficient (because we want to
8//! cross-crate inline them). These items "need cross-crate MIR". When a reachable function `f`
9//! needs cross-crate MIR, then its MIR may be codegen'd in a downstream crate, and hence items it
10//! mentions need to be considered reachable.
11//!
12//! Furthermore, if a `const`/`const fn` is reachable, then it can return pointers to other items,
13//! making those reachable as well. For instance, consider a `const fn` returning a pointer to an
14//! otherwise entirely private function: if a downstream crate calls that `const fn` to compute the
15//! initial value of a `static`, then it needs to generate a direct reference to this function --
16//! i.e., the function is directly reachable from that downstream crate! Hence we have to recurse
17//! into `const` and `const fn`.
18//!
19//! Conversely, reachability *stops* when it hits a monomorphic non-`const` function that we do not
20//! want to cross-crate inline. That function will just be codegen'd in this crate, which means the
21//! monomorphization collector will consider it a root and then do another graph traversal to
22//! codegen everything called by this function -- but that's a very different graph from what we are
23//! considering here as at that point, everything is monomorphic.
24
25use hir::def_id::LocalDefIdSet;
26use rustc_data_structures::stack::ensure_sufficient_stack;
27use rustc_hir as hir;
28use rustc_hir::Node;
29use rustc_hir::def::{DefKind, Res};
30use rustc_hir::def_id::{DefId, LocalDefId};
31use rustc_hir::intravisit::{self, Visitor};
32use rustc_middle::bug;
33use rustc_middle::middle::codegen_fn_attrs::{CodegenFnAttrFlags, CodegenFnAttrs};
34use rustc_middle::middle::privacy::{self, Level};
35use rustc_middle::mir::interpret::{ConstAllocation, ErrorHandled, GlobalAlloc};
36use rustc_middle::query::Providers;
37use rustc_middle::ty::{self, ExistentialTraitRef, TyCtxt};
38use rustc_privacy::DefIdVisitor;
39use rustc_session::config::CrateType;
40use tracing::debug;
41
42/// Determines whether this item is recursive for reachability. See `is_recursively_reachable_local`
43/// below for details.
44fn recursively_reachable(tcx: TyCtxt<'_>, def_id: DefId) -> bool {
45    tcx.generics_of(def_id).requires_monomorphization(tcx)
46        || tcx.cross_crate_inlinable(def_id)
47        || tcx.is_const_fn(def_id)
48}
49
50// Information needed while computing reachability.
51struct ReachableContext<'tcx> {
52    // The type context.
53    tcx: TyCtxt<'tcx>,
54    maybe_typeck_results: Option<&'tcx ty::TypeckResults<'tcx>>,
55    // The set of items which must be exported in the linkage sense.
56    reachable_symbols: LocalDefIdSet,
57    // A worklist of item IDs. Each item ID in this worklist will be inlined
58    // and will be scanned for further references.
59    // FIXME(eddyb) benchmark if this would be faster as a `VecDeque`.
60    worklist: Vec<LocalDefId>,
61    // Whether any output of this compilation is a library
62    any_library: bool,
63}
64
65impl<'tcx> Visitor<'tcx> for ReachableContext<'tcx> {
66    fn visit_nested_body(&mut self, body: hir::BodyId) {
67        let old_maybe_typeck_results =
68            self.maybe_typeck_results.replace(self.tcx.typeck_body(body));
69        let body = self.tcx.hir_body(body);
70        self.visit_body(body);
71        self.maybe_typeck_results = old_maybe_typeck_results;
72    }
73
74    fn visit_expr(&mut self, expr: &'tcx hir::Expr<'tcx>) {
75        let res = match expr.kind {
76            hir::ExprKind::Path(ref qpath) => {
77                // This covers fn ptr casts but also "non-method" calls.
78                Some(self.typeck_results().qpath_res(qpath, expr.hir_id))
79            }
80            hir::ExprKind::MethodCall(..) => {
81                // Method calls don't involve a full "path", so we need to determine the callee
82                // based on the receiver type.
83                // If this is a method call on a generic type, we might not be able to find the
84                // callee. That's why `reachable_set` also adds all potential callees for such
85                // calls, i.e. all trait impl items, to the reachable set. So here we only worry
86                // about the calls we can identify.
87                self.typeck_results()
88                    .type_dependent_def(expr.hir_id)
89                    .map(|(kind, def_id)| Res::Def(kind, def_id))
90            }
91            hir::ExprKind::Closure(&hir::Closure { def_id, .. }) => {
92                self.reachable_symbols.insert(def_id);
93                None
94            }
95            _ => None,
96        };
97
98        if let Some(res) = res {
99            self.propagate_item(res);
100        }
101
102        intravisit::walk_expr(self, expr)
103    }
104
105    fn visit_inline_asm(&mut self, asm: &'tcx hir::InlineAsm<'tcx>, id: hir::HirId) {
106        for (op, _) in asm.operands {
107            if let hir::InlineAsmOperand::SymStatic { def_id, .. } = op {
108                if let Some(def_id) = def_id.as_local() {
109                    self.reachable_symbols.insert(def_id);
110                }
111            }
112        }
113        intravisit::walk_inline_asm(self, asm, id);
114    }
115}
116
117impl<'tcx> ReachableContext<'tcx> {
118    /// Gets the type-checking results for the current body.
119    /// As this will ICE if called outside bodies, only call when working with
120    /// `Expr` or `Pat` nodes (they are guaranteed to be found only in bodies).
121    #[track_caller]
122    fn typeck_results(&self) -> &'tcx ty::TypeckResults<'tcx> {
123        self.maybe_typeck_results
124            .expect("`ReachableContext::typeck_results` called outside of body")
125    }
126
127    /// Returns true if the given def ID represents a local item that is recursive for reachability,
128    /// i.e. whether everything mentioned in here also needs to be considered reachable.
129    ///
130    /// There are two reasons why an item may be recursively reachable:
131    /// - It needs cross-crate MIR (see the module-level doc comment above).
132    /// - It is a `const` or `const fn`. This is *not* because we need the MIR to interpret them
133    ///   (MIR for const-eval and MIR for codegen is separate, and MIR for const-eval is always
134    ///   encoded). Instead, it is because `const fn` can create `fn()` pointers to other items
135    ///   which end up in the evaluated result of the constant and can then be called from other
136    ///   crates. Those items must be considered reachable.
137    fn is_recursively_reachable_local(&self, def_id: DefId) -> bool {
138        let Some(def_id) = def_id.as_local() else {
139            return false;
140        };
141
142        match self.tcx.hir_node_by_def_id(def_id) {
143            Node::Item(item) => match item.kind {
144                hir::ItemKind::Fn { .. } => recursively_reachable(self.tcx, def_id.into()),
145                _ => false,
146            },
147            Node::TraitItem(trait_method) => match trait_method.kind {
148                hir::TraitItemKind::Const(_, ref default) => default.is_some(),
149                hir::TraitItemKind::Fn(_, hir::TraitFn::Provided(_)) => true,
150                hir::TraitItemKind::Fn(_, hir::TraitFn::Required(_))
151                | hir::TraitItemKind::Type(..) => false,
152            },
153            Node::ImplItem(impl_item) => match impl_item.kind {
154                hir::ImplItemKind::Const(..) => true,
155                hir::ImplItemKind::Fn(..) => {
156                    recursively_reachable(self.tcx, impl_item.hir_id().owner.to_def_id())
157                }
158                hir::ImplItemKind::Type(_) => false,
159            },
160            Node::Expr(&hir::Expr { kind: hir::ExprKind::Closure(..), .. }) => true,
161            _ => false,
162        }
163    }
164
165    // Step 2: Mark all symbols that the symbols on the worklist touch.
166    fn propagate(&mut self) {
167        let mut scanned = LocalDefIdSet::default();
168        while let Some(search_item) = self.worklist.pop() {
169            if !scanned.insert(search_item) {
170                continue;
171            }
172
173            self.propagate_node(&self.tcx.hir_node_by_def_id(search_item), search_item);
174        }
175    }
176
177    fn propagate_node(&mut self, node: &Node<'tcx>, search_item: LocalDefId) {
178        if !self.any_library {
179            // If we are building an executable, only explicitly extern
180            // types need to be exported.
181            let codegen_attrs = if self.tcx.def_kind(search_item).has_codegen_attrs() {
182                self.tcx.codegen_fn_attrs(search_item)
183            } else {
184                CodegenFnAttrs::EMPTY
185            };
186            let is_extern = codegen_attrs.contains_extern_indicator();
187            if is_extern {
188                self.reachable_symbols.insert(search_item);
189            }
190        } else {
191            // If we are building a library, then reachable symbols will
192            // continue to participate in linkage after this product is
193            // produced. In this case, we traverse the ast node, recursing on
194            // all reachable nodes from this one.
195            self.reachable_symbols.insert(search_item);
196        }
197
198        match *node {
199            Node::Item(item) => {
200                match item.kind {
201                    hir::ItemKind::Fn { body, .. } => {
202                        if recursively_reachable(self.tcx, item.owner_id.into()) {
203                            self.visit_nested_body(body);
204                        }
205                    }
206
207                    hir::ItemKind::Const(_, _, _, init) => {
208                        // Only things actually ending up in the final constant value are reachable
209                        // for codegen. Everything else is only needed during const-eval, so even if
210                        // const-eval happens in a downstream crate, all they need is
211                        // `mir_for_ctfe`.
212                        match self.tcx.const_eval_poly_to_alloc(item.owner_id.def_id.into()) {
213                            Ok(alloc) => {
214                                let alloc = self.tcx.global_alloc(alloc.alloc_id).unwrap_memory();
215                                self.propagate_from_alloc(alloc);
216                            }
217                            // We can't figure out which value the constant will evaluate to. In
218                            // lieu of that, we have to consider everything mentioned in the const
219                            // initializer reachable, since it *may* end up in the final value.
220                            Err(ErrorHandled::TooGeneric(_)) => self.visit_nested_body(init),
221                            // If there was an error evaluating the const, nothing can be reachable
222                            // via it, and anyway compilation will fail.
223                            Err(ErrorHandled::Reported(..)) => {}
224                        }
225                    }
226                    hir::ItemKind::Static(..) => {
227                        if let Ok(alloc) = self.tcx.eval_static_initializer(item.owner_id.def_id) {
228                            self.propagate_from_alloc(alloc);
229                        }
230                    }
231
232                    // These are normal, nothing reachable about these
233                    // inherently and their children are already in the
234                    // worklist, as determined by the privacy pass
235                    hir::ItemKind::ExternCrate(..)
236                    | hir::ItemKind::Use(..)
237                    | hir::ItemKind::TyAlias(..)
238                    | hir::ItemKind::Macro(..)
239                    | hir::ItemKind::Mod(..)
240                    | hir::ItemKind::ForeignMod { .. }
241                    | hir::ItemKind::Impl { .. }
242                    | hir::ItemKind::Trait(..)
243                    | hir::ItemKind::TraitAlias(..)
244                    | hir::ItemKind::Struct(..)
245                    | hir::ItemKind::Enum(..)
246                    | hir::ItemKind::Union(..)
247                    | hir::ItemKind::GlobalAsm { .. } => {}
248                }
249            }
250            Node::TraitItem(trait_method) => {
251                match trait_method.kind {
252                    hir::TraitItemKind::Const(_, None)
253                    | hir::TraitItemKind::Fn(_, hir::TraitFn::Required(_)) => {
254                        // Keep going, nothing to get exported
255                    }
256                    hir::TraitItemKind::Const(_, Some(body_id))
257                    | hir::TraitItemKind::Fn(_, hir::TraitFn::Provided(body_id)) => {
258                        self.visit_nested_body(body_id);
259                    }
260                    hir::TraitItemKind::Type(..) => {}
261                }
262            }
263            Node::ImplItem(impl_item) => match impl_item.kind {
264                hir::ImplItemKind::Const(_, body) => {
265                    self.visit_nested_body(body);
266                }
267                hir::ImplItemKind::Fn(_, body) => {
268                    if recursively_reachable(self.tcx, impl_item.hir_id().owner.to_def_id()) {
269                        self.visit_nested_body(body)
270                    }
271                }
272                hir::ImplItemKind::Type(_) => {}
273            },
274            Node::Expr(&hir::Expr {
275                kind: hir::ExprKind::Closure(&hir::Closure { body, .. }),
276                ..
277            }) => {
278                self.visit_nested_body(body);
279            }
280            // Nothing to recurse on for these
281            Node::ForeignItem(_)
282            | Node::Variant(_)
283            | Node::Ctor(..)
284            | Node::Field(_)
285            | Node::Ty(_)
286            | Node::Crate(_)
287            | Node::Synthetic
288            | Node::OpaqueTy(..) => {}
289            _ => {
290                bug!(
291                    "found unexpected node kind in worklist: {} ({:?})",
292                    self.tcx.hir_id_to_string(self.tcx.local_def_id_to_hir_id(search_item)),
293                    node,
294                );
295            }
296        }
297    }
298
299    /// Finds things to add to `reachable_symbols` within allocations.
300    /// In contrast to visit_nested_body this ignores things that were only needed to evaluate
301    /// the allocation.
302    fn propagate_from_alloc(&mut self, alloc: ConstAllocation<'tcx>) {
303        if !self.any_library {
304            return;
305        }
306        for (_, prov) in alloc.0.provenance().ptrs().iter() {
307            match self.tcx.global_alloc(prov.alloc_id()) {
308                GlobalAlloc::Static(def_id) => {
309                    self.propagate_item(Res::Def(self.tcx.def_kind(def_id), def_id))
310                }
311                GlobalAlloc::Function { instance, .. } => {
312                    // Manually visit to actually see the instance's `DefId`. Type visitors won't see it
313                    self.propagate_item(Res::Def(
314                        self.tcx.def_kind(instance.def_id()),
315                        instance.def_id(),
316                    ));
317                    self.visit(instance.args);
318                }
319                GlobalAlloc::VTable(ty, dyn_ty) => {
320                    self.visit(ty);
321                    // Manually visit to actually see the trait's `DefId`. Type visitors won't see it
322                    if let Some(trait_ref) = dyn_ty.principal() {
323                        let ExistentialTraitRef { def_id, args, .. } = trait_ref.skip_binder();
324                        self.visit_def_id(def_id, "", &"");
325                        self.visit(args);
326                    }
327                }
328                GlobalAlloc::Memory(alloc) => self.propagate_from_alloc(alloc),
329            }
330        }
331    }
332
333    fn propagate_item(&mut self, res: Res) {
334        let Res::Def(kind, def_id) = res else { return };
335        let Some(def_id) = def_id.as_local() else { return };
336        match kind {
337            DefKind::Static { nested: true, .. } => {
338                // This is the main purpose of this function: add the def_id we find
339                // to `reachable_symbols`.
340                if self.reachable_symbols.insert(def_id) {
341                    if let Ok(alloc) = self.tcx.eval_static_initializer(def_id) {
342                        // This cannot cause infinite recursion, because we abort by inserting into the
343                        // work list once we hit a normal static. Nested statics, even if they somehow
344                        // become recursive, are also not infinitely recursing, because of the
345                        // `reachable_symbols` check above.
346                        // We still need to protect against stack overflow due to deeply nested statics.
347                        ensure_sufficient_stack(|| self.propagate_from_alloc(alloc));
348                    }
349                }
350            }
351            // Reachable constants and reachable statics can have their contents inlined
352            // into other crates. Mark them as reachable and recurse into their body.
353            DefKind::Const | DefKind::AssocConst | DefKind::Static { .. } => {
354                self.worklist.push(def_id);
355            }
356            _ => {
357                if self.is_recursively_reachable_local(def_id.to_def_id()) {
358                    self.worklist.push(def_id);
359                } else {
360                    self.reachable_symbols.insert(def_id);
361                }
362            }
363        }
364    }
365}
366
367impl<'tcx> DefIdVisitor<'tcx> for ReachableContext<'tcx> {
368    type Result = ();
369
370    fn tcx(&self) -> TyCtxt<'tcx> {
371        self.tcx
372    }
373
374    fn visit_def_id(
375        &mut self,
376        def_id: DefId,
377        _kind: &str,
378        _descr: &dyn std::fmt::Display,
379    ) -> Self::Result {
380        self.propagate_item(Res::Def(self.tcx.def_kind(def_id), def_id))
381    }
382}
383
384fn check_item<'tcx>(
385    tcx: TyCtxt<'tcx>,
386    id: hir::ItemId,
387    worklist: &mut Vec<LocalDefId>,
388    effective_visibilities: &privacy::EffectiveVisibilities,
389) {
390    if has_custom_linkage(tcx, id.owner_id.def_id) {
391        worklist.push(id.owner_id.def_id);
392    }
393
394    if !matches!(tcx.def_kind(id.owner_id), DefKind::Impl { of_trait: true }) {
395        return;
396    }
397
398    // We need only trait impls here, not inherent impls, and only non-exported ones
399    if effective_visibilities.is_reachable(id.owner_id.def_id) {
400        return;
401    }
402
403    let items = tcx.associated_item_def_ids(id.owner_id);
404    worklist.extend(items.iter().map(|ii_ref| ii_ref.expect_local()));
405
406    let Some(trait_def_id) = tcx.trait_id_of_impl(id.owner_id.to_def_id()) else {
407        unreachable!();
408    };
409
410    if !trait_def_id.is_local() {
411        return;
412    }
413
414    worklist
415        .extend(tcx.provided_trait_methods(trait_def_id).map(|assoc| assoc.def_id.expect_local()));
416}
417
418fn has_custom_linkage(tcx: TyCtxt<'_>, def_id: LocalDefId) -> bool {
419    // Anything which has custom linkage gets thrown on the worklist no
420    // matter where it is in the crate, along with "special std symbols"
421    // which are currently akin to allocator symbols.
422    if !tcx.def_kind(def_id).has_codegen_attrs() {
423        return false;
424    }
425    let codegen_attrs = tcx.codegen_fn_attrs(def_id);
426    codegen_attrs.contains_extern_indicator()
427        // FIXME(nbdd0121): `#[used]` are marked as reachable here so it's picked up by
428        // `linked_symbols` in cg_ssa. They won't be exported in binary or cdylib due to their
429        // `SymbolExportLevel::Rust` export level but may end up being exported in dylibs.
430        || codegen_attrs.flags.contains(CodegenFnAttrFlags::USED)
431        || codegen_attrs.flags.contains(CodegenFnAttrFlags::USED_LINKER)
432}
433
434/// See module-level doc comment above.
435fn reachable_set(tcx: TyCtxt<'_>, (): ()) -> LocalDefIdSet {
436    let effective_visibilities = &tcx.effective_visibilities(());
437
438    let any_library = tcx
439        .crate_types()
440        .iter()
441        .any(|ty| *ty == CrateType::Rlib || *ty == CrateType::Dylib || *ty == CrateType::ProcMacro);
442    let mut reachable_context = ReachableContext {
443        tcx,
444        maybe_typeck_results: None,
445        reachable_symbols: Default::default(),
446        worklist: Vec::new(),
447        any_library,
448    };
449
450    // Step 1: Seed the worklist with all nodes which were found to be public as
451    //         a result of the privacy pass along with all local lang items and impl items.
452    //         If other crates link to us, they're going to expect to be able to
453    //         use the lang items, so we need to be sure to mark them as
454    //         exported.
455    reachable_context.worklist = effective_visibilities
456        .iter()
457        .filter_map(|(&id, effective_vis)| {
458            effective_vis.is_public_at_level(Level::ReachableThroughImplTrait).then_some(id)
459        })
460        .collect::<Vec<_>>();
461
462    for (_, def_id) in tcx.lang_items().iter() {
463        if let Some(def_id) = def_id.as_local() {
464            reachable_context.worklist.push(def_id);
465        }
466    }
467    {
468        // As explained above, we have to mark all functions called from reachable
469        // `item_might_be_inlined` items as reachable. The issue is, when those functions are
470        // generic and call a trait method, we have no idea where that call goes! So, we
471        // conservatively mark all trait impl items as reachable.
472        // FIXME: One possible strategy for pruning the reachable set is to avoid marking impl
473        // items of non-exported traits (or maybe all local traits?) unless their respective
474        // trait items are used from inlinable code through method call syntax or UFCS, or their
475        // trait is a lang item.
476        // (But if you implement this, don't forget to take into account that vtables can also
477        // make trait methods reachable!)
478        let crate_items = tcx.hir_crate_items(());
479
480        for id in crate_items.free_items() {
481            check_item(tcx, id, &mut reachable_context.worklist, effective_visibilities);
482        }
483
484        for id in crate_items.impl_items() {
485            if has_custom_linkage(tcx, id.owner_id.def_id) {
486                reachable_context.worklist.push(id.owner_id.def_id);
487            }
488        }
489    }
490
491    // Step 2: Mark all symbols that the symbols on the worklist touch.
492    reachable_context.propagate();
493
494    debug!("Inline reachability shows: {:?}", reachable_context.reachable_symbols);
495
496    // Return the set of reachable symbols.
497    reachable_context.reachable_symbols
498}
499
500pub(crate) fn provide(providers: &mut Providers) {
501    *providers = Providers { reachable_set, ..*providers };
502}