diff options
Diffstat (limited to 'compiler/rustc_monomorphize/src/polymorphize.rs')
-rw-r--r-- | compiler/rustc_monomorphize/src/polymorphize.rs | 385 |
1 files changed, 385 insertions, 0 deletions
diff --git a/compiler/rustc_monomorphize/src/polymorphize.rs b/compiler/rustc_monomorphize/src/polymorphize.rs new file mode 100644 index 000000000..394843e51 --- /dev/null +++ b/compiler/rustc_monomorphize/src/polymorphize.rs @@ -0,0 +1,385 @@ +//! Polymorphization Analysis +//! ========================= +//! +//! This module implements an analysis of functions, methods and closures to determine which +//! generic parameters are unused (and eventually, in what ways generic parameters are used - only +//! for their size, offset of a field, etc.). + +use rustc_hir::{def::DefKind, def_id::DefId, ConstContext}; +use rustc_index::bit_set::FiniteBitSet; +use rustc_middle::mir::{ + visit::{TyContext, Visitor}, + Local, LocalDecl, Location, +}; +use rustc_middle::ty::{ + self, + query::Providers, + subst::SubstsRef, + visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor}, + Const, Ty, TyCtxt, +}; +use rustc_span::symbol::sym; +use std::convert::TryInto; +use std::ops::ControlFlow; + +/// Provide implementations of queries relating to polymorphization analysis. +pub fn provide(providers: &mut Providers) { + providers.unused_generic_params = unused_generic_params; +} + +/// Determine which generic parameters are used by the instance. +/// +/// Returns a bitset where bits representing unused parameters are set (`is_empty` indicates all +/// parameters are used). +#[instrument(level = "debug", skip(tcx))] +fn unused_generic_params<'tcx>( + tcx: TyCtxt<'tcx>, + instance: ty::InstanceDef<'tcx>, +) -> FiniteBitSet<u32> { + if !tcx.sess.opts.unstable_opts.polymorphize { + // If polymorphization disabled, then all parameters are used. + return FiniteBitSet::new_empty(); + } + + let def_id = instance.def_id(); + // Exit early if this instance should not be polymorphized. + if !should_polymorphize(tcx, def_id, instance) { + return FiniteBitSet::new_empty(); + } + + let generics = tcx.generics_of(def_id); + debug!(?generics); + + // Exit early when there are no parameters to be unused. + if generics.count() == 0 { + return FiniteBitSet::new_empty(); + } + + // Create a bitset with N rightmost ones for each parameter. + let generics_count: u32 = + generics.count().try_into().expect("more generic parameters than can fit into a `u32`"); + let mut unused_parameters = FiniteBitSet::<u32>::new_empty(); + unused_parameters.set_range(0..generics_count); + debug!(?unused_parameters, "(start)"); + + mark_used_by_default_parameters(tcx, def_id, generics, &mut unused_parameters); + debug!(?unused_parameters, "(after default)"); + + // Visit MIR and accumulate used generic parameters. + let body = match tcx.hir().body_const_context(def_id.expect_local()) { + // Const functions are actually called and should thus be considered for polymorphization + // via their runtime MIR. + Some(ConstContext::ConstFn) | None => tcx.optimized_mir(def_id), + Some(_) => tcx.mir_for_ctfe(def_id), + }; + let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters: &mut unused_parameters }; + vis.visit_body(body); + debug!(?unused_parameters, "(end)"); + + // Emit errors for debugging and testing if enabled. + if !unused_parameters.is_empty() { + emit_unused_generic_params_error(tcx, def_id, generics, &unused_parameters); + } + + unused_parameters +} + +/// Returns `true` if the instance should be polymorphized. +fn should_polymorphize<'tcx>( + tcx: TyCtxt<'tcx>, + def_id: DefId, + instance: ty::InstanceDef<'tcx>, +) -> bool { + // If an instance's MIR body is not polymorphic then the modified substitutions that are + // derived from polymorphization's result won't make any difference. + if !instance.has_polymorphic_mir_body() { + return false; + } + + // Don't polymorphize intrinsics or virtual calls - calling `instance_mir` will panic. + if matches!(instance, ty::InstanceDef::Intrinsic(..) | ty::InstanceDef::Virtual(..)) { + return false; + } + + // Polymorphization results are stored in cross-crate metadata only when there are unused + // parameters, so assume that non-local items must have only used parameters (else this query + // would not be invoked, and the cross-crate metadata used instead). + if !def_id.is_local() { + return false; + } + + // Foreign items have no bodies to analyze. + if tcx.is_foreign_item(def_id) { + return false; + } + + // Make sure there is MIR available. + match tcx.hir().body_const_context(def_id.expect_local()) { + Some(ConstContext::ConstFn) | None if !tcx.is_mir_available(def_id) => { + debug!("no mir available"); + return false; + } + Some(_) if !tcx.is_ctfe_mir_available(def_id) => { + debug!("no ctfe mir available"); + return false; + } + _ => true, + } +} + +/// Some parameters are considered used-by-default, such as non-generic parameters and the dummy +/// generic parameters from closures, this function marks them as used. `leaf_is_closure` should +/// be `true` if the item that `unused_generic_params` was invoked on is a closure. +#[instrument(level = "debug", skip(tcx, def_id, generics, unused_parameters))] +fn mark_used_by_default_parameters<'tcx>( + tcx: TyCtxt<'tcx>, + def_id: DefId, + generics: &'tcx ty::Generics, + unused_parameters: &mut FiniteBitSet<u32>, +) { + match tcx.def_kind(def_id) { + DefKind::Closure | DefKind::Generator => { + for param in &generics.params { + debug!(?param, "(closure/gen)"); + unused_parameters.clear(param.index); + } + } + DefKind::Mod + | DefKind::Struct + | DefKind::Union + | DefKind::Enum + | DefKind::Variant + | DefKind::Trait + | DefKind::TyAlias + | DefKind::ForeignTy + | DefKind::TraitAlias + | DefKind::AssocTy + | DefKind::TyParam + | DefKind::Fn + | DefKind::Const + | DefKind::ConstParam + | DefKind::Static(_) + | DefKind::Ctor(_, _) + | DefKind::AssocFn + | DefKind::AssocConst + | DefKind::Macro(_) + | DefKind::ExternCrate + | DefKind::Use + | DefKind::ForeignMod + | DefKind::AnonConst + | DefKind::InlineConst + | DefKind::OpaqueTy + | DefKind::Field + | DefKind::LifetimeParam + | DefKind::GlobalAsm + | DefKind::Impl => { + for param in &generics.params { + debug!(?param, "(other)"); + if let ty::GenericParamDefKind::Lifetime = param.kind { + unused_parameters.clear(param.index); + } + } + } + } + + if let Some(parent) = generics.parent { + mark_used_by_default_parameters(tcx, parent, tcx.generics_of(parent), unused_parameters); + } +} + +/// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic +/// parameter which was unused. +#[instrument(level = "debug", skip(tcx, generics))] +fn emit_unused_generic_params_error<'tcx>( + tcx: TyCtxt<'tcx>, + def_id: DefId, + generics: &'tcx ty::Generics, + unused_parameters: &FiniteBitSet<u32>, +) { + let base_def_id = tcx.typeck_root_def_id(def_id); + if !tcx.has_attr(base_def_id, sym::rustc_polymorphize_error) { + return; + } + + let fn_span = match tcx.opt_item_ident(def_id) { + Some(ident) => ident.span, + _ => tcx.def_span(def_id), + }; + + let mut err = tcx.sess.struct_span_err(fn_span, "item has unused generic parameters"); + + let mut next_generics = Some(generics); + while let Some(generics) = next_generics { + for param in &generics.params { + if unused_parameters.contains(param.index).unwrap_or(false) { + debug!(?param); + let def_span = tcx.def_span(param.def_id); + err.span_label(def_span, &format!("generic parameter `{}` is unused", param.name)); + } + } + + next_generics = generics.parent.map(|did| tcx.generics_of(did)); + } + + err.emit(); +} + +/// Visitor used to aggregate generic parameter uses. +struct MarkUsedGenericParams<'a, 'tcx> { + tcx: TyCtxt<'tcx>, + def_id: DefId, + unused_parameters: &'a mut FiniteBitSet<u32>, +} + +impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> { + /// Invoke `unused_generic_params` on a body contained within the current item (e.g. + /// a closure, generator or constant). + #[instrument(level = "debug", skip(self, def_id, substs))] + fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) { + let instance = ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id)); + let unused = self.tcx.unused_generic_params(instance); + debug!(?self.unused_parameters, ?unused); + for (i, arg) in substs.iter().enumerate() { + let i = i.try_into().unwrap(); + if !unused.contains(i).unwrap_or(false) { + arg.visit_with(self); + } + } + debug!(?self.unused_parameters); + } +} + +impl<'a, 'tcx> Visitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> { + #[instrument(level = "debug", skip(self, local))] + fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) { + if local == Local::from_usize(1) { + let def_kind = self.tcx.def_kind(self.def_id); + if matches!(def_kind, DefKind::Closure | DefKind::Generator) { + // Skip visiting the closure/generator that is currently being processed. This only + // happens because the first argument to the closure is a reference to itself and + // that will call `visit_substs`, resulting in each generic parameter captured being + // considered used by default. + debug!("skipping closure substs"); + return; + } + } + + self.super_local_decl(local, local_decl); + } + + fn visit_const(&mut self, c: Const<'tcx>, _: Location) { + c.visit_with(self); + } + + fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) { + ty.visit_with(self); + } +} + +impl<'a, 'tcx> TypeVisitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> { + #[instrument(level = "debug", skip(self))] + fn visit_const(&mut self, c: Const<'tcx>) -> ControlFlow<Self::BreakTy> { + if !c.has_param_types_or_consts() { + return ControlFlow::CONTINUE; + } + + match c.kind() { + ty::ConstKind::Param(param) => { + debug!(?param); + self.unused_parameters.clear(param.index); + ControlFlow::CONTINUE + } + ty::ConstKind::Unevaluated(ty::Unevaluated { def, substs: _, promoted: Some(p)}) + // Avoid considering `T` unused when constants are of the form: + // `<Self as Foo<T>>::foo::promoted[p]` + if self.def_id == def.did && !self.tcx.generics_of(def.did).has_self => + { + // If there is a promoted, don't look at the substs - since it will always contain + // the generic parameters, instead, traverse the promoted MIR. + let promoted = self.tcx.promoted_mir(def.did); + self.visit_body(&promoted[p]); + ControlFlow::CONTINUE + } + ty::ConstKind::Unevaluated(uv) + if matches!(self.tcx.def_kind(uv.def.did), DefKind::AnonConst | DefKind::InlineConst) => + { + self.visit_child_body(uv.def.did, uv.substs); + ControlFlow::CONTINUE + } + _ => c.super_visit_with(self), + } + } + + #[instrument(level = "debug", skip(self))] + fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { + if !ty.has_param_types_or_consts() { + return ControlFlow::CONTINUE; + } + + match *ty.kind() { + ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => { + debug!(?def_id); + // Avoid cycle errors with generators. + if def_id == self.def_id { + return ControlFlow::CONTINUE; + } + + // Consider any generic parameters used by any closures/generators as used in the + // parent. + self.visit_child_body(def_id, substs); + ControlFlow::CONTINUE + } + ty::Param(param) => { + debug!(?param); + self.unused_parameters.clear(param.index); + ControlFlow::CONTINUE + } + _ => ty.super_visit_with(self), + } + } +} + +/// Visitor used to check if a generic parameter is used. +struct HasUsedGenericParams<'a> { + unused_parameters: &'a FiniteBitSet<u32>, +} + +impl<'a, 'tcx> TypeVisitor<'tcx> for HasUsedGenericParams<'a> { + type BreakTy = (); + + #[instrument(level = "debug", skip(self))] + fn visit_const(&mut self, c: Const<'tcx>) -> ControlFlow<Self::BreakTy> { + if !c.has_param_types_or_consts() { + return ControlFlow::CONTINUE; + } + + match c.kind() { + ty::ConstKind::Param(param) => { + if self.unused_parameters.contains(param.index).unwrap_or(false) { + ControlFlow::CONTINUE + } else { + ControlFlow::BREAK + } + } + _ => c.super_visit_with(self), + } + } + + #[instrument(level = "debug", skip(self))] + fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { + if !ty.has_param_types_or_consts() { + return ControlFlow::CONTINUE; + } + + match ty.kind() { + ty::Param(param) => { + if self.unused_parameters.contains(param.index).unwrap_or(false) { + ControlFlow::CONTINUE + } else { + ControlFlow::BREAK + } + } + _ => ty.super_visit_with(self), + } + } +} |