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
;
98 use rustc_data_structures
::fx
::{FxHashMap, FxHashSet}
;
99 use rustc_data_structures
::sync
;
100 use rustc_hir
::def
::DefKind
;
101 use rustc_hir
::def_id
::{CrateNum, DefId, DefIdSet, CRATE_DEF_INDEX, LOCAL_CRATE}
;
102 use rustc_middle
::middle
::codegen_fn_attrs
::CodegenFnAttrFlags
;
103 use rustc_middle
::middle
::exported_symbols
::SymbolExportLevel
;
104 use rustc_middle
::mir
::mono
::{CodegenUnit, CodegenUnitNameBuilder, Linkage, Visibility}
;
105 use rustc_middle
::mir
::mono
::{InstantiationMode, MonoItem}
;
106 use rustc_middle
::ty
::print
::characteristic_def_id_of_type
;
107 use rustc_middle
::ty
::query
::Providers
;
108 use rustc_middle
::ty
::{self, DefIdTree, InstanceDef, TyCtxt}
;
109 use rustc_span
::symbol
::{Symbol, SymbolStr}
;
111 use crate::monomorphize
::collector
::InliningMap
;
112 use crate::monomorphize
::collector
::{self, MonoItemCollectionMode}
;
114 // Anything we can't find a proper codegen unit for goes into this.
115 fn fallback_cgu_name(name_builder
: &mut CodegenUnitNameBuilder
<'_
>) -> Symbol
{
116 name_builder
.build_cgu_name(LOCAL_CRATE
, &["fallback"], Some("cgu"))
119 pub fn partition
<'tcx
, I
>(
122 max_cgu_count
: usize,
123 inlining_map
: &InliningMap
<'tcx
>,
124 ) -> Vec
<CodegenUnit
<'tcx
>>
126 I
: Iterator
<Item
= MonoItem
<'tcx
>>,
128 let _prof_timer
= tcx
.prof
.generic_activity("cgu_partitioning");
130 // In the first step, we place all regular monomorphizations into their
131 // respective 'home' codegen unit. Regular monomorphizations are all
132 // functions and statics defined in the local crate.
133 let mut initial_partitioning
= {
134 let _prof_timer
= tcx
.prof
.generic_activity("cgu_partitioning_place_roots");
135 place_root_mono_items(tcx
, mono_items
)
138 initial_partitioning
.codegen_units
.iter_mut().for_each(|cgu
| cgu
.estimate_size(tcx
));
140 debug_dump(tcx
, "INITIAL PARTITIONING:", initial_partitioning
.codegen_units
.iter());
142 // Merge until we have at most `max_cgu_count` codegen units.
144 let _prof_timer
= tcx
.prof
.generic_activity("cgu_partitioning_merge_cgus");
145 merge_codegen_units(tcx
, &mut initial_partitioning
, max_cgu_count
);
146 debug_dump(tcx
, "POST MERGING:", initial_partitioning
.codegen_units
.iter());
149 // In the next step, we use the inlining map to determine which additional
150 // monomorphizations have to go into each codegen unit. These additional
151 // monomorphizations can be drop-glue, functions from external crates, and
152 // local functions the definition of which is marked with `#[inline]`.
153 let mut post_inlining
= {
154 let _prof_timer
= tcx
.prof
.generic_activity("cgu_partitioning_place_inline_items");
155 place_inlined_mono_items(initial_partitioning
, inlining_map
)
158 post_inlining
.codegen_units
.iter_mut().for_each(|cgu
| cgu
.estimate_size(tcx
));
160 debug_dump(tcx
, "POST INLINING:", post_inlining
.codegen_units
.iter());
162 // Next we try to make as many symbols "internal" as possible, so LLVM has
163 // more freedom to optimize.
164 if !tcx
.sess
.opts
.cg
.link_dead_code
{
165 let _prof_timer
= tcx
.prof
.generic_activity("cgu_partitioning_internalize_symbols");
166 internalize_symbols(tcx
, &mut post_inlining
, inlining_map
);
169 // Finally, sort by codegen unit name, so that we get deterministic results.
170 let PostInliningPartitioning
{
171 codegen_units
: mut result
,
172 mono_item_placements
: _
,
173 internalization_candidates
: _
,
176 result
.sort_by_cached_key(|cgu
| cgu
.name().as_str());
181 struct PreInliningPartitioning
<'tcx
> {
182 codegen_units
: Vec
<CodegenUnit
<'tcx
>>,
183 roots
: FxHashSet
<MonoItem
<'tcx
>>,
184 internalization_candidates
: FxHashSet
<MonoItem
<'tcx
>>,
187 /// For symbol internalization, we need to know whether a symbol/mono-item is
188 /// accessed from outside the codegen unit it is defined in. This type is used
189 /// to keep track of that.
190 #[derive(Clone, PartialEq, Eq, Debug)]
191 enum MonoItemPlacement
{
192 SingleCgu { cgu_name: Symbol }
,
196 struct PostInliningPartitioning
<'tcx
> {
197 codegen_units
: Vec
<CodegenUnit
<'tcx
>>,
198 mono_item_placements
: FxHashMap
<MonoItem
<'tcx
>, MonoItemPlacement
>,
199 internalization_candidates
: FxHashSet
<MonoItem
<'tcx
>>,
202 fn place_root_mono_items
<'tcx
, I
>(tcx
: TyCtxt
<'tcx
>, mono_items
: I
) -> PreInliningPartitioning
<'tcx
>
204 I
: Iterator
<Item
= MonoItem
<'tcx
>>,
206 let mut roots
= FxHashSet
::default();
207 let mut codegen_units
= FxHashMap
::default();
208 let is_incremental_build
= tcx
.sess
.opts
.incremental
.is_some();
209 let mut internalization_candidates
= FxHashSet
::default();
211 // Determine if monomorphizations instantiated in this crate will be made
212 // available to downstream crates. This depends on whether we are in
213 // share-generics mode and whether the current crate can even have
214 // downstream crates.
215 let export_generics
= tcx
.sess
.opts
.share_generics() && tcx
.local_crate_exports_generics();
217 let cgu_name_builder
= &mut CodegenUnitNameBuilder
::new(tcx
);
218 let cgu_name_cache
= &mut FxHashMap
::default();
220 for mono_item
in mono_items
{
221 match mono_item
.instantiation_mode(tcx
) {
222 InstantiationMode
::GloballyShared { .. }
=> {}
223 InstantiationMode
::LocalCopy
=> continue,
226 let characteristic_def_id
= characteristic_def_id_of_mono_item(tcx
, mono_item
);
227 let is_volatile
= is_incremental_build
&& mono_item
.is_generic_fn();
229 let codegen_unit_name
= match characteristic_def_id
{
230 Some(def_id
) => compute_codegen_unit_name(
237 None
=> fallback_cgu_name(cgu_name_builder
),
240 let codegen_unit
= codegen_units
241 .entry(codegen_unit_name
)
242 .or_insert_with(|| CodegenUnit
::new(codegen_unit_name
));
244 let mut can_be_internalized
= true;
245 let (linkage
, visibility
) = mono_item_linkage_and_visibility(
248 &mut can_be_internalized
,
251 if visibility
== Visibility
::Hidden
&& can_be_internalized
{
252 internalization_candidates
.insert(mono_item
);
255 codegen_unit
.items_mut().insert(mono_item
, (linkage
, visibility
));
256 roots
.insert(mono_item
);
259 // Always ensure we have at least one CGU; otherwise, if we have a
260 // crate with just types (for example), we could wind up with no CGU.
261 if codegen_units
.is_empty() {
262 let codegen_unit_name
= fallback_cgu_name(cgu_name_builder
);
263 codegen_units
.insert(codegen_unit_name
, CodegenUnit
::new(codegen_unit_name
));
266 PreInliningPartitioning
{
267 codegen_units
: codegen_units
.into_iter().map(|(_
, codegen_unit
)| codegen_unit
).collect(),
269 internalization_candidates
,
273 fn mono_item_linkage_and_visibility(
275 mono_item
: &MonoItem
<'tcx
>,
276 can_be_internalized
: &mut bool
,
277 export_generics
: bool
,
278 ) -> (Linkage
, Visibility
) {
279 if let Some(explicit_linkage
) = mono_item
.explicit_linkage(tcx
) {
280 return (explicit_linkage
, Visibility
::Default
);
282 let vis
= mono_item_visibility(tcx
, mono_item
, can_be_internalized
, export_generics
);
283 (Linkage
::External
, vis
)
286 fn mono_item_visibility(
288 mono_item
: &MonoItem
<'tcx
>,
289 can_be_internalized
: &mut bool
,
290 export_generics
: bool
,
292 let instance
= match mono_item
{
293 // This is pretty complicated; see below.
294 MonoItem
::Fn(instance
) => instance
,
296 // Misc handling for generics and such, but otherwise:
297 MonoItem
::Static(def_id
) => {
298 return if tcx
.is_reachable_non_generic(*def_id
) {
299 *can_be_internalized
= false;
300 default_visibility(tcx
, *def_id
, false)
305 MonoItem
::GlobalAsm(hir_id
) => {
306 let def_id
= tcx
.hir().local_def_id(*hir_id
);
307 return if tcx
.is_reachable_non_generic(def_id
) {
308 *can_be_internalized
= false;
309 default_visibility(tcx
, def_id
.to_def_id(), false)
316 let def_id
= match instance
.def
{
317 InstanceDef
::Item(def_id
) | InstanceDef
::DropGlue(def_id
, Some(_
)) => def_id
,
319 // These are all compiler glue and such, never exported, always hidden.
320 InstanceDef
::VtableShim(..)
321 | InstanceDef
::ReifyShim(..)
322 | InstanceDef
::FnPtrShim(..)
323 | InstanceDef
::Virtual(..)
324 | InstanceDef
::Intrinsic(..)
325 | InstanceDef
::ClosureOnceShim { .. }
326 | InstanceDef
::DropGlue(..)
327 | InstanceDef
::CloneShim(..) => return Visibility
::Hidden
,
330 // The `start_fn` lang item is actually a monomorphized instance of a
331 // function in the standard library, used for the `main` function. We don't
332 // want to export it so we tag it with `Hidden` visibility but this symbol
333 // is only referenced from the actual `main` symbol which we unfortunately
334 // don't know anything about during partitioning/collection. As a result we
335 // forcibly keep this symbol out of the `internalization_candidates` set.
337 // FIXME: eventually we don't want to always force this symbol to have
338 // hidden visibility, it should indeed be a candidate for
339 // internalization, but we have to understand that it's referenced
340 // from the `main` symbol we'll generate later.
342 // This may be fixable with a new `InstanceDef` perhaps? Unsure!
343 if tcx
.lang_items().start_fn() == Some(def_id
) {
344 *can_be_internalized
= false;
345 return Visibility
::Hidden
;
348 let is_generic
= instance
.substs
.non_erasable_generics().next().is_some();
350 // Upstream `DefId` instances get different handling than local ones.
351 if !def_id
.is_local() {
352 return if export_generics
&& is_generic
{
353 // If it is a upstream monomorphization and we export generics, we must make
354 // it available to downstream crates.
355 *can_be_internalized
= false;
356 default_visibility(tcx
, def_id
, true)
364 if tcx
.is_unreachable_local_definition(def_id
) {
365 // This instance cannot be used from another crate.
368 // This instance might be useful in a downstream crate.
369 *can_be_internalized
= false;
370 default_visibility(tcx
, def_id
, true)
373 // We are not exporting generics or the definition is not reachable
374 // for downstream crates, we can internalize its instantiations.
378 // If this isn't a generic function then we mark this a `Default` if
379 // this is a reachable item, meaning that it's a symbol other crates may
380 // access when they link to us.
381 if tcx
.is_reachable_non_generic(def_id
) {
382 *can_be_internalized
= false;
383 debug_assert
!(!is_generic
);
384 return default_visibility(tcx
, def_id
, false);
387 // If this isn't reachable then we're gonna tag this with `Hidden`
388 // visibility. In some situations though we'll want to prevent this
389 // symbol from being internalized.
391 // There's two categories of items here:
393 // * First is weak lang items. These are basically mechanisms for
394 // libcore to forward-reference symbols defined later in crates like
395 // the standard library or `#[panic_handler]` definitions. The
396 // definition of these weak lang items needs to be referenceable by
397 // libcore, so we're no longer a candidate for internalization.
398 // Removal of these functions can't be done by LLVM but rather must be
399 // done by the linker as it's a non-local decision.
401 // * Second is "std internal symbols". Currently this is primarily used
402 // for allocator symbols. Allocators are a little weird in their
403 // implementation, but the idea is that the compiler, at the last
404 // minute, defines an allocator with an injected object file. The
405 // `alloc` crate references these symbols (`__rust_alloc`) and the
406 // definition doesn't get hooked up until a linked crate artifact is
409 // The symbols synthesized by the compiler (`__rust_alloc`) are thin
410 // veneers around the actual implementation, some other symbol which
411 // implements the same ABI. These symbols (things like `__rg_alloc`,
412 // `__rdl_alloc`, `__rde_alloc`, etc), are all tagged with "std
413 // internal symbols".
415 // The std-internal symbols here **should not show up in a dll as an
416 // exported interface**, so they return `false` from
417 // `is_reachable_non_generic` above and we'll give them `Hidden`
418 // visibility below. Like the weak lang items, though, we can't let
419 // LLVM internalize them as this decision is left up to the linker to
420 // omit them, so prevent them from being internalized.
421 let attrs
= tcx
.codegen_fn_attrs(def_id
);
422 if attrs
.flags
.contains(CodegenFnAttrFlags
::RUSTC_STD_INTERNAL_SYMBOL
) {
423 *can_be_internalized
= false;
430 fn default_visibility(tcx
: TyCtxt
<'_
>, id
: DefId
, is_generic
: bool
) -> Visibility
{
431 if !tcx
.sess
.target
.target
.options
.default_hidden_visibility
{
432 return Visibility
::Default
;
435 // Generic functions never have export-level C.
437 return Visibility
::Hidden
;
440 // Things with export level C don't get instantiated in
441 // downstream crates.
443 return Visibility
::Hidden
;
446 // C-export level items remain at `Default`, all other internal
447 // items become `Hidden`.
448 match tcx
.reachable_non_generics(id
.krate
).get(&id
) {
449 Some(SymbolExportLevel
::C
) => Visibility
::Default
,
450 _
=> Visibility
::Hidden
,
454 fn merge_codegen_units
<'tcx
>(
456 initial_partitioning
: &mut PreInliningPartitioning
<'tcx
>,
457 target_cgu_count
: usize,
459 assert
!(target_cgu_count
>= 1);
460 let codegen_units
= &mut initial_partitioning
.codegen_units
;
462 // Note that at this point in time the `codegen_units` here may not be in a
463 // deterministic order (but we know they're deterministically the same set).
464 // We want this merging to produce a deterministic ordering of codegen units
467 // Due to basically how we've implemented the merging below (merge the two
468 // smallest into each other) we're sure to start off with a deterministic
469 // order (sorted by name). This'll mean that if two cgus have the same size
470 // the stable sort below will keep everything nice and deterministic.
471 codegen_units
.sort_by_cached_key(|cgu
| cgu
.name().as_str());
473 // This map keeps track of what got merged into what.
474 let mut cgu_contents
: FxHashMap
<Symbol
, Vec
<SymbolStr
>> =
475 codegen_units
.iter().map(|cgu
| (cgu
.name(), vec
![cgu
.name().as_str()])).collect();
477 // Merge the two smallest codegen units until the target size is reached.
478 while codegen_units
.len() > target_cgu_count
{
479 // Sort small cgus to the back
480 codegen_units
.sort_by_cached_key(|cgu
| cmp
::Reverse(cgu
.size_estimate()));
481 let mut smallest
= codegen_units
.pop().unwrap();
482 let second_smallest
= codegen_units
.last_mut().unwrap();
484 // Move the mono-items from `smallest` to `second_smallest`
485 second_smallest
.modify_size_estimate(smallest
.size_estimate());
486 for (k
, v
) in smallest
.items_mut().drain() {
487 second_smallest
.items_mut().insert(k
, v
);
490 // Record that `second_smallest` now contains all the stuff that was in
491 // `smallest` before.
492 let mut consumed_cgu_names
= cgu_contents
.remove(&smallest
.name()).unwrap();
493 cgu_contents
.get_mut(&second_smallest
.name()).unwrap().extend(consumed_cgu_names
.drain(..));
496 "CodegenUnit {} merged into CodegenUnit {}",
498 second_smallest
.name()
502 let cgu_name_builder
= &mut CodegenUnitNameBuilder
::new(tcx
);
504 if tcx
.sess
.opts
.incremental
.is_some() {
505 // If we are doing incremental compilation, we want CGU names to
506 // reflect the path of the source level module they correspond to.
507 // For CGUs that contain the code of multiple modules because of the
508 // merging done above, we use a concatenation of the names of
509 // all contained CGUs.
510 let new_cgu_names
: FxHashMap
<Symbol
, String
> = cgu_contents
512 // This `filter` makes sure we only update the name of CGUs that
513 // were actually modified by merging.
514 .filter(|(_
, cgu_contents
)| cgu_contents
.len() > 1)
515 .map(|(current_cgu_name
, cgu_contents
)| {
516 let mut cgu_contents
: Vec
<&str> = cgu_contents
.iter().map(|s
| &s
[..]).collect();
518 // Sort the names, so things are deterministic and easy to
522 (current_cgu_name
, cgu_contents
.join("--"))
526 for cgu
in codegen_units
.iter_mut() {
527 if let Some(new_cgu_name
) = new_cgu_names
.get(&cgu
.name()) {
528 if tcx
.sess
.opts
.debugging_opts
.human_readable_cgu_names
{
529 cgu
.set_name(Symbol
::intern(&new_cgu_name
));
531 // If we don't require CGU names to be human-readable, we
532 // use a fixed length hash of the composite CGU name
534 let new_cgu_name
= CodegenUnit
::mangle_name(&new_cgu_name
);
535 cgu
.set_name(Symbol
::intern(&new_cgu_name
));
540 // If we are compiling non-incrementally we just generate simple CGU
541 // names containing an index.
542 for (index
, cgu
) in codegen_units
.iter_mut().enumerate() {
543 cgu
.set_name(numbered_codegen_unit_name(cgu_name_builder
, index
));
548 fn place_inlined_mono_items
<'tcx
>(
549 initial_partitioning
: PreInliningPartitioning
<'tcx
>,
550 inlining_map
: &InliningMap
<'tcx
>,
551 ) -> PostInliningPartitioning
<'tcx
> {
552 let mut new_partitioning
= Vec
::new();
553 let mut mono_item_placements
= FxHashMap
::default();
555 let PreInliningPartitioning { codegen_units: initial_cgus, roots, internalization_candidates }
=
556 initial_partitioning
;
558 let single_codegen_unit
= initial_cgus
.len() == 1;
560 for old_codegen_unit
in initial_cgus
{
561 // Collect all items that need to be available in this codegen unit.
562 let mut reachable
= FxHashSet
::default();
563 for root
in old_codegen_unit
.items().keys() {
564 follow_inlining(*root
, inlining_map
, &mut reachable
);
567 let mut new_codegen_unit
= CodegenUnit
::new(old_codegen_unit
.name());
569 // Add all monomorphizations that are not already there.
570 for mono_item
in reachable
{
571 if let Some(linkage
) = old_codegen_unit
.items().get(&mono_item
) {
572 // This is a root, just copy it over.
573 new_codegen_unit
.items_mut().insert(mono_item
, *linkage
);
575 if roots
.contains(&mono_item
) {
577 "GloballyShared mono-item inlined into other CGU: \
583 // This is a CGU-private copy.
586 .insert(mono_item
, (Linkage
::Internal
, Visibility
::Default
));
589 if !single_codegen_unit
{
590 // If there is more than one codegen unit, we need to keep track
591 // in which codegen units each monomorphization is placed.
592 match mono_item_placements
.entry(mono_item
) {
593 Entry
::Occupied(e
) => {
594 let placement
= e
.into_mut();
595 debug_assert
!(match *placement
{
596 MonoItemPlacement
::SingleCgu { cgu_name }
=> {
597 cgu_name
!= new_codegen_unit
.name()
599 MonoItemPlacement
::MultipleCgus
=> true,
601 *placement
= MonoItemPlacement
::MultipleCgus
;
603 Entry
::Vacant(e
) => {
604 e
.insert(MonoItemPlacement
::SingleCgu
{
605 cgu_name
: new_codegen_unit
.name(),
612 new_partitioning
.push(new_codegen_unit
);
615 return PostInliningPartitioning
{
616 codegen_units
: new_partitioning
,
617 mono_item_placements
,
618 internalization_candidates
,
621 fn follow_inlining
<'tcx
>(
622 mono_item
: MonoItem
<'tcx
>,
623 inlining_map
: &InliningMap
<'tcx
>,
624 visited
: &mut FxHashSet
<MonoItem
<'tcx
>>,
626 if !visited
.insert(mono_item
) {
630 inlining_map
.with_inlining_candidates(mono_item
, |target
| {
631 follow_inlining(target
, inlining_map
, visited
);
636 fn internalize_symbols
<'tcx
>(
638 partitioning
: &mut PostInliningPartitioning
<'tcx
>,
639 inlining_map
: &InliningMap
<'tcx
>,
641 if partitioning
.codegen_units
.len() == 1 {
642 // Fast path for when there is only one codegen unit. In this case we
643 // can internalize all candidates, since there is nowhere else they
644 // could be accessed from.
645 for cgu
in &mut partitioning
.codegen_units
{
646 for candidate
in &partitioning
.internalization_candidates
{
647 cgu
.items_mut().insert(*candidate
, (Linkage
::Internal
, Visibility
::Default
));
654 // Build a map from every monomorphization to all the monomorphizations that
656 let mut accessor_map
: FxHashMap
<MonoItem
<'tcx
>, Vec
<MonoItem
<'tcx
>>> = Default
::default();
657 inlining_map
.iter_accesses(|accessor
, accessees
| {
658 for accessee
in accessees
{
659 accessor_map
.entry(*accessee
).or_default().push(accessor
);
663 let mono_item_placements
= &partitioning
.mono_item_placements
;
665 // For each internalization candidates in each codegen unit, check if it is
666 // accessed from outside its defining codegen unit.
667 for cgu
in &mut partitioning
.codegen_units
{
668 let home_cgu
= MonoItemPlacement
::SingleCgu { cgu_name: cgu.name() }
;
670 for (accessee
, linkage_and_visibility
) in cgu
.items_mut() {
671 if !partitioning
.internalization_candidates
.contains(accessee
) {
672 // This item is no candidate for internalizing, so skip it.
675 debug_assert_eq
!(mono_item_placements
[accessee
], home_cgu
);
677 if let Some(accessors
) = accessor_map
.get(accessee
) {
680 .filter_map(|accessor
| {
681 // Some accessors might not have been
682 // instantiated. We can safely ignore those.
683 mono_item_placements
.get(accessor
)
685 .any(|placement
| *placement
!= home_cgu
)
687 // Found an accessor from another CGU, so skip to the next
688 // item without marking this one as internal.
693 // If we got here, we did not find any accesses from other CGUs,
694 // so it's fine to make this monomorphization internal.
695 *linkage_and_visibility
= (Linkage
::Internal
, Visibility
::Default
);
700 fn characteristic_def_id_of_mono_item
<'tcx
>(
702 mono_item
: MonoItem
<'tcx
>,
705 MonoItem
::Fn(instance
) => {
706 let def_id
= match instance
.def
{
707 ty
::InstanceDef
::Item(def_id
) => def_id
,
708 ty
::InstanceDef
::VtableShim(..)
709 | ty
::InstanceDef
::ReifyShim(..)
710 | ty
::InstanceDef
::FnPtrShim(..)
711 | ty
::InstanceDef
::ClosureOnceShim { .. }
712 | ty
::InstanceDef
::Intrinsic(..)
713 | ty
::InstanceDef
::DropGlue(..)
714 | ty
::InstanceDef
::Virtual(..)
715 | ty
::InstanceDef
::CloneShim(..) => return None
,
718 // If this is a method, we want to put it into the same module as
719 // its self-type. If the self-type does not provide a characteristic
720 // DefId, we use the location of the impl after all.
722 if tcx
.trait_of_item(def_id
).is_some() {
723 let self_ty
= instance
.substs
.type_at(0);
724 // This is a default implementation of a trait method.
725 return characteristic_def_id_of_type(self_ty
).or(Some(def_id
));
728 if let Some(impl_def_id
) = tcx
.impl_of_method(def_id
) {
729 if tcx
.sess
.opts
.incremental
.is_some()
730 && tcx
.trait_id_of_impl(impl_def_id
) == tcx
.lang_items().drop_trait()
732 // Put `Drop::drop` into the same cgu as `drop_in_place`
733 // since `drop_in_place` is the only thing that can
737 // This is a method within an impl, find out what the self-type is:
738 let impl_self_ty
= tcx
.subst_and_normalize_erasing_regions(
740 ty
::ParamEnv
::reveal_all(),
741 &tcx
.type_of(impl_def_id
),
743 if let Some(def_id
) = characteristic_def_id_of_type(impl_self_ty
) {
750 MonoItem
::Static(def_id
) => Some(def_id
),
751 MonoItem
::GlobalAsm(hir_id
) => Some(tcx
.hir().local_def_id(hir_id
).to_def_id()),
755 type CguNameCache
= FxHashMap
<(DefId
, bool
), Symbol
>;
757 fn compute_codegen_unit_name(
759 name_builder
: &mut CodegenUnitNameBuilder
<'_
>,
762 cache
: &mut CguNameCache
,
764 // Find the innermost module that is not nested within a function.
765 let mut current_def_id
= def_id
;
766 let mut cgu_def_id
= None
;
767 // Walk backwards from the item we want to find the module for.
769 if current_def_id
.index
== CRATE_DEF_INDEX
{
770 if cgu_def_id
.is_none() {
771 // If we have not found a module yet, take the crate root.
772 cgu_def_id
= Some(DefId { krate: def_id.krate, index: CRATE_DEF_INDEX }
);
775 } else if tcx
.def_kind(current_def_id
) == DefKind
::Mod
{
776 if cgu_def_id
.is_none() {
777 cgu_def_id
= Some(current_def_id
);
780 // If we encounter something that is not a module, throw away
781 // any module that we've found so far because we now know that
782 // it is nested within something else.
786 current_def_id
= tcx
.parent(current_def_id
).unwrap();
789 let cgu_def_id
= cgu_def_id
.unwrap();
791 *cache
.entry((cgu_def_id
, volatile
)).or_insert_with(|| {
792 let def_path
= tcx
.def_path(cgu_def_id
);
794 let components
= def_path
.data
.iter().map(|part
| part
.data
.as_symbol());
796 let volatile_suffix
= volatile
.then_some("volatile");
798 name_builder
.build_cgu_name(def_path
.krate
, components
, volatile_suffix
)
802 fn numbered_codegen_unit_name(
803 name_builder
: &mut CodegenUnitNameBuilder
<'_
>,
806 name_builder
.build_cgu_name_no_mangle(LOCAL_CRATE
, &["cgu"], Some(index
))
809 fn debug_dump
<'a
, 'tcx
, I
>(tcx
: TyCtxt
<'tcx
>, label
: &str, cgus
: I
)
811 I
: Iterator
<Item
= &'a CodegenUnit
<'tcx
>>,
814 if cfg
!(debug_assertions
) {
817 debug
!("CodegenUnit {} estimated size {} :", cgu
.name(), cgu
.size_estimate());
819 for (mono_item
, linkage
) in cgu
.items() {
820 let symbol_name
= mono_item
.symbol_name(tcx
).name
.as_str();
821 let symbol_hash_start
= symbol_name
.rfind('h'
);
823 symbol_hash_start
.map(|i
| &symbol_name
[i
..]).unwrap_or("<no hash>");
826 " - {} [{:?}] [{}] estimated size {}",
827 mono_item
.to_string(tcx
, true),
830 mono_item
.size_estimate(tcx
)
839 #[inline(never)] // give this a place in the profiler
840 fn assert_symbols_are_distinct
<'a
, 'tcx
, I
>(tcx
: TyCtxt
<'tcx
>, mono_items
: I
)
842 I
: Iterator
<Item
= &'a MonoItem
<'tcx
>>,
845 let _prof_timer
= tcx
.prof
.generic_activity("assert_symbols_are_distinct");
847 let mut symbols
: Vec
<_
> =
848 mono_items
.map(|mono_item
| (mono_item
, mono_item
.symbol_name(tcx
))).collect();
850 symbols
.sort_by_key(|sym
| sym
.1);
852 for pair
in symbols
.windows(2) {
853 let sym1
= &pair
[0].1;
854 let sym2
= &pair
[1].1;
857 let mono_item1
= pair
[0].0;
858 let mono_item2
= pair
[1].0;
860 let span1
= mono_item1
.local_span(tcx
);
861 let span2
= mono_item2
.local_span(tcx
);
863 // Deterministically select one of the spans for error reporting
864 let span
= match (span1
, span2
) {
865 (Some(span1
), Some(span2
)) => {
866 Some(if span1
.lo().0 > span2
.lo().0 { span1 }
else { span2 }
)
868 (span1
, span2
) => span1
.or(span2
),
871 let error_message
= format
!("symbol `{}` is already defined", sym1
);
873 if let Some(span
) = span
{
874 tcx
.sess
.span_fatal(span
, &error_message
)
876 tcx
.sess
.fatal(&error_message
)
882 fn collect_and_partition_mono_items(
885 ) -> (&'tcx DefIdSet
, &'tcx
[CodegenUnit
<'tcx
>]) {
886 assert_eq
!(cnum
, LOCAL_CRATE
);
888 let collection_mode
= match tcx
.sess
.opts
.debugging_opts
.print_mono_items
{
890 let mode_string
= s
.to_lowercase();
891 let mode_string
= mode_string
.trim();
892 if mode_string
== "eager" {
893 MonoItemCollectionMode
::Eager
895 if mode_string
!= "lazy" {
896 let message
= format
!(
897 "Unknown codegen-item collection mode '{}'. \
898 Falling back to 'lazy' mode.",
901 tcx
.sess
.warn(&message
);
904 MonoItemCollectionMode
::Lazy
908 if tcx
.sess
.opts
.cg
.link_dead_code
{
909 MonoItemCollectionMode
::Eager
911 MonoItemCollectionMode
::Lazy
916 let (items
, inlining_map
) = collector
::collect_crate_mono_items(tcx
, collection_mode
);
918 tcx
.sess
.abort_if_errors();
920 let (codegen_units
, _
) = tcx
.sess
.time("partition_and_assert_distinct_symbols", || {
923 &*tcx
.arena
.alloc_from_iter(partition(
925 items
.iter().cloned(),
926 tcx
.sess
.codegen_units(),
930 || assert_symbols_are_distinct(tcx
, items
.iter()),
934 let mono_items
: DefIdSet
= items
936 .filter_map(|mono_item
| match *mono_item
{
937 MonoItem
::Fn(ref instance
) => Some(instance
.def_id()),
938 MonoItem
::Static(def_id
) => Some(def_id
),
943 if tcx
.sess
.opts
.debugging_opts
.print_mono_items
.is_some() {
944 let mut item_to_cgus
: FxHashMap
<_
, Vec
<_
>> = Default
::default();
946 for cgu
in codegen_units
{
947 for (&mono_item
, &linkage
) in cgu
.items() {
948 item_to_cgus
.entry(mono_item
).or_default().push((cgu
.name(), linkage
));
952 let mut item_keys
: Vec
<_
> = items
955 let mut output
= i
.to_string(tcx
, false);
956 output
.push_str(" @@");
957 let mut empty
= Vec
::new();
958 let cgus
= item_to_cgus
.get_mut(i
).unwrap_or(&mut empty
);
959 cgus
.sort_by_key(|(name
, _
)| *name
);
961 for &(ref cgu_name
, (linkage
, _
)) in cgus
.iter() {
962 output
.push_str(" ");
963 output
.push_str(&cgu_name
.as_str());
965 let linkage_abbrev
= match linkage
{
966 Linkage
::External
=> "External",
967 Linkage
::AvailableExternally
=> "Available",
968 Linkage
::LinkOnceAny
=> "OnceAny",
969 Linkage
::LinkOnceODR
=> "OnceODR",
970 Linkage
::WeakAny
=> "WeakAny",
971 Linkage
::WeakODR
=> "WeakODR",
972 Linkage
::Appending
=> "Appending",
973 Linkage
::Internal
=> "Internal",
974 Linkage
::Private
=> "Private",
975 Linkage
::ExternalWeak
=> "ExternalWeak",
976 Linkage
::Common
=> "Common",
979 output
.push_str("[");
980 output
.push_str(linkage_abbrev
);
981 output
.push_str("]");
989 for item
in item_keys
{
990 println
!("MONO_ITEM {}", item
);
994 (tcx
.arena
.alloc(mono_items
), codegen_units
)
997 pub fn provide(providers
: &mut Providers
) {
998 providers
.collect_and_partition_mono_items
= collect_and_partition_mono_items
;
1000 providers
.is_codegened_item
= |tcx
, def_id
| {
1001 let (all_mono_items
, _
) = tcx
.collect_and_partition_mono_items(LOCAL_CRATE
);
1002 all_mono_items
.contains(&def_id
)
1005 providers
.codegen_unit
= |tcx
, name
| {
1006 let (_
, all
) = tcx
.collect_and_partition_mono_items(LOCAL_CRATE
);
1008 .find(|cgu
| cgu
.name() == name
)
1009 .unwrap_or_else(|| panic
!("failed to find cgu with name {:?}", name
))