1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! Partitioning Codegen Units for Incremental Compilation
12 //! ======================================================
14 //! The task of this module is to take the complete set of translation items of
15 //! a crate and produce a set of codegen units from it, where a codegen unit
16 //! is a named set of (translation-item, linkage) pairs. That is, this module
17 //! decides which translation item appears in which codegen units with which
18 //! linkage. The following paragraphs describe some of the background on the
19 //! partitioning scheme.
21 //! The most important opportunity for saving on compilation time with
22 //! incremental compilation is to avoid re-translating and re-optimizing code.
23 //! Since the unit of translation and optimization for LLVM is "modules" or, how
24 //! we call them "codegen units", the particulars of how much time can be saved
25 //! by incremental compilation are tightly linked to how the output program is
26 //! partitioned into these codegen units prior to passing it to LLVM --
27 //! especially because we have to treat codegen units as opaque entities once
28 //! they are created: There is no way for us to incrementally update an existing
29 //! LLVM module and so we have to build any such module from scratch if it was
30 //! affected by some change in the source code.
32 //! From that point of view it would make sense to maximize the number of
33 //! codegen units by, for example, putting each function into its own module.
34 //! That way only those modules would have to be re-compiled that were actually
35 //! affected by some change, minimizing the number of functions that could have
36 //! been re-used but just happened to be located in a module that is
39 //! However, since LLVM optimization does not work across module boundaries,
40 //! using such a highly granular partitioning would lead to very slow runtime
41 //! code since it would effectively prohibit inlining and other inter-procedure
42 //! optimizations. We want to avoid that as much as possible.
44 //! Thus we end up with a trade-off: The bigger the codegen units, the better
45 //! LLVM's optimizer can do its work, but also the smaller the compilation time
46 //! reduction we get from incremental compilation.
48 //! Ideally, we would create a partitioning such that there are few big codegen
49 //! units with few interdependencies between them. For now though, we use the
50 //! following heuristic to determine the partitioning:
52 //! - There are two codegen units for every source-level module:
53 //! - One for "stable", that is non-generic, code
54 //! - One for more "volatile" code, i.e. monomorphized instances of functions
55 //! defined in that module
57 //! In order to see why this heuristic makes sense, let's take a look at when a
58 //! codegen unit can get invalidated:
60 //! 1. The most straightforward case is when the BODY of a function or global
61 //! changes. Then any codegen unit containing the code for that item has to be
62 //! re-compiled. Note that this includes all codegen units where the function
65 //! 2. The next case is when the SIGNATURE of a function or global changes. In
66 //! this case, all codegen units containing a REFERENCE to that item have to be
67 //! re-compiled. This is a superset of case 1.
69 //! 3. The final and most subtle case is when a REFERENCE to a generic function
70 //! is added or removed somewhere. Even though the definition of the function
71 //! might be unchanged, a new REFERENCE might introduce a new monomorphized
72 //! instance of this function which has to be placed and compiled somewhere.
73 //! Conversely, when removing a REFERENCE, it might have been the last one with
74 //! that particular set of generic arguments and thus we have to remove it.
76 //! From the above we see that just using one codegen unit per source-level
77 //! module is not such a good idea, since just adding a REFERENCE to some
78 //! generic item somewhere else would invalidate everything within the module
79 //! containing the generic item. The heuristic above reduces this detrimental
80 //! side-effect of references a little by at least not touching the non-generic
81 //! code of the module.
83 //! A Note on Inlining
84 //! ------------------
85 //! As briefly mentioned above, in order for LLVM to be able to inline a
86 //! function call, the body of the function has to be available in the LLVM
87 //! module where the call is made. This has a few consequences for partitioning:
89 //! - The partitioning algorithm has to take care of placing functions into all
90 //! codegen units where they should be available for inlining. It also has to
91 //! decide on the correct linkage for these functions.
93 //! - The partitioning algorithm has to know which functions are likely to get
94 //! inlined, so it can distribute function instantiations accordingly. Since
95 //! there is no way of knowing for sure which functions LLVM will decide to
96 //! inline in the end, we apply a heuristic here: Only functions marked with
97 //! #[inline] are considered for inlining by the partitioner. The current
98 //! implementation will not try to determine if a function is likely to be
99 //! inlined by looking at the functions definition.
101 //! Note though that as a side-effect of creating a codegen units per
102 //! source-level module, functions from the same module will be available for
103 //! inlining, even when they are not marked #[inline].
105 use collector
::InliningMap
;
107 use rustc
::dep_graph
::WorkProductId
;
108 use rustc
::hir
::def_id
::DefId
;
109 use rustc
::hir
::map
::DefPathData
;
110 use rustc
::middle
::trans
::{Linkage, Visibility}
;
111 use rustc
::ty
::{self, TyCtxt, InstanceDef}
;
112 use rustc
::ty
::item_path
::characteristic_def_id_of_type
;
113 use rustc
::util
::nodemap
::{FxHashMap, FxHashSet}
;
114 use std
::collections
::hash_map
::Entry
;
115 use syntax
::ast
::NodeId
;
116 use syntax
::symbol
::{Symbol, InternedString}
;
117 use trans_item
::{TransItem, BaseTransItemExt, TransItemExt, InstantiationMode}
;
119 pub use rustc
::middle
::trans
::CodegenUnit
;
121 pub enum PartitioningStrategy
{
122 /// Generate one codegen unit per source-level module.
125 /// Partition the whole crate into a fixed number of codegen units.
126 FixedUnitCount(usize)
129 pub trait CodegenUnitExt
<'tcx
> {
130 fn as_codegen_unit(&self) -> &CodegenUnit
<'tcx
>;
132 fn contains_item(&self, item
: &TransItem
<'tcx
>) -> bool
{
133 self.items().contains_key(item
)
136 fn name
<'a
>(&'a
self) -> &'a InternedString
139 &self.as_codegen_unit().name()
142 fn items(&self) -> &FxHashMap
<TransItem
<'tcx
>, (Linkage
, Visibility
)> {
143 &self.as_codegen_unit().items()
146 fn work_product_id(&self) -> WorkProductId
{
147 WorkProductId
::from_cgu_name(self.name())
150 fn items_in_deterministic_order
<'a
>(&self,
151 tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>)
152 -> Vec
<(TransItem
<'tcx
>,
153 (Linkage
, Visibility
))> {
154 // The codegen tests rely on items being process in the same order as
155 // they appear in the file, so for local items, we sort by node_id first
156 #[derive(PartialEq, Eq, PartialOrd, Ord)]
157 pub struct ItemSortKey(Option
<NodeId
>, ty
::SymbolName
);
159 fn item_sort_key
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
160 item
: TransItem
<'tcx
>) -> ItemSortKey
{
161 ItemSortKey(match item
{
162 TransItem
::Fn(ref instance
) => {
164 // We only want to take NodeIds of user-defined
165 // instances into account. The others don't matter for
166 // the codegen tests and can even make item order
168 InstanceDef
::Item(def_id
) => {
169 tcx
.hir
.as_local_node_id(def_id
)
171 InstanceDef
::Intrinsic(..) |
172 InstanceDef
::FnPtrShim(..) |
173 InstanceDef
::Virtual(..) |
174 InstanceDef
::ClosureOnceShim { .. }
|
175 InstanceDef
::DropGlue(..) |
176 InstanceDef
::CloneShim(..) => {
181 TransItem
::Static(node_id
) |
182 TransItem
::GlobalAsm(node_id
) => {
185 }, item
.symbol_name(tcx
))
188 let items
: Vec
<_
> = self.items().iter().map(|(&i
, &l
)| (i
, l
)).collect();
189 let mut items
: Vec
<_
> = items
.iter()
190 .map(|il
| (il
, item_sort_key(tcx
, il
.0))).collect();
191 items
.sort_by(|&(_
, ref key1
), &(_
, ref key2
)| key1
.cmp(key2
));
192 items
.into_iter().map(|(&item_linkage
, _
)| item_linkage
).collect()
196 impl<'tcx
> CodegenUnitExt
<'tcx
> for CodegenUnit
<'tcx
> {
197 fn as_codegen_unit(&self) -> &CodegenUnit
<'tcx
> {
202 // Anything we can't find a proper codegen unit for goes into this.
203 const FALLBACK_CODEGEN_UNIT
: &'
static str = "__rustc_fallback_codegen_unit";
205 pub fn partition
<'a
, 'tcx
, I
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
207 strategy
: PartitioningStrategy
,
208 inlining_map
: &InliningMap
<'tcx
>)
209 -> Vec
<CodegenUnit
<'tcx
>>
210 where I
: Iterator
<Item
= TransItem
<'tcx
>>
212 // In the first step, we place all regular translation items into their
213 // respective 'home' codegen unit. Regular translation items are all
214 // functions and statics defined in the local crate.
215 let mut initial_partitioning
= place_root_translation_items(tcx
,
218 debug_dump(tcx
, "INITIAL PARTITIONING:", initial_partitioning
.codegen_units
.iter());
220 // If the partitioning should produce a fixed count of codegen units, merge
221 // until that count is reached.
222 if let PartitioningStrategy
::FixedUnitCount(count
) = strategy
{
223 merge_codegen_units(&mut initial_partitioning
, count
, &tcx
.crate_name
.as_str());
225 debug_dump(tcx
, "POST MERGING:", initial_partitioning
.codegen_units
.iter());
228 // In the next step, we use the inlining map to determine which additional
229 // translation items have to go into each codegen unit. These additional
230 // translation items can be drop-glue, functions from external crates, and
231 // local functions the definition of which is marked with #[inline].
232 let mut post_inlining
= place_inlined_translation_items(initial_partitioning
,
235 debug_dump(tcx
, "POST INLINING:", post_inlining
.codegen_units
.iter());
237 // Next we try to make as many symbols "internal" as possible, so LLVM has
238 // more freedom to optimize.
239 internalize_symbols(tcx
, &mut post_inlining
, inlining_map
);
241 // Finally, sort by codegen unit name, so that we get deterministic results
242 let PostInliningPartitioning
{
243 codegen_units
: mut result
,
244 trans_item_placements
: _
,
245 internalization_candidates
: _
,
248 result
.sort_by(|cgu1
, cgu2
| {
249 cgu1
.name().cmp(cgu2
.name())
255 struct PreInliningPartitioning
<'tcx
> {
256 codegen_units
: Vec
<CodegenUnit
<'tcx
>>,
257 roots
: FxHashSet
<TransItem
<'tcx
>>,
258 internalization_candidates
: FxHashSet
<TransItem
<'tcx
>>,
261 /// For symbol internalization, we need to know whether a symbol/trans-item is
262 /// accessed from outside the codegen unit it is defined in. This type is used
263 /// to keep track of that.
264 #[derive(Clone, PartialEq, Eq, Debug)]
265 enum TransItemPlacement
{
266 SingleCgu { cgu_name: InternedString }
,
270 struct PostInliningPartitioning
<'tcx
> {
271 codegen_units
: Vec
<CodegenUnit
<'tcx
>>,
272 trans_item_placements
: FxHashMap
<TransItem
<'tcx
>, TransItemPlacement
>,
273 internalization_candidates
: FxHashSet
<TransItem
<'tcx
>>,
276 fn place_root_translation_items
<'a
, 'tcx
, I
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
278 -> PreInliningPartitioning
<'tcx
>
279 where I
: Iterator
<Item
= TransItem
<'tcx
>>
281 let mut roots
= FxHashSet();
282 let mut codegen_units
= FxHashMap();
283 let is_incremental_build
= tcx
.sess
.opts
.incremental
.is_some();
284 let mut internalization_candidates
= FxHashSet();
286 for trans_item
in trans_items
{
287 match trans_item
.instantiation_mode(tcx
) {
288 InstantiationMode
::GloballyShared { .. }
=> {}
289 InstantiationMode
::LocalCopy
=> continue,
292 let characteristic_def_id
= characteristic_def_id_of_trans_item(tcx
, trans_item
);
293 let is_volatile
= is_incremental_build
&&
294 trans_item
.is_generic_fn();
296 let codegen_unit_name
= match characteristic_def_id
{
297 Some(def_id
) => compute_codegen_unit_name(tcx
, def_id
, is_volatile
),
298 None
=> Symbol
::intern(FALLBACK_CODEGEN_UNIT
).as_str(),
301 let make_codegen_unit
= || {
302 CodegenUnit
::new(codegen_unit_name
.clone())
305 let codegen_unit
= codegen_units
.entry(codegen_unit_name
.clone())
306 .or_insert_with(make_codegen_unit
);
308 let (linkage
, visibility
) = match trans_item
.explicit_linkage(tcx
) {
309 Some(explicit_linkage
) => (explicit_linkage
, Visibility
::Default
),
312 TransItem
::Fn(ref instance
) => {
313 let visibility
= match instance
.def
{
314 InstanceDef
::Item(def_id
) => {
315 if def_id
.is_local() {
316 if tcx
.is_exported_symbol(def_id
) {
325 InstanceDef
::FnPtrShim(..) |
326 InstanceDef
::Virtual(..) |
327 InstanceDef
::Intrinsic(..) |
328 InstanceDef
::ClosureOnceShim { .. }
|
329 InstanceDef
::DropGlue(..) |
330 InstanceDef
::CloneShim(..) => {
334 (Linkage
::External
, visibility
)
336 TransItem
::Static(node_id
) |
337 TransItem
::GlobalAsm(node_id
) => {
338 let def_id
= tcx
.hir
.local_def_id(node_id
);
339 let visibility
= if tcx
.is_exported_symbol(def_id
) {
344 (Linkage
::External
, visibility
)
349 if visibility
== Visibility
::Hidden
{
350 internalization_candidates
.insert(trans_item
);
353 codegen_unit
.items_mut().insert(trans_item
, (linkage
, visibility
));
354 roots
.insert(trans_item
);
357 // always ensure we have at least one CGU; otherwise, if we have a
358 // crate with just types (for example), we could wind up with no CGU
359 if codegen_units
.is_empty() {
360 let codegen_unit_name
= Symbol
::intern(FALLBACK_CODEGEN_UNIT
).as_str();
361 codegen_units
.insert(codegen_unit_name
.clone(),
362 CodegenUnit
::new(codegen_unit_name
.clone()));
365 PreInliningPartitioning
{
366 codegen_units
: codegen_units
.into_iter()
367 .map(|(_
, codegen_unit
)| codegen_unit
)
370 internalization_candidates
,
374 fn merge_codegen_units
<'tcx
>(initial_partitioning
: &mut PreInliningPartitioning
<'tcx
>,
375 target_cgu_count
: usize,
377 assert
!(target_cgu_count
>= 1);
378 let codegen_units
= &mut initial_partitioning
.codegen_units
;
380 // Merge the two smallest codegen units until the target size is reached.
381 // Note that "size" is estimated here rather inaccurately as the number of
382 // translation items in a given unit. This could be improved on.
383 while codegen_units
.len() > target_cgu_count
{
384 // Sort small cgus to the back
385 codegen_units
.sort_by_key(|cgu
| -(cgu
.items().len() as i64));
386 let mut smallest
= codegen_units
.pop().unwrap();
387 let second_smallest
= codegen_units
.last_mut().unwrap();
389 for (k
, v
) in smallest
.items_mut().drain() {
390 second_smallest
.items_mut().insert(k
, v
);
394 for (index
, cgu
) in codegen_units
.iter_mut().enumerate() {
395 cgu
.set_name(numbered_codegen_unit_name(crate_name
, index
));
399 fn place_inlined_translation_items
<'tcx
>(initial_partitioning
: PreInliningPartitioning
<'tcx
>,
400 inlining_map
: &InliningMap
<'tcx
>)
401 -> PostInliningPartitioning
<'tcx
> {
402 let mut new_partitioning
= Vec
::new();
403 let mut trans_item_placements
= FxHashMap();
405 let PreInliningPartitioning
{
406 codegen_units
: initial_cgus
,
408 internalization_candidates
,
409 } = initial_partitioning
;
411 let single_codegen_unit
= initial_cgus
.len() == 1;
413 for old_codegen_unit
in initial_cgus
{
414 // Collect all items that need to be available in this codegen unit
415 let mut reachable
= FxHashSet();
416 for root
in old_codegen_unit
.items().keys() {
417 follow_inlining(*root
, inlining_map
, &mut reachable
);
420 let mut new_codegen_unit
= CodegenUnit
::new(old_codegen_unit
.name().clone());
422 // Add all translation items that are not already there
423 for trans_item
in reachable
{
424 if let Some(linkage
) = old_codegen_unit
.items().get(&trans_item
) {
425 // This is a root, just copy it over
426 new_codegen_unit
.items_mut().insert(trans_item
, *linkage
);
428 if roots
.contains(&trans_item
) {
429 bug
!("GloballyShared trans-item inlined into other CGU: \
433 // This is a cgu-private copy
434 new_codegen_unit
.items_mut().insert(
436 (Linkage
::Internal
, Visibility
::Default
),
440 if !single_codegen_unit
{
441 // If there is more than one codegen unit, we need to keep track
442 // in which codegen units each translation item is placed:
443 match trans_item_placements
.entry(trans_item
) {
444 Entry
::Occupied(e
) => {
445 let placement
= e
.into_mut();
446 debug_assert
!(match *placement
{
447 TransItemPlacement
::SingleCgu { ref cgu_name }
=> {
448 *cgu_name
!= *new_codegen_unit
.name()
450 TransItemPlacement
::MultipleCgus
=> true,
452 *placement
= TransItemPlacement
::MultipleCgus
;
454 Entry
::Vacant(e
) => {
455 e
.insert(TransItemPlacement
::SingleCgu
{
456 cgu_name
: new_codegen_unit
.name().clone()
463 new_partitioning
.push(new_codegen_unit
);
466 return PostInliningPartitioning
{
467 codegen_units
: new_partitioning
,
468 trans_item_placements
,
469 internalization_candidates
,
472 fn follow_inlining
<'tcx
>(trans_item
: TransItem
<'tcx
>,
473 inlining_map
: &InliningMap
<'tcx
>,
474 visited
: &mut FxHashSet
<TransItem
<'tcx
>>) {
475 if !visited
.insert(trans_item
) {
479 inlining_map
.with_inlining_candidates(trans_item
, |target
| {
480 follow_inlining(target
, inlining_map
, visited
);
485 fn internalize_symbols
<'a
, 'tcx
>(_tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
486 partitioning
: &mut PostInliningPartitioning
<'tcx
>,
487 inlining_map
: &InliningMap
<'tcx
>) {
488 if partitioning
.codegen_units
.len() == 1 {
489 // Fast path for when there is only one codegen unit. In this case we
490 // can internalize all candidates, since there is nowhere else they
491 // could be accessed from.
492 for cgu
in &mut partitioning
.codegen_units
{
493 for candidate
in &partitioning
.internalization_candidates
{
494 cgu
.items_mut().insert(*candidate
,
495 (Linkage
::Internal
, Visibility
::Default
));
502 // Build a map from every translation item to all the translation items that
504 let mut accessor_map
: FxHashMap
<TransItem
<'tcx
>, Vec
<TransItem
<'tcx
>>> = FxHashMap();
505 inlining_map
.iter_accesses(|accessor
, accessees
| {
506 for accessee
in accessees
{
507 accessor_map
.entry(*accessee
)
508 .or_insert(Vec
::new())
513 let trans_item_placements
= &partitioning
.trans_item_placements
;
515 // For each internalization candidates in each codegen unit, check if it is
516 // accessed from outside its defining codegen unit.
517 for cgu
in &mut partitioning
.codegen_units
{
518 let home_cgu
= TransItemPlacement
::SingleCgu
{
519 cgu_name
: cgu
.name().clone()
522 for (accessee
, linkage_and_visibility
) in cgu
.items_mut() {
523 if !partitioning
.internalization_candidates
.contains(accessee
) {
524 // This item is no candidate for internalizing, so skip it.
527 debug_assert_eq
!(trans_item_placements
[accessee
], home_cgu
);
529 if let Some(accessors
) = accessor_map
.get(accessee
) {
531 .filter_map(|accessor
| {
532 // Some accessors might not have been
533 // instantiated. We can safely ignore those.
534 trans_item_placements
.get(accessor
)
536 .any(|placement
| *placement
!= home_cgu
) {
537 // Found an accessor from another CGU, so skip to the next
538 // item without marking this one as internal.
543 // If we got here, we did not find any accesses from other CGUs,
544 // so it's fine to make this translation item internal.
545 *linkage_and_visibility
= (Linkage
::Internal
, Visibility
::Default
);
550 fn characteristic_def_id_of_trans_item
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
551 trans_item
: TransItem
<'tcx
>)
554 TransItem
::Fn(instance
) => {
555 let def_id
= match instance
.def
{
556 ty
::InstanceDef
::Item(def_id
) => def_id
,
557 ty
::InstanceDef
::FnPtrShim(..) |
558 ty
::InstanceDef
::ClosureOnceShim { .. }
|
559 ty
::InstanceDef
::Intrinsic(..) |
560 ty
::InstanceDef
::DropGlue(..) |
561 ty
::InstanceDef
::Virtual(..) |
562 ty
::InstanceDef
::CloneShim(..) => return None
565 // If this is a method, we want to put it into the same module as
566 // its self-type. If the self-type does not provide a characteristic
567 // DefId, we use the location of the impl after all.
569 if tcx
.trait_of_item(def_id
).is_some() {
570 let self_ty
= instance
.substs
.type_at(0);
571 // This is an implementation of a trait method.
572 return characteristic_def_id_of_type(self_ty
).or(Some(def_id
));
575 if let Some(impl_def_id
) = tcx
.impl_of_method(def_id
) {
576 // This is a method within an inherent impl, find out what the
578 let impl_self_ty
= common
::def_ty(tcx
, impl_def_id
, instance
.substs
);
579 if let Some(def_id
) = characteristic_def_id_of_type(impl_self_ty
) {
586 TransItem
::Static(node_id
) |
587 TransItem
::GlobalAsm(node_id
) => Some(tcx
.hir
.local_def_id(node_id
)),
591 fn compute_codegen_unit_name
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
595 // Unfortunately we cannot just use the `ty::item_path` infrastructure here
596 // because we need paths to modules and the DefIds of those are not
597 // available anymore for external items.
598 let mut mod_path
= String
::with_capacity(64);
600 let def_path
= tcx
.def_path(def_id
);
601 mod_path
.push_str(&tcx
.crate_name(def_path
.krate
).as_str());
603 for part
in tcx
.def_path(def_id
)
608 DefPathData
::Module(..) => true,
612 mod_path
.push_str("-");
613 mod_path
.push_str(&part
.data
.as_interned_str());
617 mod_path
.push_str(".volatile");
620 return Symbol
::intern(&mod_path
[..]).as_str();
623 fn numbered_codegen_unit_name(crate_name
: &str, index
: usize) -> InternedString
{
624 Symbol
::intern(&format
!("{}{}", crate_name
, index
)).as_str()
627 fn debug_dump
<'a
, 'b
, 'tcx
, I
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
630 where I
: Iterator
<Item
=&'b CodegenUnit
<'tcx
>>,
633 if cfg
!(debug_assertions
) {
636 debug
!("CodegenUnit {}:", cgu
.name());
638 for (trans_item
, linkage
) in cgu
.items() {
639 let symbol_name
= trans_item
.symbol_name(tcx
);
640 let symbol_hash_start
= symbol_name
.rfind('h'
);
641 let symbol_hash
= symbol_hash_start
.map(|i
| &symbol_name
[i
..])
642 .unwrap_or("<no hash>");
644 debug
!(" - {} [{:?}] [{}]",
645 trans_item
.to_string(tcx
),