1use std::path::PathBuf;
209
210use rustc_attr_parsing::InlineAttr;
211use rustc_data_structures::fx::FxIndexMap;
212use rustc_data_structures::sync::{MTLock, par_for_each_in};
213use rustc_data_structures::unord::{UnordMap, UnordSet};
214use rustc_hir as hir;
215use rustc_hir::def::DefKind;
216use rustc_hir::def_id::{DefId, DefIdMap, LocalDefId};
217use rustc_hir::lang_items::LangItem;
218use rustc_middle::middle::codegen_fn_attrs::CodegenFnAttrFlags;
219use rustc_middle::mir::interpret::{AllocId, ErrorHandled, GlobalAlloc, Scalar};
220use rustc_middle::mir::mono::{CollectionMode, InstantiationMode, MonoItem};
221use rustc_middle::mir::visit::Visitor as MirVisitor;
222use rustc_middle::mir::{self, Location, MentionedItem, traversal};
223use rustc_middle::query::TyCtxtAt;
224use rustc_middle::ty::adjustment::{CustomCoerceUnsized, PointerCoercion};
225use rustc_middle::ty::layout::ValidityRequirement;
226use rustc_middle::ty::print::{shrunk_instance_name, with_no_trimmed_paths};
227use rustc_middle::ty::{
228 self, GenericArgs, GenericParamDefKind, Instance, InstanceKind, Interner, Ty, TyCtxt,
229 TypeFoldable, TypeVisitableExt, VtblEntry,
230};
231use rustc_middle::util::Providers;
232use rustc_middle::{bug, span_bug};
233use rustc_session::Limit;
234use rustc_session::config::EntryFnType;
235use rustc_span::source_map::{Spanned, dummy_spanned, respan};
236use rustc_span::{DUMMY_SP, Span};
237use tracing::{debug, instrument, trace};
238
239use crate::errors::{self, EncounteredErrorWhileInstantiating, NoOptimizedMir, RecursionLimit};
240
241#[derive(PartialEq)]
242pub(crate) enum MonoItemCollectionStrategy {
243 Eager,
244 Lazy,
245}
246
247struct SharedState<'tcx> {
249 visited: MTLock<UnordSet<MonoItem<'tcx>>>,
251 mentioned: MTLock<UnordSet<MonoItem<'tcx>>>,
254 usage_map: MTLock<UsageMap<'tcx>>,
256}
257
258pub(crate) struct UsageMap<'tcx> {
259 pub used_map: UnordMap<MonoItem<'tcx>, Vec<MonoItem<'tcx>>>,
261
262 user_map: UnordMap<MonoItem<'tcx>, Vec<MonoItem<'tcx>>>,
264}
265
266impl<'tcx> UsageMap<'tcx> {
267 fn new() -> UsageMap<'tcx> {
268 UsageMap { used_map: Default::default(), user_map: Default::default() }
269 }
270
271 fn record_used<'a>(&mut self, user_item: MonoItem<'tcx>, used_items: &'a MonoItems<'tcx>)
272 where
273 'tcx: 'a,
274 {
275 for used_item in used_items.items() {
276 self.user_map.entry(used_item).or_default().push(user_item);
277 }
278
279 assert!(self.used_map.insert(user_item, used_items.items().collect()).is_none());
280 }
281
282 pub(crate) fn get_user_items(&self, item: MonoItem<'tcx>) -> &[MonoItem<'tcx>] {
283 self.user_map.get(&item).map(|items| items.as_slice()).unwrap_or(&[])
284 }
285
286 pub(crate) fn for_each_inlined_used_item<F>(
288 &self,
289 tcx: TyCtxt<'tcx>,
290 item: MonoItem<'tcx>,
291 mut f: F,
292 ) where
293 F: FnMut(MonoItem<'tcx>),
294 {
295 let used_items = self.used_map.get(&item).unwrap();
296 for used_item in used_items.iter() {
297 let is_inlined = used_item.instantiation_mode(tcx) == InstantiationMode::LocalCopy;
298 if is_inlined {
299 f(*used_item);
300 }
301 }
302 }
303}
304
305struct MonoItems<'tcx> {
306 items: FxIndexMap<MonoItem<'tcx>, Span>,
309}
310
311impl<'tcx> MonoItems<'tcx> {
312 fn new() -> Self {
313 Self { items: FxIndexMap::default() }
314 }
315
316 fn is_empty(&self) -> bool {
317 self.items.is_empty()
318 }
319
320 fn push(&mut self, item: Spanned<MonoItem<'tcx>>) {
321 self.items.entry(item.node).or_insert(item.span);
324 }
325
326 fn items(&self) -> impl Iterator<Item = MonoItem<'tcx>> {
327 self.items.keys().cloned()
328 }
329}
330
331impl<'tcx> IntoIterator for MonoItems<'tcx> {
332 type Item = Spanned<MonoItem<'tcx>>;
333 type IntoIter = impl Iterator<Item = Spanned<MonoItem<'tcx>>>;
334
335 fn into_iter(self) -> Self::IntoIter {
336 self.items.into_iter().map(|(item, span)| respan(span, item))
337 }
338}
339
340impl<'tcx> Extend<Spanned<MonoItem<'tcx>>> for MonoItems<'tcx> {
341 fn extend<I>(&mut self, iter: I)
342 where
343 I: IntoIterator<Item = Spanned<MonoItem<'tcx>>>,
344 {
345 for item in iter {
346 self.push(item)
347 }
348 }
349}
350
351#[instrument(skip(tcx, state, recursion_depths, recursion_limit), level = "debug")]
357fn collect_items_rec<'tcx>(
358 tcx: TyCtxt<'tcx>,
359 starting_item: Spanned<MonoItem<'tcx>>,
360 state: &SharedState<'tcx>,
361 recursion_depths: &mut DefIdMap<usize>,
362 recursion_limit: Limit,
363 mode: CollectionMode,
364) {
365 if mode == CollectionMode::UsedItems {
366 if !state.visited.lock_mut().insert(starting_item.node) {
367 return;
369 }
370 } else {
371 if state.visited.lock().contains(&starting_item.node) {
372 return;
374 }
375 if !state.mentioned.lock_mut().insert(starting_item.node) {
376 return;
378 }
379 }
382
383 let mut used_items = MonoItems::new();
384 let mut mentioned_items = MonoItems::new();
385 let recursion_depth_reset;
386
387 let error_count = tcx.dcx().err_count();
411
412 match starting_item.node {
416 MonoItem::Static(def_id) => {
417 recursion_depth_reset = None;
418
419 if mode == CollectionMode::UsedItems {
422 let instance = Instance::mono(tcx, def_id);
423
424 debug_assert!(tcx.should_codegen_locally(instance));
426
427 let DefKind::Static { nested, .. } = tcx.def_kind(def_id) else { bug!() };
428 if !nested {
430 let ty = instance.ty(tcx, ty::TypingEnv::fully_monomorphized());
431 visit_drop_use(tcx, ty, true, starting_item.span, &mut used_items);
432 }
433
434 if let Ok(alloc) = tcx.eval_static_initializer(def_id) {
435 for &prov in alloc.inner().provenance().ptrs().values() {
436 collect_alloc(tcx, prov.alloc_id(), &mut used_items);
437 }
438 }
439
440 if tcx.needs_thread_local_shim(def_id) {
441 used_items.push(respan(
442 starting_item.span,
443 MonoItem::Fn(Instance {
444 def: InstanceKind::ThreadLocalShim(def_id),
445 args: GenericArgs::empty(),
446 }),
447 ));
448 }
449 }
450
451 }
455 MonoItem::Fn(instance) => {
456 debug_assert!(tcx.should_codegen_locally(instance));
458
459 recursion_depth_reset = Some(check_recursion_limit(
461 tcx,
462 instance,
463 starting_item.span,
464 recursion_depths,
465 recursion_limit,
466 ));
467
468 rustc_data_structures::stack::ensure_sufficient_stack(|| {
469 let (used, mentioned) = tcx.items_of_instance((instance, mode));
470 used_items.extend(used.into_iter().copied());
471 mentioned_items.extend(mentioned.into_iter().copied());
472 });
473 }
474 MonoItem::GlobalAsm(item_id) => {
475 assert!(
476 mode == CollectionMode::UsedItems,
477 "should never encounter global_asm when collecting mentioned items"
478 );
479 recursion_depth_reset = None;
480
481 let item = tcx.hir_item(item_id);
482 if let hir::ItemKind::GlobalAsm { asm, .. } = item.kind {
483 for (op, op_sp) in asm.operands {
484 match *op {
485 hir::InlineAsmOperand::Const { .. } => {
486 }
490 hir::InlineAsmOperand::SymFn { expr } => {
491 let fn_ty = tcx.typeck(item_id.owner_id).expr_ty(expr);
492 visit_fn_use(tcx, fn_ty, false, *op_sp, &mut used_items);
493 }
494 hir::InlineAsmOperand::SymStatic { path: _, def_id } => {
495 let instance = Instance::mono(tcx, def_id);
496 if tcx.should_codegen_locally(instance) {
497 trace!("collecting static {:?}", def_id);
498 used_items.push(dummy_spanned(MonoItem::Static(def_id)));
499 }
500 }
501 hir::InlineAsmOperand::In { .. }
502 | hir::InlineAsmOperand::Out { .. }
503 | hir::InlineAsmOperand::InOut { .. }
504 | hir::InlineAsmOperand::SplitInOut { .. }
505 | hir::InlineAsmOperand::Label { .. } => {
506 span_bug!(*op_sp, "invalid operand type for global_asm!")
507 }
508 }
509 }
510 } else {
511 span_bug!(item.span, "Mismatch between hir::Item type and MonoItem type")
512 }
513
514 }
516 };
517
518 if tcx.dcx().err_count() > error_count
521 && starting_item.node.is_generic_fn()
522 && starting_item.node.is_user_defined()
523 {
524 let formatted_item = with_no_trimmed_paths!(starting_item.node.to_string());
525 tcx.dcx().emit_note(EncounteredErrorWhileInstantiating {
526 span: starting_item.span,
527 formatted_item,
528 });
529 }
530 if mode == CollectionMode::UsedItems {
536 state.usage_map.lock_mut().record_used(starting_item.node, &used_items);
537 }
538
539 if mode == CollectionMode::MentionedItems {
540 assert!(used_items.is_empty(), "'mentioned' collection should never encounter used items");
541 } else {
542 for used_item in used_items {
543 collect_items_rec(
544 tcx,
545 used_item,
546 state,
547 recursion_depths,
548 recursion_limit,
549 CollectionMode::UsedItems,
550 );
551 }
552 }
553
554 for mentioned_item in mentioned_items {
557 collect_items_rec(
558 tcx,
559 mentioned_item,
560 state,
561 recursion_depths,
562 recursion_limit,
563 CollectionMode::MentionedItems,
564 );
565 }
566
567 if let Some((def_id, depth)) = recursion_depth_reset {
568 recursion_depths.insert(def_id, depth);
569 }
570}
571
572fn check_recursion_limit<'tcx>(
573 tcx: TyCtxt<'tcx>,
574 instance: Instance<'tcx>,
575 span: Span,
576 recursion_depths: &mut DefIdMap<usize>,
577 recursion_limit: Limit,
578) -> (DefId, usize) {
579 let def_id = instance.def_id();
580 let recursion_depth = recursion_depths.get(&def_id).cloned().unwrap_or(0);
581 debug!(" => recursion depth={}", recursion_depth);
582
583 let adjusted_recursion_depth = if tcx.is_lang_item(def_id, LangItem::DropInPlace) {
584 recursion_depth / 4
587 } else {
588 recursion_depth
589 };
590
591 if !recursion_limit.value_within_limit(adjusted_recursion_depth) {
595 let def_span = tcx.def_span(def_id);
596 let def_path_str = tcx.def_path_str(def_id);
597 let (shrunk, written_to_path) = shrunk_instance_name(tcx, instance);
598 let mut path = PathBuf::new();
599 let was_written = if let Some(written_to_path) = written_to_path {
600 path = written_to_path;
601 true
602 } else {
603 false
604 };
605 tcx.dcx().emit_fatal(RecursionLimit {
606 span,
607 shrunk,
608 def_span,
609 def_path_str,
610 was_written,
611 path,
612 });
613 }
614
615 recursion_depths.insert(def_id, recursion_depth + 1);
616
617 (def_id, recursion_depth)
618}
619
620struct MirUsedCollector<'a, 'tcx> {
621 tcx: TyCtxt<'tcx>,
622 body: &'a mir::Body<'tcx>,
623 used_items: &'a mut MonoItems<'tcx>,
624 used_mentioned_items: &'a mut UnordSet<MentionedItem<'tcx>>,
627 instance: Instance<'tcx>,
628}
629
630impl<'a, 'tcx> MirUsedCollector<'a, 'tcx> {
631 fn monomorphize<T>(&self, value: T) -> T
632 where
633 T: TypeFoldable<TyCtxt<'tcx>>,
634 {
635 trace!("monomorphize: self.instance={:?}", self.instance);
636 self.instance.instantiate_mir_and_normalize_erasing_regions(
637 self.tcx,
638 ty::TypingEnv::fully_monomorphized(),
639 ty::EarlyBinder::bind(value),
640 )
641 }
642
643 fn eval_constant(
645 &mut self,
646 constant: &mir::ConstOperand<'tcx>,
647 ) -> Option<mir::ConstValue<'tcx>> {
648 let const_ = self.monomorphize(constant.const_);
649 match const_.eval(self.tcx, ty::TypingEnv::fully_monomorphized(), constant.span) {
654 Ok(v) => Some(v),
655 Err(ErrorHandled::TooGeneric(..)) => span_bug!(
656 constant.span,
657 "collection encountered polymorphic constant: {:?}",
658 const_
659 ),
660 Err(err @ ErrorHandled::Reported(..)) => {
661 err.emit_note(self.tcx);
662 return None;
663 }
664 }
665 }
666}
667
668impl<'a, 'tcx> MirVisitor<'tcx> for MirUsedCollector<'a, 'tcx> {
669 fn visit_rvalue(&mut self, rvalue: &mir::Rvalue<'tcx>, location: Location) {
670 debug!("visiting rvalue {:?}", *rvalue);
671
672 let span = self.body.source_info(location).span;
673
674 match *rvalue {
675 mir::Rvalue::Cast(
679 mir::CastKind::PointerCoercion(PointerCoercion::Unsize, _)
680 | mir::CastKind::PointerCoercion(PointerCoercion::DynStar, _),
681 ref operand,
682 target_ty,
683 ) => {
684 let source_ty = operand.ty(self.body, self.tcx);
685 self.used_mentioned_items
687 .insert(MentionedItem::UnsizeCast { source_ty, target_ty });
688 let target_ty = self.monomorphize(target_ty);
689 let source_ty = self.monomorphize(source_ty);
690 let (source_ty, target_ty) =
691 find_vtable_types_for_unsizing(self.tcx.at(span), source_ty, target_ty);
692 if (target_ty.is_trait() && !source_ty.is_trait())
696 || (target_ty.is_dyn_star() && !source_ty.is_dyn_star())
697 {
698 create_mono_items_for_vtable_methods(
699 self.tcx,
700 target_ty,
701 source_ty,
702 span,
703 self.used_items,
704 );
705 }
706 }
707 mir::Rvalue::Cast(
708 mir::CastKind::PointerCoercion(PointerCoercion::ReifyFnPointer, _),
709 ref operand,
710 _,
711 ) => {
712 let fn_ty = operand.ty(self.body, self.tcx);
713 self.used_mentioned_items.insert(MentionedItem::Fn(fn_ty));
715 let fn_ty = self.monomorphize(fn_ty);
716 visit_fn_use(self.tcx, fn_ty, false, span, self.used_items);
717 }
718 mir::Rvalue::Cast(
719 mir::CastKind::PointerCoercion(PointerCoercion::ClosureFnPointer(_), _),
720 ref operand,
721 _,
722 ) => {
723 let source_ty = operand.ty(self.body, self.tcx);
724 self.used_mentioned_items.insert(MentionedItem::Closure(source_ty));
726 let source_ty = self.monomorphize(source_ty);
727 if let ty::Closure(def_id, args) = *source_ty.kind() {
728 let instance =
729 Instance::resolve_closure(self.tcx, def_id, args, ty::ClosureKind::FnOnce);
730 if self.tcx.should_codegen_locally(instance) {
731 self.used_items.push(create_fn_mono_item(self.tcx, instance, span));
732 }
733 } else {
734 bug!()
735 }
736 }
737 mir::Rvalue::ThreadLocalRef(def_id) => {
738 assert!(self.tcx.is_thread_local_static(def_id));
739 let instance = Instance::mono(self.tcx, def_id);
740 if self.tcx.should_codegen_locally(instance) {
741 trace!("collecting thread-local static {:?}", def_id);
742 self.used_items.push(respan(span, MonoItem::Static(def_id)));
743 }
744 }
745 _ => { }
746 }
747
748 self.super_rvalue(rvalue, location);
749 }
750
751 #[instrument(skip(self), level = "debug")]
754 fn visit_const_operand(&mut self, constant: &mir::ConstOperand<'tcx>, _location: Location) {
755 let Some(val) = self.eval_constant(constant) else { return };
757 collect_const_value(self.tcx, val, self.used_items);
758 }
759
760 fn visit_terminator(&mut self, terminator: &mir::Terminator<'tcx>, location: Location) {
761 debug!("visiting terminator {:?} @ {:?}", terminator, location);
762 let source = self.body.source_info(location).span;
763
764 let tcx = self.tcx;
765 let push_mono_lang_item = |this: &mut Self, lang_item: LangItem| {
766 let instance = Instance::mono(tcx, tcx.require_lang_item(lang_item, Some(source)));
767 if tcx.should_codegen_locally(instance) {
768 this.used_items.push(create_fn_mono_item(tcx, instance, source));
769 }
770 };
771
772 match terminator.kind {
773 mir::TerminatorKind::Call { ref func, .. }
774 | mir::TerminatorKind::TailCall { ref func, .. } => {
775 let callee_ty = func.ty(self.body, tcx);
776 self.used_mentioned_items.insert(MentionedItem::Fn(callee_ty));
778 let callee_ty = self.monomorphize(callee_ty);
779 visit_fn_use(self.tcx, callee_ty, true, source, &mut self.used_items)
780 }
781 mir::TerminatorKind::Drop { ref place, .. } => {
782 let ty = place.ty(self.body, self.tcx).ty;
783 self.used_mentioned_items.insert(MentionedItem::Drop(ty));
785 let ty = self.monomorphize(ty);
786 visit_drop_use(self.tcx, ty, true, source, self.used_items);
787 }
788 mir::TerminatorKind::InlineAsm { ref operands, .. } => {
789 for op in operands {
790 match *op {
791 mir::InlineAsmOperand::SymFn { ref value } => {
792 let fn_ty = value.const_.ty();
793 self.used_mentioned_items.insert(MentionedItem::Fn(fn_ty));
795 let fn_ty = self.monomorphize(fn_ty);
796 visit_fn_use(self.tcx, fn_ty, false, source, self.used_items);
797 }
798 mir::InlineAsmOperand::SymStatic { def_id } => {
799 let instance = Instance::mono(self.tcx, def_id);
800 if self.tcx.should_codegen_locally(instance) {
801 trace!("collecting asm sym static {:?}", def_id);
802 self.used_items.push(respan(source, MonoItem::Static(def_id)));
803 }
804 }
805 _ => {}
806 }
807 }
808 }
809 mir::TerminatorKind::Assert { ref msg, .. } => match &**msg {
810 mir::AssertKind::BoundsCheck { .. } => {
811 push_mono_lang_item(self, LangItem::PanicBoundsCheck);
812 }
813 mir::AssertKind::MisalignedPointerDereference { .. } => {
814 push_mono_lang_item(self, LangItem::PanicMisalignedPointerDereference);
815 }
816 mir::AssertKind::NullPointerDereference => {
817 push_mono_lang_item(self, LangItem::PanicNullPointerDereference);
818 }
819 _ => {
820 push_mono_lang_item(self, msg.panic_function());
821 }
822 },
823 mir::TerminatorKind::UnwindTerminate(reason) => {
824 push_mono_lang_item(self, reason.lang_item());
825 }
826 mir::TerminatorKind::Goto { .. }
827 | mir::TerminatorKind::SwitchInt { .. }
828 | mir::TerminatorKind::UnwindResume
829 | mir::TerminatorKind::Return
830 | mir::TerminatorKind::Unreachable => {}
831 mir::TerminatorKind::CoroutineDrop
832 | mir::TerminatorKind::Yield { .. }
833 | mir::TerminatorKind::FalseEdge { .. }
834 | mir::TerminatorKind::FalseUnwind { .. } => bug!(),
835 }
836
837 if let Some(mir::UnwindAction::Terminate(reason)) = terminator.unwind() {
838 push_mono_lang_item(self, reason.lang_item());
839 }
840
841 self.super_terminator(terminator, location);
842 }
843}
844
845fn visit_drop_use<'tcx>(
846 tcx: TyCtxt<'tcx>,
847 ty: Ty<'tcx>,
848 is_direct_call: bool,
849 source: Span,
850 output: &mut MonoItems<'tcx>,
851) {
852 let instance = Instance::resolve_drop_in_place(tcx, ty);
853 visit_instance_use(tcx, instance, is_direct_call, source, output);
854}
855
856fn visit_fn_use<'tcx>(
859 tcx: TyCtxt<'tcx>,
860 ty: Ty<'tcx>,
861 is_direct_call: bool,
862 source: Span,
863 output: &mut MonoItems<'tcx>,
864) {
865 if let ty::FnDef(def_id, args) = *ty.kind() {
866 let instance = if is_direct_call {
867 ty::Instance::expect_resolve(
868 tcx,
869 ty::TypingEnv::fully_monomorphized(),
870 def_id,
871 args,
872 source,
873 )
874 } else {
875 match ty::Instance::resolve_for_fn_ptr(
876 tcx,
877 ty::TypingEnv::fully_monomorphized(),
878 def_id,
879 args,
880 ) {
881 Some(instance) => instance,
882 _ => bug!("failed to resolve instance for {ty}"),
883 }
884 };
885 visit_instance_use(tcx, instance, is_direct_call, source, output);
886 }
887}
888
889fn visit_instance_use<'tcx>(
890 tcx: TyCtxt<'tcx>,
891 instance: ty::Instance<'tcx>,
892 is_direct_call: bool,
893 source: Span,
894 output: &mut MonoItems<'tcx>,
895) {
896 debug!("visit_item_use({:?}, is_direct_call={:?})", instance, is_direct_call);
897 if !tcx.should_codegen_locally(instance) {
898 return;
899 }
900 if let Some(intrinsic) = tcx.intrinsic(instance.def_id()) {
901 if let Some(_requirement) = ValidityRequirement::from_intrinsic(intrinsic.name) {
902 let def_id = tcx.require_lang_item(LangItem::PanicNounwind, None);
907 let panic_instance = Instance::mono(tcx, def_id);
908 if tcx.should_codegen_locally(panic_instance) {
909 output.push(create_fn_mono_item(tcx, panic_instance, source));
910 }
911 } else if !intrinsic.must_be_overridden {
912 let instance = ty::Instance::new(instance.def_id(), instance.args);
917 if tcx.should_codegen_locally(instance) {
918 output.push(create_fn_mono_item(tcx, instance, source));
919 }
920 }
921 }
922
923 match instance.def {
924 ty::InstanceKind::Virtual(..) | ty::InstanceKind::Intrinsic(_) => {
925 if !is_direct_call {
926 bug!("{:?} being reified", instance);
927 }
928 }
929 ty::InstanceKind::ThreadLocalShim(..) => {
930 bug!("{:?} being reified", instance);
931 }
932 ty::InstanceKind::DropGlue(_, None) | ty::InstanceKind::AsyncDropGlueCtorShim(_, None) => {
933 if !is_direct_call {
935 output.push(create_fn_mono_item(tcx, instance, source));
936 }
937 }
938 ty::InstanceKind::DropGlue(_, Some(_))
939 | ty::InstanceKind::AsyncDropGlueCtorShim(_, Some(_))
940 | ty::InstanceKind::VTableShim(..)
941 | ty::InstanceKind::ReifyShim(..)
942 | ty::InstanceKind::ClosureOnceShim { .. }
943 | ty::InstanceKind::ConstructCoroutineInClosureShim { .. }
944 | ty::InstanceKind::Item(..)
945 | ty::InstanceKind::FnPtrShim(..)
946 | ty::InstanceKind::CloneShim(..)
947 | ty::InstanceKind::FnPtrAddrShim(..) => {
948 output.push(create_fn_mono_item(tcx, instance, source));
949 }
950 }
951}
952
953fn should_codegen_locally<'tcx>(tcx: TyCtxt<'tcx>, instance: Instance<'tcx>) -> bool {
956 let Some(def_id) = instance.def.def_id_if_not_guaranteed_local_codegen() else {
957 return true;
958 };
959
960 if tcx.is_foreign_item(def_id) {
961 return false;
963 }
964
965 if tcx.def_kind(def_id).has_codegen_attrs()
966 && matches!(tcx.codegen_fn_attrs(def_id).inline, InlineAttr::Force { .. })
967 {
968 tcx.delay_bug("attempt to codegen `#[rustc_force_inline]` item");
971 }
972
973 if def_id.is_local() {
974 return true;
976 }
977
978 if tcx.is_reachable_non_generic(def_id) || instance.upstream_monomorphization(tcx).is_some() {
979 return false;
981 }
982
983 if let DefKind::Static { .. } = tcx.def_kind(def_id) {
984 return false;
986 }
987
988 if !tcx.is_mir_available(def_id) {
989 tcx.dcx().emit_fatal(NoOptimizedMir {
990 span: tcx.def_span(def_id),
991 crate_name: tcx.crate_name(def_id.krate),
992 });
993 }
994
995 true
996}
997
998fn find_vtable_types_for_unsizing<'tcx>(
1040 tcx: TyCtxtAt<'tcx>,
1041 source_ty: Ty<'tcx>,
1042 target_ty: Ty<'tcx>,
1043) -> (Ty<'tcx>, Ty<'tcx>) {
1044 let ptr_vtable = |inner_source: Ty<'tcx>, inner_target: Ty<'tcx>| {
1045 let typing_env = ty::TypingEnv::fully_monomorphized();
1046 if tcx.type_has_metadata(inner_source, typing_env) {
1047 (inner_source, inner_target)
1048 } else {
1049 tcx.struct_lockstep_tails_for_codegen(inner_source, inner_target, typing_env)
1050 }
1051 };
1052
1053 match (source_ty.kind(), target_ty.kind()) {
1054 (&ty::Ref(_, a, _), &ty::Ref(_, b, _) | &ty::RawPtr(b, _))
1055 | (&ty::RawPtr(a, _), &ty::RawPtr(b, _)) => ptr_vtable(a, b),
1056 (_, _)
1057 if let Some(source_boxed) = source_ty.boxed_ty()
1058 && let Some(target_boxed) = target_ty.boxed_ty() =>
1059 {
1060 ptr_vtable(source_boxed, target_boxed)
1061 }
1062
1063 (_, &ty::Dynamic(_, _, ty::DynStar)) => ptr_vtable(source_ty, target_ty),
1065
1066 (&ty::Adt(source_adt_def, source_args), &ty::Adt(target_adt_def, target_args)) => {
1067 assert_eq!(source_adt_def, target_adt_def);
1068
1069 let CustomCoerceUnsized::Struct(coerce_index) =
1070 match crate::custom_coerce_unsize_info(tcx, source_ty, target_ty) {
1071 Ok(ccu) => ccu,
1072 Err(e) => {
1073 let e = Ty::new_error(tcx.tcx, e);
1074 return (e, e);
1075 }
1076 };
1077
1078 let source_fields = &source_adt_def.non_enum_variant().fields;
1079 let target_fields = &target_adt_def.non_enum_variant().fields;
1080
1081 assert!(
1082 coerce_index.index() < source_fields.len()
1083 && source_fields.len() == target_fields.len()
1084 );
1085
1086 find_vtable_types_for_unsizing(
1087 tcx,
1088 source_fields[coerce_index].ty(*tcx, source_args),
1089 target_fields[coerce_index].ty(*tcx, target_args),
1090 )
1091 }
1092 _ => bug!(
1093 "find_vtable_types_for_unsizing: invalid coercion {:?} -> {:?}",
1094 source_ty,
1095 target_ty
1096 ),
1097 }
1098}
1099
1100#[instrument(skip(tcx), level = "debug", ret)]
1101fn create_fn_mono_item<'tcx>(
1102 tcx: TyCtxt<'tcx>,
1103 instance: Instance<'tcx>,
1104 source: Span,
1105) -> Spanned<MonoItem<'tcx>> {
1106 let def_id = instance.def_id();
1107 if tcx.sess.opts.unstable_opts.profile_closures
1108 && def_id.is_local()
1109 && tcx.is_closure_like(def_id)
1110 {
1111 crate::util::dump_closure_profile(tcx, instance);
1112 }
1113
1114 respan(source, MonoItem::Fn(instance))
1115}
1116
1117fn create_mono_items_for_vtable_methods<'tcx>(
1120 tcx: TyCtxt<'tcx>,
1121 trait_ty: Ty<'tcx>,
1122 impl_ty: Ty<'tcx>,
1123 source: Span,
1124 output: &mut MonoItems<'tcx>,
1125) {
1126 assert!(!trait_ty.has_escaping_bound_vars() && !impl_ty.has_escaping_bound_vars());
1127
1128 let ty::Dynamic(trait_ty, ..) = trait_ty.kind() else {
1129 bug!("create_mono_items_for_vtable_methods: {trait_ty:?} not a trait type");
1130 };
1131 if let Some(principal) = trait_ty.principal() {
1132 let trait_ref =
1133 tcx.instantiate_bound_regions_with_erased(principal.with_self_ty(tcx, impl_ty));
1134 assert!(!trait_ref.has_escaping_bound_vars());
1135
1136 let entries = tcx.vtable_entries(trait_ref);
1138 debug!(?entries);
1139 let methods = entries
1140 .iter()
1141 .filter_map(|entry| match entry {
1142 VtblEntry::MetadataDropInPlace
1143 | VtblEntry::MetadataSize
1144 | VtblEntry::MetadataAlign
1145 | VtblEntry::Vacant => None,
1146 VtblEntry::TraitVPtr(_) => {
1147 None
1149 }
1150 VtblEntry::Method(instance) => {
1151 Some(*instance).filter(|instance| tcx.should_codegen_locally(*instance))
1152 }
1153 })
1154 .map(|item| create_fn_mono_item(tcx, item, source));
1155 output.extend(methods);
1156 }
1157
1158 visit_drop_use(tcx, impl_ty, false, source, output);
1160}
1161
1162fn collect_alloc<'tcx>(tcx: TyCtxt<'tcx>, alloc_id: AllocId, output: &mut MonoItems<'tcx>) {
1164 match tcx.global_alloc(alloc_id) {
1165 GlobalAlloc::Static(def_id) => {
1166 assert!(!tcx.is_thread_local_static(def_id));
1167 let instance = Instance::mono(tcx, def_id);
1168 if tcx.should_codegen_locally(instance) {
1169 trace!("collecting static {:?}", def_id);
1170 output.push(dummy_spanned(MonoItem::Static(def_id)));
1171 }
1172 }
1173 GlobalAlloc::Memory(alloc) => {
1174 trace!("collecting {:?} with {:#?}", alloc_id, alloc);
1175 let ptrs = alloc.inner().provenance().ptrs();
1176 if !ptrs.is_empty() {
1178 rustc_data_structures::stack::ensure_sufficient_stack(move || {
1179 for &prov in ptrs.values() {
1180 collect_alloc(tcx, prov.alloc_id(), output);
1181 }
1182 });
1183 }
1184 }
1185 GlobalAlloc::Function { instance, .. } => {
1186 if tcx.should_codegen_locally(instance) {
1187 trace!("collecting {:?} with {:#?}", alloc_id, instance);
1188 output.push(create_fn_mono_item(tcx, instance, DUMMY_SP));
1189 }
1190 }
1191 GlobalAlloc::VTable(ty, dyn_ty) => {
1192 let alloc_id = tcx.vtable_allocation((
1193 ty,
1194 dyn_ty
1195 .principal()
1196 .map(|principal| tcx.instantiate_bound_regions_with_erased(principal)),
1197 ));
1198 collect_alloc(tcx, alloc_id, output)
1199 }
1200 }
1201}
1202
1203#[instrument(skip(tcx), level = "debug")]
1207fn collect_items_of_instance<'tcx>(
1208 tcx: TyCtxt<'tcx>,
1209 instance: Instance<'tcx>,
1210 mode: CollectionMode,
1211) -> (MonoItems<'tcx>, MonoItems<'tcx>) {
1212 tcx.ensure_ok().check_mono_item(instance);
1214
1215 let body = tcx.instance_mir(instance.def);
1216 let mut used_items = MonoItems::new();
1227 let mut mentioned_items = MonoItems::new();
1228 let mut used_mentioned_items = Default::default();
1229 let mut collector = MirUsedCollector {
1230 tcx,
1231 body,
1232 used_items: &mut used_items,
1233 used_mentioned_items: &mut used_mentioned_items,
1234 instance,
1235 };
1236
1237 if mode == CollectionMode::UsedItems {
1238 for (bb, data) in traversal::mono_reachable(body, tcx, instance) {
1239 collector.visit_basic_block_data(bb, data)
1240 }
1241 }
1242
1243 for const_op in body.required_consts() {
1246 if let Some(val) = collector.eval_constant(const_op) {
1247 collect_const_value(tcx, val, &mut mentioned_items);
1248 }
1249 }
1250
1251 for item in body.mentioned_items() {
1254 if !collector.used_mentioned_items.contains(&item.node) {
1255 let item_mono = collector.monomorphize(item.node);
1256 visit_mentioned_item(tcx, &item_mono, item.span, &mut mentioned_items);
1257 }
1258 }
1259
1260 (used_items, mentioned_items)
1261}
1262
1263fn items_of_instance<'tcx>(
1264 tcx: TyCtxt<'tcx>,
1265 (instance, mode): (Instance<'tcx>, CollectionMode),
1266) -> (&'tcx [Spanned<MonoItem<'tcx>>], &'tcx [Spanned<MonoItem<'tcx>>]) {
1267 let (used_items, mentioned_items) = collect_items_of_instance(tcx, instance, mode);
1268
1269 let used_items = tcx.arena.alloc_from_iter(used_items);
1270 let mentioned_items = tcx.arena.alloc_from_iter(mentioned_items);
1271
1272 (used_items, mentioned_items)
1273}
1274
1275#[instrument(skip(tcx, span, output), level = "debug")]
1277fn visit_mentioned_item<'tcx>(
1278 tcx: TyCtxt<'tcx>,
1279 item: &MentionedItem<'tcx>,
1280 span: Span,
1281 output: &mut MonoItems<'tcx>,
1282) {
1283 match *item {
1284 MentionedItem::Fn(ty) => {
1285 if let ty::FnDef(def_id, args) = *ty.kind() {
1286 let instance = Instance::expect_resolve(
1287 tcx,
1288 ty::TypingEnv::fully_monomorphized(),
1289 def_id,
1290 args,
1291 span,
1292 );
1293 visit_instance_use(tcx, instance, true, span, output);
1298 }
1299 }
1300 MentionedItem::Drop(ty) => {
1301 visit_drop_use(tcx, ty, true, span, output);
1302 }
1303 MentionedItem::UnsizeCast { source_ty, target_ty } => {
1304 let (source_ty, target_ty) =
1305 find_vtable_types_for_unsizing(tcx.at(span), source_ty, target_ty);
1306 if (target_ty.is_trait() && !source_ty.is_trait())
1310 || (target_ty.is_dyn_star() && !source_ty.is_dyn_star())
1311 {
1312 create_mono_items_for_vtable_methods(tcx, target_ty, source_ty, span, output);
1313 }
1314 }
1315 MentionedItem::Closure(source_ty) => {
1316 if let ty::Closure(def_id, args) = *source_ty.kind() {
1317 let instance =
1318 Instance::resolve_closure(tcx, def_id, args, ty::ClosureKind::FnOnce);
1319 if tcx.should_codegen_locally(instance) {
1320 output.push(create_fn_mono_item(tcx, instance, span));
1321 }
1322 } else {
1323 bug!()
1324 }
1325 }
1326 }
1327}
1328
1329#[instrument(skip(tcx, output), level = "debug")]
1330fn collect_const_value<'tcx>(
1331 tcx: TyCtxt<'tcx>,
1332 value: mir::ConstValue<'tcx>,
1333 output: &mut MonoItems<'tcx>,
1334) {
1335 match value {
1336 mir::ConstValue::Scalar(Scalar::Ptr(ptr, _size)) => {
1337 collect_alloc(tcx, ptr.provenance.alloc_id(), output)
1338 }
1339 mir::ConstValue::Indirect { alloc_id, .. } => collect_alloc(tcx, alloc_id, output),
1340 mir::ConstValue::Slice { data, meta: _ } => {
1341 for &prov in data.inner().provenance().ptrs().values() {
1342 collect_alloc(tcx, prov.alloc_id(), output);
1343 }
1344 }
1345 _ => {}
1346 }
1347}
1348
1349#[instrument(skip(tcx, mode), level = "debug")]
1356fn collect_roots(tcx: TyCtxt<'_>, mode: MonoItemCollectionStrategy) -> Vec<MonoItem<'_>> {
1357 debug!("collecting roots");
1358 let mut roots = MonoItems::new();
1359
1360 {
1361 let entry_fn = tcx.entry_fn(());
1362
1363 debug!("collect_roots: entry_fn = {:?}", entry_fn);
1364
1365 let mut collector = RootCollector { tcx, strategy: mode, entry_fn, output: &mut roots };
1366
1367 let crate_items = tcx.hir_crate_items(());
1368
1369 for id in crate_items.free_items() {
1370 collector.process_item(id);
1371 }
1372
1373 for id in crate_items.impl_items() {
1374 collector.process_impl_item(id);
1375 }
1376
1377 for id in crate_items.nested_bodies() {
1378 collector.process_nested_body(id);
1379 }
1380
1381 collector.push_extra_entry_roots();
1382 }
1383
1384 roots
1388 .into_iter()
1389 .filter_map(|Spanned { node: mono_item, .. }| {
1390 mono_item.is_instantiable(tcx).then_some(mono_item)
1391 })
1392 .collect()
1393}
1394
1395struct RootCollector<'a, 'tcx> {
1396 tcx: TyCtxt<'tcx>,
1397 strategy: MonoItemCollectionStrategy,
1398 output: &'a mut MonoItems<'tcx>,
1399 entry_fn: Option<(DefId, EntryFnType)>,
1400}
1401
1402impl<'v> RootCollector<'_, 'v> {
1403 fn process_item(&mut self, id: hir::ItemId) {
1404 match self.tcx.def_kind(id.owner_id) {
1405 DefKind::Enum | DefKind::Struct | DefKind::Union => {
1406 if self.strategy == MonoItemCollectionStrategy::Eager
1407 && !self.tcx.generics_of(id.owner_id).requires_monomorphization(self.tcx)
1408 {
1409 debug!("RootCollector: ADT drop-glue for `{id:?}`",);
1410 let id_args =
1411 ty::GenericArgs::for_item(self.tcx, id.owner_id.to_def_id(), |param, _| {
1412 match param.kind {
1413 GenericParamDefKind::Lifetime => {
1414 self.tcx.lifetimes.re_erased.into()
1415 }
1416 GenericParamDefKind::Type { .. }
1417 | GenericParamDefKind::Const { .. } => {
1418 unreachable!(
1419 "`own_requires_monomorphization` check means that \
1420 we should have no type/const params"
1421 )
1422 }
1423 }
1424 });
1425
1426 if self.tcx.instantiate_and_check_impossible_predicates((
1429 id.owner_id.to_def_id(),
1430 id_args,
1431 )) {
1432 return;
1433 }
1434
1435 let ty =
1436 self.tcx.type_of(id.owner_id.to_def_id()).instantiate(self.tcx, id_args);
1437 assert!(!ty.has_non_region_param());
1438 visit_drop_use(self.tcx, ty, true, DUMMY_SP, self.output);
1439 }
1440 }
1441 DefKind::GlobalAsm => {
1442 debug!(
1443 "RootCollector: ItemKind::GlobalAsm({})",
1444 self.tcx.def_path_str(id.owner_id)
1445 );
1446 self.output.push(dummy_spanned(MonoItem::GlobalAsm(id)));
1447 }
1448 DefKind::Static { .. } => {
1449 let def_id = id.owner_id.to_def_id();
1450 debug!("RootCollector: ItemKind::Static({})", self.tcx.def_path_str(def_id));
1451 self.output.push(dummy_spanned(MonoItem::Static(def_id)));
1452 }
1453 DefKind::Const => {
1454 if !self.tcx.generics_of(id.owner_id).requires_monomorphization(self.tcx)
1460 && let Ok(val) = self.tcx.const_eval_poly(id.owner_id.to_def_id())
1461 {
1462 collect_const_value(self.tcx, val, self.output);
1463 }
1464 }
1465 DefKind::Impl { .. } => {
1466 if self.strategy == MonoItemCollectionStrategy::Eager {
1467 create_mono_items_for_default_impls(self.tcx, id, self.output);
1468 }
1469 }
1470 DefKind::Fn => {
1471 self.push_if_root(id.owner_id.def_id);
1472 }
1473 _ => {}
1474 }
1475 }
1476
1477 fn process_impl_item(&mut self, id: hir::ImplItemId) {
1478 if matches!(self.tcx.def_kind(id.owner_id), DefKind::AssocFn) {
1479 self.push_if_root(id.owner_id.def_id);
1480 }
1481 }
1482
1483 fn process_nested_body(&mut self, def_id: LocalDefId) {
1484 match self.tcx.def_kind(def_id) {
1485 DefKind::Closure => {
1486 if self.strategy == MonoItemCollectionStrategy::Eager
1487 && !self
1488 .tcx
1489 .generics_of(self.tcx.typeck_root_def_id(def_id.to_def_id()))
1490 .requires_monomorphization(self.tcx)
1491 {
1492 let instance = match *self.tcx.type_of(def_id).instantiate_identity().kind() {
1493 ty::Closure(def_id, args)
1494 | ty::Coroutine(def_id, args)
1495 | ty::CoroutineClosure(def_id, args) => {
1496 Instance::new(def_id, self.tcx.erase_regions(args))
1497 }
1498 _ => unreachable!(),
1499 };
1500 let Ok(instance) = self.tcx.try_normalize_erasing_regions(
1501 ty::TypingEnv::fully_monomorphized(),
1502 instance,
1503 ) else {
1504 return;
1506 };
1507 let mono_item = create_fn_mono_item(self.tcx, instance, DUMMY_SP);
1508 if mono_item.node.is_instantiable(self.tcx) {
1509 self.output.push(mono_item);
1510 }
1511 }
1512 }
1513 _ => {}
1514 }
1515 }
1516
1517 fn is_root(&self, def_id: LocalDefId) -> bool {
1518 !self.tcx.generics_of(def_id).requires_monomorphization(self.tcx)
1519 && match self.strategy {
1520 MonoItemCollectionStrategy::Eager => {
1521 !matches!(self.tcx.codegen_fn_attrs(def_id).inline, InlineAttr::Force { .. })
1522 }
1523 MonoItemCollectionStrategy::Lazy => {
1524 self.entry_fn.and_then(|(id, _)| id.as_local()) == Some(def_id)
1525 || self.tcx.is_reachable_non_generic(def_id)
1526 || self
1527 .tcx
1528 .codegen_fn_attrs(def_id)
1529 .flags
1530 .contains(CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL)
1531 }
1532 }
1533 }
1534
1535 #[instrument(skip(self), level = "debug")]
1538 fn push_if_root(&mut self, def_id: LocalDefId) {
1539 if self.is_root(def_id) {
1540 debug!("found root");
1541
1542 let instance = Instance::mono(self.tcx, def_id.to_def_id());
1543 self.output.push(create_fn_mono_item(self.tcx, instance, DUMMY_SP));
1544 }
1545 }
1546
1547 fn push_extra_entry_roots(&mut self) {
1553 let Some((main_def_id, EntryFnType::Main { .. })) = self.entry_fn else {
1554 return;
1555 };
1556
1557 let Some(start_def_id) = self.tcx.lang_items().start_fn() else {
1558 self.tcx.dcx().emit_fatal(errors::StartNotFound);
1559 };
1560 let main_ret_ty = self.tcx.fn_sig(main_def_id).no_bound_vars().unwrap().output();
1561
1562 let main_ret_ty = self.tcx.normalize_erasing_regions(
1568 ty::TypingEnv::fully_monomorphized(),
1569 main_ret_ty.no_bound_vars().unwrap(),
1570 );
1571
1572 let start_instance = Instance::expect_resolve(
1573 self.tcx,
1574 ty::TypingEnv::fully_monomorphized(),
1575 start_def_id,
1576 self.tcx.mk_args(&[main_ret_ty.into()]),
1577 DUMMY_SP,
1578 );
1579
1580 self.output.push(create_fn_mono_item(self.tcx, start_instance, DUMMY_SP));
1581 }
1582}
1583
1584#[instrument(level = "debug", skip(tcx, output))]
1585fn create_mono_items_for_default_impls<'tcx>(
1586 tcx: TyCtxt<'tcx>,
1587 item: hir::ItemId,
1588 output: &mut MonoItems<'tcx>,
1589) {
1590 let Some(impl_) = tcx.impl_trait_header(item.owner_id) else {
1591 return;
1592 };
1593
1594 if matches!(impl_.polarity, ty::ImplPolarity::Negative) {
1595 return;
1596 }
1597
1598 if tcx.generics_of(item.owner_id).own_requires_monomorphization() {
1599 return;
1600 }
1601
1602 let only_region_params = |param: &ty::GenericParamDef, _: &_| match param.kind {
1608 GenericParamDefKind::Lifetime => tcx.lifetimes.re_erased.into(),
1609 GenericParamDefKind::Type { .. } | GenericParamDefKind::Const { .. } => {
1610 unreachable!(
1611 "`own_requires_monomorphization` check means that \
1612 we should have no type/const params"
1613 )
1614 }
1615 };
1616 let impl_args = GenericArgs::for_item(tcx, item.owner_id.to_def_id(), only_region_params);
1617 let trait_ref = impl_.trait_ref.instantiate(tcx, impl_args);
1618
1619 if tcx.instantiate_and_check_impossible_predicates((item.owner_id.to_def_id(), impl_args)) {
1629 return;
1630 }
1631
1632 let typing_env = ty::TypingEnv::fully_monomorphized();
1633 let trait_ref = tcx.normalize_erasing_regions(typing_env, trait_ref);
1634 let overridden_methods = tcx.impl_item_implementor_ids(item.owner_id);
1635 for method in tcx.provided_trait_methods(trait_ref.def_id) {
1636 if overridden_methods.contains_key(&method.def_id) {
1637 continue;
1638 }
1639
1640 if tcx.generics_of(method.def_id).own_requires_monomorphization() {
1641 continue;
1642 }
1643
1644 let args = trait_ref.args.extend_to(tcx, method.def_id, only_region_params);
1648 let instance = ty::Instance::expect_resolve(tcx, typing_env, method.def_id, args, DUMMY_SP);
1649
1650 let mono_item = create_fn_mono_item(tcx, instance, DUMMY_SP);
1651 if mono_item.node.is_instantiable(tcx) && tcx.should_codegen_locally(instance) {
1652 output.push(mono_item);
1653 }
1654 }
1655}
1656
1657#[instrument(skip(tcx, strategy), level = "debug")]
1662pub(crate) fn collect_crate_mono_items<'tcx>(
1663 tcx: TyCtxt<'tcx>,
1664 strategy: MonoItemCollectionStrategy,
1665) -> (Vec<MonoItem<'tcx>>, UsageMap<'tcx>) {
1666 let _prof_timer = tcx.prof.generic_activity("monomorphization_collector");
1667
1668 let roots = tcx
1669 .sess
1670 .time("monomorphization_collector_root_collections", || collect_roots(tcx, strategy));
1671
1672 debug!("building mono item graph, beginning at roots");
1673
1674 let state = SharedState {
1675 visited: MTLock::new(UnordSet::default()),
1676 mentioned: MTLock::new(UnordSet::default()),
1677 usage_map: MTLock::new(UsageMap::new()),
1678 };
1679 let recursion_limit = tcx.recursion_limit();
1680
1681 tcx.sess.time("monomorphization_collector_graph_walk", || {
1682 par_for_each_in(roots, |root| {
1683 let mut recursion_depths = DefIdMap::default();
1684 collect_items_rec(
1685 tcx,
1686 dummy_spanned(root),
1687 &state,
1688 &mut recursion_depths,
1689 recursion_limit,
1690 CollectionMode::UsedItems,
1691 );
1692 });
1693 });
1694
1695 let mono_items = tcx.with_stable_hashing_context(move |ref hcx| {
1698 state.visited.into_inner().into_sorted(hcx, true)
1699 });
1700
1701 (mono_items, state.usage_map.into_inner())
1702}
1703
1704pub(crate) fn provide(providers: &mut Providers) {
1705 providers.hooks.should_codegen_locally = should_codegen_locally;
1706 providers.items_of_instance = items_of_instance;
1707}