compiler/rustc_middle/src/mir/mono.rs

   1 use crate::dep_graph::{DepNode, WorkProduct, WorkProductId};
   2 use crate::ich::{NodeIdHashingMode, StableHashingContext};
   3 use crate::ty::{subst::InternalSubsts, Instance, InstanceDef, SymbolName, TyCtxt};
   4 use rustc_attr::InlineAttr;
   5 use rustc_data_structures::base_n;
   6 use rustc_data_structures::fingerprint::Fingerprint;
   7 use rustc_data_structures::fx::FxHashMap;
   8 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
   9 use rustc_hir::def_id::{CrateNum, DefId, LOCAL_CRATE};
  10 use rustc_hir::{HirId, ItemId};
  11 use rustc_session::config::OptLevel;
  12 use rustc_span::source_map::Span;
  13 use rustc_span::symbol::Symbol;
  14 use std::fmt;
  15 use std::hash::Hash;
  16
  17 /// Describes how a monomorphization will be instantiated in object files.
  18 #[derive(PartialEq)]
  19 pub enum InstantiationMode {
  20     /// There will be exactly one instance of the given MonoItem. It will have
  21     /// external linkage so that it can be linked to from other codegen units.
  22     GloballyShared {
  23         /// In some compilation scenarios we may decide to take functions that
  24         /// are typically `LocalCopy` and instead move them to `GloballyShared`
  25         /// to avoid codegenning them a bunch of times. In this situation,
  26         /// however, our local copy may conflict with other crates also
  27         /// inlining the same function.
  28         ///
  29         /// This flag indicates that this situation is occurring, and informs
  30         /// symbol name calculation that some extra mangling is needed to
  31         /// avoid conflicts. Note that this may eventually go away entirely if
  32         /// ThinLTO enables us to *always* have a globally shared instance of a
  33         /// function within one crate's compilation.
  34         may_conflict: bool,
  35     },
  36
  37     /// Each codegen unit containing a reference to the given MonoItem will
  38     /// have its own private copy of the function (with internal linkage).
  39     LocalCopy,
  40 }
  41
  42 #[derive(PartialEq, Eq, Clone, Copy, Debug, Hash)]
  43 pub enum MonoItem<'tcx> {
  44     Fn(Instance<'tcx>),
  45     Static(DefId),
  46     GlobalAsm(ItemId),
  47 }
  48
  49 impl<'tcx> MonoItem<'tcx> {
  50     pub fn size_estimate(&self, tcx: TyCtxt<'tcx>) -> usize {
  51         match *self {
  52             MonoItem::Fn(instance) => {
  53                 // Estimate the size of a function based on how many statements
  54                 // it contains.
  55                 tcx.instance_def_size_estimate(instance.def)
  56             }
  57             // Conservatively estimate the size of a static declaration
  58             // or assembly to be 1.
  59             MonoItem::Static(_) | MonoItem::GlobalAsm(_) => 1,
  60         }
  61     }
  62
  63     pub fn is_generic_fn(&self) -> bool {
  64         match *self {
  65             MonoItem::Fn(ref instance) => instance.substs.non_erasable_generics().next().is_some(),
  66             MonoItem::Static(..) | MonoItem::GlobalAsm(..) => false,
  67         }
  68     }
  69
  70     pub fn symbol_name(&self, tcx: TyCtxt<'tcx>) -> SymbolName<'tcx> {
  71         match *self {
  72             MonoItem::Fn(instance) => tcx.symbol_name(instance),
  73             MonoItem::Static(def_id) => tcx.symbol_name(Instance::mono(tcx, def_id)),
  74             MonoItem::GlobalAsm(item_id) => {
  75                 SymbolName::new(tcx, &format!("global_asm_{:?}", item_id.def_id))
  76             }
  77         }
  78     }
  79
  80     pub fn instantiation_mode(&self, tcx: TyCtxt<'tcx>) -> InstantiationMode {
  81         let generate_cgu_internal_copies = tcx
  82             .sess
  83             .opts
  84             .debugging_opts
  85             .inline_in_all_cgus
  86             .unwrap_or_else(|| tcx.sess.opts.optimize != OptLevel::No)
  87             && !tcx.sess.link_dead_code();
  88
  89         match *self {
  90             MonoItem::Fn(ref instance) => {
  91                 let entry_def_id = tcx.entry_fn(()).map(|(id, _)| id);
  92                 // If this function isn't inlined or otherwise has an extern
  93                 // indicator, then we'll be creating a globally shared version.
  94                 if tcx.codegen_fn_attrs(instance.def_id()).contains_extern_indicator()
  95                     || !instance.def.generates_cgu_internal_copy(tcx)
  96                     || Some(instance.def_id()) == entry_def_id
  97                 {
  98                     return InstantiationMode::GloballyShared { may_conflict: false };
  99                 }
 100
 101                 // At this point we don't have explicit linkage and we're an
 102                 // inlined function. If we're inlining into all CGUs then we'll
 103                 // be creating a local copy per CGU.
 104                 if generate_cgu_internal_copies {
 105                     return InstantiationMode::LocalCopy;
 106                 }
 107
 108                 // Finally, if this is `#[inline(always)]` we're sure to respect
 109                 // that with an inline copy per CGU, but otherwise we'll be
 110                 // creating one copy of this `#[inline]` function which may
 111                 // conflict with upstream crates as it could be an exported
 112                 // symbol.
 113                 match tcx.codegen_fn_attrs(instance.def_id()).inline {
 114                     InlineAttr::Always => InstantiationMode::LocalCopy,
 115                     _ => InstantiationMode::GloballyShared { may_conflict: true },
 116                 }
 117             }
 118             MonoItem::Static(..) | MonoItem::GlobalAsm(..) => {
 119                 InstantiationMode::GloballyShared { may_conflict: false }
 120             }
 121         }
 122     }
 123
 124     pub fn explicit_linkage(&self, tcx: TyCtxt<'tcx>) -> Option<Linkage> {
 125         let def_id = match *self {
 126             MonoItem::Fn(ref instance) => instance.def_id(),
 127             MonoItem::Static(def_id) => def_id,
 128             MonoItem::GlobalAsm(..) => return None,
 129         };
 130
 131         let codegen_fn_attrs = tcx.codegen_fn_attrs(def_id);
 132         codegen_fn_attrs.linkage
 133     }
 134
 135     /// Returns `true` if this instance is instantiable - whether it has no unsatisfied
 136     /// predicates.
 137     ///
 138     /// In order to codegen an item, all of its predicates must hold, because
 139     /// otherwise the item does not make sense. Type-checking ensures that
 140     /// the predicates of every item that is *used by* a valid item *do*
 141     /// hold, so we can rely on that.
 142     ///
 143     /// However, we codegen collector roots (reachable items) and functions
 144     /// in vtables when they are seen, even if they are not used, and so they
 145     /// might not be instantiable. For example, a programmer can define this
 146     /// public function:
 147     ///
 148     ///     pub fn foo<'a>(s: &'a mut ()) where &'a mut (): Clone {
 149     ///         <&mut () as Clone>::clone(&s);
 150     ///     }
 151     ///
 152     /// That function can't be codegened, because the method `<&mut () as Clone>::clone`
 153     /// does not exist. Luckily for us, that function can't ever be used,
 154     /// because that would require for `&'a mut (): Clone` to hold, so we
 155     /// can just not emit any code, or even a linker reference for it.
 156     ///
 157     /// Similarly, if a vtable method has such a signature, and therefore can't
 158     /// be used, we can just not emit it and have a placeholder (a null pointer,
 159     /// which will never be accessed) in its place.
 160     pub fn is_instantiable(&self, tcx: TyCtxt<'tcx>) -> bool {
 161         debug!("is_instantiable({:?})", self);
 162         let (def_id, substs) = match *self {
 163             MonoItem::Fn(ref instance) => (instance.def_id(), instance.substs),
 164             MonoItem::Static(def_id) => (def_id, InternalSubsts::empty()),
 165             // global asm never has predicates
 166             MonoItem::GlobalAsm(..) => return true,
 167         };
 168
 169         !tcx.subst_and_check_impossible_predicates((def_id, &substs))
 170     }
 171
 172     pub fn local_span(&self, tcx: TyCtxt<'tcx>) -> Option<Span> {
 173         match *self {
 174             MonoItem::Fn(Instance { def, .. }) => {
 175                 def.def_id().as_local().map(|def_id| tcx.hir().local_def_id_to_hir_id(def_id))
 176             }
 177             MonoItem::Static(def_id) => {
 178                 def_id.as_local().map(|def_id| tcx.hir().local_def_id_to_hir_id(def_id))
 179             }
 180             MonoItem::GlobalAsm(item_id) => Some(item_id.hir_id()),
 181         }
 182         .map(|hir_id| tcx.hir().span(hir_id))
 183     }
 184
 185     // Only used by rustc_codegen_cranelift
 186     pub fn codegen_dep_node(&self, tcx: TyCtxt<'tcx>) -> DepNode {
 187         crate::dep_graph::make_compile_mono_item(tcx, self)
 188     }
 189
 190     /// Returns the item's `CrateNum`
 191     pub fn krate(&self) -> CrateNum {
 192         match self {
 193             MonoItem::Fn(ref instance) => instance.def_id().krate,
 194             MonoItem::Static(def_id) => def_id.krate,
 195             MonoItem::GlobalAsm(..) => LOCAL_CRATE,
 196         }
 197     }
 198 }
 199
 200 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for MonoItem<'tcx> {
 201     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 202         ::std::mem::discriminant(self).hash_stable(hcx, hasher);
 203
 204         match *self {
 205             MonoItem::Fn(ref instance) => {
 206                 instance.hash_stable(hcx, hasher);
 207             }
 208             MonoItem::Static(def_id) => {
 209                 def_id.hash_stable(hcx, hasher);
 210             }
 211             MonoItem::GlobalAsm(item_id) => {
 212                 hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
 213                     item_id.hash_stable(hcx, hasher);
 214                 })
 215             }
 216         }
 217     }
 218 }
 219
 220 impl<'tcx> fmt::Display for MonoItem<'tcx> {
 221     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 222         match *self {
 223             MonoItem::Fn(instance) => write!(f, "fn {}", instance),
 224             MonoItem::Static(def_id) => {
 225                 write!(f, "static {}", Instance::new(def_id, InternalSubsts::empty()))
 226             }
 227             MonoItem::GlobalAsm(..) => write!(f, "global_asm"),
 228         }
 229     }
 230 }
 231
 232 #[derive(Debug)]
 233 pub struct CodegenUnit<'tcx> {
 234     /// A name for this CGU. Incremental compilation requires that
 235     /// name be unique amongst **all** crates. Therefore, it should
 236     /// contain something unique to this crate (e.g., a module path)
 237     /// as well as the crate name and disambiguator.
 238     name: Symbol,
 239     items: FxHashMap<MonoItem<'tcx>, (Linkage, Visibility)>,
 240     size_estimate: Option<usize>,
 241     primary: bool,
 242 }
 243
 244 /// Specifies the linkage type for a `MonoItem`.
 245 ///
 246 /// See <https://llvm.org/docs/LangRef.html#linkage-types> for more details about these variants.
 247 #[derive(Copy, Clone, PartialEq, Debug, TyEncodable, TyDecodable, HashStable)]
 248 pub enum Linkage {
 249     External,
 250     AvailableExternally,
 251     LinkOnceAny,
 252     LinkOnceODR,
 253     WeakAny,
 254     WeakODR,
 255     Appending,
 256     Internal,
 257     Private,
 258     ExternalWeak,
 259     Common,
 260 }
 261
 262 #[derive(Copy, Clone, PartialEq, Debug, HashStable)]
 263 pub enum Visibility {
 264     Default,
 265     Hidden,
 266     Protected,
 267 }
 268
 269 impl<'tcx> CodegenUnit<'tcx> {
 270     #[inline]
 271     pub fn new(name: Symbol) -> CodegenUnit<'tcx> {
 272         CodegenUnit { name, items: Default::default(), size_estimate: None, primary: false }
 273     }
 274
 275     pub fn name(&self) -> Symbol {
 276         self.name
 277     }
 278
 279     pub fn set_name(&mut self, name: Symbol) {
 280         self.name = name;
 281     }
 282
 283     pub fn is_primary(&self) -> bool {
 284         self.primary
 285     }
 286
 287     pub fn make_primary(&mut self) {
 288         self.primary = true;
 289     }
 290
 291     pub fn items(&self) -> &FxHashMap<MonoItem<'tcx>, (Linkage, Visibility)> {
 292         &self.items
 293     }
 294
 295     pub fn items_mut(&mut self) -> &mut FxHashMap<MonoItem<'tcx>, (Linkage, Visibility)> {
 296         &mut self.items
 297     }
 298
 299     pub fn mangle_name(human_readable_name: &str) -> String {
 300         // We generate a 80 bit hash from the name. This should be enough to
 301         // avoid collisions and is still reasonably short for filenames.
 302         let mut hasher = StableHasher::new();
 303         human_readable_name.hash(&mut hasher);
 304         let hash: u128 = hasher.finish();
 305         let hash = hash & ((1u128 << 80) - 1);
 306         base_n::encode(hash, base_n::CASE_INSENSITIVE)
 307     }
 308
 309     pub fn estimate_size(&mut self, tcx: TyCtxt<'tcx>) {
 310         // Estimate the size of a codegen unit as (approximately) the number of MIR
 311         // statements it corresponds to.
 312         self.size_estimate = Some(self.items.keys().map(|mi| mi.size_estimate(tcx)).sum());
 313     }
 314
 315     #[inline]
 316     pub fn size_estimate(&self) -> usize {
 317         // Should only be called if `estimate_size` has previously been called.
 318         self.size_estimate.expect("estimate_size must be called before getting a size_estimate")
 319     }
 320
 321     pub fn modify_size_estimate(&mut self, delta: usize) {
 322         assert!(self.size_estimate.is_some());
 323         if let Some(size_estimate) = self.size_estimate {
 324             self.size_estimate = Some(size_estimate + delta);
 325         }
 326     }
 327
 328     pub fn contains_item(&self, item: &MonoItem<'tcx>) -> bool {
 329         self.items().contains_key(item)
 330     }
 331
 332     pub fn work_product_id(&self) -> WorkProductId {
 333         WorkProductId::from_cgu_name(&self.name().as_str())
 334     }
 335
 336     pub fn work_product(&self, tcx: TyCtxt<'_>) -> WorkProduct {
 337         let work_product_id = self.work_product_id();
 338         tcx.dep_graph
 339             .previous_work_product(&work_product_id)
 340             .unwrap_or_else(|| panic!("Could not find work-product for CGU `{}`", self.name()))
 341     }
 342
 343     pub fn items_in_deterministic_order(
 344         &self,
 345         tcx: TyCtxt<'tcx>,
 346     ) -> Vec<(MonoItem<'tcx>, (Linkage, Visibility))> {
 347         // The codegen tests rely on items being process in the same order as
 348         // they appear in the file, so for local items, we sort by node_id first
 349         #[derive(PartialEq, Eq, PartialOrd, Ord)]
 350         pub struct ItemSortKey<'tcx>(Option<HirId>, SymbolName<'tcx>);
 351
 352         fn item_sort_key<'tcx>(tcx: TyCtxt<'tcx>, item: MonoItem<'tcx>) -> ItemSortKey<'tcx> {
 353             ItemSortKey(
 354                 match item {
 355                     MonoItem::Fn(ref instance) => {
 356                         match instance.def {
 357                             // We only want to take HirIds of user-defined
 358                             // instances into account. The others don't matter for
 359                             // the codegen tests and can even make item order
 360                             // unstable.
 361                             InstanceDef::Item(def) => def
 362                                 .did
 363                                 .as_local()
 364                                 .map(|def_id| tcx.hir().local_def_id_to_hir_id(def_id)),
 365                             InstanceDef::VtableShim(..)
 366                             | InstanceDef::ReifyShim(..)
 367                             | InstanceDef::Intrinsic(..)
 368                             | InstanceDef::FnPtrShim(..)
 369                             | InstanceDef::Virtual(..)
 370                             | InstanceDef::ClosureOnceShim { .. }
 371                             | InstanceDef::DropGlue(..)
 372                             | InstanceDef::CloneShim(..) => None,
 373                         }
 374                     }
 375                     MonoItem::Static(def_id) => {
 376                         def_id.as_local().map(|def_id| tcx.hir().local_def_id_to_hir_id(def_id))
 377                     }
 378                     MonoItem::GlobalAsm(item_id) => Some(item_id.hir_id()),
 379                 },
 380                 item.symbol_name(tcx),
 381             )
 382         }
 383
 384         let mut items: Vec<_> = self.items().iter().map(|(&i, &l)| (i, l)).collect();
 385         items.sort_by_cached_key(|&(i, _)| item_sort_key(tcx, i));
 386         items
 387     }
 388
 389     pub fn codegen_dep_node(&self, tcx: TyCtxt<'tcx>) -> DepNode {
 390         crate::dep_graph::make_compile_codegen_unit(tcx, self.name())
 391     }
 392 }
 393
 394 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for CodegenUnit<'tcx> {
 395     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 396         let CodegenUnit {
 397             ref items,
 398             name,
 399             // The size estimate is not relevant to the hash
 400             size_estimate: _,
 401             primary: _,
 402         } = *self;
 403
 404         name.hash_stable(hcx, hasher);
 405
 406         let mut items: Vec<(Fingerprint, _)> = items
 407             .iter()
 408             .map(|(mono_item, &attrs)| {
 409                 let mut hasher = StableHasher::new();
 410                 mono_item.hash_stable(hcx, &mut hasher);
 411                 let mono_item_fingerprint = hasher.finish();
 412                 (mono_item_fingerprint, attrs)
 413             })
 414             .collect();
 415
 416         items.sort_unstable_by_key(|i| i.0);
 417         items.hash_stable(hcx, hasher);
 418     }
 419 }
 420
 421 pub struct CodegenUnitNameBuilder<'tcx> {
 422     tcx: TyCtxt<'tcx>,
 423     cache: FxHashMap<CrateNum, String>,
 424 }
 425
 426 impl CodegenUnitNameBuilder<'tcx> {
 427     pub fn new(tcx: TyCtxt<'tcx>) -> Self {
 428         CodegenUnitNameBuilder { tcx, cache: Default::default() }
 429     }
 430
 431     /// CGU names should fulfill the following requirements:
 432     /// - They should be able to act as a file name on any kind of file system
 433     /// - They should not collide with other CGU names, even for different versions
 434     ///   of the same crate.
 435     ///
 436     /// Consequently, we don't use special characters except for '.' and '-' and we
 437     /// prefix each name with the crate-name and crate-disambiguator.
 438     ///
 439     /// This function will build CGU names of the form:
 440     ///
 441     /// ```
 442     /// <crate-name>.<crate-disambiguator>[-in-<local-crate-id>](-<component>)*[.<special-suffix>]
 443     /// <local-crate-id> = <local-crate-name>.<local-crate-disambiguator>
 444     /// ```
 445     ///
 446     /// The '.' before `<special-suffix>` makes sure that names with a special
 447     /// suffix can never collide with a name built out of regular Rust
 448     /// identifiers (e.g., module paths).
 449     pub fn build_cgu_name<I, C, S>(
 450         &mut self,
 451         cnum: CrateNum,
 452         components: I,
 453         special_suffix: Option<S>,
 454     ) -> Symbol
 455     where
 456         I: IntoIterator<Item = C>,
 457         C: fmt::Display,
 458         S: fmt::Display,
 459     {
 460         let cgu_name = self.build_cgu_name_no_mangle(cnum, components, special_suffix);
 461
 462         if self.tcx.sess.opts.debugging_opts.human_readable_cgu_names {
 463             cgu_name
 464         } else {
 465             Symbol::intern(&CodegenUnit::mangle_name(&cgu_name.as_str()))
 466         }
 467     }
 468
 469     /// Same as `CodegenUnit::build_cgu_name()` but will never mangle the
 470     /// resulting name.
 471     pub fn build_cgu_name_no_mangle<I, C, S>(
 472         &mut self,
 473         cnum: CrateNum,
 474         components: I,
 475         special_suffix: Option<S>,
 476     ) -> Symbol
 477     where
 478         I: IntoIterator<Item = C>,
 479         C: fmt::Display,
 480         S: fmt::Display,
 481     {
 482         use std::fmt::Write;
 483
 484         let mut cgu_name = String::with_capacity(64);
 485
 486         // Start out with the crate name and disambiguator
 487         let tcx = self.tcx;
 488         let crate_prefix = self.cache.entry(cnum).or_insert_with(|| {
 489             // Whenever the cnum is not LOCAL_CRATE we also mix in the
 490             // local crate's ID. Otherwise there can be collisions between CGUs
 491             // instantiating stuff for upstream crates.
 492             let local_crate_id = if cnum != LOCAL_CRATE {
 493                 let local_crate_disambiguator = format!("{}", tcx.crate_disambiguator(LOCAL_CRATE));
 494                 format!("-in-{}.{}", tcx.crate_name(LOCAL_CRATE), &local_crate_disambiguator[0..8])
 495             } else {
 496                 String::new()
 497             };
 498
 499             let crate_disambiguator = tcx.crate_disambiguator(cnum).to_string();
 500             // Using a shortened disambiguator of about 40 bits
 501             format!("{}.{}{}", tcx.crate_name(cnum), &crate_disambiguator[0..8], local_crate_id)
 502         });
 503
 504         write!(cgu_name, "{}", crate_prefix).unwrap();
 505
 506         // Add the components
 507         for component in components {
 508             write!(cgu_name, "-{}", component).unwrap();
 509         }
 510
 511         if let Some(special_suffix) = special_suffix {
 512             // We add a dot in here so it cannot clash with anything in a regular
 513             // Rust identifier
 514             write!(cgu_name, ".{}", special_suffix).unwrap();
 515         }
 516
 517         Symbol::intern(&cgu_name[..])
 518     }
 519 }