1 //! Partitioning Codegen Units for Incremental Compilation
2 //! ======================================================
4 //! The task of this module is to take the complete set of monomorphizations of
5 //! a crate and produce a set of codegen units from it, where a codegen unit
6 //! is a named set of (mono-item, linkage) pairs. That is, this module
7 //! decides which monomorphization appears in which codegen units with which
8 //! linkage. The following paragraphs describe some of the background on the
9 //! partitioning scheme.
11 //! The most important opportunity for saving on compilation time with
12 //! incremental compilation is to avoid re-codegenning and re-optimizing code.
13 //! Since the unit of codegen and optimization for LLVM is "modules" or, how
14 //! we call them "codegen units", the particulars of how much time can be saved
15 //! by incremental compilation are tightly linked to how the output program is
16 //! partitioned into these codegen units prior to passing it to LLVM --
17 //! especially because we have to treat codegen units as opaque entities once
18 //! they are created: There is no way for us to incrementally update an existing
19 //! LLVM module and so we have to build any such module from scratch if it was
20 //! affected by some change in the source code.
22 //! From that point of view it would make sense to maximize the number of
23 //! codegen units by, for example, putting each function into its own module.
24 //! That way only those modules would have to be re-compiled that were actually
25 //! affected by some change, minimizing the number of functions that could have
26 //! been re-used but just happened to be located in a module that is
29 //! However, since LLVM optimization does not work across module boundaries,
30 //! using such a highly granular partitioning would lead to very slow runtime
31 //! code since it would effectively prohibit inlining and other inter-procedure
32 //! optimizations. We want to avoid that as much as possible.
34 //! Thus we end up with a trade-off: The bigger the codegen units, the better
35 //! LLVM's optimizer can do its work, but also the smaller the compilation time
36 //! reduction we get from incremental compilation.
38 //! Ideally, we would create a partitioning such that there are few big codegen
39 //! units with few interdependencies between them. For now though, we use the
40 //! following heuristic to determine the partitioning:
42 //! - There are two codegen units for every source-level module:
43 //! - One for "stable", that is non-generic, code
44 //! - One for more "volatile" code, i.e., monomorphized instances of functions
45 //! defined in that module
47 //! In order to see why this heuristic makes sense, let's take a look at when a
48 //! codegen unit can get invalidated:
50 //! 1. The most straightforward case is when the BODY of a function or global
51 //! changes. Then any codegen unit containing the code for that item has to be
52 //! re-compiled. Note that this includes all codegen units where the function
55 //! 2. The next case is when the SIGNATURE of a function or global changes. In
56 //! this case, all codegen units containing a REFERENCE to that item have to be
57 //! re-compiled. This is a superset of case 1.
59 //! 3. The final and most subtle case is when a REFERENCE to a generic function
60 //! is added or removed somewhere. Even though the definition of the function
61 //! might be unchanged, a new REFERENCE might introduce a new monomorphized
62 //! instance of this function which has to be placed and compiled somewhere.
63 //! Conversely, when removing a REFERENCE, it might have been the last one with
64 //! that particular set of generic arguments and thus we have to remove it.
66 //! From the above we see that just using one codegen unit per source-level
67 //! module is not such a good idea, since just adding a REFERENCE to some
68 //! generic item somewhere else would invalidate everything within the module
69 //! containing the generic item. The heuristic above reduces this detrimental
70 //! side-effect of references a little by at least not touching the non-generic
71 //! code of the module.
73 //! A Note on Inlining
74 //! ------------------
75 //! As briefly mentioned above, in order for LLVM to be able to inline a
76 //! function call, the body of the function has to be available in the LLVM
77 //! module where the call is made. This has a few consequences for partitioning:
79 //! - The partitioning algorithm has to take care of placing functions into all
80 //! codegen units where they should be available for inlining. It also has to
81 //! decide on the correct linkage for these functions.
83 //! - The partitioning algorithm has to know which functions are likely to get
84 //! inlined, so it can distribute function instantiations accordingly. Since
85 //! there is no way of knowing for sure which functions LLVM will decide to
86 //! inline in the end, we apply a heuristic here: Only functions marked with
87 //! `#[inline]` are considered for inlining by the partitioner. The current
88 //! implementation will not try to determine if a function is likely to be
89 //! inlined by looking at the functions definition.
91 //! Note though that as a side-effect of creating a codegen units per
92 //! source-level module, functions from the same module will be available for
93 //! inlining, even when they are not marked `#[inline]`.
96 use std
::collections
::hash_map
::Entry
;
99 use rustc
::middle
::codegen_fn_attrs
::CodegenFnAttrFlags
;
100 use rustc
::middle
::exported_symbols
::SymbolExportLevel
;
101 use rustc
::mir
::mono
::{CodegenUnit, CodegenUnitNameBuilder, Linkage, Visibility}
;
102 use rustc
::mir
::mono
::{InstantiationMode, MonoItem}
;
103 use rustc
::ty
::print
::characteristic_def_id_of_type
;
104 use rustc
::ty
::query
::Providers
;
105 use rustc
::ty
::{self, DefIdTree, InstanceDef, TyCtxt}
;
106 use rustc_data_structures
::fx
::{FxHashMap, FxHashSet}
;
107 use rustc_data_structures
::sync
;
108 use rustc_hir
::def
::DefKind
;
109 use rustc_hir
::def_id
::{CrateNum, DefId, DefIdSet, CRATE_DEF_INDEX, LOCAL_CRATE}
;
110 use rustc_span
::symbol
::Symbol
;
112 use crate::monomorphize
::collector
::InliningMap
;
113 use crate::monomorphize
::collector
::{self, MonoItemCollectionMode}
;
115 pub enum PartitioningStrategy
{
116 /// Generates one codegen unit per source-level module.
119 /// Partition the whole crate into a fixed number of codegen units.
120 FixedUnitCount(usize),
123 // Anything we can't find a proper codegen unit for goes into this.
124 fn fallback_cgu_name(name_builder
: &mut CodegenUnitNameBuilder
<'_
>) -> Symbol
{
125 name_builder
.build_cgu_name(LOCAL_CRATE
, &["fallback"], Some("cgu"))
128 pub fn partition
<'tcx
, I
>(
131 strategy
: PartitioningStrategy
,
132 inlining_map
: &InliningMap
<'tcx
>,
133 ) -> Vec
<CodegenUnit
<'tcx
>>
135 I
: Iterator
<Item
= MonoItem
<'tcx
>>,
137 let _prof_timer
= tcx
.prof
.generic_activity("cgu_partitioning");
139 // In the first step, we place all regular monomorphizations into their
140 // respective 'home' codegen unit. Regular monomorphizations are all
141 // functions and statics defined in the local crate.
142 let mut initial_partitioning
= {
143 let _prof_timer
= tcx
.prof
.generic_activity("cgu_partitioning_place_roots");
144 place_root_mono_items(tcx
, mono_items
)
147 initial_partitioning
.codegen_units
.iter_mut().for_each(|cgu
| cgu
.estimate_size(tcx
));
149 debug_dump(tcx
, "INITIAL PARTITIONING:", initial_partitioning
.codegen_units
.iter());
151 // If the partitioning should produce a fixed count of codegen units, merge
152 // until that count is reached.
153 if let PartitioningStrategy
::FixedUnitCount(count
) = strategy
{
154 let _prof_timer
= tcx
.prof
.generic_activity("cgu_partitioning_merge_cgus");
155 merge_codegen_units(tcx
, &mut initial_partitioning
, count
);
156 debug_dump(tcx
, "POST MERGING:", initial_partitioning
.codegen_units
.iter());
159 // In the next step, we use the inlining map to determine which additional
160 // monomorphizations have to go into each codegen unit. These additional
161 // monomorphizations can be drop-glue, functions from external crates, and
162 // local functions the definition of which is marked with `#[inline]`.
163 let mut post_inlining
= {
164 let _prof_timer
= tcx
.prof
.generic_activity("cgu_partitioning_place_inline_items");
165 place_inlined_mono_items(initial_partitioning
, inlining_map
)
168 post_inlining
.codegen_units
.iter_mut().for_each(|cgu
| cgu
.estimate_size(tcx
));
170 debug_dump(tcx
, "POST INLINING:", post_inlining
.codegen_units
.iter());
172 // Next we try to make as many symbols "internal" as possible, so LLVM has
173 // more freedom to optimize.
174 if !tcx
.sess
.opts
.cg
.link_dead_code
{
175 let _prof_timer
= tcx
.prof
.generic_activity("cgu_partitioning_internalize_symbols");
176 internalize_symbols(tcx
, &mut post_inlining
, inlining_map
);
179 // Finally, sort by codegen unit name, so that we get deterministic results.
180 let PostInliningPartitioning
{
181 codegen_units
: mut result
,
182 mono_item_placements
: _
,
183 internalization_candidates
: _
,
186 result
.sort_by_cached_key(|cgu
| cgu
.name().as_str());
191 struct PreInliningPartitioning
<'tcx
> {
192 codegen_units
: Vec
<CodegenUnit
<'tcx
>>,
193 roots
: FxHashSet
<MonoItem
<'tcx
>>,
194 internalization_candidates
: FxHashSet
<MonoItem
<'tcx
>>,
197 /// For symbol internalization, we need to know whether a symbol/mono-item is
198 /// accessed from outside the codegen unit it is defined in. This type is used
199 /// to keep track of that.
200 #[derive(Clone, PartialEq, Eq, Debug)]
201 enum MonoItemPlacement
{
202 SingleCgu { cgu_name: Symbol }
,
206 struct PostInliningPartitioning
<'tcx
> {
207 codegen_units
: Vec
<CodegenUnit
<'tcx
>>,
208 mono_item_placements
: FxHashMap
<MonoItem
<'tcx
>, MonoItemPlacement
>,
209 internalization_candidates
: FxHashSet
<MonoItem
<'tcx
>>,
212 fn place_root_mono_items
<'tcx
, I
>(tcx
: TyCtxt
<'tcx
>, mono_items
: I
) -> PreInliningPartitioning
<'tcx
>
214 I
: Iterator
<Item
= MonoItem
<'tcx
>>,
216 let mut roots
= FxHashSet
::default();
217 let mut codegen_units
= FxHashMap
::default();
218 let is_incremental_build
= tcx
.sess
.opts
.incremental
.is_some();
219 let mut internalization_candidates
= FxHashSet
::default();
221 // Determine if monomorphizations instantiated in this crate will be made
222 // available to downstream crates. This depends on whether we are in
223 // share-generics mode and whether the current crate can even have
224 // downstream crates.
225 let export_generics
= tcx
.sess
.opts
.share_generics() && tcx
.local_crate_exports_generics();
227 let cgu_name_builder
= &mut CodegenUnitNameBuilder
::new(tcx
);
228 let cgu_name_cache
= &mut FxHashMap
::default();
230 for mono_item
in mono_items
{
231 match mono_item
.instantiation_mode(tcx
) {
232 InstantiationMode
::GloballyShared { .. }
=> {}
233 InstantiationMode
::LocalCopy
=> continue,
236 let characteristic_def_id
= characteristic_def_id_of_mono_item(tcx
, mono_item
);
237 let is_volatile
= is_incremental_build
&& mono_item
.is_generic_fn();
239 let codegen_unit_name
= match characteristic_def_id
{
240 Some(def_id
) => compute_codegen_unit_name(
247 None
=> fallback_cgu_name(cgu_name_builder
),
250 let codegen_unit
= codegen_units
251 .entry(codegen_unit_name
)
252 .or_insert_with(|| CodegenUnit
::new(codegen_unit_name
));
254 let mut can_be_internalized
= true;
255 let (linkage
, visibility
) = mono_item_linkage_and_visibility(
258 &mut can_be_internalized
,
261 if visibility
== Visibility
::Hidden
&& can_be_internalized
{
262 internalization_candidates
.insert(mono_item
);
265 codegen_unit
.items_mut().insert(mono_item
, (linkage
, visibility
));
266 roots
.insert(mono_item
);
269 // Always ensure we have at least one CGU; otherwise, if we have a
270 // crate with just types (for example), we could wind up with no CGU.
271 if codegen_units
.is_empty() {
272 let codegen_unit_name
= fallback_cgu_name(cgu_name_builder
);
273 codegen_units
.insert(codegen_unit_name
, CodegenUnit
::new(codegen_unit_name
));
276 PreInliningPartitioning
{
277 codegen_units
: codegen_units
.into_iter().map(|(_
, codegen_unit
)| codegen_unit
).collect(),
279 internalization_candidates
,
283 fn mono_item_linkage_and_visibility(
285 mono_item
: &MonoItem
<'tcx
>,
286 can_be_internalized
: &mut bool
,
287 export_generics
: bool
,
288 ) -> (Linkage
, Visibility
) {
289 if let Some(explicit_linkage
) = mono_item
.explicit_linkage(tcx
) {
290 return (explicit_linkage
, Visibility
::Default
);
292 let vis
= mono_item_visibility(tcx
, mono_item
, can_be_internalized
, export_generics
);
293 (Linkage
::External
, vis
)
296 fn mono_item_visibility(
298 mono_item
: &MonoItem
<'tcx
>,
299 can_be_internalized
: &mut bool
,
300 export_generics
: bool
,
302 let instance
= match mono_item
{
303 // This is pretty complicated; see below.
304 MonoItem
::Fn(instance
) => instance
,
306 // Misc handling for generics and such, but otherwise:
307 MonoItem
::Static(def_id
) => {
308 return if tcx
.is_reachable_non_generic(*def_id
) {
309 *can_be_internalized
= false;
310 default_visibility(tcx
, *def_id
, false)
315 MonoItem
::GlobalAsm(hir_id
) => {
316 let def_id
= tcx
.hir().local_def_id(*hir_id
);
317 return if tcx
.is_reachable_non_generic(def_id
) {
318 *can_be_internalized
= false;
319 default_visibility(tcx
, def_id
, false)
326 let def_id
= match instance
.def
{
327 InstanceDef
::Item(def_id
) | InstanceDef
::DropGlue(def_id
, Some(_
)) => def_id
,
329 // These are all compiler glue and such, never exported, always hidden.
330 InstanceDef
::VtableShim(..)
331 | InstanceDef
::ReifyShim(..)
332 | InstanceDef
::FnPtrShim(..)
333 | InstanceDef
::Virtual(..)
334 | InstanceDef
::Intrinsic(..)
335 | InstanceDef
::ClosureOnceShim { .. }
336 | InstanceDef
::DropGlue(..)
337 | InstanceDef
::CloneShim(..) => return Visibility
::Hidden
,
340 // The `start_fn` lang item is actually a monomorphized instance of a
341 // function in the standard library, used for the `main` function. We don't
342 // want to export it so we tag it with `Hidden` visibility but this symbol
343 // is only referenced from the actual `main` symbol which we unfortunately
344 // don't know anything about during partitioning/collection. As a result we
345 // forcibly keep this symbol out of the `internalization_candidates` set.
347 // FIXME: eventually we don't want to always force this symbol to have
348 // hidden visibility, it should indeed be a candidate for
349 // internalization, but we have to understand that it's referenced
350 // from the `main` symbol we'll generate later.
352 // This may be fixable with a new `InstanceDef` perhaps? Unsure!
353 if tcx
.lang_items().start_fn() == Some(def_id
) {
354 *can_be_internalized
= false;
355 return Visibility
::Hidden
;
358 let is_generic
= instance
.substs
.non_erasable_generics().next().is_some();
360 // Upstream `DefId` instances get different handling than local ones.
361 if !def_id
.is_local() {
362 return if export_generics
&& is_generic
{
363 // If it is a upstream monomorphization and we export generics, we must make
364 // it available to downstream crates.
365 *can_be_internalized
= false;
366 default_visibility(tcx
, def_id
, true)
374 if tcx
.is_unreachable_local_definition(def_id
) {
375 // This instance cannot be used from another crate.
378 // This instance might be useful in a downstream crate.
379 *can_be_internalized
= false;
380 default_visibility(tcx
, def_id
, true)
383 // We are not exporting generics or the definition is not reachable
384 // for downstream crates, we can internalize its instantiations.
388 // If this isn't a generic function then we mark this a `Default` if
389 // this is a reachable item, meaning that it's a symbol other crates may
390 // access when they link to us.
391 if tcx
.is_reachable_non_generic(def_id
) {
392 *can_be_internalized
= false;
393 debug_assert
!(!is_generic
);
394 return default_visibility(tcx
, def_id
, false);
397 // If this isn't reachable then we're gonna tag this with `Hidden`
398 // visibility. In some situations though we'll want to prevent this
399 // symbol from being internalized.
401 // There's two categories of items here:
403 // * First is weak lang items. These are basically mechanisms for
404 // libcore to forward-reference symbols defined later in crates like
405 // the standard library or `#[panic_handler]` definitions. The
406 // definition of these weak lang items needs to be referenceable by
407 // libcore, so we're no longer a candidate for internalization.
408 // Removal of these functions can't be done by LLVM but rather must be
409 // done by the linker as it's a non-local decision.
411 // * Second is "std internal symbols". Currently this is primarily used
412 // for allocator symbols. Allocators are a little weird in their
413 // implementation, but the idea is that the compiler, at the last
414 // minute, defines an allocator with an injected object file. The
415 // `alloc` crate references these symbols (`__rust_alloc`) and the
416 // definition doesn't get hooked up until a linked crate artifact is
419 // The symbols synthesized by the compiler (`__rust_alloc`) are thin
420 // veneers around the actual implementation, some other symbol which
421 // implements the same ABI. These symbols (things like `__rg_alloc`,
422 // `__rdl_alloc`, `__rde_alloc`, etc), are all tagged with "std
423 // internal symbols".
425 // The std-internal symbols here **should not show up in a dll as an
426 // exported interface**, so they return `false` from
427 // `is_reachable_non_generic` above and we'll give them `Hidden`
428 // visibility below. Like the weak lang items, though, we can't let
429 // LLVM internalize them as this decision is left up to the linker to
430 // omit them, so prevent them from being internalized.
431 let attrs
= tcx
.codegen_fn_attrs(def_id
);
432 if attrs
.flags
.contains(CodegenFnAttrFlags
::RUSTC_STD_INTERNAL_SYMBOL
) {
433 *can_be_internalized
= false;
440 fn default_visibility(tcx
: TyCtxt
<'_
>, id
: DefId
, is_generic
: bool
) -> Visibility
{
441 if !tcx
.sess
.target
.target
.options
.default_hidden_visibility
{
442 return Visibility
::Default
;
445 // Generic functions never have export-level C.
447 return Visibility
::Hidden
;
450 // Things with export level C don't get instantiated in
451 // downstream crates.
453 return Visibility
::Hidden
;
456 // C-export level items remain at `Default`, all other internal
457 // items become `Hidden`.
458 match tcx
.reachable_non_generics(id
.krate
).get(&id
) {
459 Some(SymbolExportLevel
::C
) => Visibility
::Default
,
460 _
=> Visibility
::Hidden
,
464 fn merge_codegen_units
<'tcx
>(
466 initial_partitioning
: &mut PreInliningPartitioning
<'tcx
>,
467 target_cgu_count
: usize,
469 assert
!(target_cgu_count
>= 1);
470 let codegen_units
= &mut initial_partitioning
.codegen_units
;
472 // Note that at this point in time the `codegen_units` here may not be in a
473 // deterministic order (but we know they're deterministically the same set).
474 // We want this merging to produce a deterministic ordering of codegen units
477 // Due to basically how we've implemented the merging below (merge the two
478 // smallest into each other) we're sure to start off with a deterministic
479 // order (sorted by name). This'll mean that if two cgus have the same size
480 // the stable sort below will keep everything nice and deterministic.
481 codegen_units
.sort_by_cached_key(|cgu
| cgu
.name().as_str());
483 // Merge the two smallest codegen units until the target size is reached.
484 while codegen_units
.len() > target_cgu_count
{
485 // Sort small cgus to the back
486 codegen_units
.sort_by_cached_key(|cgu
| cmp
::Reverse(cgu
.size_estimate()));
487 let mut smallest
= codegen_units
.pop().unwrap();
488 let second_smallest
= codegen_units
.last_mut().unwrap();
490 second_smallest
.modify_size_estimate(smallest
.size_estimate());
491 for (k
, v
) in smallest
.items_mut().drain() {
492 second_smallest
.items_mut().insert(k
, v
);
495 "CodegenUnit {} merged in to CodegenUnit {}",
497 second_smallest
.name()
501 let cgu_name_builder
= &mut CodegenUnitNameBuilder
::new(tcx
);
502 for (index
, cgu
) in codegen_units
.iter_mut().enumerate() {
503 cgu
.set_name(numbered_codegen_unit_name(cgu_name_builder
, index
));
507 fn place_inlined_mono_items
<'tcx
>(
508 initial_partitioning
: PreInliningPartitioning
<'tcx
>,
509 inlining_map
: &InliningMap
<'tcx
>,
510 ) -> PostInliningPartitioning
<'tcx
> {
511 let mut new_partitioning
= Vec
::new();
512 let mut mono_item_placements
= FxHashMap
::default();
514 let PreInliningPartitioning { codegen_units: initial_cgus, roots, internalization_candidates }
=
515 initial_partitioning
;
517 let single_codegen_unit
= initial_cgus
.len() == 1;
519 for old_codegen_unit
in initial_cgus
{
520 // Collect all items that need to be available in this codegen unit.
521 let mut reachable
= FxHashSet
::default();
522 for root
in old_codegen_unit
.items().keys() {
523 follow_inlining(*root
, inlining_map
, &mut reachable
);
526 let mut new_codegen_unit
= CodegenUnit
::new(old_codegen_unit
.name());
528 // Add all monomorphizations that are not already there.
529 for mono_item
in reachable
{
530 if let Some(linkage
) = old_codegen_unit
.items().get(&mono_item
) {
531 // This is a root, just copy it over.
532 new_codegen_unit
.items_mut().insert(mono_item
, *linkage
);
534 if roots
.contains(&mono_item
) {
536 "GloballyShared mono-item inlined into other CGU: \
542 // This is a CGU-private copy.
545 .insert(mono_item
, (Linkage
::Internal
, Visibility
::Default
));
548 if !single_codegen_unit
{
549 // If there is more than one codegen unit, we need to keep track
550 // in which codegen units each monomorphization is placed.
551 match mono_item_placements
.entry(mono_item
) {
552 Entry
::Occupied(e
) => {
553 let placement
= e
.into_mut();
554 debug_assert
!(match *placement
{
555 MonoItemPlacement
::SingleCgu { cgu_name }
=> {
556 cgu_name
!= new_codegen_unit
.name()
558 MonoItemPlacement
::MultipleCgus
=> true,
560 *placement
= MonoItemPlacement
::MultipleCgus
;
562 Entry
::Vacant(e
) => {
563 e
.insert(MonoItemPlacement
::SingleCgu
{
564 cgu_name
: new_codegen_unit
.name(),
571 new_partitioning
.push(new_codegen_unit
);
574 return PostInliningPartitioning
{
575 codegen_units
: new_partitioning
,
576 mono_item_placements
,
577 internalization_candidates
,
580 fn follow_inlining
<'tcx
>(
581 mono_item
: MonoItem
<'tcx
>,
582 inlining_map
: &InliningMap
<'tcx
>,
583 visited
: &mut FxHashSet
<MonoItem
<'tcx
>>,
585 if !visited
.insert(mono_item
) {
589 inlining_map
.with_inlining_candidates(mono_item
, |target
| {
590 follow_inlining(target
, inlining_map
, visited
);
595 fn internalize_symbols
<'tcx
>(
597 partitioning
: &mut PostInliningPartitioning
<'tcx
>,
598 inlining_map
: &InliningMap
<'tcx
>,
600 if partitioning
.codegen_units
.len() == 1 {
601 // Fast path for when there is only one codegen unit. In this case we
602 // can internalize all candidates, since there is nowhere else they
603 // could be accessed from.
604 for cgu
in &mut partitioning
.codegen_units
{
605 for candidate
in &partitioning
.internalization_candidates
{
606 cgu
.items_mut().insert(*candidate
, (Linkage
::Internal
, Visibility
::Default
));
613 // Build a map from every monomorphization to all the monomorphizations that
615 let mut accessor_map
: FxHashMap
<MonoItem
<'tcx
>, Vec
<MonoItem
<'tcx
>>> = Default
::default();
616 inlining_map
.iter_accesses(|accessor
, accessees
| {
617 for accessee
in accessees
{
618 accessor_map
.entry(*accessee
).or_default().push(accessor
);
622 let mono_item_placements
= &partitioning
.mono_item_placements
;
624 // For each internalization candidates in each codegen unit, check if it is
625 // accessed from outside its defining codegen unit.
626 for cgu
in &mut partitioning
.codegen_units
{
627 let home_cgu
= MonoItemPlacement
::SingleCgu { cgu_name: cgu.name() }
;
629 for (accessee
, linkage_and_visibility
) in cgu
.items_mut() {
630 if !partitioning
.internalization_candidates
.contains(accessee
) {
631 // This item is no candidate for internalizing, so skip it.
634 debug_assert_eq
!(mono_item_placements
[accessee
], home_cgu
);
636 if let Some(accessors
) = accessor_map
.get(accessee
) {
639 .filter_map(|accessor
| {
640 // Some accessors might not have been
641 // instantiated. We can safely ignore those.
642 mono_item_placements
.get(accessor
)
644 .any(|placement
| *placement
!= home_cgu
)
646 // Found an accessor from another CGU, so skip to the next
647 // item without marking this one as internal.
652 // If we got here, we did not find any accesses from other CGUs,
653 // so it's fine to make this monomorphization internal.
654 *linkage_and_visibility
= (Linkage
::Internal
, Visibility
::Default
);
659 fn characteristic_def_id_of_mono_item
<'tcx
>(
661 mono_item
: MonoItem
<'tcx
>,
664 MonoItem
::Fn(instance
) => {
665 let def_id
= match instance
.def
{
666 ty
::InstanceDef
::Item(def_id
) => def_id
,
667 ty
::InstanceDef
::VtableShim(..)
668 | ty
::InstanceDef
::ReifyShim(..)
669 | ty
::InstanceDef
::FnPtrShim(..)
670 | ty
::InstanceDef
::ClosureOnceShim { .. }
671 | ty
::InstanceDef
::Intrinsic(..)
672 | ty
::InstanceDef
::DropGlue(..)
673 | ty
::InstanceDef
::Virtual(..)
674 | ty
::InstanceDef
::CloneShim(..) => return None
,
677 // If this is a method, we want to put it into the same module as
678 // its self-type. If the self-type does not provide a characteristic
679 // DefId, we use the location of the impl after all.
681 if tcx
.trait_of_item(def_id
).is_some() {
682 let self_ty
= instance
.substs
.type_at(0);
683 // This is a default implementation of a trait method.
684 return characteristic_def_id_of_type(self_ty
).or(Some(def_id
));
687 if let Some(impl_def_id
) = tcx
.impl_of_method(def_id
) {
688 if tcx
.sess
.opts
.incremental
.is_some()
689 && tcx
.trait_id_of_impl(impl_def_id
) == tcx
.lang_items().drop_trait()
691 // Put `Drop::drop` into the same cgu as `drop_in_place`
692 // since `drop_in_place` is the only thing that can
696 // This is a method within an impl, find out what the self-type is:
697 let impl_self_ty
= tcx
.subst_and_normalize_erasing_regions(
699 ty
::ParamEnv
::reveal_all(),
700 &tcx
.type_of(impl_def_id
),
702 if let Some(def_id
) = characteristic_def_id_of_type(impl_self_ty
) {
709 MonoItem
::Static(def_id
) => Some(def_id
),
710 MonoItem
::GlobalAsm(hir_id
) => Some(tcx
.hir().local_def_id(hir_id
)),
714 type CguNameCache
= FxHashMap
<(DefId
, bool
), Symbol
>;
716 fn compute_codegen_unit_name(
718 name_builder
: &mut CodegenUnitNameBuilder
<'_
>,
721 cache
: &mut CguNameCache
,
723 // Find the innermost module that is not nested within a function.
724 let mut current_def_id
= def_id
;
725 let mut cgu_def_id
= None
;
726 // Walk backwards from the item we want to find the module for.
728 if current_def_id
.index
== CRATE_DEF_INDEX
{
729 if cgu_def_id
.is_none() {
730 // If we have not found a module yet, take the crate root.
731 cgu_def_id
= Some(DefId { krate: def_id.krate, index: CRATE_DEF_INDEX }
);
734 } else if tcx
.def_kind(current_def_id
) == Some(DefKind
::Mod
) {
735 if cgu_def_id
.is_none() {
736 cgu_def_id
= Some(current_def_id
);
739 // If we encounter something that is not a module, throw away
740 // any module that we've found so far because we now know that
741 // it is nested within something else.
745 current_def_id
= tcx
.parent(current_def_id
).unwrap();
748 let cgu_def_id
= cgu_def_id
.unwrap();
750 *cache
.entry((cgu_def_id
, volatile
)).or_insert_with(|| {
751 let def_path
= tcx
.def_path(cgu_def_id
);
753 let components
= def_path
.data
.iter().map(|part
| part
.data
.as_symbol());
755 let volatile_suffix
= volatile
.then_some("volatile");
757 name_builder
.build_cgu_name(def_path
.krate
, components
, volatile_suffix
)
761 fn numbered_codegen_unit_name(
762 name_builder
: &mut CodegenUnitNameBuilder
<'_
>,
765 name_builder
.build_cgu_name_no_mangle(LOCAL_CRATE
, &["cgu"], Some(index
))
768 fn debug_dump
<'a
, 'tcx
, I
>(tcx
: TyCtxt
<'tcx
>, label
: &str, cgus
: I
)
770 I
: Iterator
<Item
= &'a CodegenUnit
<'tcx
>>,
773 if cfg
!(debug_assertions
) {
776 debug
!("CodegenUnit {} estimated size {} :", cgu
.name(), cgu
.size_estimate());
778 for (mono_item
, linkage
) in cgu
.items() {
779 let symbol_name
= mono_item
.symbol_name(tcx
).name
.as_str();
780 let symbol_hash_start
= symbol_name
.rfind('h'
);
782 symbol_hash_start
.map(|i
| &symbol_name
[i
..]).unwrap_or("<no hash>");
785 " - {} [{:?}] [{}] estimated size {}",
786 mono_item
.to_string(tcx
, true),
789 mono_item
.size_estimate(tcx
)
798 #[inline(never)] // give this a place in the profiler
799 fn assert_symbols_are_distinct
<'a
, 'tcx
, I
>(tcx
: TyCtxt
<'tcx
>, mono_items
: I
)
801 I
: Iterator
<Item
= &'a MonoItem
<'tcx
>>,
804 let _prof_timer
= tcx
.prof
.generic_activity("assert_symbols_are_distinct");
806 let mut symbols
: Vec
<_
> =
807 mono_items
.map(|mono_item
| (mono_item
, mono_item
.symbol_name(tcx
))).collect();
809 symbols
.sort_by_key(|sym
| sym
.1);
811 for pair
in symbols
.windows(2) {
812 let sym1
= &pair
[0].1;
813 let sym2
= &pair
[1].1;
816 let mono_item1
= pair
[0].0;
817 let mono_item2
= pair
[1].0;
819 let span1
= mono_item1
.local_span(tcx
);
820 let span2
= mono_item2
.local_span(tcx
);
822 // Deterministically select one of the spans for error reporting
823 let span
= match (span1
, span2
) {
824 (Some(span1
), Some(span2
)) => {
825 Some(if span1
.lo().0 > span2
.lo().0 { span1 }
else { span2 }
)
827 (span1
, span2
) => span1
.or(span2
),
830 let error_message
= format
!("symbol `{}` is already defined", sym1
);
832 if let Some(span
) = span
{
833 tcx
.sess
.span_fatal(span
, &error_message
)
835 tcx
.sess
.fatal(&error_message
)
841 fn collect_and_partition_mono_items(
844 ) -> (Arc
<DefIdSet
>, Arc
<Vec
<Arc
<CodegenUnit
<'_
>>>>) {
845 assert_eq
!(cnum
, LOCAL_CRATE
);
847 let collection_mode
= match tcx
.sess
.opts
.debugging_opts
.print_mono_items
{
849 let mode_string
= s
.to_lowercase();
850 let mode_string
= mode_string
.trim();
851 if mode_string
== "eager" {
852 MonoItemCollectionMode
::Eager
854 if mode_string
!= "lazy" {
855 let message
= format
!(
856 "Unknown codegen-item collection mode '{}'. \
857 Falling back to 'lazy' mode.",
860 tcx
.sess
.warn(&message
);
863 MonoItemCollectionMode
::Lazy
867 if tcx
.sess
.opts
.cg
.link_dead_code
{
868 MonoItemCollectionMode
::Eager
870 MonoItemCollectionMode
::Lazy
875 let (items
, inlining_map
) = collector
::collect_crate_mono_items(tcx
, collection_mode
);
877 tcx
.sess
.abort_if_errors();
879 let (codegen_units
, _
) = tcx
.sess
.time("partition_and_assert_distinct_symbols", || {
882 let strategy
= if tcx
.sess
.opts
.incremental
.is_some() {
883 PartitioningStrategy
::PerModule
885 PartitioningStrategy
::FixedUnitCount(tcx
.sess
.codegen_units())
888 partition(tcx
, items
.iter().cloned(), strategy
, &inlining_map
)
893 || assert_symbols_are_distinct(tcx
, items
.iter()),
897 let mono_items
: DefIdSet
= items
899 .filter_map(|mono_item
| match *mono_item
{
900 MonoItem
::Fn(ref instance
) => Some(instance
.def_id()),
901 MonoItem
::Static(def_id
) => Some(def_id
),
906 if tcx
.sess
.opts
.debugging_opts
.print_mono_items
.is_some() {
907 let mut item_to_cgus
: FxHashMap
<_
, Vec
<_
>> = Default
::default();
909 for cgu
in &codegen_units
{
910 for (&mono_item
, &linkage
) in cgu
.items() {
911 item_to_cgus
.entry(mono_item
).or_default().push((cgu
.name(), linkage
));
915 let mut item_keys
: Vec
<_
> = items
918 let mut output
= i
.to_string(tcx
, false);
919 output
.push_str(" @@");
920 let mut empty
= Vec
::new();
921 let cgus
= item_to_cgus
.get_mut(i
).unwrap_or(&mut empty
);
922 cgus
.sort_by_key(|(name
, _
)| *name
);
924 for &(ref cgu_name
, (linkage
, _
)) in cgus
.iter() {
925 output
.push_str(" ");
926 output
.push_str(&cgu_name
.as_str());
928 let linkage_abbrev
= match linkage
{
929 Linkage
::External
=> "External",
930 Linkage
::AvailableExternally
=> "Available",
931 Linkage
::LinkOnceAny
=> "OnceAny",
932 Linkage
::LinkOnceODR
=> "OnceODR",
933 Linkage
::WeakAny
=> "WeakAny",
934 Linkage
::WeakODR
=> "WeakODR",
935 Linkage
::Appending
=> "Appending",
936 Linkage
::Internal
=> "Internal",
937 Linkage
::Private
=> "Private",
938 Linkage
::ExternalWeak
=> "ExternalWeak",
939 Linkage
::Common
=> "Common",
942 output
.push_str("[");
943 output
.push_str(linkage_abbrev
);
944 output
.push_str("]");
952 for item
in item_keys
{
953 println
!("MONO_ITEM {}", item
);
957 (Arc
::new(mono_items
), Arc
::new(codegen_units
))
960 pub fn provide(providers
: &mut Providers
<'_
>) {
961 providers
.collect_and_partition_mono_items
= collect_and_partition_mono_items
;
963 providers
.is_codegened_item
= |tcx
, def_id
| {
964 let (all_mono_items
, _
) = tcx
.collect_and_partition_mono_items(LOCAL_CRATE
);
965 all_mono_items
.contains(&def_id
)
968 providers
.codegen_unit
= |tcx
, name
| {
969 let (_
, all
) = tcx
.collect_and_partition_mono_items(LOCAL_CRATE
);
971 .find(|cgu
| cgu
.name() == name
)
973 .unwrap_or_else(|| panic
!("failed to find cgu with name {:?}", name
))