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, Ty, TyCtxt, TypeFoldable,
229 TypeVisitableExt, VtblEntry,
230};
231use rustc_middle::util::Providers;
232use rustc_middle::{bug, span_bug};
233use rustc_session::Limit;
234use rustc_session::config::{DebugInfo, 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.dcx().delayed_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 if tcx.sess.opts.debuginfo == DebugInfo::Full {
1239 for var_debug_info in &body.var_debug_info {
1240 collector.visit_var_debug_info(var_debug_info);
1241 }
1242 }
1243 for (bb, data) in traversal::mono_reachable(body, tcx, instance) {
1244 collector.visit_basic_block_data(bb, data)
1245 }
1246 }
1247
1248 for const_op in body.required_consts() {
1251 if let Some(val) = collector.eval_constant(const_op) {
1252 collect_const_value(tcx, val, &mut mentioned_items);
1253 }
1254 }
1255
1256 for item in body.mentioned_items() {
1259 if !collector.used_mentioned_items.contains(&item.node) {
1260 let item_mono = collector.monomorphize(item.node);
1261 visit_mentioned_item(tcx, &item_mono, item.span, &mut mentioned_items);
1262 }
1263 }
1264
1265 (used_items, mentioned_items)
1266}
1267
1268fn items_of_instance<'tcx>(
1269 tcx: TyCtxt<'tcx>,
1270 (instance, mode): (Instance<'tcx>, CollectionMode),
1271) -> (&'tcx [Spanned<MonoItem<'tcx>>], &'tcx [Spanned<MonoItem<'tcx>>]) {
1272 let (used_items, mentioned_items) = collect_items_of_instance(tcx, instance, mode);
1273
1274 let used_items = tcx.arena.alloc_from_iter(used_items);
1275 let mentioned_items = tcx.arena.alloc_from_iter(mentioned_items);
1276
1277 (used_items, mentioned_items)
1278}
1279
1280#[instrument(skip(tcx, span, output), level = "debug")]
1282fn visit_mentioned_item<'tcx>(
1283 tcx: TyCtxt<'tcx>,
1284 item: &MentionedItem<'tcx>,
1285 span: Span,
1286 output: &mut MonoItems<'tcx>,
1287) {
1288 match *item {
1289 MentionedItem::Fn(ty) => {
1290 if let ty::FnDef(def_id, args) = *ty.kind() {
1291 let instance = Instance::expect_resolve(
1292 tcx,
1293 ty::TypingEnv::fully_monomorphized(),
1294 def_id,
1295 args,
1296 span,
1297 );
1298 visit_instance_use(tcx, instance, true, span, output);
1303 }
1304 }
1305 MentionedItem::Drop(ty) => {
1306 visit_drop_use(tcx, ty, true, span, output);
1307 }
1308 MentionedItem::UnsizeCast { source_ty, target_ty } => {
1309 let (source_ty, target_ty) =
1310 find_vtable_types_for_unsizing(tcx.at(span), source_ty, target_ty);
1311 if (target_ty.is_trait() && !source_ty.is_trait())
1315 || (target_ty.is_dyn_star() && !source_ty.is_dyn_star())
1316 {
1317 create_mono_items_for_vtable_methods(tcx, target_ty, source_ty, span, output);
1318 }
1319 }
1320 MentionedItem::Closure(source_ty) => {
1321 if let ty::Closure(def_id, args) = *source_ty.kind() {
1322 let instance =
1323 Instance::resolve_closure(tcx, def_id, args, ty::ClosureKind::FnOnce);
1324 if tcx.should_codegen_locally(instance) {
1325 output.push(create_fn_mono_item(tcx, instance, span));
1326 }
1327 } else {
1328 bug!()
1329 }
1330 }
1331 }
1332}
1333
1334#[instrument(skip(tcx, output), level = "debug")]
1335fn collect_const_value<'tcx>(
1336 tcx: TyCtxt<'tcx>,
1337 value: mir::ConstValue<'tcx>,
1338 output: &mut MonoItems<'tcx>,
1339) {
1340 match value {
1341 mir::ConstValue::Scalar(Scalar::Ptr(ptr, _size)) => {
1342 collect_alloc(tcx, ptr.provenance.alloc_id(), output)
1343 }
1344 mir::ConstValue::Indirect { alloc_id, .. } => collect_alloc(tcx, alloc_id, output),
1345 mir::ConstValue::Slice { data, meta: _ } => {
1346 for &prov in data.inner().provenance().ptrs().values() {
1347 collect_alloc(tcx, prov.alloc_id(), output);
1348 }
1349 }
1350 _ => {}
1351 }
1352}
1353
1354#[instrument(skip(tcx, mode), level = "debug")]
1361fn collect_roots(tcx: TyCtxt<'_>, mode: MonoItemCollectionStrategy) -> Vec<MonoItem<'_>> {
1362 debug!("collecting roots");
1363 let mut roots = MonoItems::new();
1364
1365 {
1366 let entry_fn = tcx.entry_fn(());
1367
1368 debug!("collect_roots: entry_fn = {:?}", entry_fn);
1369
1370 let mut collector = RootCollector { tcx, strategy: mode, entry_fn, output: &mut roots };
1371
1372 let crate_items = tcx.hir_crate_items(());
1373
1374 for id in crate_items.free_items() {
1375 collector.process_item(id);
1376 }
1377
1378 for id in crate_items.impl_items() {
1379 collector.process_impl_item(id);
1380 }
1381
1382 for id in crate_items.nested_bodies() {
1383 collector.process_nested_body(id);
1384 }
1385
1386 collector.push_extra_entry_roots();
1387 }
1388
1389 roots
1393 .into_iter()
1394 .filter_map(|Spanned { node: mono_item, .. }| {
1395 mono_item.is_instantiable(tcx).then_some(mono_item)
1396 })
1397 .collect()
1398}
1399
1400struct RootCollector<'a, 'tcx> {
1401 tcx: TyCtxt<'tcx>,
1402 strategy: MonoItemCollectionStrategy,
1403 output: &'a mut MonoItems<'tcx>,
1404 entry_fn: Option<(DefId, EntryFnType)>,
1405}
1406
1407impl<'v> RootCollector<'_, 'v> {
1408 fn process_item(&mut self, id: hir::ItemId) {
1409 match self.tcx.def_kind(id.owner_id) {
1410 DefKind::Enum | DefKind::Struct | DefKind::Union => {
1411 if self.strategy == MonoItemCollectionStrategy::Eager
1412 && !self.tcx.generics_of(id.owner_id).requires_monomorphization(self.tcx)
1413 {
1414 debug!("RootCollector: ADT drop-glue for `{id:?}`",);
1415 let id_args =
1416 ty::GenericArgs::for_item(self.tcx, id.owner_id.to_def_id(), |param, _| {
1417 match param.kind {
1418 GenericParamDefKind::Lifetime => {
1419 self.tcx.lifetimes.re_erased.into()
1420 }
1421 GenericParamDefKind::Type { .. }
1422 | GenericParamDefKind::Const { .. } => {
1423 unreachable!(
1424 "`own_requires_monomorphization` check means that \
1425 we should have no type/const params"
1426 )
1427 }
1428 }
1429 });
1430
1431 if self.tcx.instantiate_and_check_impossible_predicates((
1434 id.owner_id.to_def_id(),
1435 id_args,
1436 )) {
1437 return;
1438 }
1439
1440 let ty =
1441 self.tcx.type_of(id.owner_id.to_def_id()).instantiate(self.tcx, id_args);
1442 assert!(!ty.has_non_region_param());
1443 visit_drop_use(self.tcx, ty, true, DUMMY_SP, self.output);
1444 }
1445 }
1446 DefKind::GlobalAsm => {
1447 debug!(
1448 "RootCollector: ItemKind::GlobalAsm({})",
1449 self.tcx.def_path_str(id.owner_id)
1450 );
1451 self.output.push(dummy_spanned(MonoItem::GlobalAsm(id)));
1452 }
1453 DefKind::Static { .. } => {
1454 let def_id = id.owner_id.to_def_id();
1455 debug!("RootCollector: ItemKind::Static({})", self.tcx.def_path_str(def_id));
1456 self.output.push(dummy_spanned(MonoItem::Static(def_id)));
1457 }
1458 DefKind::Const => {
1459 if !self.tcx.generics_of(id.owner_id).requires_monomorphization(self.tcx)
1465 && let Ok(val) = self.tcx.const_eval_poly(id.owner_id.to_def_id())
1466 {
1467 collect_const_value(self.tcx, val, self.output);
1468 }
1469 }
1470 DefKind::Impl { .. } => {
1471 if self.strategy == MonoItemCollectionStrategy::Eager {
1472 create_mono_items_for_default_impls(self.tcx, id, self.output);
1473 }
1474 }
1475 DefKind::Fn => {
1476 self.push_if_root(id.owner_id.def_id);
1477 }
1478 _ => {}
1479 }
1480 }
1481
1482 fn process_impl_item(&mut self, id: hir::ImplItemId) {
1483 if matches!(self.tcx.def_kind(id.owner_id), DefKind::AssocFn) {
1484 self.push_if_root(id.owner_id.def_id);
1485 }
1486 }
1487
1488 fn process_nested_body(&mut self, def_id: LocalDefId) {
1489 match self.tcx.def_kind(def_id) {
1490 DefKind::Closure => {
1491 if self.strategy == MonoItemCollectionStrategy::Eager
1492 && !self
1493 .tcx
1494 .generics_of(self.tcx.typeck_root_def_id(def_id.to_def_id()))
1495 .requires_monomorphization(self.tcx)
1496 {
1497 let instance = match *self.tcx.type_of(def_id).instantiate_identity().kind() {
1498 ty::Closure(def_id, args)
1499 | ty::Coroutine(def_id, args)
1500 | ty::CoroutineClosure(def_id, args) => {
1501 Instance::new(def_id, self.tcx.erase_regions(args))
1502 }
1503 _ => unreachable!(),
1504 };
1505 let Ok(instance) = self.tcx.try_normalize_erasing_regions(
1506 ty::TypingEnv::fully_monomorphized(),
1507 instance,
1508 ) else {
1509 return;
1511 };
1512 let mono_item = create_fn_mono_item(self.tcx, instance, DUMMY_SP);
1513 if mono_item.node.is_instantiable(self.tcx) {
1514 self.output.push(mono_item);
1515 }
1516 }
1517 }
1518 _ => {}
1519 }
1520 }
1521
1522 fn is_root(&self, def_id: LocalDefId) -> bool {
1523 !self.tcx.generics_of(def_id).requires_monomorphization(self.tcx)
1524 && match self.strategy {
1525 MonoItemCollectionStrategy::Eager => {
1526 !matches!(self.tcx.codegen_fn_attrs(def_id).inline, InlineAttr::Force { .. })
1527 }
1528 MonoItemCollectionStrategy::Lazy => {
1529 self.entry_fn.and_then(|(id, _)| id.as_local()) == Some(def_id)
1530 || self.tcx.is_reachable_non_generic(def_id)
1531 || self
1532 .tcx
1533 .codegen_fn_attrs(def_id)
1534 .flags
1535 .contains(CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL)
1536 }
1537 }
1538 }
1539
1540 #[instrument(skip(self), level = "debug")]
1543 fn push_if_root(&mut self, def_id: LocalDefId) {
1544 if self.is_root(def_id) {
1545 debug!("found root");
1546
1547 let instance = Instance::mono(self.tcx, def_id.to_def_id());
1548 self.output.push(create_fn_mono_item(self.tcx, instance, DUMMY_SP));
1549 }
1550 }
1551
1552 fn push_extra_entry_roots(&mut self) {
1558 let Some((main_def_id, EntryFnType::Main { .. })) = self.entry_fn else {
1559 return;
1560 };
1561
1562 let Some(start_def_id) = self.tcx.lang_items().start_fn() else {
1563 self.tcx.dcx().emit_fatal(errors::StartNotFound);
1564 };
1565 let main_ret_ty = self.tcx.fn_sig(main_def_id).no_bound_vars().unwrap().output();
1566
1567 let main_ret_ty = self.tcx.normalize_erasing_regions(
1573 ty::TypingEnv::fully_monomorphized(),
1574 main_ret_ty.no_bound_vars().unwrap(),
1575 );
1576
1577 let start_instance = Instance::expect_resolve(
1578 self.tcx,
1579 ty::TypingEnv::fully_monomorphized(),
1580 start_def_id,
1581 self.tcx.mk_args(&[main_ret_ty.into()]),
1582 DUMMY_SP,
1583 );
1584
1585 self.output.push(create_fn_mono_item(self.tcx, start_instance, DUMMY_SP));
1586 }
1587}
1588
1589#[instrument(level = "debug", skip(tcx, output))]
1590fn create_mono_items_for_default_impls<'tcx>(
1591 tcx: TyCtxt<'tcx>,
1592 item: hir::ItemId,
1593 output: &mut MonoItems<'tcx>,
1594) {
1595 let Some(impl_) = tcx.impl_trait_header(item.owner_id) else {
1596 return;
1597 };
1598
1599 if matches!(impl_.polarity, ty::ImplPolarity::Negative) {
1600 return;
1601 }
1602
1603 if tcx.generics_of(item.owner_id).own_requires_monomorphization() {
1604 return;
1605 }
1606
1607 let only_region_params = |param: &ty::GenericParamDef, _: &_| match param.kind {
1613 GenericParamDefKind::Lifetime => tcx.lifetimes.re_erased.into(),
1614 GenericParamDefKind::Type { .. } | GenericParamDefKind::Const { .. } => {
1615 unreachable!(
1616 "`own_requires_monomorphization` check means that \
1617 we should have no type/const params"
1618 )
1619 }
1620 };
1621 let impl_args = GenericArgs::for_item(tcx, item.owner_id.to_def_id(), only_region_params);
1622 let trait_ref = impl_.trait_ref.instantiate(tcx, impl_args);
1623
1624 if tcx.instantiate_and_check_impossible_predicates((item.owner_id.to_def_id(), impl_args)) {
1634 return;
1635 }
1636
1637 let typing_env = ty::TypingEnv::fully_monomorphized();
1638 let trait_ref = tcx.normalize_erasing_regions(typing_env, trait_ref);
1639 let overridden_methods = tcx.impl_item_implementor_ids(item.owner_id);
1640 for method in tcx.provided_trait_methods(trait_ref.def_id) {
1641 if overridden_methods.contains_key(&method.def_id) {
1642 continue;
1643 }
1644
1645 if tcx.generics_of(method.def_id).own_requires_monomorphization() {
1646 continue;
1647 }
1648
1649 let args = trait_ref.args.extend_to(tcx, method.def_id, only_region_params);
1653 let instance = ty::Instance::expect_resolve(tcx, typing_env, method.def_id, args, DUMMY_SP);
1654
1655 let mono_item = create_fn_mono_item(tcx, instance, DUMMY_SP);
1656 if mono_item.node.is_instantiable(tcx) && tcx.should_codegen_locally(instance) {
1657 output.push(mono_item);
1658 }
1659 }
1660}
1661
1662#[instrument(skip(tcx, strategy), level = "debug")]
1667pub(crate) fn collect_crate_mono_items<'tcx>(
1668 tcx: TyCtxt<'tcx>,
1669 strategy: MonoItemCollectionStrategy,
1670) -> (Vec<MonoItem<'tcx>>, UsageMap<'tcx>) {
1671 let _prof_timer = tcx.prof.generic_activity("monomorphization_collector");
1672
1673 let roots = tcx
1674 .sess
1675 .time("monomorphization_collector_root_collections", || collect_roots(tcx, strategy));
1676
1677 debug!("building mono item graph, beginning at roots");
1678
1679 let state = SharedState {
1680 visited: MTLock::new(UnordSet::default()),
1681 mentioned: MTLock::new(UnordSet::default()),
1682 usage_map: MTLock::new(UsageMap::new()),
1683 };
1684 let recursion_limit = tcx.recursion_limit();
1685
1686 tcx.sess.time("monomorphization_collector_graph_walk", || {
1687 par_for_each_in(roots, |root| {
1688 let mut recursion_depths = DefIdMap::default();
1689 collect_items_rec(
1690 tcx,
1691 dummy_spanned(root),
1692 &state,
1693 &mut recursion_depths,
1694 recursion_limit,
1695 CollectionMode::UsedItems,
1696 );
1697 });
1698 });
1699
1700 let mono_items = tcx.with_stable_hashing_context(move |ref hcx| {
1703 state.visited.into_inner().into_sorted(hcx, true)
1704 });
1705
1706 (mono_items, state.usage_map.into_inner())
1707}
1708
1709pub(crate) fn provide(providers: &mut Providers) {
1710 providers.hooks.should_codegen_locally = should_codegen_locally;
1711 providers.items_of_instance = items_of_instance;
1712}