]>
Commit | Line | Data |
---|---|---|
970d7e83 LB |
1 | // Finds items that are externally reachable, to determine which items |
2 | // need to have their metadata (and possibly their AST) serialized. | |
3 | // All items that can be referred to through an exported name are | |
4 | // reachable, and when a reachable thing is inline or generic, it | |
5 | // makes all other generics or inline functions that it references | |
6 | // reachable as well. | |
7 | ||
dfeec247 | 8 | use rustc_data_structures::fx::FxHashSet; |
dfeec247 XL |
9 | use rustc_hir as hir; |
10 | use rustc_hir::def::{DefKind, Res}; | |
17df50a5 | 11 | use rustc_hir::def_id::{DefId, LocalDefId}; |
5099ac24 | 12 | use rustc_hir::intravisit::{self, Visitor}; |
3dfed10e | 13 | use rustc_hir::Node; |
ba9703b0 XL |
14 | use rustc_middle::middle::codegen_fn_attrs::{CodegenFnAttrFlags, CodegenFnAttrs}; |
15 | use rustc_middle::middle::privacy; | |
16 | use rustc_middle::ty::query::Providers; | |
3dfed10e | 17 | use rustc_middle::ty::{self, DefIdTree, TyCtxt}; |
f9f354fc | 18 | use rustc_session::config::CrateType; |
83c7162d | 19 | use rustc_target::spec::abi::Abi; |
970d7e83 | 20 | |
970d7e83 LB |
21 | // Returns true if the given item must be inlined because it may be |
22 | // monomorphized or it was marked with `#[inline]`. This will only return | |
23 | // true for functions. | |
a2a8927a | 24 | fn item_might_be_inlined(tcx: TyCtxt<'_>, item: &hir::Item<'_>, attrs: &CodegenFnAttrs) -> bool { |
0531ce1d | 25 | if attrs.requests_inline() { |
dfeec247 | 26 | return true; |
970d7e83 LB |
27 | } |
28 | ||
e74abb32 | 29 | match item.kind { |
ba9703b0 | 30 | hir::ItemKind::Fn(ref sig, ..) if sig.header.is_const() => true, |
dfeec247 | 31 | hir::ItemKind::Impl { .. } | hir::ItemKind::Fn(..) => { |
6a06907d | 32 | let generics = tcx.generics_of(item.def_id); |
b7449926 | 33 | generics.requires_monomorphization(tcx) |
970d7e83 LB |
34 | } |
35 | _ => false, | |
36 | } | |
37 | } | |
38 | ||
416331ca XL |
39 | fn method_might_be_inlined( |
40 | tcx: TyCtxt<'_>, | |
dfeec247 | 41 | impl_item: &hir::ImplItem<'_>, |
ba9703b0 | 42 | impl_src: LocalDefId, |
dc9dc135 | 43 | ) -> bool { |
6a06907d XL |
44 | let codegen_fn_attrs = tcx.codegen_fn_attrs(impl_item.hir_id().owner.to_def_id()); |
45 | let generics = tcx.generics_of(impl_item.def_id); | |
b7449926 | 46 | if codegen_fn_attrs.requests_inline() || generics.requires_monomorphization(tcx) { |
dfeec247 | 47 | return true; |
1a4d82fc | 48 | } |
ba9703b0 | 49 | if let hir::ImplItemKind::Fn(method_sig, _) = &impl_item.kind { |
e1599b0c | 50 | if method_sig.header.is_const() { |
dfeec247 | 51 | return true; |
e1599b0c XL |
52 | } |
53 | } | |
5099ac24 | 54 | match tcx.hir().find_by_def_id(impl_src) { |
f9f354fc XL |
55 | Some(Node::Item(item)) => item_might_be_inlined(tcx, &item, codegen_fn_attrs), |
56 | Some(..) | None => span_bug!(impl_item.span, "impl did is not an item"), | |
970d7e83 | 57 | } |
970d7e83 LB |
58 | } |
59 | ||
60 | // Information needed while computing reachability. | |
f035d41b | 61 | struct ReachableContext<'tcx> { |
970d7e83 | 62 | // The type context. |
dc9dc135 | 63 | tcx: TyCtxt<'tcx>, |
3dfed10e | 64 | maybe_typeck_results: Option<&'tcx ty::TypeckResults<'tcx>>, |
970d7e83 | 65 | // The set of items which must be exported in the linkage sense. |
3dfed10e | 66 | reachable_symbols: FxHashSet<LocalDefId>, |
970d7e83 LB |
67 | // A worklist of item IDs. Each item ID in this worklist will be inlined |
68 | // and will be scanned for further references. | |
3dfed10e XL |
69 | // FIXME(eddyb) benchmark if this would be faster as a `VecDeque`. |
70 | worklist: Vec<LocalDefId>, | |
1a4d82fc JJ |
71 | // Whether any output of this compilation is a library |
72 | any_library: bool, | |
970d7e83 LB |
73 | } |
74 | ||
f035d41b | 75 | impl<'tcx> Visitor<'tcx> for ReachableContext<'tcx> { |
32a655c1 | 76 | fn visit_nested_body(&mut self, body: hir::BodyId) { |
3dfed10e XL |
77 | let old_maybe_typeck_results = |
78 | self.maybe_typeck_results.replace(self.tcx.typeck_body(body)); | |
0731742a | 79 | let body = self.tcx.hir().body(body); |
32a655c1 | 80 | self.visit_body(body); |
3dfed10e | 81 | self.maybe_typeck_results = old_maybe_typeck_results; |
476ff2be | 82 | } |
970d7e83 | 83 | |
dfeec247 | 84 | fn visit_expr(&mut self, expr: &'tcx hir::Expr<'tcx>) { |
e74abb32 | 85 | let res = match expr.kind { |
3dfed10e XL |
86 | hir::ExprKind::Path(ref qpath) => { |
87 | Some(self.typeck_results().qpath_res(qpath, expr.hir_id)) | |
88 | } | |
dfeec247 | 89 | hir::ExprKind::MethodCall(..) => self |
3dfed10e | 90 | .typeck_results() |
dfeec247 XL |
91 | .type_dependent_def(expr.hir_id) |
92 | .map(|(kind, def_id)| Res::Def(kind, def_id)), | |
93 | _ => None, | |
476ff2be SL |
94 | }; |
95 | ||
5e7ed085 FG |
96 | if let Some(res) = res && let Some(def_id) = res.opt_def_id().and_then(|el| el.as_local()) { |
97 | if self.def_id_represents_local_inlined_item(def_id.to_def_id()) { | |
98 | self.worklist.push(def_id); | |
99 | } else { | |
100 | match res { | |
101 | // If this path leads to a constant, then we need to | |
102 | // recurse into the constant to continue finding | |
103 | // items that are reachable. | |
104 | Res::Def(DefKind::Const | DefKind::AssocConst, _) => { | |
105 | self.worklist.push(def_id); | |
106 | } | |
92a42be0 | 107 | |
5e7ed085 FG |
108 | // If this wasn't a static, then the destination is |
109 | // surely reachable. | |
110 | _ => { | |
111 | self.reachable_symbols.insert(def_id); | |
970d7e83 | 112 | } |
970d7e83 | 113 | } |
1a4d82fc | 114 | } |
1a4d82fc | 115 | } |
970d7e83 | 116 | |
92a42be0 | 117 | intravisit::walk_expr(self, expr) |
1a4d82fc JJ |
118 | } |
119 | } | |
970d7e83 | 120 | |
f035d41b | 121 | impl<'tcx> ReachableContext<'tcx> { |
3dfed10e | 122 | /// Gets the type-checking results for the current body. |
f035d41b XL |
123 | /// As this will ICE if called outside bodies, only call when working with |
124 | /// `Expr` or `Pat` nodes (they are guaranteed to be found only in bodies). | |
125 | #[track_caller] | |
3dfed10e XL |
126 | fn typeck_results(&self) -> &'tcx ty::TypeckResults<'tcx> { |
127 | self.maybe_typeck_results | |
128 | .expect("`ReachableContext::typeck_results` called outside of body") | |
f035d41b XL |
129 | } |
130 | ||
970d7e83 LB |
131 | // Returns true if the given def ID represents a local item that is |
132 | // eligible for inlining and false otherwise. | |
e9174d1e | 133 | fn def_id_represents_local_inlined_item(&self, def_id: DefId) -> bool { |
5099ac24 FG |
134 | let Some(def_id) = def_id.as_local() else { |
135 | return false; | |
b039eaaf | 136 | }; |
970d7e83 | 137 | |
5099ac24 | 138 | match self.tcx.hir().find_by_def_id(def_id) { |
dfeec247 XL |
139 | Some(Node::Item(item)) => match item.kind { |
140 | hir::ItemKind::Fn(..) => { | |
141 | item_might_be_inlined(self.tcx, &item, self.tcx.codegen_fn_attrs(def_id)) | |
970d7e83 | 142 | } |
dfeec247 XL |
143 | _ => false, |
144 | }, | |
145 | Some(Node::TraitItem(trait_method)) => match trait_method.kind { | |
146 | hir::TraitItemKind::Const(_, ref default) => default.is_some(), | |
ba9703b0 XL |
147 | hir::TraitItemKind::Fn(_, hir::TraitFn::Provided(_)) => true, |
148 | hir::TraitItemKind::Fn(_, hir::TraitFn::Required(_)) | |
dfeec247 XL |
149 | | hir::TraitItemKind::Type(..) => false, |
150 | }, | |
923072b8 FG |
151 | Some(Node::ImplItem(impl_item)) => match impl_item.kind { |
152 | hir::ImplItemKind::Const(..) => true, | |
153 | hir::ImplItemKind::Fn(..) => { | |
154 | let hir_id = self.tcx.hir().local_def_id_to_hir_id(def_id); | |
155 | let impl_did = self.tcx.hir().get_parent_item(hir_id); | |
156 | method_might_be_inlined(self.tcx, impl_item, impl_did) | |
970d7e83 | 157 | } |
923072b8 FG |
158 | hir::ImplItemKind::TyAlias(_) => false, |
159 | }, | |
970d7e83 | 160 | Some(_) => false, |
dfeec247 | 161 | None => false, // This will happen for default methods. |
970d7e83 LB |
162 | } |
163 | } | |
164 | ||
1a4d82fc JJ |
165 | // Step 2: Mark all symbols that the symbols on the worklist touch. |
166 | fn propagate(&mut self) { | |
0bf4aa26 | 167 | let mut scanned = FxHashSet::default(); |
0531ce1d | 168 | while let Some(search_item) = self.worklist.pop() { |
1a4d82fc | 169 | if !scanned.insert(search_item) { |
dfeec247 | 170 | continue; |
1a4d82fc | 171 | } |
970d7e83 | 172 | |
5099ac24 | 173 | if let Some(ref item) = self.tcx.hir().find_by_def_id(search_item) { |
92a42be0 | 174 | self.propagate_node(item, search_item); |
1a4d82fc JJ |
175 | } |
176 | } | |
970d7e83 LB |
177 | } |
178 | ||
3dfed10e | 179 | fn propagate_node(&mut self, node: &Node<'tcx>, search_item: LocalDefId) { |
1a4d82fc | 180 | if !self.any_library { |
7453a54e SL |
181 | // If we are building an executable, only explicitly extern |
182 | // types need to be exported. | |
94222f64 XL |
183 | let reachable = |
184 | if let Node::Item(hir::Item { kind: hir::ItemKind::Fn(sig, ..), .. }) | |
185 | | Node::ImplItem(hir::ImplItem { | |
186 | kind: hir::ImplItemKind::Fn(sig, ..), .. | |
187 | }) = *node | |
188 | { | |
60c5eb7d | 189 | sig.header.abi != Abi::Rust |
7453a54e SL |
190 | } else { |
191 | false | |
192 | }; | |
04454e1e FG |
193 | let codegen_attrs = if self.tcx.def_kind(search_item).has_codegen_attrs() { |
194 | self.tcx.codegen_fn_attrs(search_item) | |
195 | } else { | |
196 | CodegenFnAttrs::EMPTY | |
197 | }; | |
94222f64 XL |
198 | let is_extern = codegen_attrs.contains_extern_indicator(); |
199 | let std_internal = | |
200 | codegen_attrs.flags.contains(CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL); | |
201 | if reachable || is_extern || std_internal { | |
202 | self.reachable_symbols.insert(search_item); | |
970d7e83 | 203 | } |
1a4d82fc JJ |
204 | } else { |
205 | // If we are building a library, then reachable symbols will | |
206 | // continue to participate in linkage after this product is | |
207 | // produced. In this case, we traverse the ast node, recursing on | |
208 | // all reachable nodes from this one. | |
970d7e83 | 209 | self.reachable_symbols.insert(search_item); |
1a4d82fc | 210 | } |
970d7e83 | 211 | |
1a4d82fc | 212 | match *node { |
b7449926 | 213 | Node::Item(item) => { |
e74abb32 | 214 | match item.kind { |
8faf50e0 | 215 | hir::ItemKind::Fn(.., body) => { |
6a06907d XL |
216 | if item_might_be_inlined( |
217 | self.tcx, | |
218 | &item, | |
219 | self.tcx.codegen_fn_attrs(item.def_id), | |
220 | ) { | |
32a655c1 | 221 | self.visit_nested_body(body); |
970d7e83 LB |
222 | } |
223 | } | |
1a4d82fc JJ |
224 | |
225 | // Reachable constants will be inlined into other crates | |
226 | // unconditionally, so we need to make sure that their | |
227 | // contents are also reachable. | |
17df50a5 | 228 | hir::ItemKind::Const(_, init) | hir::ItemKind::Static(_, _, init) => { |
32a655c1 | 229 | self.visit_nested_body(init); |
1a4d82fc JJ |
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 | |
dfeec247 XL |
235 | hir::ItemKind::ExternCrate(_) |
236 | | hir::ItemKind::Use(..) | |
237 | | hir::ItemKind::OpaqueTy(..) | |
238 | | hir::ItemKind::TyAlias(..) | |
94222f64 | 239 | | hir::ItemKind::Macro(..) |
dfeec247 | 240 | | hir::ItemKind::Mod(..) |
fc512014 | 241 | | hir::ItemKind::ForeignMod { .. } |
dfeec247 XL |
242 | | hir::ItemKind::Impl { .. } |
243 | | hir::ItemKind::Trait(..) | |
244 | | hir::ItemKind::TraitAlias(..) | |
245 | | hir::ItemKind::Struct(..) | |
246 | | hir::ItemKind::Enum(..) | |
247 | | hir::ItemKind::Union(..) | |
248 | | hir::ItemKind::GlobalAsm(..) => {} | |
970d7e83 | 249 | } |
1a4d82fc | 250 | } |
b7449926 | 251 | Node::TraitItem(trait_method) => { |
e74abb32 | 252 | match trait_method.kind { |
dfeec247 | 253 | hir::TraitItemKind::Const(_, None) |
ba9703b0 | 254 | | hir::TraitItemKind::Fn(_, hir::TraitFn::Required(_)) => { |
1a4d82fc JJ |
255 | // Keep going, nothing to get exported |
256 | } | |
dfeec247 | 257 | hir::TraitItemKind::Const(_, Some(body_id)) |
ba9703b0 | 258 | | hir::TraitItemKind::Fn(_, hir::TraitFn::Provided(body_id)) => { |
32a655c1 | 259 | self.visit_nested_body(body_id); |
d9579d0f | 260 | } |
32a655c1 | 261 | hir::TraitItemKind::Type(..) => {} |
970d7e83 | 262 | } |
1a4d82fc | 263 | } |
dfeec247 XL |
264 | Node::ImplItem(impl_item) => match impl_item.kind { |
265 | hir::ImplItemKind::Const(_, body) => { | |
266 | self.visit_nested_body(body); | |
267 | } | |
ba9703b0 | 268 | hir::ImplItemKind::Fn(_, body) => { |
04454e1e | 269 | let impl_def_id = self.tcx.local_parent(search_item); |
3dfed10e | 270 | if method_might_be_inlined(self.tcx, impl_item, impl_def_id) { |
dfeec247 | 271 | self.visit_nested_body(body) |
1a4d82fc | 272 | } |
970d7e83 | 273 | } |
f035d41b | 274 | hir::ImplItemKind::TyAlias(_) => {} |
dfeec247 | 275 | }, |
923072b8 | 276 | Node::Expr(&hir::Expr { kind: hir::ExprKind::Closure { body, .. }, .. }) => { |
3b2f2976 XL |
277 | self.visit_nested_body(body); |
278 | } | |
1a4d82fc | 279 | // Nothing to recurse on for these |
dfeec247 XL |
280 | Node::ForeignItem(_) |
281 | | Node::Variant(_) | |
282 | | Node::Ctor(..) | |
283 | | Node::Field(_) | |
284 | | Node::Ty(_) | |
94222f64 | 285 | | Node::Crate(_) => {} |
1a4d82fc | 286 | _ => { |
9fa01778 XL |
287 | bug!( |
288 | "found unexpected node kind in worklist: {} ({:?})", | |
3dfed10e XL |
289 | self.tcx |
290 | .hir() | |
291 | .node_to_string(self.tcx.hir().local_def_id_to_hir_id(search_item)), | |
9fa01778 XL |
292 | node, |
293 | ); | |
1a4d82fc | 294 | } |
970d7e83 LB |
295 | } |
296 | } | |
92a42be0 | 297 | } |
970d7e83 | 298 | |
923072b8 | 299 | fn check_item<'tcx>( |
dc9dc135 | 300 | tcx: TyCtxt<'tcx>, |
923072b8 FG |
301 | id: hir::ItemId, |
302 | worklist: &mut Vec<LocalDefId>, | |
303 | access_levels: &privacy::AccessLevels, | |
304 | ) { | |
305 | if has_custom_linkage(tcx, id.def_id) { | |
306 | worklist.push(id.def_id); | |
307 | } | |
92a42be0 | 308 | |
923072b8 FG |
309 | if !matches!(tcx.def_kind(id.def_id), DefKind::Impl) { |
310 | return; | |
94222f64 | 311 | } |
94222f64 | 312 | |
923072b8 FG |
313 | // We need only trait impls here, not inherent impls, and only non-exported ones |
314 | let item = tcx.hir().item(id); | |
315 | if let hir::ItemKind::Impl(hir::Impl { of_trait: Some(ref trait_ref), ref items, .. }) = | |
316 | item.kind | |
317 | { | |
318 | if !access_levels.is_reachable(item.def_id) { | |
319 | worklist.extend(items.iter().map(|ii_ref| ii_ref.id.def_id)); | |
476ff2be | 320 | |
923072b8 FG |
321 | let Res::Def(DefKind::Trait, trait_def_id) = trait_ref.path.res else { |
322 | unreachable!(); | |
323 | }; | |
476ff2be | 324 | |
923072b8 FG |
325 | if !trait_def_id.is_local() { |
326 | return; | |
970d7e83 | 327 | } |
32a655c1 | 328 | |
923072b8 FG |
329 | worklist.extend( |
330 | tcx.provided_trait_methods(trait_def_id).map(|assoc| assoc.def_id.expect_local()), | |
331 | ); | |
332 | } | |
476ff2be | 333 | } |
923072b8 | 334 | } |
fc512014 | 335 | |
923072b8 FG |
336 | fn has_custom_linkage<'tcx>(tcx: TyCtxt<'tcx>, def_id: LocalDefId) -> bool { |
337 | // Anything which has custom linkage gets thrown on the worklist no | |
338 | // matter where it is in the crate, along with "special std symbols" | |
339 | // which are currently akin to allocator symbols. | |
340 | if !tcx.def_kind(def_id).has_codegen_attrs() { | |
341 | return false; | |
fc512014 | 342 | } |
923072b8 FG |
343 | let codegen_attrs = tcx.codegen_fn_attrs(def_id); |
344 | codegen_attrs.contains_extern_indicator() | |
345 | || codegen_attrs.flags.contains(CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL) | |
346 | // FIXME(nbdd0121): `#[used]` are marked as reachable here so it's picked up by | |
347 | // `linked_symbols` in cg_ssa. They won't be exported in binary or cdylib due to their | |
348 | // `SymbolExportLevel::Rust` export level but may end up being exported in dylibs. | |
349 | || codegen_attrs.flags.contains(CodegenFnAttrFlags::USED) | |
350 | || codegen_attrs.flags.contains(CodegenFnAttrFlags::USED_LINKER) | |
970d7e83 LB |
351 | } |
352 | ||
17df50a5 XL |
353 | fn reachable_set<'tcx>(tcx: TyCtxt<'tcx>, (): ()) -> FxHashSet<LocalDefId> { |
354 | let access_levels = &tcx.privacy_access_levels(()); | |
92a42be0 | 355 | |
f9f354fc XL |
356 | let any_library = |
357 | tcx.sess.crate_types().iter().any(|ty| { | |
358 | *ty == CrateType::Rlib || *ty == CrateType::Dylib || *ty == CrateType::ProcMacro | |
359 | }); | |
32a655c1 | 360 | let mut reachable_context = ReachableContext { |
041b39d2 | 361 | tcx, |
3dfed10e | 362 | maybe_typeck_results: None, |
a1dfa0c6 | 363 | reachable_symbols: Default::default(), |
32a655c1 | 364 | worklist: Vec::new(), |
041b39d2 | 365 | any_library, |
32a655c1 | 366 | }; |
1a4d82fc JJ |
367 | |
368 | // Step 1: Seed the worklist with all nodes which were found to be public as | |
92a42be0 SL |
369 | // a result of the privacy pass along with all local lang items and impl items. |
370 | // If other crates link to us, they're going to expect to be able to | |
1a4d82fc JJ |
371 | // use the lang items, so we need to be sure to mark them as |
372 | // exported. | |
94222f64 | 373 | reachable_context.worklist.extend(access_levels.map.keys()); |
ea8adc8c | 374 | for item in tcx.lang_items().items().iter() { |
3dfed10e XL |
375 | if let Some(def_id) = *item { |
376 | if let Some(def_id) = def_id.as_local() { | |
377 | reachable_context.worklist.push(def_id); | |
1a4d82fc | 378 | } |
1a4d82fc JJ |
379 | } |
380 | } | |
92a42be0 | 381 | { |
923072b8 FG |
382 | // Some methods from non-exported (completely private) trait impls still have to be |
383 | // reachable if they are called from inlinable code. Generally, it's not known until | |
384 | // monomorphization if a specific trait impl item can be reachable or not. So, we | |
385 | // conservatively mark all of them as reachable. | |
386 | // FIXME: One possible strategy for pruning the reachable set is to avoid marking impl | |
387 | // items of non-exported traits (or maybe all local traits?) unless their respective | |
388 | // trait items are used from inlinable code through method call syntax or UFCS, or their | |
389 | // trait is a lang item. | |
390 | let crate_items = tcx.hir_crate_items(()); | |
391 | ||
392 | for id in crate_items.items() { | |
393 | check_item(tcx, id, &mut reachable_context.worklist, access_levels); | |
394 | } | |
395 | ||
396 | for id in crate_items.impl_items() { | |
397 | if has_custom_linkage(tcx, id.def_id) { | |
398 | reachable_context.worklist.push(id.def_id); | |
399 | } | |
400 | } | |
92a42be0 | 401 | } |
970d7e83 LB |
402 | |
403 | // Step 2: Mark all symbols that the symbols on the worklist touch. | |
404 | reachable_context.propagate(); | |
405 | ||
b7449926 XL |
406 | debug!("Inline reachability shows: {:?}", reachable_context.reachable_symbols); |
407 | ||
970d7e83 | 408 | // Return the set of reachable symbols. |
3dfed10e | 409 | reachable_context.reachable_symbols |
cc61c64b XL |
410 | } |
411 | ||
f035d41b | 412 | pub fn provide(providers: &mut Providers) { |
dfeec247 | 413 | *providers = Providers { reachable_set, ..*providers }; |
970d7e83 | 414 | } |