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::OpaqueTy
 171         | DefKind::Field
 172         | DefKind::LifetimeParam
 173         | DefKind::GlobalAsm
 174         | DefKind::Impl => {
 175             for param in &generics.params {
 176                 debug!(?param, "(other)");
 177                 if let ty::GenericParamDefKind::Lifetime = param.kind {
 178                     unused_parameters.clear(param.index);
 179                 }
 180             }
 181         }
 182     }
 183
 184     if let Some(parent) = generics.parent {
 185         mark_used_by_default_parameters(tcx, parent, tcx.generics_of(parent), unused_parameters);
 186     }
 187 }
 188
 189 /// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic
 190 /// parameter which was unused.
 191 #[instrument(level = "debug", skip(tcx, generics))]
 192 fn emit_unused_generic_params_error<'tcx>(
 193     tcx: TyCtxt<'tcx>,
 194     def_id: DefId,
 195     generics: &'tcx ty::Generics,
 196     unused_parameters: &FiniteBitSet<u32>,
 197 ) {
 198     let base_def_id = tcx.closure_base_def_id(def_id);
 199     if !tcx.get_attrs(base_def_id).iter().any(|a| a.has_name(sym::rustc_polymorphize_error)) {
 200         return;
 201     }
 202
 203     let fn_span = match tcx.opt_item_name(def_id) {
 204         Some(ident) => ident.span,
 205         _ => tcx.def_span(def_id),
 206     };
 207
 208     let mut err = tcx.sess.struct_span_err(fn_span, "item has unused generic parameters");
 209
 210     let mut next_generics = Some(generics);
 211     while let Some(generics) = next_generics {
 212         for param in &generics.params {
 213             if unused_parameters.contains(param.index).unwrap_or(false) {
 214                 debug!(?param);
 215                 let def_span = tcx.def_span(param.def_id);
 216                 err.span_label(def_span, &format!("generic parameter `{}` is unused", param.name));
 217             }
 218         }
 219
 220         next_generics = generics.parent.map(|did| tcx.generics_of(did));
 221     }
 222
 223     err.emit();
 224 }
 225
 226 /// Visitor used to aggregate generic parameter uses.
 227 struct MarkUsedGenericParams<'a, 'tcx> {
 228     tcx: TyCtxt<'tcx>,
 229     def_id: DefId,
 230     unused_parameters: &'a mut FiniteBitSet<u32>,
 231 }
 232
 233 impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> {
 234     /// Invoke `unused_generic_params` on a body contained within the current item (e.g.
 235     /// a closure, generator or constant).
 236     #[instrument(level = "debug", skip(self, def_id, substs))]
 237     fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) {
 238         let instance = ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id));
 239         let unused = self.tcx.unused_generic_params(instance);
 240         debug!(?self.unused_parameters, ?unused);
 241         for (i, arg) in substs.iter().enumerate() {
 242             let i = i.try_into().unwrap();
 243             if !unused.contains(i).unwrap_or(false) {
 244                 arg.visit_with(self);
 245             }
 246         }
 247         debug!(?self.unused_parameters);
 248     }
 249 }
 250
 251 impl<'a, 'tcx> Visitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
 252     #[instrument(level = "debug", skip(self, local))]
 253     fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
 254         if local == Local::from_usize(1) {
 255             let def_kind = self.tcx.def_kind(self.def_id);
 256             if matches!(def_kind, DefKind::Closure | DefKind::Generator) {
 257                 // Skip visiting the closure/generator that is currently being processed. This only
 258                 // happens because the first argument to the closure is a reference to itself and
 259                 // that will call `visit_substs`, resulting in each generic parameter captured being
 260                 // considered used by default.
 261                 debug!("skipping closure substs");
 262                 return;
 263             }
 264         }
 265
 266         self.super_local_decl(local, local_decl);
 267     }
 268
 269     fn visit_const(&mut self, c: &&'tcx Const<'tcx>, _: Location) {
 270         c.visit_with(self);
 271     }
 272
 273     fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) {
 274         ty.visit_with(self);
 275     }
 276 }
 277
 278 impl<'a, 'tcx> TypeVisitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
 279     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
 280         Some(self.tcx)
 281     }
 282     #[instrument(level = "debug", skip(self))]
 283     fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 284         if !c.potentially_has_param_types_or_consts() {
 285             return ControlFlow::CONTINUE;
 286         }
 287
 288         match c.val {
 289             ty::ConstKind::Param(param) => {
 290                 debug!(?param);
 291                 self.unused_parameters.clear(param.index);
 292                 ControlFlow::CONTINUE
 293             }
 294             ty::ConstKind::Unevaluated(ty::Unevaluated { def, substs_: _, promoted: Some(p)})
 295                 // Avoid considering `T` unused when constants are of the form:
 296                 //   `<Self as Foo<T>>::foo::promoted[p]`
 297                 if self.def_id == def.did && !self.tcx.generics_of(def.did).has_self =>
 298             {
 299                 // If there is a promoted, don't look at the substs - since it will always contain
 300                 // the generic parameters, instead, traverse the promoted MIR.
 301                 let promoted = self.tcx.promoted_mir(def.did);
 302                 self.visit_body(&promoted[p]);
 303                 ControlFlow::CONTINUE
 304             }
 305             ty::ConstKind::Unevaluated(uv)
 306                 if self.tcx.def_kind(uv.def.did) == DefKind::AnonConst =>
 307             {
 308                 self.visit_child_body(uv.def.did, uv.substs(self.tcx));
 309                 ControlFlow::CONTINUE
 310             }
 311             _ => c.super_visit_with(self),
 312         }
 313     }
 314
 315     #[instrument(level = "debug", skip(self))]
 316     fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 317         if !ty.potentially_has_param_types_or_consts() {
 318             return ControlFlow::CONTINUE;
 319         }
 320
 321         match *ty.kind() {
 322             ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => {
 323                 debug!(?def_id);
 324                 // Avoid cycle errors with generators.
 325                 if def_id == self.def_id {
 326                     return ControlFlow::CONTINUE;
 327                 }
 328
 329                 // Consider any generic parameters used by any closures/generators as used in the
 330                 // parent.
 331                 self.visit_child_body(def_id, substs);
 332                 ControlFlow::CONTINUE
 333             }
 334             ty::Param(param) => {
 335                 debug!(?param);
 336                 self.unused_parameters.clear(param.index);
 337                 ControlFlow::CONTINUE
 338             }
 339             _ => ty.super_visit_with(self),
 340         }
 341     }
 342 }
 343
 344 /// Visitor used to check if a generic parameter is used.
 345 struct HasUsedGenericParams<'a, 'tcx> {
 346     tcx: TyCtxt<'tcx>,
 347     unused_parameters: &'a FiniteBitSet<u32>,
 348 }
 349
 350 impl<'a, 'tcx> TypeVisitor<'tcx> for HasUsedGenericParams<'a, 'tcx> {
 351     type BreakTy = ();
 352
 353     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
 354         Some(self.tcx)
 355     }
 356
 357     #[instrument(level = "debug", skip(self))]
 358     fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 359         if !c.potentially_has_param_types_or_consts() {
 360             return ControlFlow::CONTINUE;
 361         }
 362
 363         match c.val {
 364             ty::ConstKind::Param(param) => {
 365                 if self.unused_parameters.contains(param.index).unwrap_or(false) {
 366                     ControlFlow::CONTINUE
 367                 } else {
 368                     ControlFlow::BREAK
 369                 }
 370             }
 371             _ => c.super_visit_with(self),
 372         }
 373     }
 374
 375     #[instrument(level = "debug", skip(self))]
 376     fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 377         if !ty.potentially_has_param_types_or_consts() {
 378             return ControlFlow::CONTINUE;
 379         }
 380
 381         match ty.kind() {
 382             ty::Param(param) => {
 383                 if self.unused_parameters.contains(param.index).unwrap_or(false) {
 384                     ControlFlow::CONTINUE
 385                 } else {
 386                     ControlFlow::BREAK
 387                 }
 388             }
 389             _ => ty.super_visit_with(self),
 390         }
 391     }
 392 }