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