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
56 //! - Code for monomorphized instances of functions from external crates gets
57 //! placed into every codegen unit that uses that instance.
59 //! In order to see why this heuristic makes sense, let's take a look at when a
60 //! codegen unit can get invalidated:
62 //! 1. The most straightforward case is when the BODY of a function or global
63 //! changes. Then any codegen unit containing the code for that item has to be
64 //! re-compiled. Note that this includes all codegen units where the function
67 //! 2. The next case is when the SIGNATURE of a function or global changes. In
68 //! this case, all codegen units containing a REFERENCE to that item have to be
69 //! re-compiled. This is a superset of case 1.
71 //! 3. The final and most subtle case is when a REFERENCE to a generic function
72 //! is added or removed somewhere. Even though the definition of the function
73 //! might be unchanged, a new REFERENCE might introduce a new monomorphized
74 //! instance of this function which has to be placed and compiled somewhere.
75 //! Conversely, when removing a REFERENCE, it might have been the last one with
76 //! that particular set of generic arguments and thus we have to remove it.
78 //! From the above we see that just using one codegen unit per source-level
79 //! module is not such a good idea, since just adding a REFERENCE to some
80 //! generic item somewhere else would invalidate everything within the module
81 //! containing the generic item. The heuristic above reduces this detrimental
82 //! side-effect of references a little by at least not touching the non-generic
83 //! code of the module.
85 //! As another optimization, monomorphized functions from external crates get
86 //! some special handling. Since we assume that the definition of such a
87 //! function changes rather infrequently compared to local items, we can just
88 //! instantiate external functions in every codegen unit where it is referenced
89 //! -- without having to fear that doing this will cause a lot of unnecessary
90 //! re-compilations. If such a reference is added or removed, the codegen unit
91 //! has to be re-translated anyway.
92 //! (Note that this only makes sense if external crates actually don't change
93 //! frequently. For certain multi-crate projects this might not be a valid
96 //! A Note on Inlining
97 //! ------------------
98 //! As briefly mentioned above, in order for LLVM to be able to inline a
99 //! function call, the body of the function has to be available in the LLVM
100 //! module where the call is made. This has a few consequences for partitioning:
102 //! - The partitioning algorithm has to take care of placing functions into all
103 //! codegen units where they should be available for inlining. It also has to
104 //! decide on the correct linkage for these functions.
106 //! - The partitioning algorithm has to know which functions are likely to get
107 //! inlined, so it can distribute function instantiations accordingly. Since
108 //! there is no way of knowing for sure which functions LLVM will decide to
109 //! inline in the end, we apply a heuristic here: Only functions marked with
110 //! #[inline] and (as stated above) functions from external crates are
111 //! considered for inlining by the partitioner. The current implementation
112 //! will not try to determine if a function is likely to be inlined by looking
113 //! at the functions definition.
115 //! Note though that as a side-effect of creating a codegen units per
116 //! source-level module, functions from the same module will be available for
117 //! inlining, even when they are not marked #[inline].
119 use collector
::InliningMap
;
122 use rustc
::dep_graph
::{DepNode, WorkProductId}
;
123 use rustc
::hir
::def_id
::DefId
;
124 use rustc
::hir
::map
::DefPathData
;
125 use rustc
::session
::config
::NUMBERED_CODEGEN_UNIT_MARKER
;
126 use rustc
::ty
::TyCtxt
;
127 use rustc
::ty
::item_path
::characteristic_def_id_of_type
;
128 use std
::cmp
::Ordering
;
129 use std
::hash
::{Hash, Hasher, SipHasher}
;
131 use symbol_map
::SymbolMap
;
132 use syntax
::ast
::NodeId
;
133 use syntax
::parse
::token
::{self, InternedString}
;
134 use trans_item
::TransItem
;
135 use util
::nodemap
::{FnvHashMap, FnvHashSet, NodeSet}
;
137 pub enum PartitioningStrategy
{
138 /// Generate one codegen unit per source-level module.
141 /// Partition the whole crate into a fixed number of codegen units.
142 FixedUnitCount(usize)
145 pub struct CodegenUnit
<'tcx
> {
146 /// A name for this CGU. Incremental compilation requires that
147 /// name be unique amongst **all** crates. Therefore, it should
148 /// contain something unique to this crate (e.g., a module path)
149 /// as well as the crate name and disambiguator.
150 name
: InternedString
,
152 items
: FnvHashMap
<TransItem
<'tcx
>, llvm
::Linkage
>,
155 impl<'tcx
> CodegenUnit
<'tcx
> {
156 pub fn new(name
: InternedString
,
157 items
: FnvHashMap
<TransItem
<'tcx
>, llvm
::Linkage
>)
165 pub fn empty(name
: InternedString
) -> Self {
166 Self::new(name
, FnvHashMap())
169 pub fn contains_item(&self, item
: &TransItem
<'tcx
>) -> bool
{
170 self.items
.contains_key(item
)
173 pub fn name(&self) -> &str {
177 pub fn items(&self) -> &FnvHashMap
<TransItem
<'tcx
>, llvm
::Linkage
> {
181 pub fn work_product_id(&self) -> Arc
<WorkProductId
> {
182 Arc
::new(WorkProductId(self.name().to_string()))
185 pub fn work_product_dep_node(&self) -> DepNode
<DefId
> {
186 DepNode
::WorkProduct(self.work_product_id())
189 pub fn compute_symbol_name_hash(&self, tcx
: TyCtxt
, symbol_map
: &SymbolMap
) -> u64 {
190 let mut state
= SipHasher
::new();
191 let all_items
= self.items_in_deterministic_order(tcx
, symbol_map
);
192 for (item
, _
) in all_items
{
193 let symbol_name
= symbol_map
.get(item
).unwrap();
194 symbol_name
.hash(&mut state
);
199 pub fn items_in_deterministic_order(&self,
201 symbol_map
: &SymbolMap
)
202 -> Vec
<(TransItem
<'tcx
>, llvm
::Linkage
)> {
203 let mut items
: Vec
<(TransItem
<'tcx
>, llvm
::Linkage
)> =
204 self.items
.iter().map(|(item
, linkage
)| (*item
, *linkage
)).collect();
206 // The codegen tests rely on items being process in the same order as
207 // they appear in the file, so for local items, we sort by node_id first
208 items
.sort_by(|&(trans_item1
, _
), &(trans_item2
, _
)| {
209 let node_id1
= local_node_id(tcx
, trans_item1
);
210 let node_id2
= local_node_id(tcx
, trans_item2
);
212 match (node_id1
, node_id2
) {
214 let symbol_name1
= symbol_map
.get(trans_item1
).unwrap();
215 let symbol_name2
= symbol_map
.get(trans_item2
).unwrap();
216 symbol_name1
.cmp(symbol_name2
)
218 // In the following two cases we can avoid looking up the symbol
219 (None
, Some(_
)) => Ordering
::Less
,
220 (Some(_
), None
) => Ordering
::Greater
,
221 (Some(node_id1
), Some(node_id2
)) => {
222 let ordering
= node_id1
.cmp(&node_id2
);
224 if ordering
!= Ordering
::Equal
{
228 let symbol_name1
= symbol_map
.get(trans_item1
).unwrap();
229 let symbol_name2
= symbol_map
.get(trans_item2
).unwrap();
230 symbol_name1
.cmp(symbol_name2
)
237 fn local_node_id(tcx
: TyCtxt
, trans_item
: TransItem
) -> Option
<NodeId
> {
239 TransItem
::Fn(instance
) => {
240 tcx
.map
.as_local_node_id(instance
.def
)
242 TransItem
::Static(node_id
) => Some(node_id
),
243 TransItem
::DropGlue(_
) => None
,
250 // Anything we can't find a proper codegen unit for goes into this.
251 const FALLBACK_CODEGEN_UNIT
: &'
static str = "__rustc_fallback_codegen_unit";
253 pub fn partition
<'a
, 'tcx
, I
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
255 strategy
: PartitioningStrategy
,
256 inlining_map
: &InliningMap
<'tcx
>,
258 -> Vec
<CodegenUnit
<'tcx
>>
259 where I
: Iterator
<Item
= TransItem
<'tcx
>>
261 if let PartitioningStrategy
::FixedUnitCount(1) = strategy
{
262 // If there is only a single codegen-unit, we can use a very simple
263 // scheme and don't have to bother with doing much analysis.
264 return vec
![single_codegen_unit(tcx
, trans_items
, reachable
)];
267 // In the first step, we place all regular translation items into their
268 // respective 'home' codegen unit. Regular translation items are all
269 // functions and statics defined in the local crate.
270 let mut initial_partitioning
= place_root_translation_items(tcx
,
274 debug_dump(tcx
, "INITIAL PARTITONING:", initial_partitioning
.codegen_units
.iter());
276 // If the partitioning should produce a fixed count of codegen units, merge
277 // until that count is reached.
278 if let PartitioningStrategy
::FixedUnitCount(count
) = strategy
{
279 merge_codegen_units(&mut initial_partitioning
, count
, &tcx
.crate_name
[..]);
281 debug_dump(tcx
, "POST MERGING:", initial_partitioning
.codegen_units
.iter());
284 // In the next step, we use the inlining map to determine which addtional
285 // translation items have to go into each codegen unit. These additional
286 // translation items can be drop-glue, functions from external crates, and
287 // local functions the definition of which is marked with #[inline].
288 let post_inlining
= place_inlined_translation_items(initial_partitioning
,
291 debug_dump(tcx
, "POST INLINING:", post_inlining
.0.iter
());
293 // Finally, sort by codegen unit name, so that we get deterministic results
294 let mut result
= post_inlining
.0;
295 result
.sort_by(|cgu1
, cgu2
| {
296 (&cgu1
.name
[..]).cmp(&cgu2
.name
[..])
302 struct PreInliningPartitioning
<'tcx
> {
303 codegen_units
: Vec
<CodegenUnit
<'tcx
>>,
304 roots
: FnvHashSet
<TransItem
<'tcx
>>,
307 struct PostInliningPartitioning
<'tcx
>(Vec
<CodegenUnit
<'tcx
>>);
309 fn place_root_translation_items
<'a
, 'tcx
, I
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
311 _reachable
: &NodeSet
)
312 -> PreInliningPartitioning
<'tcx
>
313 where I
: Iterator
<Item
= TransItem
<'tcx
>>
315 let mut roots
= FnvHashSet();
316 let mut codegen_units
= FnvHashMap();
318 for trans_item
in trans_items
{
319 let is_root
= !trans_item
.is_instantiated_only_on_demand();
322 let characteristic_def_id
= characteristic_def_id_of_trans_item(tcx
, trans_item
);
323 let is_volatile
= trans_item
.is_generic_fn();
325 let codegen_unit_name
= match characteristic_def_id
{
326 Some(def_id
) => compute_codegen_unit_name(tcx
, def_id
, is_volatile
),
327 None
=> InternedString
::new(FALLBACK_CODEGEN_UNIT
),
330 let make_codegen_unit
= || {
331 CodegenUnit
::empty(codegen_unit_name
.clone())
334 let mut codegen_unit
= codegen_units
.entry(codegen_unit_name
.clone())
335 .or_insert_with(make_codegen_unit
);
337 let linkage
= match trans_item
.explicit_linkage(tcx
) {
338 Some(explicit_linkage
) => explicit_linkage
,
341 TransItem
::Static(..) => llvm
::ExternalLinkage
,
342 TransItem
::DropGlue(..) => unreachable
!(),
343 // Is there any benefit to using ExternalLinkage?:
344 TransItem
::Fn(ref instance
) => {
345 if instance
.substs
.types
.is_empty() {
346 // This is a non-generic functions, we always
347 // make it visible externally on the chance that
348 // it might be used in another codegen unit.
349 llvm
::ExternalLinkage
351 // In the current setup, generic functions cannot
360 codegen_unit
.items
.insert(trans_item
, linkage
);
361 roots
.insert(trans_item
);
365 // always ensure we have at least one CGU; otherwise, if we have a
366 // crate with just types (for example), we could wind up with no CGU
367 if codegen_units
.is_empty() {
368 let codegen_unit_name
= InternedString
::new(FALLBACK_CODEGEN_UNIT
);
369 codegen_units
.entry(codegen_unit_name
.clone())
370 .or_insert_with(|| CodegenUnit
::empty(codegen_unit_name
.clone()));
373 PreInliningPartitioning
{
374 codegen_units
: codegen_units
.into_iter()
375 .map(|(_
, codegen_unit
)| codegen_unit
)
381 fn merge_codegen_units
<'tcx
>(initial_partitioning
: &mut PreInliningPartitioning
<'tcx
>,
382 target_cgu_count
: usize,
384 assert
!(target_cgu_count
>= 1);
385 let codegen_units
= &mut initial_partitioning
.codegen_units
;
387 // Merge the two smallest codegen units until the target size is reached.
388 // Note that "size" is estimated here rather inaccurately as the number of
389 // translation items in a given unit. This could be improved on.
390 while codegen_units
.len() > target_cgu_count
{
391 // Sort small cgus to the back
392 codegen_units
.sort_by_key(|cgu
| -(cgu
.items
.len() as i64));
393 let smallest
= codegen_units
.pop().unwrap();
394 let second_smallest
= codegen_units
.last_mut().unwrap();
396 for (k
, v
) in smallest
.items
.into_iter() {
397 second_smallest
.items
.insert(k
, v
);
401 for (index
, cgu
) in codegen_units
.iter_mut().enumerate() {
402 cgu
.name
= numbered_codegen_unit_name(crate_name
, index
);
405 // If the initial partitioning contained less than target_cgu_count to begin
406 // with, we won't have enough codegen units here, so add a empty units until
407 // we reach the target count
408 while codegen_units
.len() < target_cgu_count
{
409 let index
= codegen_units
.len();
411 CodegenUnit
::empty(numbered_codegen_unit_name(crate_name
, index
)));
415 fn place_inlined_translation_items
<'tcx
>(initial_partitioning
: PreInliningPartitioning
<'tcx
>,
416 inlining_map
: &InliningMap
<'tcx
>)
417 -> PostInliningPartitioning
<'tcx
> {
418 let mut new_partitioning
= Vec
::new();
420 for codegen_unit
in &initial_partitioning
.codegen_units
[..] {
421 // Collect all items that need to be available in this codegen unit
422 let mut reachable
= FnvHashSet();
423 for root
in codegen_unit
.items
.keys() {
424 follow_inlining(*root
, inlining_map
, &mut reachable
);
427 let mut new_codegen_unit
=
428 CodegenUnit
::empty(codegen_unit
.name
.clone());
430 // Add all translation items that are not already there
431 for trans_item
in reachable
{
432 if let Some(linkage
) = codegen_unit
.items
.get(&trans_item
) {
433 // This is a root, just copy it over
434 new_codegen_unit
.items
.insert(trans_item
, *linkage
);
435 } else if initial_partitioning
.roots
.contains(&trans_item
) {
436 // This item will be instantiated in some other codegen unit,
437 // so we just add it here with AvailableExternallyLinkage
438 // FIXME(mw): I have not seen it happening yet but having
439 // available_externally here could potentially lead
440 // to the same problem with exception handling tables
441 // as in the case below.
442 new_codegen_unit
.items
.insert(trans_item
,
443 llvm
::AvailableExternallyLinkage
);
444 } else if trans_item
.is_from_extern_crate() && !trans_item
.is_generic_fn() {
445 // FIXME(mw): It would be nice if we could mark these as
446 // `AvailableExternallyLinkage`, since they should have
447 // been instantiated in the extern crate. But this
448 // sometimes leads to crashes on Windows because LLVM
449 // does not handle exception handling table instantiation
450 // reliably in that case.
451 new_codegen_unit
.items
.insert(trans_item
, llvm
::InternalLinkage
);
453 assert
!(trans_item
.is_instantiated_only_on_demand());
454 // We can't be sure if this will also be instantiated
455 // somewhere else, so we add an instance here with
456 // InternalLinkage so we don't get any conflicts.
457 new_codegen_unit
.items
.insert(trans_item
,
458 llvm
::InternalLinkage
);
462 new_partitioning
.push(new_codegen_unit
);
465 return PostInliningPartitioning(new_partitioning
);
467 fn follow_inlining
<'tcx
>(trans_item
: TransItem
<'tcx
>,
468 inlining_map
: &InliningMap
<'tcx
>,
469 visited
: &mut FnvHashSet
<TransItem
<'tcx
>>) {
470 if !visited
.insert(trans_item
) {
474 inlining_map
.with_inlining_candidates(trans_item
, |target
| {
475 follow_inlining(target
, inlining_map
, visited
);
480 fn characteristic_def_id_of_trans_item
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
481 trans_item
: TransItem
<'tcx
>)
484 TransItem
::Fn(instance
) => {
485 // If this is a method, we want to put it into the same module as
486 // its self-type. If the self-type does not provide a characteristic
487 // DefId, we use the location of the impl after all.
489 if let Some(self_ty
) = instance
.substs
.self_ty() {
490 // This is an implementation of a trait method.
491 return characteristic_def_id_of_type(self_ty
).or(Some(instance
.def
));
494 if let Some(impl_def_id
) = tcx
.impl_of_method(instance
.def
) {
495 // This is a method within an inherent impl, find out what the
497 let impl_self_ty
= tcx
.lookup_item_type(impl_def_id
).ty
;
498 let impl_self_ty
= tcx
.erase_regions(&impl_self_ty
);
499 let impl_self_ty
= monomorphize
::apply_param_substs(tcx
,
503 if let Some(def_id
) = characteristic_def_id_of_type(impl_self_ty
) {
510 TransItem
::DropGlue(dg
) => characteristic_def_id_of_type(dg
.ty()),
511 TransItem
::Static(node_id
) => Some(tcx
.map
.local_def_id(node_id
)),
515 fn compute_codegen_unit_name
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
519 // Unfortunately we cannot just use the `ty::item_path` infrastructure here
520 // because we need paths to modules and the DefIds of those are not
521 // available anymore for external items.
522 let mut mod_path
= String
::with_capacity(64);
524 let def_path
= tcx
.def_path(def_id
);
525 mod_path
.push_str(&tcx
.crate_name(def_path
.krate
));
527 for part
in tcx
.def_path(def_id
)
532 DefPathData
::Module(..) => true,
536 mod_path
.push_str("-");
537 mod_path
.push_str(&part
.data
.as_interned_str());
541 mod_path
.push_str(".volatile");
544 return token
::intern_and_get_ident(&mod_path
[..]);
547 fn single_codegen_unit
<'a
, 'tcx
, I
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
551 where I
: Iterator
<Item
= TransItem
<'tcx
>>
553 let mut items
= FnvHashMap();
555 for trans_item
in trans_items
{
556 let linkage
= trans_item
.explicit_linkage(tcx
).unwrap_or_else(|| {
558 TransItem
::Static(node_id
) => {
559 if reachable
.contains(&node_id
) {
560 llvm
::ExternalLinkage
565 TransItem
::DropGlue(_
) => {
566 llvm
::InternalLinkage
568 TransItem
::Fn(instance
) => {
569 if trans_item
.is_generic_fn() {
570 // FIXME(mw): Assigning internal linkage to all
571 // monomorphizations is potentially a waste of space
572 // since monomorphizations could be shared between
573 // crates. The main reason for making them internal is
574 // a limitation in MingW's binutils that cannot deal
575 // with COFF object that have more than 2^15 sections,
576 // which is something that can happen for large programs
577 // when every function gets put into its own COMDAT
579 llvm
::InternalLinkage
580 } else if trans_item
.is_from_extern_crate() {
581 // FIXME(mw): It would be nice if we could mark these as
582 // `AvailableExternallyLinkage`, since they should have
583 // been instantiated in the extern crate. But this
584 // sometimes leads to crashes on Windows because LLVM
585 // does not handle exception handling table instantiation
586 // reliably in that case.
587 llvm
::InternalLinkage
588 } else if reachable
.contains(&tcx
.map
589 .as_local_node_id(instance
.def
)
591 llvm
::ExternalLinkage
593 // Functions that are not visible outside this crate can
594 // be marked as internal.
595 llvm
::InternalLinkage
601 items
.insert(trans_item
, linkage
);
605 numbered_codegen_unit_name(&tcx
.crate_name
[..], 0),
609 fn numbered_codegen_unit_name(crate_name
: &str, index
: usize) -> InternedString
{
610 token
::intern_and_get_ident(&format
!("{}{}{}",
612 NUMBERED_CODEGEN_UNIT_MARKER
,
616 fn debug_dump
<'a
, 'b
, 'tcx
, I
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
619 where I
: Iterator
<Item
=&'b CodegenUnit
<'tcx
>>,
622 if cfg
!(debug_assertions
) {
625 debug
!("CodegenUnit {}:", cgu
.name
);
627 for (trans_item
, linkage
) in &cgu
.items
{
628 debug
!(" - {} [{:?}]", trans_item
.to_string(tcx
), linkage
);