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