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