src/librustc/mir/mono.rs

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