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_middle::mir::{
  10     self,
  11     visit::{TyContext, Visitor},
  12     Constant, ConstantKind, Local, LocalDecl, Location,
  13 };
  14 use rustc_middle::ty::{
  15     self,
  16     query::Providers,
  17     subst::SubstsRef,
  18     visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor},
  19     Const, Ty, TyCtxt, UnusedGenericParams,
  20 };
  21 use rustc_span::symbol::sym;
  22 use std::ops::ControlFlow;
  23
  24 use crate::errors::UnusedGenericParamsHint;
  25
  26 /// Provide implementations of queries relating to polymorphization analysis.
  27 pub fn provide(providers: &mut Providers) {
  28     providers.unused_generic_params = unused_generic_params;
  29 }
  30
  31 /// Determine which generic parameters are used by the instance.
  32 ///
  33 /// Returns a bitset where bits representing unused parameters are set (`is_empty` indicates all
  34 /// parameters are used).
  35 fn unused_generic_params<'tcx>(
  36     tcx: TyCtxt<'tcx>,
  37     instance: ty::InstanceDef<'tcx>,
  38 ) -> UnusedGenericParams {
  39     if !tcx.sess.opts.unstable_opts.polymorphize {
  40         // If polymorphization disabled, then all parameters are used.
  41         return UnusedGenericParams::new_all_used();
  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 UnusedGenericParams::new_all_used();
  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 UnusedGenericParams::new_all_used();
  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 = UnusedGenericParams::new_all_unused(generics_count);
  62     debug!(?unused_parameters, "(start)");
  63
  64     mark_used_by_default_parameters(tcx, def_id, generics, &mut unused_parameters);
  65     debug!(?unused_parameters, "(after default)");
  66
  67     // Visit MIR and accumulate used generic parameters.
  68     let body = match tcx.hir().body_const_context(def_id.expect_local()) {
  69         // Const functions are actually called and should thus be considered for polymorphization
  70         // via their runtime MIR.
  71         Some(ConstContext::ConstFn) | None => tcx.optimized_mir(def_id),
  72         Some(_) => tcx.mir_for_ctfe(def_id),
  73     };
  74     let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters: &mut unused_parameters };
  75     vis.visit_body(body);
  76     debug!(?unused_parameters, "(end)");
  77
  78     // Emit errors for debugging and testing if enabled.
  79     if !unused_parameters.all_used() {
  80         emit_unused_generic_params_error(tcx, def_id, generics, &unused_parameters);
  81     }
  82
  83     unused_parameters
  84 }
  85
  86 /// Returns `true` if the instance should be polymorphized.
  87 fn should_polymorphize<'tcx>(
  88     tcx: TyCtxt<'tcx>,
  89     def_id: DefId,
  90     instance: ty::InstanceDef<'tcx>,
  91 ) -> bool {
  92     // If an instance's MIR body is not polymorphic then the modified substitutions that are
  93     // derived from polymorphization's result won't make any difference.
  94     if !instance.has_polymorphic_mir_body() {
  95         return false;
  96     }
  97
  98     // Don't polymorphize intrinsics or virtual calls - calling `instance_mir` will panic.
  99     if matches!(instance, ty::InstanceDef::Intrinsic(..) | ty::InstanceDef::Virtual(..)) {
 100         return false;
 101     }
 102
 103     // Polymorphization results are stored in cross-crate metadata only when there are unused
 104     // parameters, so assume that non-local items must have only used parameters (else this query
 105     // would not be invoked, and the cross-crate metadata used instead).
 106     if !def_id.is_local() {
 107         return false;
 108     }
 109
 110     // Foreign items have no bodies to analyze.
 111     if tcx.is_foreign_item(def_id) {
 112         return false;
 113     }
 114
 115     // Make sure there is MIR available.
 116     match tcx.hir().body_const_context(def_id.expect_local()) {
 117         Some(ConstContext::ConstFn) | None if !tcx.is_mir_available(def_id) => {
 118             debug!("no mir available");
 119             return false;
 120         }
 121         Some(_) if !tcx.is_ctfe_mir_available(def_id) => {
 122             debug!("no ctfe mir available");
 123             return false;
 124         }
 125         _ => true,
 126     }
 127 }
 128
 129 /// Some parameters are considered used-by-default, such as non-generic parameters and the dummy
 130 /// generic parameters from closures, this function marks them as used. `leaf_is_closure` should
 131 /// be `true` if the item that `unused_generic_params` was invoked on is a closure.
 132 #[instrument(level = "debug", skip(tcx, def_id, generics, unused_parameters))]
 133 fn mark_used_by_default_parameters<'tcx>(
 134     tcx: TyCtxt<'tcx>,
 135     def_id: DefId,
 136     generics: &'tcx ty::Generics,
 137     unused_parameters: &mut UnusedGenericParams,
 138 ) {
 139     match tcx.def_kind(def_id) {
 140         DefKind::Closure | DefKind::Generator => {
 141             for param in &generics.params {
 142                 debug!(?param, "(closure/gen)");
 143                 unused_parameters.mark_used(param.index);
 144             }
 145         }
 146         DefKind::Mod
 147         | DefKind::Struct
 148         | DefKind::Union
 149         | DefKind::Enum
 150         | DefKind::Variant
 151         | DefKind::Trait
 152         | DefKind::TyAlias
 153         | DefKind::ForeignTy
 154         | DefKind::TraitAlias
 155         | DefKind::AssocTy
 156         | DefKind::TyParam
 157         | DefKind::Fn
 158         | DefKind::Const
 159         | DefKind::ConstParam
 160         | DefKind::Static(_)
 161         | DefKind::Ctor(_, _)
 162         | DefKind::AssocFn
 163         | DefKind::AssocConst
 164         | DefKind::Macro(_)
 165         | DefKind::ExternCrate
 166         | DefKind::Use
 167         | DefKind::ForeignMod
 168         | DefKind::AnonConst
 169         | DefKind::InlineConst
 170         | DefKind::OpaqueTy
 171         | DefKind::ImplTraitPlaceholder
 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.mark_used(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: &UnusedGenericParams,
 198 ) {
 199     let base_def_id = tcx.typeck_root_def_id(def_id);
 200     if !tcx.has_attr(base_def_id, sym::rustc_polymorphize_error) {
 201         return;
 202     }
 203
 204     let fn_span = match tcx.opt_item_ident(def_id) {
 205         Some(ident) => ident.span,
 206         _ => tcx.def_span(def_id),
 207     };
 208
 209     let mut param_spans = Vec::new();
 210     let mut param_names = Vec::new();
 211     let mut next_generics = Some(generics);
 212     while let Some(generics) = next_generics {
 213         for param in &generics.params {
 214             if unused_parameters.is_unused(param.index) {
 215                 debug!(?param);
 216                 let def_span = tcx.def_span(param.def_id);
 217                 param_spans.push(def_span);
 218                 param_names.push(param.name.to_string());
 219             }
 220         }
 221
 222         next_generics = generics.parent.map(|did| tcx.generics_of(did));
 223     }
 224
 225     tcx.sess.emit_err(UnusedGenericParamsHint { span: fn_span, param_spans, param_names });
 226 }
 227
 228 /// Visitor used to aggregate generic parameter uses.
 229 struct MarkUsedGenericParams<'a, 'tcx> {
 230     tcx: TyCtxt<'tcx>,
 231     def_id: DefId,
 232     unused_parameters: &'a mut UnusedGenericParams,
 233 }
 234
 235 impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> {
 236     /// Invoke `unused_generic_params` on a body contained within the current item (e.g.
 237     /// a closure, generator or constant).
 238     #[instrument(level = "debug", skip(self, def_id, substs))]
 239     fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) {
 240         let instance = ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id));
 241         let unused = self.tcx.unused_generic_params(instance);
 242         debug!(?self.unused_parameters, ?unused);
 243         for (i, arg) in substs.iter().enumerate() {
 244             let i = i.try_into().unwrap();
 245             if unused.is_used(i) {
 246                 arg.visit_with(self);
 247             }
 248         }
 249         debug!(?self.unused_parameters);
 250     }
 251 }
 252
 253 impl<'a, 'tcx> Visitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
 254     #[instrument(level = "debug", skip(self, local))]
 255     fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
 256         if local == Local::from_usize(1) {
 257             let def_kind = self.tcx.def_kind(self.def_id);
 258             if matches!(def_kind, DefKind::Closure | DefKind::Generator) {
 259                 // Skip visiting the closure/generator that is currently being processed. This only
 260                 // happens because the first argument to the closure is a reference to itself and
 261                 // that will call `visit_substs`, resulting in each generic parameter captured being
 262                 // considered used by default.
 263                 debug!("skipping closure substs");
 264                 return;
 265             }
 266         }
 267
 268         self.super_local_decl(local, local_decl);
 269     }
 270
 271     fn visit_constant(&mut self, ct: &Constant<'tcx>, location: Location) {
 272         match ct.literal {
 273             ConstantKind::Ty(c) => {
 274                 c.visit_with(self);
 275             }
 276             ConstantKind::Unevaluated(mir::UnevaluatedConst { def, substs: _, promoted }, ty) => {
 277                 // Avoid considering `T` unused when constants are of the form:
 278                 //   `<Self as Foo<T>>::foo::promoted[p]`
 279                 if let Some(p) = promoted {
 280                     if self.def_id == def.did && !self.tcx.generics_of(def.did).has_self {
 281                         // If there is a promoted, don't look at the substs - since it will always contain
 282                         // the generic parameters, instead, traverse the promoted MIR.
 283                         let promoted = self.tcx.promoted_mir(def.did);
 284                         self.visit_body(&promoted[p]);
 285                     }
 286                 }
 287
 288                 Visitor::visit_ty(self, ty, TyContext::Location(location));
 289             }
 290             ConstantKind::Val(_, ty) => Visitor::visit_ty(self, ty, TyContext::Location(location)),
 291         }
 292     }
 293
 294     fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) {
 295         ty.visit_with(self);
 296     }
 297 }
 298
 299 impl<'a, 'tcx> TypeVisitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
 300     #[instrument(level = "debug", skip(self))]
 301     fn visit_const(&mut self, c: Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 302         if !c.has_non_region_param() {
 303             return ControlFlow::Continue(());
 304         }
 305
 306         match c.kind() {
 307             ty::ConstKind::Param(param) => {
 308                 debug!(?param);
 309                 self.unused_parameters.mark_used(param.index);
 310                 ControlFlow::Continue(())
 311             }
 312             ty::ConstKind::Unevaluated(ty::UnevaluatedConst { def, substs })
 313                 if matches!(self.tcx.def_kind(def.did), DefKind::AnonConst) =>
 314             {
 315                 self.visit_child_body(def.did, substs);
 316                 ControlFlow::Continue(())
 317             }
 318             _ => c.super_visit_with(self),
 319         }
 320     }
 321
 322     #[instrument(level = "debug", skip(self))]
 323     fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 324         if !ty.has_non_region_param() {
 325             return ControlFlow::Continue(());
 326         }
 327
 328         match *ty.kind() {
 329             ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => {
 330                 debug!(?def_id);
 331                 // Avoid cycle errors with generators.
 332                 if def_id == self.def_id {
 333                     return ControlFlow::Continue(());
 334                 }
 335
 336                 // Consider any generic parameters used by any closures/generators as used in the
 337                 // parent.
 338                 self.visit_child_body(def_id, substs);
 339                 ControlFlow::Continue(())
 340             }
 341             ty::Param(param) => {
 342                 debug!(?param);
 343                 self.unused_parameters.mark_used(param.index);
 344                 ControlFlow::Continue(())
 345             }
 346             _ => ty.super_visit_with(self),
 347         }
 348     }
 349 }