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 context
::SharedCrateContext
;
109 use rustc
::dep_graph
::{DepNode, WorkProductId}
;
110 use rustc
::hir
::def_id
::DefId
;
111 use rustc
::hir
::map
::DefPathData
;
112 use rustc
::session
::config
::NUMBERED_CODEGEN_UNIT_MARKER
;
113 use rustc
::ty
::{self, TyCtxt}
;
114 use rustc
::ty
::item_path
::characteristic_def_id_of_type
;
115 use rustc_incremental
::IchHasher
;
117 use syntax
::ast
::NodeId
;
118 use syntax
::symbol
::{Symbol, InternedString}
;
119 use trans_item
::{TransItem, InstantiationMode}
;
120 use rustc
::util
::nodemap
::{FxHashMap, FxHashSet}
;
122 pub enum PartitioningStrategy
{
123 /// Generate one codegen unit per source-level module.
126 /// Partition the whole crate into a fixed number of codegen units.
127 FixedUnitCount(usize)
130 pub struct CodegenUnit
<'tcx
> {
131 /// A name for this CGU. Incremental compilation requires that
132 /// name be unique amongst **all** crates. Therefore, it should
133 /// contain something unique to this crate (e.g., a module path)
134 /// as well as the crate name and disambiguator.
135 name
: InternedString
,
137 items
: FxHashMap
<TransItem
<'tcx
>, llvm
::Linkage
>,
140 impl<'tcx
> CodegenUnit
<'tcx
> {
141 pub fn new(name
: InternedString
,
142 items
: FxHashMap
<TransItem
<'tcx
>, llvm
::Linkage
>)
150 pub fn empty(name
: InternedString
) -> Self {
151 Self::new(name
, FxHashMap())
154 pub fn contains_item(&self, item
: &TransItem
<'tcx
>) -> bool
{
155 self.items
.contains_key(item
)
158 pub fn name(&self) -> &str {
162 pub fn items(&self) -> &FxHashMap
<TransItem
<'tcx
>, llvm
::Linkage
> {
166 pub fn work_product_id(&self) -> WorkProductId
{
167 WorkProductId
::from_cgu_name(self.name())
170 pub fn work_product_dep_node(&self) -> DepNode
{
171 self.work_product_id().to_dep_node()
174 pub fn compute_symbol_name_hash
<'a
>(&self,
175 scx
: &SharedCrateContext
<'a
, 'tcx
>)
177 let mut state
= IchHasher
::new();
178 let exported_symbols
= scx
.exported_symbols();
179 let all_items
= self.items_in_deterministic_order(scx
.tcx());
180 for (item
, _
) in all_items
{
181 let symbol_name
= item
.symbol_name(scx
.tcx());
182 symbol_name
.len().hash(&mut state
);
183 symbol_name
.hash(&mut state
);
184 let exported
= match item
{
185 TransItem
::Fn(ref instance
) => {
187 scx
.tcx().hir
.as_local_node_id(instance
.def_id());
188 node_id
.map(|node_id
| exported_symbols
.contains(&node_id
))
191 TransItem
::Static(node_id
) => {
192 exported_symbols
.contains(&node_id
)
194 TransItem
::GlobalAsm(..) => true,
196 exported
.hash(&mut state
);
198 state
.finish().to_smaller_hash()
201 pub fn items_in_deterministic_order
<'a
>(&self,
202 tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>)
203 -> Vec
<(TransItem
<'tcx
>, llvm
::Linkage
)> {
204 // The codegen tests rely on items being process in the same order as
205 // they appear in the file, so for local items, we sort by node_id first
206 #[derive(PartialEq, Eq, PartialOrd, Ord)]
207 pub struct ItemSortKey(Option
<NodeId
>, ty
::SymbolName
);
209 fn item_sort_key
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
210 item
: TransItem
<'tcx
>) -> ItemSortKey
{
211 ItemSortKey(match item
{
212 TransItem
::Fn(instance
) => {
213 tcx
.hir
.as_local_node_id(instance
.def_id())
215 TransItem
::Static(node_id
) | TransItem
::GlobalAsm(node_id
) => {
218 }, item
.symbol_name(tcx
))
221 let items
: Vec
<_
> = self.items
.iter().map(|(&i
, &l
)| (i
, l
)).collect();
222 let mut items
: Vec
<_
> = items
.iter()
223 .map(|il
| (il
, item_sort_key(tcx
, il
.0))).collect();
224 items
.sort_by(|&(_
, ref key1
), &(_
, ref key2
)| key1
.cmp(key2
));
225 items
.into_iter().map(|(&item_linkage
, _
)| item_linkage
).collect()
230 // Anything we can't find a proper codegen unit for goes into this.
231 const FALLBACK_CODEGEN_UNIT
: &'
static str = "__rustc_fallback_codegen_unit";
233 pub fn partition
<'a
, 'tcx
, I
>(scx
: &SharedCrateContext
<'a
, 'tcx
>,
235 strategy
: PartitioningStrategy
,
236 inlining_map
: &InliningMap
<'tcx
>)
237 -> Vec
<CodegenUnit
<'tcx
>>
238 where I
: Iterator
<Item
= TransItem
<'tcx
>>
242 // In the first step, we place all regular translation items into their
243 // respective 'home' codegen unit. Regular translation items are all
244 // functions and statics defined in the local crate.
245 let mut initial_partitioning
= place_root_translation_items(scx
,
248 debug_dump(tcx
, "INITIAL PARTITONING:", initial_partitioning
.codegen_units
.iter());
250 // If the partitioning should produce a fixed count of codegen units, merge
251 // until that count is reached.
252 if let PartitioningStrategy
::FixedUnitCount(count
) = strategy
{
253 merge_codegen_units(&mut initial_partitioning
, count
, &tcx
.crate_name
.as_str());
255 debug_dump(tcx
, "POST MERGING:", initial_partitioning
.codegen_units
.iter());
258 // In the next step, we use the inlining map to determine which addtional
259 // translation items have to go into each codegen unit. These additional
260 // translation items can be drop-glue, functions from external crates, and
261 // local functions the definition of which is marked with #[inline].
262 let post_inlining
= place_inlined_translation_items(initial_partitioning
,
265 debug_dump(tcx
, "POST INLINING:", post_inlining
.0.iter
());
267 // Finally, sort by codegen unit name, so that we get deterministic results
268 let mut result
= post_inlining
.0;
269 result
.sort_by(|cgu1
, cgu2
| {
270 (&cgu1
.name
[..]).cmp(&cgu2
.name
[..])
273 if scx
.sess().opts
.enable_dep_node_debug_strs() {
275 let dep_node
= cgu
.work_product_dep_node();
276 scx
.tcx().dep_graph
.register_dep_node_debug_str(dep_node
,
277 || cgu
.name().to_string());
284 struct PreInliningPartitioning
<'tcx
> {
285 codegen_units
: Vec
<CodegenUnit
<'tcx
>>,
286 roots
: FxHashSet
<TransItem
<'tcx
>>,
289 struct PostInliningPartitioning
<'tcx
>(Vec
<CodegenUnit
<'tcx
>>);
291 fn place_root_translation_items
<'a
, 'tcx
, I
>(scx
: &SharedCrateContext
<'a
, 'tcx
>,
293 -> PreInliningPartitioning
<'tcx
>
294 where I
: Iterator
<Item
= TransItem
<'tcx
>>
297 let mut roots
= FxHashSet();
298 let mut codegen_units
= FxHashMap();
299 let is_incremental_build
= tcx
.sess
.opts
.incremental
.is_some();
301 for trans_item
in trans_items
{
302 let is_root
= trans_item
.instantiation_mode(tcx
) == InstantiationMode
::GloballyShared
;
305 let characteristic_def_id
= characteristic_def_id_of_trans_item(scx
, trans_item
);
306 let is_volatile
= is_incremental_build
&&
307 trans_item
.is_generic_fn();
309 let codegen_unit_name
= match characteristic_def_id
{
310 Some(def_id
) => compute_codegen_unit_name(tcx
, def_id
, is_volatile
),
311 None
=> Symbol
::intern(FALLBACK_CODEGEN_UNIT
).as_str(),
314 let make_codegen_unit
= || {
315 CodegenUnit
::empty(codegen_unit_name
.clone())
318 let mut codegen_unit
= codegen_units
.entry(codegen_unit_name
.clone())
319 .or_insert_with(make_codegen_unit
);
321 let linkage
= match trans_item
.explicit_linkage(tcx
) {
322 Some(explicit_linkage
) => explicit_linkage
,
326 TransItem
::Static(..) |
327 TransItem
::GlobalAsm(..) => llvm
::ExternalLinkage
,
332 codegen_unit
.items
.insert(trans_item
, linkage
);
333 roots
.insert(trans_item
);
337 // always ensure we have at least one CGU; otherwise, if we have a
338 // crate with just types (for example), we could wind up with no CGU
339 if codegen_units
.is_empty() {
340 let codegen_unit_name
= Symbol
::intern(FALLBACK_CODEGEN_UNIT
).as_str();
341 codegen_units
.entry(codegen_unit_name
.clone())
342 .or_insert_with(|| CodegenUnit
::empty(codegen_unit_name
.clone()));
345 PreInliningPartitioning
{
346 codegen_units
: codegen_units
.into_iter()
347 .map(|(_
, codegen_unit
)| codegen_unit
)
353 fn merge_codegen_units
<'tcx
>(initial_partitioning
: &mut PreInliningPartitioning
<'tcx
>,
354 target_cgu_count
: usize,
356 assert
!(target_cgu_count
>= 1);
357 let codegen_units
= &mut initial_partitioning
.codegen_units
;
359 // Merge the two smallest codegen units until the target size is reached.
360 // Note that "size" is estimated here rather inaccurately as the number of
361 // translation items in a given unit. This could be improved on.
362 while codegen_units
.len() > target_cgu_count
{
363 // Sort small cgus to the back
364 codegen_units
.sort_by_key(|cgu
| -(cgu
.items
.len() as i64));
365 let smallest
= codegen_units
.pop().unwrap();
366 let second_smallest
= codegen_units
.last_mut().unwrap();
368 for (k
, v
) in smallest
.items
.into_iter() {
369 second_smallest
.items
.insert(k
, v
);
373 for (index
, cgu
) in codegen_units
.iter_mut().enumerate() {
374 cgu
.name
= numbered_codegen_unit_name(crate_name
, index
);
377 // If the initial partitioning contained less than target_cgu_count to begin
378 // with, we won't have enough codegen units here, so add a empty units until
379 // we reach the target count
380 while codegen_units
.len() < target_cgu_count
{
381 let index
= codegen_units
.len();
383 CodegenUnit
::empty(numbered_codegen_unit_name(crate_name
, index
)));
387 fn place_inlined_translation_items
<'tcx
>(initial_partitioning
: PreInliningPartitioning
<'tcx
>,
388 inlining_map
: &InliningMap
<'tcx
>)
389 -> PostInliningPartitioning
<'tcx
> {
390 let mut new_partitioning
= Vec
::new();
392 for codegen_unit
in &initial_partitioning
.codegen_units
[..] {
393 // Collect all items that need to be available in this codegen unit
394 let mut reachable
= FxHashSet();
395 for root
in codegen_unit
.items
.keys() {
396 follow_inlining(*root
, inlining_map
, &mut reachable
);
399 let mut new_codegen_unit
=
400 CodegenUnit
::empty(codegen_unit
.name
.clone());
402 // Add all translation items that are not already there
403 for trans_item
in reachable
{
404 if let Some(linkage
) = codegen_unit
.items
.get(&trans_item
) {
405 // This is a root, just copy it over
406 new_codegen_unit
.items
.insert(trans_item
, *linkage
);
408 if initial_partitioning
.roots
.contains(&trans_item
) {
409 bug
!("GloballyShared trans-item inlined into other CGU: \
413 // This is a cgu-private copy
414 new_codegen_unit
.items
.insert(trans_item
, llvm
::InternalLinkage
);
418 new_partitioning
.push(new_codegen_unit
);
421 return PostInliningPartitioning(new_partitioning
);
423 fn follow_inlining
<'tcx
>(trans_item
: TransItem
<'tcx
>,
424 inlining_map
: &InliningMap
<'tcx
>,
425 visited
: &mut FxHashSet
<TransItem
<'tcx
>>) {
426 if !visited
.insert(trans_item
) {
430 inlining_map
.with_inlining_candidates(trans_item
, |target
| {
431 follow_inlining(target
, inlining_map
, visited
);
436 fn characteristic_def_id_of_trans_item
<'a
, 'tcx
>(scx
: &SharedCrateContext
<'a
, 'tcx
>,
437 trans_item
: TransItem
<'tcx
>)
441 TransItem
::Fn(instance
) => {
442 let def_id
= match instance
.def
{
443 ty
::InstanceDef
::Item(def_id
) => def_id
,
444 ty
::InstanceDef
::FnPtrShim(..) |
445 ty
::InstanceDef
::ClosureOnceShim { .. }
|
446 ty
::InstanceDef
::Intrinsic(..) |
447 ty
::InstanceDef
::DropGlue(..) |
448 ty
::InstanceDef
::Virtual(..) => return None
451 // If this is a method, we want to put it into the same module as
452 // its self-type. If the self-type does not provide a characteristic
453 // DefId, we use the location of the impl after all.
455 if tcx
.trait_of_item(def_id
).is_some() {
456 let self_ty
= instance
.substs
.type_at(0);
457 // This is an implementation of a trait method.
458 return characteristic_def_id_of_type(self_ty
).or(Some(def_id
));
461 if let Some(impl_def_id
) = tcx
.impl_of_method(def_id
) {
462 // This is a method within an inherent impl, find out what the
464 let impl_self_ty
= common
::def_ty(scx
, impl_def_id
, instance
.substs
);
465 if let Some(def_id
) = characteristic_def_id_of_type(impl_self_ty
) {
472 TransItem
::Static(node_id
) |
473 TransItem
::GlobalAsm(node_id
) => Some(tcx
.hir
.local_def_id(node_id
)),
477 fn compute_codegen_unit_name
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
481 // Unfortunately we cannot just use the `ty::item_path` infrastructure here
482 // because we need paths to modules and the DefIds of those are not
483 // available anymore for external items.
484 let mut mod_path
= String
::with_capacity(64);
486 let def_path
= tcx
.def_path(def_id
);
487 mod_path
.push_str(&tcx
.crate_name(def_path
.krate
).as_str());
489 for part
in tcx
.def_path(def_id
)
494 DefPathData
::Module(..) => true,
498 mod_path
.push_str("-");
499 mod_path
.push_str(&part
.data
.as_interned_str());
503 mod_path
.push_str(".volatile");
506 return Symbol
::intern(&mod_path
[..]).as_str();
509 fn numbered_codegen_unit_name(crate_name
: &str, index
: usize) -> InternedString
{
510 Symbol
::intern(&format
!("{}{}{}", crate_name
, NUMBERED_CODEGEN_UNIT_MARKER
, index
)).as_str()
513 fn debug_dump
<'a
, 'b
, 'tcx
, I
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
516 where I
: Iterator
<Item
=&'b CodegenUnit
<'tcx
>>,
519 if cfg
!(debug_assertions
) {
522 debug
!("CodegenUnit {}:", cgu
.name
);
524 for (trans_item
, linkage
) in &cgu
.items
{
525 let symbol_name
= trans_item
.symbol_name(tcx
);
526 let symbol_hash_start
= symbol_name
.rfind('h'
);
527 let symbol_hash
= symbol_hash_start
.map(|i
| &symbol_name
[i
..])
528 .unwrap_or("<no hash>");
530 debug
!(" - {} [{:?}] [{}]",
531 trans_item
.to_string(tcx
),