compiler/rustc_monomorphize/src/polymorphize.rs

   1 //! Polymorphization Analysis
   2 //! =========================
   3 //!
   4 //! This module implements an analysis of functions, methods and closures to determine which
   5 //! generic parameters are unused (and eventually, in what ways generic parameters are used - only
   6 //! for their size, offset of a field, etc.).
   7
   8 use rustc_hir::{def::DefKind, def_id::DefId, ConstContext};
   9 use rustc_index::bit_set::FiniteBitSet;
  10 use rustc_middle::mir::{
  11     visit::{TyContext, Visitor},
  12     Local, LocalDecl, Location,
  13 };
  14 use rustc_middle::ty::{
  15     self,
  16     fold::{TypeFoldable, TypeVisitor},
  17     query::Providers,
  18     subst::SubstsRef,
  19     Const, Ty, TyCtxt,
  20 };
  21 use rustc_span::symbol::sym;
  22 use std::convert::TryInto;
  23 use std::ops::ControlFlow;
  24
  25 /// Provide implementations of queries relating to polymorphization analysis.
  26 pub fn provide(providers: &mut Providers) {
  27     providers.unused_generic_params = unused_generic_params;
  28 }
  29
  30 /// Determine which generic parameters are used by the instance.
  31 ///
  32 /// Returns a bitset where bits representing unused parameters are set (`is_empty` indicates all
  33 /// parameters are used).
  34 #[instrument(level = "debug", skip(tcx))]
  35 fn unused_generic_params<'tcx>(
  36     tcx: TyCtxt<'tcx>,
  37     instance: ty::InstanceDef<'tcx>,
  38 ) -> FiniteBitSet<u32> {
  39     if !tcx.sess.opts.debugging_opts.polymorphize {
  40         // If polymorphization disabled, then all parameters are used.
  41         return FiniteBitSet::new_empty();
  42     }
  43
  44     let def_id = instance.def_id();
  45     // Exit early if this instance should not be polymorphized.
  46     if !should_polymorphize(tcx, def_id, instance) {
  47         return FiniteBitSet::new_empty();
  48     }
  49
  50     let generics = tcx.generics_of(def_id);
  51     debug!(?generics);
  52
  53     // Exit early when there are no parameters to be unused.
  54     if generics.count() == 0 {
  55         return FiniteBitSet::new_empty();
  56     }
  57
  58     // Create a bitset with N rightmost ones for each parameter.
  59     let generics_count: u32 =
  60         generics.count().try_into().expect("more generic parameters than can fit into a `u32`");
  61     let mut unused_parameters = FiniteBitSet::<u32>::new_empty();
  62     unused_parameters.set_range(0..generics_count);
  63     debug!(?unused_parameters, "(start)");
  64
  65     mark_used_by_default_parameters(tcx, def_id, generics, &mut unused_parameters);
  66     debug!(?unused_parameters, "(after default)");
  67
  68     // Visit MIR and accumululate used generic parameters.
  69     let body = match tcx.hir().body_const_context(def_id.expect_local()) {
  70         // Const functions are actually called and should thus be considered for polymorphization
  71         // via their runtime MIR.
  72         Some(ConstContext::ConstFn) | None => tcx.optimized_mir(def_id),
  73         Some(_) => tcx.mir_for_ctfe(def_id),
  74     };
  75     let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters: &mut unused_parameters };
  76     vis.visit_body(body);
  77     debug!(?unused_parameters, "(end)");
  78
  79     // Emit errors for debugging and testing if enabled.
  80     if !unused_parameters.is_empty() {
  81         emit_unused_generic_params_error(tcx, def_id, generics, &unused_parameters);
  82     }
  83
  84     unused_parameters
  85 }
  86
  87 /// Returns `true` if the instance should be polymorphized.
  88 fn should_polymorphize<'tcx>(
  89     tcx: TyCtxt<'tcx>,
  90     def_id: DefId,
  91     instance: ty::InstanceDef<'tcx>,
  92 ) -> bool {
  93     // If an instance's MIR body is not polymorphic then the modified substitutions that are
  94     // derived from polymorphization's result won't make any difference.
  95     if !instance.has_polymorphic_mir_body() {
  96         return false;
  97     }
  98
  99     // Don't polymorphize intrinsics or virtual calls - calling `instance_mir` will panic.
 100     if matches!(instance, ty::InstanceDef::Intrinsic(..) | ty::InstanceDef::Virtual(..)) {
 101         return false;
 102     }
 103
 104     // Polymorphization results are stored in cross-crate metadata only when there are unused
 105     // parameters, so assume that non-local items must have only used parameters (else this query
 106     // would not be invoked, and the cross-crate metadata used instead).
 107     if !def_id.is_local() {
 108         return false;
 109     }
 110
 111     // Foreign items have no bodies to analyze.
 112     if tcx.is_foreign_item(def_id) {
 113         return false;
 114     }
 115
 116     // Make sure there is MIR available.
 117     match tcx.hir().body_const_context(def_id.expect_local()) {
 118         Some(ConstContext::ConstFn) | None if !tcx.is_mir_available(def_id) => {
 119             debug!("no mir available");
 120             return false;
 121         }
 122         Some(_) if !tcx.is_ctfe_mir_available(def_id) => {
 123             debug!("no ctfe mir available");
 124             return false;
 125         }
 126         _ => true,
 127     }
 128 }
 129
 130 /// Some parameters are considered used-by-default, such as non-generic parameters and the dummy
 131 /// generic parameters from closures, this function marks them as used. `leaf_is_closure` should
 132 /// be `true` if the item that `unused_generic_params` was invoked on is a closure.
 133 #[instrument(level = "debug", skip(tcx, def_id, generics, unused_parameters))]
 134 fn mark_used_by_default_parameters<'tcx>(
 135     tcx: TyCtxt<'tcx>,
 136     def_id: DefId,
 137     generics: &'tcx ty::Generics,
 138     unused_parameters: &mut FiniteBitSet<u32>,
 139 ) {
 140     match tcx.def_kind(def_id) {
 141         DefKind::Closure | DefKind::Generator => {
 142             for param in &generics.params {
 143                 debug!(?param, "(closure/gen)");
 144                 unused_parameters.clear(param.index);
 145             }
 146         }
 147         DefKind::Mod
 148         | DefKind::Struct
 149         | DefKind::Union
 150         | DefKind::Enum
 151         | DefKind::Variant
 152         | DefKind::Trait
 153         | DefKind::TyAlias
 154         | DefKind::ForeignTy
 155         | DefKind::TraitAlias
 156         | DefKind::AssocTy
 157         | DefKind::TyParam
 158         | DefKind::Fn
 159         | DefKind::Const
 160         | DefKind::ConstParam
 161         | DefKind::Static
 162         | DefKind::Ctor(_, _)
 163         | DefKind::AssocFn
 164         | DefKind::AssocConst
 165         | DefKind::Macro(_)
 166         | DefKind::ExternCrate
 167         | DefKind::Use
 168         | DefKind::ForeignMod
 169         | DefKind::AnonConst
 170         | DefKind::InlineConst
 171         | DefKind::OpaqueTy
 172         | DefKind::Field
 173         | DefKind::LifetimeParam
 174         | DefKind::GlobalAsm
 175         | DefKind::Impl => {
 176             for param in &generics.params {
 177                 debug!(?param, "(other)");
 178                 if let ty::GenericParamDefKind::Lifetime = param.kind {
 179                     unused_parameters.clear(param.index);
 180                 }
 181             }
 182         }
 183     }
 184
 185     if let Some(parent) = generics.parent {
 186         mark_used_by_default_parameters(tcx, parent, tcx.generics_of(parent), unused_parameters);
 187     }
 188 }
 189
 190 /// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic
 191 /// parameter which was unused.
 192 #[instrument(level = "debug", skip(tcx, generics))]
 193 fn emit_unused_generic_params_error<'tcx>(
 194     tcx: TyCtxt<'tcx>,
 195     def_id: DefId,
 196     generics: &'tcx ty::Generics,
 197     unused_parameters: &FiniteBitSet<u32>,
 198 ) {
 199     let base_def_id = tcx.typeck_root_def_id(def_id);
 200     if !tcx.get_attrs(base_def_id).iter().any(|a| a.has_name(sym::rustc_polymorphize_error)) {
 201         return;
 202     }
 203
 204     let fn_span = match tcx.opt_item_name(def_id) {
 205         Some(ident) => ident.span,
 206         _ => tcx.def_span(def_id),
 207     };
 208
 209     let mut err = tcx.sess.struct_span_err(fn_span, "item has unused generic parameters");
 210
 211     let mut next_generics = Some(generics);
 212     while let Some(generics) = next_generics {
 213         for param in &generics.params {
 214             if unused_parameters.contains(param.index).unwrap_or(false) {
 215                 debug!(?param);
 216                 let def_span = tcx.def_span(param.def_id);
 217                 err.span_label(def_span, &format!("generic parameter `{}` is unused", param.name));
 218             }
 219         }
 220
 221         next_generics = generics.parent.map(|did| tcx.generics_of(did));
 222     }
 223
 224     err.emit();
 225 }
 226
 227 /// Visitor used to aggregate generic parameter uses.
 228 struct MarkUsedGenericParams<'a, 'tcx> {
 229     tcx: TyCtxt<'tcx>,
 230     def_id: DefId,
 231     unused_parameters: &'a mut FiniteBitSet<u32>,
 232 }
 233
 234 impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> {
 235     /// Invoke `unused_generic_params` on a body contained within the current item (e.g.
 236     /// a closure, generator or constant).
 237     #[instrument(level = "debug", skip(self, def_id, substs))]
 238     fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) {
 239         let instance = ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id));
 240         let unused = self.tcx.unused_generic_params(instance);
 241         debug!(?self.unused_parameters, ?unused);
 242         for (i, arg) in substs.iter().enumerate() {
 243             let i = i.try_into().unwrap();
 244             if !unused.contains(i).unwrap_or(false) {
 245                 arg.visit_with(self);
 246             }
 247         }
 248         debug!(?self.unused_parameters);
 249     }
 250 }
 251
 252 impl<'a, 'tcx> Visitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
 253     #[instrument(level = "debug", skip(self, local))]
 254     fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
 255         if local == Local::from_usize(1) {
 256             let def_kind = self.tcx.def_kind(self.def_id);
 257             if matches!(def_kind, DefKind::Closure | DefKind::Generator) {
 258                 // Skip visiting the closure/generator that is currently being processed. This only
 259                 // happens because the first argument to the closure is a reference to itself and
 260                 // that will call `visit_substs`, resulting in each generic parameter captured being
 261                 // considered used by default.
 262                 debug!("skipping closure substs");
 263                 return;
 264             }
 265         }
 266
 267         self.super_local_decl(local, local_decl);
 268     }
 269
 270     fn visit_const(&mut self, c: &&'tcx Const<'tcx>, _: Location) {
 271         c.visit_with(self);
 272     }
 273
 274     fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) {
 275         ty.visit_with(self);
 276     }
 277 }
 278
 279 impl<'a, 'tcx> TypeVisitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
 280     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
 281         Some(self.tcx)
 282     }
 283     #[instrument(level = "debug", skip(self))]
 284     fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 285         if !c.potentially_has_param_types_or_consts() {
 286             return ControlFlow::CONTINUE;
 287         }
 288
 289         match c.val {
 290             ty::ConstKind::Param(param) => {
 291                 debug!(?param);
 292                 self.unused_parameters.clear(param.index);
 293                 ControlFlow::CONTINUE
 294             }
 295             ty::ConstKind::Unevaluated(ty::Unevaluated { def, substs_: _, promoted: Some(p)})
 296                 // Avoid considering `T` unused when constants are of the form:
 297                 //   `<Self as Foo<T>>::foo::promoted[p]`
 298                 if self.def_id == def.did && !self.tcx.generics_of(def.did).has_self =>
 299             {
 300                 // If there is a promoted, don't look at the substs - since it will always contain
 301                 // the generic parameters, instead, traverse the promoted MIR.
 302                 let promoted = self.tcx.promoted_mir(def.did);
 303                 self.visit_body(&promoted[p]);
 304                 ControlFlow::CONTINUE
 305             }
 306             ty::ConstKind::Unevaluated(uv)
 307                 if matches!(self.tcx.def_kind(uv.def.did), DefKind::AnonConst | DefKind::InlineConst) =>
 308             {
 309                 self.visit_child_body(uv.def.did, uv.substs(self.tcx));
 310                 ControlFlow::CONTINUE
 311             }
 312             _ => c.super_visit_with(self),
 313         }
 314     }
 315
 316     #[instrument(level = "debug", skip(self))]
 317     fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 318         if !ty.potentially_has_param_types_or_consts() {
 319             return ControlFlow::CONTINUE;
 320         }
 321
 322         match *ty.kind() {
 323             ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => {
 324                 debug!(?def_id);
 325                 // Avoid cycle errors with generators.
 326                 if def_id == self.def_id {
 327                     return ControlFlow::CONTINUE;
 328                 }
 329
 330                 // Consider any generic parameters used by any closures/generators as used in the
 331                 // parent.
 332                 self.visit_child_body(def_id, substs);
 333                 ControlFlow::CONTINUE
 334             }
 335             ty::Param(param) => {
 336                 debug!(?param);
 337                 self.unused_parameters.clear(param.index);
 338                 ControlFlow::CONTINUE
 339             }
 340             _ => ty.super_visit_with(self),
 341         }
 342     }
 343 }
 344
 345 /// Visitor used to check if a generic parameter is used.
 346 struct HasUsedGenericParams<'a, 'tcx> {
 347     tcx: TyCtxt<'tcx>,
 348     unused_parameters: &'a FiniteBitSet<u32>,
 349 }
 350
 351 impl<'a, 'tcx> TypeVisitor<'tcx> for HasUsedGenericParams<'a, 'tcx> {
 352     type BreakTy = ();
 353
 354     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
 355         Some(self.tcx)
 356     }
 357
 358     #[instrument(level = "debug", skip(self))]
 359     fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 360         if !c.potentially_has_param_types_or_consts() {
 361             return ControlFlow::CONTINUE;
 362         }
 363
 364         match c.val {
 365             ty::ConstKind::Param(param) => {
 366                 if self.unused_parameters.contains(param.index).unwrap_or(false) {
 367                     ControlFlow::CONTINUE
 368                 } else {
 369                     ControlFlow::BREAK
 370                 }
 371             }
 372             _ => c.super_visit_with(self),
 373         }
 374     }
 375
 376     #[instrument(level = "debug", skip(self))]
 377     fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 378         if !ty.potentially_has_param_types_or_consts() {
 379             return ControlFlow::CONTINUE;
 380         }
 381
 382         match ty.kind() {
 383             ty::Param(param) => {
 384                 if self.unused_parameters.contains(param.index).unwrap_or(false) {
 385                     ControlFlow::CONTINUE
 386                 } else {
 387                     ControlFlow::BREAK
 388                 }
 389             }
 390             _ => ty.super_visit_with(self),
 391         }
 392     }
 393 }