Auto merge of #69749 - davidtwco:issue-46477-polymorphization, r=eddyb

Polymorphization

This PR implements an analysis to detect when functions could remain polymorphic during code generation.

Fixes #46477

r? @eddyb
cc @rust-lang/wg-mir-opt @nikomatsakis @pnkfelix

67 files changed, 2034 insertions, 191 deletions

diff --git a/src/librustc_codegen_llvm/callee.rs b/src/librustc_codegen_llvm/callee.rs
index 7b341651adf..75b4f2e3ca5 100644
--- a/src/librustc_codegen_llvm/callee.rs
+++ b/src/librustc_codegen_llvm/callee.rs
@@ -13,7 +13,7 @@ use log::debug;
 use rustc_codegen_ssa::traits::*;
 
 use rustc_middle::ty::layout::{FnAbiExt, HasTyCtxt};
-use rustc_middle::ty::{Instance, TypeFoldable};
+use rustc_middle::ty::{self, Instance, TypeFoldable};
 
 /// Codegens a reference to a fn/method item, monomorphizing and
 /// inlining as it goes.
@@ -29,14 +29,18 @@ pub fn get_fn(cx: &CodegenCx<'ll, 'tcx>, instance: Instance<'tcx>) -> &'ll Value
 
     assert!(!instance.substs.needs_infer());
     assert!(!instance.substs.has_escaping_bound_vars());
-    assert!(!instance.substs.has_param_types_or_consts());
 
     if let Some(&llfn) = cx.instances.borrow().get(&instance) {
         return llfn;
     }
 
     let sym = tcx.symbol_name(instance).name;
-    debug!("get_fn({:?}: {:?}) => {}", instance, instance.monomorphic_ty(cx.tcx()), sym);
+    debug!(
+        "get_fn({:?}: {:?}) => {}",
+        instance,
+        instance.ty(cx.tcx(), ty::ParamEnv::reveal_all()),
+        sym
+    );
 
     let fn_abi = FnAbi::of_instance(cx, instance, &[]);
 
diff --git a/src/librustc_codegen_llvm/consts.rs b/src/librustc_codegen_llvm/consts.rs
index c954415f19f..e8d47540509 100644
--- a/src/librustc_codegen_llvm/consts.rs
+++ b/src/librustc_codegen_llvm/consts.rs
@@ -203,7 +203,7 @@ impl CodegenCx<'ll, 'tcx> {
             def_id
         );
 
-        let ty = instance.monomorphic_ty(self.tcx);
+        let ty = instance.ty(self.tcx, ty::ParamEnv::reveal_all());
         let sym = self.tcx.symbol_name(instance).name;
 
         debug!("get_static: sym={} instance={:?}", sym, instance);
@@ -361,7 +361,7 @@ impl StaticMethods for CodegenCx<'ll, 'tcx> {
             };
 
             let instance = Instance::mono(self.tcx, def_id);
-            let ty = instance.monomorphic_ty(self.tcx);
+            let ty = instance.ty(self.tcx, ty::ParamEnv::reveal_all());
             let llty = self.layout_of(ty).llvm_type(self);
             let g = if val_llty == llty {
                 g
diff --git a/src/librustc_codegen_llvm/debuginfo/metadata.rs b/src/librustc_codegen_llvm/debuginfo/metadata.rs
index ef9d42968ae..6ae7c7efaee 100644
--- a/src/librustc_codegen_llvm/debuginfo/metadata.rs
+++ b/src/librustc_codegen_llvm/debuginfo/metadata.rs
@@ -700,6 +700,8 @@ pub fn type_metadata(cx: &CodegenCx<'ll, 'tcx>, t: Ty<'tcx>, usage_site_span: Sp
             prepare_tuple_metadata(cx, t, &tys, unique_type_id, usage_site_span, NO_SCOPE_METADATA)
                 .finalize(cx)
         }
+        // Type parameters from polymorphized functions.
+        ty::Param(_) => MetadataCreationResult::new(param_type_metadata(cx, t), false),
         _ => bug!("debuginfo: unexpected type in type_metadata: {:?}", t),
     };
 
@@ -955,6 +957,20 @@ fn pointer_type_metadata(
     }
 }
 
+fn param_type_metadata(cx: &CodegenCx<'ll, 'tcx>, t: Ty<'tcx>) -> &'ll DIType {
+    debug!("param_type_metadata: {:?}", t);
+    let name = format!("{:?}", t);
+    return unsafe {
+        llvm::LLVMRustDIBuilderCreateBasicType(
+            DIB(cx),
+            name.as_ptr().cast(),
+            name.len(),
+            Size::ZERO.bits(),
+            DW_ATE_unsigned,
+        )
+    };
+}
+
 pub fn compile_unit_metadata(
     tcx: TyCtxt<'_>,
     codegen_unit_name: &str,
@@ -2465,7 +2481,7 @@ pub fn create_global_var_metadata(cx: &CodegenCx<'ll, '_>, def_id: DefId, global
     };
 
     let is_local_to_unit = is_node_local_to_unit(cx, def_id);
-    let variable_type = Instance::mono(cx.tcx, def_id).monomorphic_ty(cx.tcx);
+    let variable_type = Instance::mono(cx.tcx, def_id).ty(cx.tcx, ty::ParamEnv::reveal_all());
     let type_metadata = type_metadata(cx, variable_type, span);
     let var_name = tcx.item_name(def_id).as_str();
     let linkage_name = mangled_name_of_instance(cx, Instance::mono(tcx, def_id)).name;
diff --git a/src/librustc_codegen_llvm/debuginfo/mod.rs b/src/librustc_codegen_llvm/debuginfo/mod.rs
index 44993d7602f..a01b8553721 100644
--- a/src/librustc_codegen_llvm/debuginfo/mod.rs
+++ b/src/librustc_codegen_llvm/debuginfo/mod.rs
@@ -26,7 +26,7 @@ use rustc_index::vec::IndexVec;
 use rustc_middle::mir;
 use rustc_middle::ty::layout::HasTyCtxt;
 use rustc_middle::ty::subst::{GenericArgKind, SubstsRef};
-use rustc_middle::ty::{self, Instance, ParamEnv, Ty};
+use rustc_middle::ty::{self, Instance, ParamEnv, Ty, TypeFoldable};
 use rustc_session::config::{self, DebugInfo};
 use rustc_span::symbol::Symbol;
 use rustc_span::{self, BytePos, Span};
@@ -470,7 +470,9 @@ impl DebugInfoMethods<'tcx> for CodegenCx<'ll, 'tcx> {
                     match impl_self_ty.kind {
                         ty::Adt(def, ..) if !def.is_box() => {
                             // Again, only create type information if full debuginfo is enabled
-                            if cx.sess().opts.debuginfo == DebugInfo::Full {
+                            if cx.sess().opts.debuginfo == DebugInfo::Full
+                                && !impl_self_ty.needs_subst()
+                            {
                                 Some(type_metadata(cx, impl_self_ty, rustc_span::DUMMY_SP))
                             } else {
                                 Some(namespace::item_namespace(cx, def.did))
diff --git a/src/librustc_codegen_llvm/intrinsic.rs b/src/librustc_codegen_llvm/intrinsic.rs
index 63ec8031483..2e5929a433d 100644
--- a/src/librustc_codegen_llvm/intrinsic.rs
+++ b/src/librustc_codegen_llvm/intrinsic.rs
@@ -160,7 +160,7 @@ impl IntrinsicCallMethods<'tcx> for Builder<'a, 'll, 'tcx> {
         caller_instance: ty::Instance<'tcx>,
     ) {
         let tcx = self.tcx;
-        let callee_ty = instance.monomorphic_ty(tcx);
+        let callee_ty = instance.ty(tcx, ty::ParamEnv::reveal_all());
 
         let (def_id, substs) = match callee_ty.kind {
             ty::FnDef(def_id, substs) => (def_id, substs),
diff --git a/src/librustc_codegen_llvm/mono_item.rs b/src/librustc_codegen_llvm/mono_item.rs
index 486ea7f22df..0936deb7bb5 100644
--- a/src/librustc_codegen_llvm/mono_item.rs
+++ b/src/librustc_codegen_llvm/mono_item.rs
@@ -10,7 +10,7 @@ use rustc_hir::def_id::{DefId, LOCAL_CRATE};
 pub use rustc_middle::mir::mono::MonoItem;
 use rustc_middle::mir::mono::{Linkage, Visibility};
 use rustc_middle::ty::layout::FnAbiExt;
-use rustc_middle::ty::{Instance, TypeFoldable};
+use rustc_middle::ty::{self, Instance, TypeFoldable};
 use rustc_target::abi::LayoutOf;
 
 impl PreDefineMethods<'tcx> for CodegenCx<'ll, 'tcx> {
@@ -22,7 +22,7 @@ impl PreDefineMethods<'tcx> for CodegenCx<'ll, 'tcx> {
         symbol_name: &str,
     ) {
         let instance = Instance::mono(self.tcx, def_id);
-        let ty = instance.monomorphic_ty(self.tcx);
+        let ty = instance.ty(self.tcx, ty::ParamEnv::reveal_all());
         let llty = self.layout_of(ty).llvm_type(self);
 
         let g = self.define_global(symbol_name, llty).unwrap_or_else(|| {
@@ -47,7 +47,7 @@ impl PreDefineMethods<'tcx> for CodegenCx<'ll, 'tcx> {
         visibility: Visibility,
         symbol_name: &str,
     ) {
-        assert!(!instance.substs.needs_infer() && !instance.substs.has_param_types_or_consts());
+        assert!(!instance.substs.needs_infer());
 
         let fn_abi = FnAbi::of_instance(self, instance, &[]);
         let lldecl = self.declare_fn(symbol_name, &fn_abi);
diff --git a/src/librustc_codegen_ssa/debuginfo/type_names.rs b/src/librustc_codegen_ssa/debuginfo/type_names.rs
index 20d440433cb..fb8f5a62989 100644
--- a/src/librustc_codegen_ssa/debuginfo/type_names.rs
+++ b/src/librustc_codegen_ssa/debuginfo/type_names.rs
@@ -205,14 +205,17 @@ pub fn push_debuginfo_type_name<'tcx>(
                 tcx.def_key(def_id).disambiguated_data.disambiguator
             ));
         }
+        // Type parameters from polymorphized functions.
+        ty::Param(_) => {
+            output.push_str(&format!("{:?}", t));
+        }
         ty::Error(_)
         | ty::Infer(_)
         | ty::Placeholder(..)
         | ty::Projection(..)
         | ty::Bound(..)
         | ty::Opaque(..)
-        | ty::GeneratorWitness(..)
-        | ty::Param(_) => {
+        | ty::GeneratorWitness(..) => {
             bug!(
                 "debuginfo: Trying to create type name for \
                   unexpected type: {:?}",
diff --git a/src/librustc_codegen_ssa/meth.rs b/src/librustc_codegen_ssa/meth.rs
index 199dd8c7df4..cfa01280e5a 100644
--- a/src/librustc_codegen_ssa/meth.rs
+++ b/src/librustc_codegen_ssa/meth.rs
@@ -94,7 +94,8 @@ pub fn get_vtable<'tcx, Cx: CodegenMethods<'tcx>>(
                     def_id,
                     substs,
                 )
-                .unwrap(),
+                .unwrap()
+                .polymorphize(cx.tcx()),
             )
         })
     });
diff --git a/src/librustc_codegen_ssa/mir/analyze.rs b/src/librustc_codegen_ssa/mir/analyze.rs
index db935c2b3e2..2e386c1e594 100644
--- a/src/librustc_codegen_ssa/mir/analyze.rs
+++ b/src/librustc_codegen_ssa/mir/analyze.rs
@@ -124,8 +124,7 @@ impl<Bx: BuilderMethods<'a, 'tcx>> LocalAnalyzer<'mir, 'a, 'tcx, Bx> {
                 let base_ty = self.fx.monomorphize(&base_ty);
 
                 // ZSTs don't require any actual memory access.
-                let elem_ty = base_ty.projection_ty(cx.tcx(), elem).ty;
-                let elem_ty = self.fx.monomorphize(&elem_ty);
+                let elem_ty = base_ty.projection_ty(cx.tcx(), self.fx.monomorphize(&elem)).ty;
                 let span = self.fx.mir.local_decls[place_ref.local].source_info.span;
                 if cx.spanned_layout_of(elem_ty, span).is_zst() {
                     return;
diff --git a/src/librustc_codegen_ssa/mir/block.rs b/src/librustc_codegen_ssa/mir/block.rs
index 7116bb8c925..e1de9677f80 100644
--- a/src/librustc_codegen_ssa/mir/block.rs
+++ b/src/librustc_codegen_ssa/mir/block.rs
@@ -543,7 +543,8 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
                 Some(
                     ty::Instance::resolve(bx.tcx(), ty::ParamEnv::reveal_all(), def_id, substs)
                         .unwrap()
-                        .unwrap(),
+                        .unwrap()
+                        .polymorphize(bx.tcx()),
                 ),
                 None,
             ),
diff --git a/src/librustc_codegen_ssa/mir/rvalue.rs b/src/librustc_codegen_ssa/mir/rvalue.rs
index 4b2be7b5321..9c108998bc9 100644
--- a/src/librustc_codegen_ssa/mir/rvalue.rs
+++ b/src/librustc_codegen_ssa/mir/rvalue.rs
@@ -190,17 +190,15 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
                                 if bx.cx().tcx().has_attr(def_id, sym::rustc_args_required_const) {
                                     bug!("reifying a fn ptr that requires const arguments");
                                 }
-                                OperandValue::Immediate(
-                                    bx.get_fn_addr(
-                                        ty::Instance::resolve_for_fn_ptr(
-                                            bx.tcx(),
-                                            ty::ParamEnv::reveal_all(),
-                                            def_id,
-                                            substs,
-                                        )
-                                        .unwrap(),
-                                    ),
+                                let instance = ty::Instance::resolve_for_fn_ptr(
+                                    bx.tcx(),
+                                    ty::ParamEnv::reveal_all(),
+                                    def_id,
+                                    substs,
                                 )
+                                .unwrap()
+                                .polymorphize(bx.cx().tcx());
+                                OperandValue::Immediate(bx.get_fn_addr(instance))
                             }
                             _ => bug!("{} cannot be reified to a fn ptr", operand.layout.ty),
                         }
@@ -213,7 +211,8 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
                                     def_id,
                                     substs,
                                     ty::ClosureKind::FnOnce,
-                                );
+                                )
+                                .polymorphize(bx.cx().tcx());
                                 OperandValue::Immediate(bx.cx().get_fn_addr(instance))
                             }
                             _ => bug!("{} cannot be cast to a fn ptr", operand.layout.ty),
diff --git a/src/librustc_data_structures/stable_hasher.rs b/src/librustc_data_structures/stable_hasher.rs
index 97b02eaef35..c1c79b174f4 100644
--- a/src/librustc_data_structures/stable_hasher.rs
+++ b/src/librustc_data_structures/stable_hasher.rs
@@ -469,6 +469,15 @@ impl<R: vec::Idx, C: vec::Idx, CTX> HashStable<CTX> for bit_set::BitMatrix<R, C>
     }
 }
 
+impl<T, CTX> HashStable<CTX> for bit_set::FiniteBitSet<T>
+where
+    T: HashStable<CTX> + bit_set::FiniteBitSetTy,
+{
+    fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
+        self.0.hash_stable(hcx, hasher);
+    }
+}
+
 impl_stable_hash_via_hash!(::std::path::Path);
 impl_stable_hash_via_hash!(::std::path::PathBuf);
 
diff --git a/src/librustc_feature/builtin_attrs.rs b/src/librustc_feature/builtin_attrs.rs
index 4e2aea34fe7..879f06f89a7 100644
--- a/src/librustc_feature/builtin_attrs.rs
+++ b/src/librustc_feature/builtin_attrs.rs
@@ -568,6 +568,7 @@ pub const BUILTIN_ATTRIBUTES: &[BuiltinAttribute] = &[
     ),
     rustc_attr!(TEST, rustc_synthetic, AssumedUsed, template!(Word)),
     rustc_attr!(TEST, rustc_symbol_name, AssumedUsed, template!(Word)),
+    rustc_attr!(TEST, rustc_polymorphize_error, AssumedUsed, template!(Word)),
     rustc_attr!(TEST, rustc_def_path, AssumedUsed, template!(Word)),
     rustc_attr!(TEST, rustc_mir, AssumedUsed, template!(List: "arg1, arg2, ...")),
     rustc_attr!(TEST, rustc_dump_program_clauses, AssumedUsed, template!(Word)),
diff --git a/src/librustc_index/bit_set.rs b/src/librustc_index/bit_set.rs
index dd2fbaf6a94..b369be25218 100644
--- a/src/librustc_index/bit_set.rs
+++ b/src/librustc_index/bit_set.rs
@@ -4,6 +4,7 @@ use std::fmt;
 use std::iter;
 use std::marker::PhantomData;
 use std::mem;
+use std::ops::{BitAnd, BitAndAssign, BitOrAssign, Not, Range, Shl};
 use std::slice;
 
 #[cfg(test)]
@@ -1001,3 +1002,137 @@ fn word_index_and_mask<T: Idx>(elem: T) -> (usize, Word) {
     let mask = 1 << (elem % WORD_BITS);
     (word_index, mask)
 }
+
+/// Integral type used to represent the bit set.
+pub trait FiniteBitSetTy:
+    BitAnd<Output = Self>
+    + BitAndAssign
+    + BitOrAssign
+    + Clone
+    + Copy
+    + Shl
+    + Not<Output = Self>
+    + PartialEq
+    + Sized
+{
+    /// Size of the domain representable by this type, e.g. 64 for `u64`.
+    const DOMAIN_SIZE: u32;
+
+    /// Value which represents the `FiniteBitSet` having every bit set.
+    const FILLED: Self;
+    /// Value which represents the `FiniteBitSet` having no bits set.
+    const EMPTY: Self;
+
+    /// Value for one as the integral type.
+    const ONE: Self;
+    /// Value for zero as the integral type.
+    const ZERO: Self;
+
+    /// Perform a checked left shift on the integral type.
+    fn checked_shl(self, rhs: u32) -> Option<Self>;
+    /// Perform a checked right shift on the integral type.
+    fn checked_shr(self, rhs: u32) -> Option<Self>;
+}
+
+impl FiniteBitSetTy for u64 {
+    const DOMAIN_SIZE: u32 = 64;
+
+    const FILLED: Self = Self::MAX;
+    const EMPTY: Self = Self::MIN;
+
+    const ONE: Self = 1u64;
+    const ZERO: Self = 0u64;
+
+    fn checked_shl(self, rhs: u32) -> Option<Self> {
+        self.checked_shl(rhs)
+    }
+
+    fn checked_shr(self, rhs: u32) -> Option<Self> {
+        self.checked_shr(rhs)
+    }
+}
+
+impl std::fmt::Debug for FiniteBitSet<u64> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "{:064b}", self.0)
+    }
+}
+
+impl FiniteBitSetTy for u128 {
+    const DOMAIN_SIZE: u32 = 128;
+
+    const FILLED: Self = Self::MAX;
+    const EMPTY: Self = Self::MIN;
+
+    const ONE: Self = 1u128;
+    const ZERO: Self = 0u128;
+
+    fn checked_shl(self, rhs: u32) -> Option<Self> {
+        self.checked_shl(rhs)
+    }
+
+    fn checked_shr(self, rhs: u32) -> Option<Self> {
+        self.checked_shr(rhs)
+    }
+}
+
+impl std::fmt::Debug for FiniteBitSet<u128> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "{:0128b}", self.0)
+    }
+}
+
+/// A fixed-sized bitset type represented by an integer type. Indices outwith than the range
+/// representable by `T` are considered set.
+#[derive(Copy, Clone, Eq, PartialEq, RustcDecodable, RustcEncodable)]
+pub struct FiniteBitSet<T: FiniteBitSetTy>(pub T);
+
+impl<T: FiniteBitSetTy> FiniteBitSet<T> {
+    /// Creates a new, empty bitset.
+    pub fn new_empty() -> Self {
+        Self(T::EMPTY)
+    }
+
+    /// Sets the `index`th bit.
+    pub fn set(&mut self, index: u32) {
+        self.0 |= T::ONE.checked_shl(index).unwrap_or(T::ZERO);
+    }
+
+    /// Unsets the `index`th bit.
+    pub fn clear(&mut self, index: u32) {
+        self.0 &= !T::ONE.checked_shl(index).unwrap_or(T::ZERO);
+    }
+
+    /// Sets the `i`th to `j`th bits.
+    pub fn set_range(&mut self, range: Range<u32>) {
+        let bits = T::FILLED
+            .checked_shl(range.end - range.start)
+            .unwrap_or(T::ZERO)
+            .not()
+            .checked_shl(range.start)
+            .unwrap_or(T::ZERO);
+        self.0 |= bits;
+    }
+
+    /// Is the set empty?
+    pub fn is_empty(&self) -> bool {
+        self.0 == T::EMPTY
+    }
+
+    /// Returns the domain size of the bitset.
+    pub fn within_domain(&self, index: u32) -> bool {
+        index < T::DOMAIN_SIZE
+    }
+
+    /// Returns if the `index`th bit is set.
+    pub fn contains(&self, index: u32) -> Option<bool> {
+        self.within_domain(index)
+            .then(|| ((self.0.checked_shr(index).unwrap_or(T::ONE)) & T::ONE) == T::ONE)
+    }
+}
+
+impl<T: FiniteBitSetTy> Default for FiniteBitSet<T> {
+    fn default() -> Self {
+        Self::new_empty()
+    }
+}
diff --git a/src/librustc_index/lib.rs b/src/librustc_index/lib.rs
index eaef4c7b54a..7ee881b0639 100644
--- a/src/librustc_index/lib.rs
+++ b/src/librustc_index/lib.rs
@@ -1,4 +1,5 @@
 #![feature(allow_internal_unstable)]
+#![feature(bool_to_option)]
 #![feature(const_fn)]
 #![feature(const_panic)]
 #![feature(extend_one)]
diff --git a/src/librustc_metadata/rmeta/decoder.rs b/src/librustc_metadata/rmeta/decoder.rs
index 4746e53ce59..a6d708ebe90 100644
--- a/src/librustc_metadata/rmeta/decoder.rs
+++ b/src/librustc_metadata/rmeta/decoder.rs
@@ -1132,6 +1132,16 @@ impl<'a, 'tcx> CrateMetadataRef<'a> {
             .decode((self, tcx))
     }
 
+    fn get_unused_generic_params(&self, id: DefIndex) -> FiniteBitSet<u64> {
+        self.root
+            .tables
+            .unused_generic_params
+            .get(self, id)
+            .filter(|_| !self.is_proc_macro(id))
+            .map(|params| params.decode(self))
+            .unwrap_or_default()
+    }
+
     fn get_promoted_mir(&self, tcx: TyCtxt<'tcx>, id: DefIndex) -> IndexVec<Promoted, Body<'tcx>> {
         self.root
             .tables
diff --git a/src/librustc_metadata/rmeta/decoder/cstore_impl.rs b/src/librustc_metadata/rmeta/decoder/cstore_impl.rs
index be153758a2a..9160327c1d1 100644
--- a/src/librustc_metadata/rmeta/decoder/cstore_impl.rs
+++ b/src/librustc_metadata/rmeta/decoder/cstore_impl.rs
@@ -113,6 +113,7 @@ provide! { <'tcx> tcx, def_id, other, cdata,
     }
     optimized_mir => { tcx.arena.alloc(cdata.get_optimized_mir(tcx, def_id.index)) }
     promoted_mir => { tcx.arena.alloc(cdata.get_promoted_mir(tcx, def_id.index)) }
+    unused_generic_params => { cdata.get_unused_generic_params(def_id.index) }
     mir_const_qualif => { cdata.mir_const_qualif(def_id.index) }
     fn_sig => { cdata.fn_sig(def_id.index, tcx) }
     inherent_impls => { cdata.get_inherent_implementations_for_type(tcx, def_id.index) }
diff --git a/src/librustc_metadata/rmeta/encoder.rs b/src/librustc_metadata/rmeta/encoder.rs
index a8c46d3e32e..186828b6a19 100644
--- a/src/librustc_metadata/rmeta/encoder.rs
+++ b/src/librustc_metadata/rmeta/encoder.rs
@@ -1065,6 +1065,8 @@ impl EncodeContext<'tcx> {
         debug!("EntryBuilder::encode_mir({:?})", def_id);
         if self.tcx.mir_keys(LOCAL_CRATE).contains(&def_id) {
             record!(self.tables.mir[def_id.to_def_id()] <- self.tcx.optimized_mir(def_id));
+            record!(self.tables.unused_generic_params[def_id.to_def_id()] <-
+                    self.tcx.unused_generic_params(def_id));
         }
     }
 
diff --git a/src/librustc_metadata/rmeta/mod.rs b/src/librustc_metadata/rmeta/mod.rs
index 8abc3784d6d..e616e8cf00a 100644
--- a/src/librustc_metadata/rmeta/mod.rs
+++ b/src/librustc_metadata/rmeta/mod.rs
@@ -9,7 +9,7 @@ use rustc_hir as hir;
 use rustc_hir::def::CtorKind;
 use rustc_hir::def_id::{DefId, DefIndex};
 use rustc_hir::lang_items;
-use rustc_index::vec::IndexVec;
+use rustc_index::{bit_set::FiniteBitSet, vec::IndexVec};
 use rustc_middle::hir::exports::Export;
 use rustc_middle::middle::cstore::{DepKind, ForeignModule, LinkagePreference, NativeLib};
 use rustc_middle::middle::exported_symbols::{ExportedSymbol, SymbolExportLevel};
@@ -277,6 +277,7 @@ define_tables! {
     super_predicates: Table<DefIndex, Lazy!(ty::GenericPredicates<'tcx>)>,
     mir: Table<DefIndex, Lazy!(mir::Body<'tcx>)>,
     promoted_mir: Table<DefIndex, Lazy!(IndexVec<mir::Promoted, mir::Body<'tcx>>)>,
+    unused_generic_params: Table<DefIndex, Lazy<FiniteBitSet<u64>>>,
 }
 
 #[derive(Copy, Clone, RustcEncodable, RustcDecodable)]
diff --git a/src/librustc_middle/mir/mono.rs b/src/librustc_middle/mir/mono.rs
index 1ad5008d28a..bb204223b60 100644
--- a/src/librustc_middle/mir/mono.rs
+++ b/src/librustc_middle/mir/mono.rs
@@ -168,7 +168,7 @@ impl<'tcx> MonoItem<'tcx> {
             MonoItem::GlobalAsm(..) => return true,
         };
 
-        tcx.substitute_normalize_and_test_predicates((def_id, &substs))
+        !tcx.subst_and_check_impossible_predicates((def_id, &substs))
     }
 
     pub fn to_string(&self, tcx: TyCtxt<'tcx>, debug: bool) -> String {
diff --git a/src/librustc_middle/query/mod.rs b/src/librustc_middle/query/mod.rs
index f479a030d63..f857af28622 100644
--- a/src/librustc_middle/query/mod.rs
+++ b/src/librustc_middle/query/mod.rs
@@ -1313,6 +1313,13 @@ rustc_queries! {
         query codegen_unit(_: Symbol) -> &'tcx CodegenUnit<'tcx> {
             desc { "codegen_unit" }
         }
+        query unused_generic_params(key: DefId) -> FiniteBitSet<u64> {
+            cache_on_disk_if { key.is_local() }
+            desc {
+                |tcx| "determining which generic parameters are unused by `{}`",
+                    tcx.def_path_str(key)
+            }
+        }
         query backend_optimization_level(_: CrateNum) -> OptLevel {
             desc { "optimization level used by backend" }
         }
@@ -1465,9 +1472,9 @@ rustc_queries! {
             desc { "normalizing `{:?}`", goal }
         }
 
-        query substitute_normalize_and_test_predicates(key: (DefId, SubstsRef<'tcx>)) -> bool {
+        query subst_and_check_impossible_predicates(key: (DefId, SubstsRef<'tcx>)) -> bool {
             desc { |tcx|
-                "testing substituted normalized predicates:`{}`",
+                "impossible substituted predicates:`{}`",
                 tcx.def_path_str(key.0)
             }
         }
diff --git a/src/librustc_middle/ty/flags.rs b/src/librustc_middle/ty/flags.rs
index 0e86fcf53b2..11a8bedb660 100644
--- a/src/librustc_middle/ty/flags.rs
+++ b/src/librustc_middle/ty/flags.rs
@@ -85,7 +85,19 @@ impl FlagComputation {
             }
 
             &ty::Generator(_, ref substs, _) => {
-                self.add_substs(substs);
+                let substs = substs.as_generator();
+                let should_remove_further_specializable =
+                    !self.flags.contains(TypeFlags::STILL_FURTHER_SPECIALIZABLE);
+                self.add_substs(substs.parent_substs());
+                if should_remove_further_specializable {
+                    self.flags -= TypeFlags::STILL_FURTHER_SPECIALIZABLE;
+                }
+
+                self.add_ty(substs.resume_ty());
+                self.add_ty(substs.return_ty());
+                self.add_ty(substs.witness());
+                self.add_ty(substs.yield_ty());
+                self.add_ty(substs.tupled_upvars_ty());
             }
 
             &ty::GeneratorWitness(ts) => {
@@ -95,7 +107,17 @@ impl FlagComputation {
             }
 
             &ty::Closure(_, substs) => {
-                self.add_substs(substs);
+                let substs = substs.as_closure();
+                let should_remove_further_specializable =
+                    !self.flags.contains(TypeFlags::STILL_FURTHER_SPECIALIZABLE);
+                self.add_substs(substs.parent_substs());
+                if should_remove_further_specializable {
+                    self.flags -= TypeFlags::STILL_FURTHER_SPECIALIZABLE;
+                }
+
+                self.add_ty(substs.sig_as_fn_ptr_ty());
+                self.add_ty(substs.kind_ty());
+                self.add_ty(substs.tupled_upvars_ty());
             }
 
             &ty::Bound(debruijn, _) => {
diff --git a/src/librustc_middle/ty/instance.rs b/src/librustc_middle/ty/instance.rs
index f627d05d3e9..cdb883da32b 100644
--- a/src/librustc_middle/ty/instance.rs
+++ b/src/librustc_middle/ty/instance.rs
@@ -1,5 +1,6 @@
 use crate::middle::codegen_fn_attrs::CodegenFnAttrFlags;
 use crate::ty::print::{FmtPrinter, Printer};
+use crate::ty::subst::InternalSubsts;
 use crate::ty::{self, SubstsRef, Ty, TyCtxt, TypeFoldable};
 use rustc_errors::ErrorReported;
 use rustc_hir::def::Namespace;
@@ -106,32 +107,9 @@ pub enum InstanceDef<'tcx> {
 }
 
 impl<'tcx> Instance<'tcx> {
-    /// Returns the `Ty` corresponding to this `Instance`,
-    /// with generic substitutions applied and lifetimes erased.
-    ///
-    /// This method can only be called when the 'substs' for this Instance
-    /// are fully monomorphic (no `ty::Param`'s are present).
-    /// This is usually the case (e.g. during codegen).
-    /// However, during constant evaluation, we may want
-    /// to try to resolve a `Instance` using generic parameters
-    /// (e.g. when we are attempting to to do const-propagation).
-    /// In this case, `Instance.ty_env` should be used to provide
-    /// the `ParamEnv` for our generic context.
-    pub fn monomorphic_ty(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
-        let ty = tcx.type_of(self.def.def_id());
-        // There shouldn't be any params - if there are, then
-        // Instance.ty_env should have been used to provide the proper
-        // ParamEnv
-        if self.substs.has_param_types_or_consts() {
-            bug!("Instance.ty called for type {:?} with params in substs: {:?}", ty, self.substs);
-        }
-        tcx.subst_and_normalize_erasing_regions(self.substs, ty::ParamEnv::reveal_all(), &ty)
-    }
-
-    /// Like `Instance.ty`, but allows a `ParamEnv` to be specified for use during
-    /// normalization. This method is only really useful during constant evaluation,
-    /// where we are dealing with potentially generic types.
-    pub fn ty_env(&self, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> Ty<'tcx> {
+    /// Returns the `Ty` corresponding to this `Instance`, with generic substitutions applied and
+    /// lifetimes erased, allowing a `ParamEnv` to be specified for use during normalization.
+    pub fn ty(&self, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> Ty<'tcx> {
         let ty = tcx.type_of(self.def.def_id());
         tcx.subst_and_normalize_erasing_regions(self.substs, param_env, &ty)
     }
@@ -486,6 +464,42 @@ impl<'tcx> Instance<'tcx> {
             | InstanceDef::VtableShim(..) => Some(self.substs),
         }
     }
+
+    /// Returns a new `Instance` where generic parameters in `instance.substs` are replaced by
+    /// identify parameters if they are determined to be unused in `instance.def`.
+    pub fn polymorphize(self, tcx: TyCtxt<'tcx>) -> Self {
+        debug!("polymorphize: running polymorphization analysis");
+        if !tcx.sess.opts.debugging_opts.polymorphize {
+            return self;
+        }
+
+        if let InstanceDef::Item(def) = self.def {
+            let unused = tcx.unused_generic_params(def.did);
+
+            if unused.is_empty() {
+                // Exit early if every parameter was used.
+                return self;
+            }
+
+            debug!("polymorphize: unused={:?}", unused);
+            let polymorphized_substs =
+                InternalSubsts::for_item(tcx, def.did, |param, _| match param.kind {
+                // If parameter is a const or type parameter..
+                ty::GenericParamDefKind::Const | ty::GenericParamDefKind::Type { .. } if
+                    // ..and is within range and unused..
+                    unused.contains(param.index).unwrap_or(false) =>
+                        // ..then use the identity for this parameter.
+                        tcx.mk_param_from_def(param),
+                // Otherwise, use the parameter as before.
+                _ => self.substs[param.index as usize],
+            });
+
+            debug!("polymorphize: self={:?} polymorphized_substs={:?}", self, polymorphized_substs);
+            Self { def: self.def, substs: polymorphized_substs }
+        } else {
+            self
+        }
+    }
 }
 
 fn needs_fn_once_adapter_shim(
diff --git a/src/librustc_middle/ty/layout.rs b/src/librustc_middle/ty/layout.rs
index 8ae9269a6bf..cb937bf0112 100644
--- a/src/librustc_middle/ty/layout.rs
+++ b/src/librustc_middle/ty/layout.rs
@@ -2299,12 +2299,22 @@ impl<'tcx> ty::Instance<'tcx> {
     // or should go through `FnAbi` instead, to avoid losing any
     // adjustments `FnAbi::of_instance` might be performing.
     fn fn_sig_for_fn_abi(&self, tcx: TyCtxt<'tcx>) -> ty::PolyFnSig<'tcx> {
-        let ty = self.monomorphic_ty(tcx);
+        // FIXME(davidtwco,eddyb): A `ParamEnv` should be passed through to this function.
+        let ty = self.ty(tcx, ty::ParamEnv::reveal_all());
         match ty.kind {
-            ty::FnDef(..) |
-            // Shims currently have type FnPtr. Not sure this should remain.
-            ty::FnPtr(_) => {
-                let mut sig = ty.fn_sig(tcx);
+            ty::FnDef(..) => {
+                // HACK(davidtwco,eddyb): This is a workaround for polymorphization considering
+                // parameters unused if they show up in the signature, but not in the `mir::Body`
+                // (i.e. due to being inside a projection that got normalized, see
+                // `src/test/ui/polymorphization/normalized_sig_types.rs`), and codegen not keeping
+                // track of a polymorphization `ParamEnv` to allow normalizing later.
+                let mut sig = match ty.kind {
+                    ty::FnDef(def_id, substs) => tcx
+                        .normalize_erasing_regions(tcx.param_env(def_id), tcx.fn_sig(def_id))
+                        .subst(tcx, substs),
+                    _ => unreachable!(),
+                };
+
                 if let ty::InstanceDef::VtableShim(..) = self.def {
                     // Modify `fn(self, ...)` to `fn(self: *mut Self, ...)`.
                     sig = sig.map_bound(|mut sig| {
@@ -2320,13 +2330,15 @@ impl<'tcx> ty::Instance<'tcx> {
                 let sig = substs.as_closure().sig();
 
                 let env_ty = tcx.closure_env_ty(def_id, substs).unwrap();
-                sig.map_bound(|sig| tcx.mk_fn_sig(
-                    iter::once(env_ty.skip_binder()).chain(sig.inputs().iter().cloned()),
-                    sig.output(),
-                    sig.c_variadic,
-                    sig.unsafety,
-                    sig.abi
-                ))
+                sig.map_bound(|sig| {
+                    tcx.mk_fn_sig(
+                        iter::once(env_ty.skip_binder()).chain(sig.inputs().iter().cloned()),
+                        sig.output(),
+                        sig.c_variadic,
+                        sig.unsafety,
+                        sig.abi,
+                    )
+                })
             }
             ty::Generator(_, substs, _) => {
                 let sig = substs.as_generator().poly_sig();
@@ -2342,10 +2354,8 @@ impl<'tcx> ty::Instance<'tcx> {
                 sig.map_bound(|sig| {
                     let state_did = tcx.require_lang_item(GeneratorStateLangItem, None);
                     let state_adt_ref = tcx.adt_def(state_did);
-                    let state_substs = tcx.intern_substs(&[
-                        sig.yield_ty.into(),
-                        sig.return_ty.into(),
-                    ]);
+                    let state_substs =
+                        tcx.intern_substs(&[sig.yield_ty.into(), sig.return_ty.into()]);
                     let ret_ty = tcx.mk_adt(state_adt_ref, state_substs);
 
                     tcx.mk_fn_sig(
@@ -2353,11 +2363,11 @@ impl<'tcx> ty::Instance<'tcx> {
                         &ret_ty,
                         false,
                         hir::Unsafety::Normal,
-                        rustc_target::spec::abi::Abi::Rust
+                        rustc_target::spec::abi::Abi::Rust,
                     )
                 })
             }
-            _ => bug!("unexpected type {:?} in Instance::fn_sig", ty)
+            _ => bug!("unexpected type {:?} in Instance::fn_sig", ty),
         }
     }
 }
diff --git a/src/librustc_middle/ty/mod.rs b/src/librustc_middle/ty/mod.rs
index 21745977b04..51a353c0132 100644
--- a/src/librustc_middle/ty/mod.rs
+++ b/src/librustc_middle/ty/mod.rs
@@ -890,6 +890,7 @@ impl<'tcx> Generics {
         false
     }
 
+    /// Returns the `GenericParamDef` with the given index.
     pub fn param_at(&'tcx self, param_index: usize, tcx: TyCtxt<'tcx>) -> &'tcx GenericParamDef {
         if let Some(index) = param_index.checked_sub(self.parent_count) {
             &self.params[index]
@@ -899,6 +900,7 @@ impl<'tcx> Generics {
         }
     }
 
+    /// Returns the `GenericParamDef` associated with this `EarlyBoundRegion`.
     pub fn region_param(
         &'tcx self,
         param: &EarlyBoundRegion,
@@ -920,7 +922,7 @@ impl<'tcx> Generics {
         }
     }
 
-    /// Returns the `ConstParameterDef` associated with this `ParamConst`.
+    /// Returns the `GenericParamDef` associated with this `ParamConst`.
     pub fn const_param(&'tcx self, param: &ParamConst, tcx: TyCtxt<'tcx>) -> &GenericParamDef {
         let param = self.param_at(param.index as usize, tcx);
         match param.kind {
diff --git a/src/librustc_middle/ty/normalize_erasing_regions.rs b/src/librustc_middle/ty/normalize_erasing_regions.rs
index 2f0a57c59eb..48a62b64604 100644
--- a/src/librustc_middle/ty/normalize_erasing_regions.rs
+++ b/src/librustc_middle/ty/normalize_erasing_regions.rs
@@ -54,7 +54,6 @@ impl<'tcx> TyCtxt<'tcx> {
     where
         T: TypeFoldable<'tcx>,
     {
-        assert!(!value.needs_subst());
         let value = self.erase_late_bound_regions(value);
         self.normalize_erasing_regions(param_env, value)
     }
diff --git a/src/librustc_middle/ty/print/obsolete.rs b/src/librustc_middle/ty/print/obsolete.rs
index 67b6433b611..2ea7cd2a6dc 100644
--- a/src/librustc_middle/ty/print/obsolete.rs
+++ b/src/librustc_middle/ty/print/obsolete.rs
@@ -144,12 +144,14 @@ impl DefPathBasedNames<'tcx> {
                 let substs = substs.truncate_to(self.tcx, generics);
                 self.push_generic_params(substs, iter::empty(), output, debug);
             }
+            ty::Param(_) => {
+                output.push_str(&t.to_string());
+            }
             ty::Error(_)
             | ty::Bound(..)
             | ty::Infer(_)
             | ty::Placeholder(..)
             | ty::Projection(..)
-            | ty::Param(_)
             | ty::GeneratorWitness(_)
             | ty::Opaque(..) => {
                 if debug {
diff --git a/src/librustc_middle/ty/query/mod.rs b/src/librustc_middle/ty/query/mod.rs
index 2ad49b1acce..2f7a9aee536 100644
--- a/src/librustc_middle/ty/query/mod.rs
+++ b/src/librustc_middle/ty/query/mod.rs
@@ -44,7 +44,7 @@ use rustc_hir::def::DefKind;
 use rustc_hir::def_id::{CrateNum, DefId, DefIdMap, DefIdSet, LocalDefId};
 use rustc_hir::lang_items::{LangItem, LanguageItems};
 use rustc_hir::{Crate, HirIdSet, ItemLocalId, TraitCandidate};
-use rustc_index::vec::IndexVec;
+use rustc_index::{bit_set::FiniteBitSet, vec::IndexVec};
 use rustc_session::config::{EntryFnType, OptLevel, OutputFilenames, SymbolManglingVersion};
 use rustc_session::utils::NativeLibKind;
 use rustc_session::CrateDisambiguator;
diff --git a/src/librustc_middle/ty/sty.rs b/src/librustc_middle/ty/sty.rs
index 2f17db62233..03bf51c95c5 100644
--- a/src/librustc_middle/ty/sty.rs
+++ b/src/librustc_middle/ty/sty.rs
@@ -318,6 +318,7 @@ pub struct ClosureSubsts<'tcx> {
 /// Struct returned by `split()`. Note that these are subslices of the
 /// parent slice and not canonical substs themselves.
 struct SplitClosureSubsts<'tcx> {
+    parent: &'tcx [GenericArg<'tcx>],
     closure_kind_ty: GenericArg<'tcx>,
     closure_sig_as_fn_ptr_ty: GenericArg<'tcx>,
     tupled_upvars_ty: GenericArg<'tcx>,
@@ -329,8 +330,13 @@ impl<'tcx> ClosureSubsts<'tcx> {
     /// ordering.
     fn split(self) -> SplitClosureSubsts<'tcx> {
         match self.substs[..] {
-            [.., closure_kind_ty, closure_sig_as_fn_ptr_ty, tupled_upvars_ty] => {
-                SplitClosureSubsts { closure_kind_ty, closure_sig_as_fn_ptr_ty, tupled_upvars_ty }
+            [ref parent @ .., closure_kind_ty, closure_sig_as_fn_ptr_ty, tupled_upvars_ty] => {
+                SplitClosureSubsts {
+                    parent,
+                    closure_kind_ty,
+                    closure_sig_as_fn_ptr_ty,
+                    tupled_upvars_ty,
+                }
             }
             _ => bug!("closure substs missing synthetics"),
         }
@@ -345,9 +351,20 @@ impl<'tcx> ClosureSubsts<'tcx> {
         self.substs.len() >= 3 && matches!(self.split().tupled_upvars_ty.expect_ty().kind, Tuple(_))
     }
 
+    /// Returns the substitutions of the closure's parent.
+    pub fn parent_substs(self) -> &'tcx [GenericArg<'tcx>] {
+        self.split().parent
+    }
+
     #[inline]
     pub fn upvar_tys(self) -> impl Iterator<Item = Ty<'tcx>> + 'tcx {
-        self.split().tupled_upvars_ty.expect_ty().tuple_fields()
+        self.tupled_upvars_ty().tuple_fields()
+    }
+
+    /// Returns the tuple type representing the upvars for this closure.
+    #[inline]
+    pub fn tupled_upvars_ty(self) -> Ty<'tcx> {
+        self.split().tupled_upvars_ty.expect_ty()
     }
 
     /// Returns the closure kind for this closure; may return a type
@@ -392,6 +409,7 @@ pub struct GeneratorSubsts<'tcx> {
 }
 
 struct SplitGeneratorSubsts<'tcx> {
+    parent: &'tcx [GenericArg<'tcx>],
     resume_ty: GenericArg<'tcx>,
     yield_ty: GenericArg<'tcx>,
     return_ty: GenericArg<'tcx>,
@@ -402,8 +420,15 @@ struct SplitGeneratorSubsts<'tcx> {
 impl<'tcx> GeneratorSubsts<'tcx> {
     fn split(self) -> SplitGeneratorSubsts<'tcx> {
         match self.substs[..] {
-            [.., resume_ty, yield_ty, return_ty, witness, tupled_upvars_ty] => {
-                SplitGeneratorSubsts { resume_ty, yield_ty, return_ty, witness, tupled_upvars_ty }
+            [ref parent @ .., resume_ty, yield_ty, return_ty, witness, tupled_upvars_ty] => {
+                SplitGeneratorSubsts {
+                    parent,
+                    resume_ty,
+                    yield_ty,
+                    return_ty,
+                    witness,
+                    tupled_upvars_ty,
+                }
             }
             _ => bug!("generator substs missing synthetics"),
         }
@@ -418,6 +443,11 @@ impl<'tcx> GeneratorSubsts<'tcx> {
         self.substs.len() >= 5 && matches!(self.split().tupled_upvars_ty.expect_ty().kind, Tuple(_))
     }
 
+    /// Returns the substitutions of the generator's parent.
+    pub fn parent_substs(self) -> &'tcx [GenericArg<'tcx>] {
+        self.split().parent
+    }
+
     /// This describes the types that can be contained in a generator.
     /// It will be a type variable initially and unified in the last stages of typeck of a body.
     /// It contains a tuple of all the types that could end up on a generator frame.
@@ -429,7 +459,13 @@ impl<'tcx> GeneratorSubsts<'tcx> {
 
     #[inline]
     pub fn upvar_tys(self) -> impl Iterator<Item = Ty<'tcx>> + 'tcx {
-        self.split().tupled_upvars_ty.expect_ty().tuple_fields()
+        self.tupled_upvars_ty().tuple_fields()
+    }
+
+    /// Returns the tuple type representing the upvars for this generator.
+    #[inline]
+    pub fn tupled_upvars_ty(self) -> Ty<'tcx> {
+        self.split().tupled_upvars_ty.expect_ty()
     }
 
     /// Returns the type representing the resume type of the generator.
diff --git a/src/librustc_mir/const_eval/eval_queries.rs b/src/librustc_mir/const_eval/eval_queries.rs
index dc3e01f3d15..705a1b2ae79 100644
--- a/src/librustc_mir/const_eval/eval_queries.rs
+++ b/src/librustc_mir/const_eval/eval_queries.rs
@@ -240,7 +240,7 @@ pub fn const_eval_validated_provider<'tcx>(
     // We call `const_eval` for zero arg intrinsics, too, in order to cache their value.
     // Catch such calls and evaluate them instead of trying to load a constant's MIR.
     if let ty::InstanceDef::Intrinsic(def_id) = key.value.instance.def {
-        let ty = key.value.instance.ty_env(tcx, key.param_env);
+        let ty = key.value.instance.ty(tcx, key.param_env);
         let substs = match ty.kind {
             ty::FnDef(_, substs) => substs,
             _ => bug!("intrinsic with type {:?}", ty),
diff --git a/src/librustc_mir/interpret/terminator.rs b/src/librustc_mir/interpret/terminator.rs
index 4681079a22d..663f61b1155 100644
--- a/src/librustc_mir/interpret/terminator.rs
+++ b/src/librustc_mir/interpret/terminator.rs
@@ -221,7 +221,7 @@ impl<'mir, 'tcx: 'mir, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> {
         // ABI check
         {
             let callee_abi = {
-                let instance_ty = instance.ty_env(*self.tcx, self.param_env);
+                let instance_ty = instance.ty(*self.tcx, self.param_env);
                 match instance_ty.kind {
                     ty::FnDef(..) => instance_ty.fn_sig(*self.tcx).abi(),
                     ty::Closure(..) => Abi::RustCall,
diff --git a/src/librustc_mir/interpret/traits.rs b/src/librustc_mir/interpret/traits.rs
index a1d124bb760..49a80ca1345 100644
--- a/src/librustc_mir/interpret/traits.rs
+++ b/src/librustc_mir/interpret/traits.rs
@@ -142,7 +142,7 @@ impl<'mir, 'tcx: 'mir, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> {
         // to determine the type.
         let drop_instance = self.memory.get_fn(drop_fn)?.as_instance()?;
         trace!("Found drop fn: {:?}", drop_instance);
-        let fn_sig = drop_instance.ty_env(*self.tcx, self.param_env).fn_sig(*self.tcx);
+        let fn_sig = drop_instance.ty(*self.tcx, self.param_env).fn_sig(*self.tcx);
         let fn_sig = self.tcx.normalize_erasing_late_bound_regions(self.param_env, &fn_sig);
         // The drop function takes `*mut T` where `T` is the type being dropped, so get that.
         let args = fn_sig.inputs();
diff --git a/src/librustc_mir/lib.rs b/src/librustc_mir/lib.rs
index cd6c38997f1..4e7142a93ae 100644
--- a/src/librustc_mir/lib.rs
+++ b/src/librustc_mir/lib.rs
@@ -51,6 +51,7 @@ pub fn provide(providers: &mut Providers) {
     shim::provide(providers);
     transform::provide(providers);
     monomorphize::partitioning::provide(providers);
+    monomorphize::polymorphize::provide(providers);
     providers.const_eval_validated = const_eval::const_eval_validated_provider;
     providers.const_eval_raw = const_eval::const_eval_raw_provider;
     providers.const_caller_location = const_eval::const_caller_location;
diff --git a/src/librustc_mir/monomorphize/collector.rs b/src/librustc_mir/monomorphize/collector.rs
index 35fb950ce66..0b5f27fc17a 100644
--- a/src/librustc_mir/monomorphize/collector.rs
+++ b/src/librustc_mir/monomorphize/collector.rs
@@ -358,9 +358,9 @@ fn collect_items_rec<'tcx>(
             let instance = Instance::mono(tcx, def_id);
 
             // Sanity check whether this ended up being collected accidentally
-            debug_assert!(should_monomorphize_locally(tcx, &instance));
+            debug_assert!(should_codegen_locally(tcx, &instance));
 
-            let ty = instance.monomorphic_ty(tcx);
+            let ty = instance.ty(tcx, ty::ParamEnv::reveal_all());
             visit_drop_use(tcx, ty, true, starting_point.span, &mut neighbors);
 
             recursion_depth_reset = None;
@@ -371,7 +371,7 @@ fn collect_items_rec<'tcx>(
         }
         MonoItem::Fn(instance) => {
             // Sanity check whether this ended up being collected accidentally
-            debug_assert!(should_monomorphize_locally(tcx, &instance));
+            debug_assert!(should_codegen_locally(tcx, &instance));
 
             // Keep track of the monomorphization recursion depth
             recursion_depth_reset =
@@ -584,8 +584,8 @@ impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> {
                             substs,
                             ty::ClosureKind::FnOnce,
                         );
-                        if should_monomorphize_locally(self.tcx, &instance) {
-                            self.output.push(create_fn_mono_item(instance, span));
+                        if should_codegen_locally(self.tcx, &instance) {
+                            self.output.push(create_fn_mono_item(self.tcx, instance, span));
                         }
                     }
                     _ => bug!(),
@@ -596,14 +596,14 @@ impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> {
                 let exchange_malloc_fn_def_id =
                     tcx.require_lang_item(ExchangeMallocFnLangItem, None);
                 let instance = Instance::mono(tcx, exchange_malloc_fn_def_id);
-                if should_monomorphize_locally(tcx, &instance) {
-                    self.output.push(create_fn_mono_item(instance, span));
+                if should_codegen_locally(tcx, &instance) {
+                    self.output.push(create_fn_mono_item(self.tcx, instance, span));
                 }
             }
             mir::Rvalue::ThreadLocalRef(def_id) => {
                 assert!(self.tcx.is_thread_local_static(def_id));
                 let instance = Instance::mono(self.tcx, def_id);
-                if should_monomorphize_locally(self.tcx, &instance) {
+                if should_codegen_locally(self.tcx, &instance) {
                     trace!("collecting thread-local static {:?}", def_id);
                     self.output.push(respan(span, MonoItem::Static(def_id)));
                 }
@@ -664,7 +664,7 @@ impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> {
                         }
                         mir::InlineAsmOperand::SymStatic { def_id } => {
                             let instance = Instance::mono(self.tcx, def_id);
-                            if should_monomorphize_locally(self.tcx, &instance) {
+                            if should_codegen_locally(self.tcx, &instance) {
                                 trace!("collecting asm sym static {:?}", def_id);
                                 self.output.push(respan(source, MonoItem::Static(def_id)));
                             }
@@ -735,7 +735,7 @@ fn visit_instance_use<'tcx>(
     output: &mut Vec<Spanned<MonoItem<'tcx>>>,
 ) {
     debug!("visit_item_use({:?}, is_direct_call={:?})", instance, is_direct_call);
-    if !should_monomorphize_locally(tcx, &instance) {
+    if !should_codegen_locally(tcx, &instance) {
         return;
     }
 
@@ -748,7 +748,7 @@ fn visit_instance_use<'tcx>(
         ty::InstanceDef::DropGlue(_, None) => {
             // Don't need to emit noop drop glue if we are calling directly.
             if !is_direct_call {
-                output.push(create_fn_mono_item(instance, source));
+                output.push(create_fn_mono_item(tcx, instance, source));
             }
         }
         ty::InstanceDef::DropGlue(_, Some(_))
@@ -758,7 +758,7 @@ fn visit_instance_use<'tcx>(
         | ty::InstanceDef::Item(..)
         | ty::InstanceDef::FnPtrShim(..)
         | ty::InstanceDef::CloneShim(..) => {
-            output.push(create_fn_mono_item(instance, source));
+            output.push(create_fn_mono_item(tcx, instance, source));
         }
     }
 }
@@ -766,7 +766,7 @@ fn visit_instance_use<'tcx>(
 // Returns `true` if we should codegen an instance in the local crate.
 // Returns `false` if we can just link to the upstream crate and therefore don't
 // need a mono item.
-fn should_monomorphize_locally<'tcx>(tcx: TyCtxt<'tcx>, instance: &Instance<'tcx>) -> bool {
+fn should_codegen_locally<'tcx>(tcx: TyCtxt<'tcx>, instance: &Instance<'tcx>) -> bool {
     let def_id = match instance.def {
         ty::InstanceDef::Item(def) => def.did,
         ty::InstanceDef::DropGlue(def_id, Some(_)) => def_id,
@@ -781,20 +781,19 @@ fn should_monomorphize_locally<'tcx>(tcx: TyCtxt<'tcx>, instance: &Instance<'tcx
     };
 
     if tcx.is_foreign_item(def_id) {
-        // Foreign items are always linked against, there's no way of
-        // instantiating them.
+        // Foreign items are always linked against, there's no way of instantiating them.
         return false;
     }
 
     if def_id.is_local() {
-        // Local items cannot be referred to locally without
-        // monomorphizing them locally.
+        // Local items cannot be referred to locally without monomorphizing them locally.
         return true;
     }
 
-    if tcx.is_reachable_non_generic(def_id) || instance.upstream_monomorphization(tcx).is_some() {
-        // We can link to the item in question, no instance needed
-        // in this crate.
+    if tcx.is_reachable_non_generic(def_id)
+        || instance.polymorphize(tcx).upstream_monomorphization(tcx).is_some()
+    {
+        // We can link to the item in question, no instance needed in this crate.
         return false;
     }
 
@@ -903,9 +902,13 @@ fn find_vtable_types_for_unsizing<'tcx>(
     }
 }
 
-fn create_fn_mono_item(instance: Instance<'_>, source: Span) -> Spanned<MonoItem<'_>> {
+fn create_fn_mono_item<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    instance: Instance<'tcx>,
+    source: Span,
+) -> Spanned<MonoItem<'tcx>> {
     debug!("create_fn_mono_item(instance={})", instance);
-    respan(source, MonoItem::Fn(instance))
+    respan(source, MonoItem::Fn(instance.polymorphize(tcx)))
 }
 
 /// Creates a `MonoItem` for each method that is referenced by the vtable for
@@ -917,12 +920,7 @@ fn create_mono_items_for_vtable_methods<'tcx>(
     source: Span,
     output: &mut Vec<Spanned<MonoItem<'tcx>>>,
 ) {
-    assert!(
-        !trait_ty.needs_subst()
-            && !trait_ty.has_escaping_bound_vars()
-            && !impl_ty.needs_subst()
-            && !impl_ty.has_escaping_bound_vars()
-    );
+    assert!(!trait_ty.has_escaping_bound_vars() && !impl_ty.has_escaping_bound_vars());
 
     if let ty::Dynamic(ref trait_ty, ..) = trait_ty.kind {
         if let Some(principal) = trait_ty.principal() {
@@ -944,8 +942,8 @@ fn create_mono_items_for_vtable_methods<'tcx>(
                     )
                     .unwrap()
                 })
-                .filter(|&instance| should_monomorphize_locally(tcx, &instance))
-                .map(|item| create_fn_mono_item(item, source));
+                .filter(|&instance| should_codegen_locally(tcx, &instance))
+                .map(|item| create_fn_mono_item(tcx, item, source));
             output.extend(methods);
         }
 
@@ -997,7 +995,7 @@ impl ItemLikeVisitor<'v> for RootCollector<'_, 'v> {
                         );
 
                         let ty = Instance::new(def_id.to_def_id(), InternalSubsts::empty())
-                            .monomorphic_ty(self.tcx);
+                            .ty(self.tcx, ty::ParamEnv::reveal_all());
                         visit_drop_use(self.tcx, ty, true, DUMMY_SP, self.output);
                     }
                 }
@@ -1069,7 +1067,7 @@ impl RootCollector<'_, 'v> {
             debug!("RootCollector::push_if_root: found root def_id={:?}", def_id);
 
             let instance = Instance::mono(self.tcx, def_id.to_def_id());
-            self.output.push(create_fn_mono_item(instance, DUMMY_SP));
+            self.output.push(create_fn_mono_item(self.tcx, instance, DUMMY_SP));
         }
     }
 
@@ -1106,7 +1104,7 @@ impl RootCollector<'_, 'v> {
         .unwrap()
         .unwrap();
 
-        self.output.push(create_fn_mono_item(start_instance, DUMMY_SP));
+        self.output.push(create_fn_mono_item(self.tcx, start_instance, DUMMY_SP));
     }
 }
 
@@ -1163,9 +1161,8 @@ fn create_mono_items_for_default_impls<'tcx>(
                         .unwrap()
                         .unwrap();
 
-                    let mono_item = create_fn_mono_item(instance, DUMMY_SP);
-                    if mono_item.node.is_instantiable(tcx)
-                        && should_monomorphize_locally(tcx, &instance)
+                    let mono_item = create_fn_mono_item(tcx, instance, DUMMY_SP);
+                    if mono_item.node.is_instantiable(tcx) && should_codegen_locally(tcx, &instance)
                     {
                         output.push(mono_item);
                     }
@@ -1186,7 +1183,7 @@ fn collect_miri<'tcx>(
         GlobalAlloc::Static(def_id) => {
             assert!(!tcx.is_thread_local_static(def_id));
             let instance = Instance::mono(tcx, def_id);
-            if should_monomorphize_locally(tcx, &instance) {
+            if should_codegen_locally(tcx, &instance) {
                 trace!("collecting static {:?}", def_id);
                 output.push(dummy_spanned(MonoItem::Static(def_id)));
             }
@@ -1200,9 +1197,9 @@ fn collect_miri<'tcx>(
             }
         }
         GlobalAlloc::Function(fn_instance) => {
-            if should_monomorphize_locally(tcx, &fn_instance) {
+            if should_codegen_locally(tcx, &fn_instance) {
                 trace!("collecting {:?} with {:#?}", alloc_id, fn_instance);
-                output.push(create_fn_mono_item(fn_instance, DUMMY_SP));
+                output.push(create_fn_mono_item(tcx, fn_instance, DUMMY_SP));
             }
         }
     }
diff --git a/src/librustc_mir/monomorphize/mod.rs b/src/librustc_mir/monomorphize/mod.rs
index 76c1c465a8b..15d7b111240 100644
--- a/src/librustc_mir/monomorphize/mod.rs
+++ b/src/librustc_mir/monomorphize/mod.rs
@@ -6,6 +6,7 @@ use rustc_hir::lang_items::CoerceUnsizedTraitLangItem;
 
 pub mod collector;
 pub mod partitioning;
+pub mod polymorphize;
 
 pub fn custom_coerce_unsize_info<'tcx>(
     tcx: TyCtxt<'tcx>,
diff --git a/src/librustc_mir/monomorphize/polymorphize.rs b/src/librustc_mir/monomorphize/polymorphize.rs
new file mode 100644
index 00000000000..071b9bb9711
--- /dev/null
+++ b/src/librustc_mir/monomorphize/polymorphize.rs
@@ -0,0 +1,285 @@
+//! 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};
+use rustc_index::bit_set::FiniteBitSet;
+use rustc_middle::mir::{
+    visit::{TyContext, Visitor},
+    Local, LocalDecl, Location,
+};
+use rustc_middle::ty::{
+    self,
+    fold::{TypeFoldable, TypeVisitor},
+    query::Providers,
+    Const, Ty, TyCtxt,
+};
+use rustc_span::symbol::sym;
+use std::convert::TryInto;
+
+/// 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 function/method/closure represented by
+/// `def_id`. Returns a bitset where bits representing unused parameters are set (`is_empty`
+/// indicates all parameters are used).
+fn unused_generic_params(tcx: TyCtxt<'_>, def_id: DefId) -> FiniteBitSet<u64> {
+    debug!("unused_generic_params({:?})", def_id);
+
+    if !tcx.sess.opts.debugging_opts.polymorphize {
+        // If polymorphization disabled, then all parameters are used.
+        return FiniteBitSet::new_empty();
+    }
+
+    let generics = tcx.generics_of(def_id);
+    debug!("unused_generic_params: generics={:?}", generics);
+
+    // Exit early when there are no parameters to be unused.
+    if generics.count() == 0 {
+        return FiniteBitSet::new_empty();
+    }
+
+    // Exit early when there is no MIR available.
+    if !tcx.is_mir_available(def_id) {
+        debug!("unused_generic_params: (no mir available) def_id={:?}", def_id);
+        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::<u64>::new_empty();
+    unused_parameters.set_range(0..generics_count);
+    debug!("unused_generic_params: (start) unused_parameters={:?}", unused_parameters);
+    mark_used_by_default_parameters(tcx, def_id, generics, &mut unused_parameters);
+    debug!("unused_generic_params: (after default) unused_parameters={:?}", unused_parameters);
+
+    // Visit MIR and accumululate used generic parameters.
+    let body = tcx.optimized_mir(def_id);
+    let mut vis =
+        UsedGenericParametersVisitor { tcx, def_id, unused_parameters: &mut unused_parameters };
+    vis.visit_body(body);
+    debug!("unused_generic_params: (after visitor) unused_parameters={:?}", unused_parameters);
+
+    mark_used_by_predicates(tcx, def_id, &mut unused_parameters);
+    debug!("unused_generic_params: (end) unused_parameters={:?}", unused_parameters);
+
+    // 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
+}
+
+/// 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.
+fn mark_used_by_default_parameters<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    def_id: DefId,
+    generics: &'tcx ty::Generics,
+    unused_parameters: &mut FiniteBitSet<u64>,
+) {
+    if !tcx.is_trait(def_id) && (tcx.is_closure(def_id) || tcx.type_of(def_id).is_generator()) {
+        for param in &generics.params {
+            debug!("mark_used_by_default_parameters: (closure/gen) param={:?}", param);
+            unused_parameters.clear(param.index);
+        }
+    } else {
+        for param in &generics.params {
+            debug!("mark_used_by_default_parameters: (other) param={:?}", param);
+            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);
+    }
+}
+
+/// Search the predicates on used generic parameters for any unused generic parameters, and mark
+/// those as used.
+fn mark_used_by_predicates<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    def_id: DefId,
+    unused_parameters: &mut FiniteBitSet<u64>,
+) {
+    let def_id = tcx.closure_base_def_id(def_id);
+
+    let is_self_ty_used = |unused_parameters: &mut FiniteBitSet<u64>, self_ty: Ty<'tcx>| {
+        debug!("unused_generic_params: self_ty={:?}", self_ty);
+        if let ty::Param(param) = self_ty.kind {
+            !unused_parameters.contains(param.index).unwrap_or(false)
+        } else {
+            false
+        }
+    };
+
+    let mark_ty = |unused_parameters: &mut FiniteBitSet<u64>, ty: Ty<'tcx>| {
+        let mut vis = UsedGenericParametersVisitor { tcx, def_id, unused_parameters };
+        ty.visit_with(&mut vis);
+    };
+
+    let predicates = tcx.explicit_predicates_of(def_id);
+    debug!("mark_parameters_used_in_predicates: predicates_of={:?}", predicates);
+    for (predicate, _) in predicates.predicates {
+        match predicate.kind() {
+            ty::PredicateKind::Trait(predicate, ..) => {
+                let trait_ref = predicate.skip_binder().trait_ref;
+                if is_self_ty_used(unused_parameters, trait_ref.self_ty()) {
+                    for ty in trait_ref.substs.types() {
+                        debug!("unused_generic_params: (trait) ty={:?}", ty);
+                        mark_ty(unused_parameters, ty);
+                    }
+                }
+            }
+            ty::PredicateKind::Projection(predicate, ..) => {
+                let self_ty = predicate.skip_binder().projection_ty.self_ty();
+                if is_self_ty_used(unused_parameters, self_ty) {
+                    let ty = predicate.ty();
+                    debug!("unused_generic_params: (projection) ty={:?}", ty);
+                    mark_ty(unused_parameters, ty.skip_binder());
+                }
+            }
+            _ => (),
+        }
+    }
+}
+
+/// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic
+/// parameter which was unused.
+fn emit_unused_generic_params_error<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    def_id: DefId,
+    generics: &'tcx ty::Generics,
+    unused_parameters: &FiniteBitSet<u64>,
+) {
+    debug!("emit_unused_generic_params_error: def_id={:?}", def_id);
+    let base_def_id = tcx.closure_base_def_id(def_id);
+    if !tcx.get_attrs(base_def_id).iter().any(|a| a.check_name(sym::rustc_polymorphize_error)) {
+        return;
+    }
+
+    debug!("emit_unused_generic_params_error: unused_parameters={:?}", unused_parameters);
+    let fn_span = match tcx.opt_item_name(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!("emit_unused_generic_params_error: param={:?}", 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 UsedGenericParametersVisitor<'a, 'tcx> {
+    tcx: TyCtxt<'tcx>,
+    def_id: DefId,
+    unused_parameters: &'a mut FiniteBitSet<u64>,
+}
+
+impl<'a, 'tcx> Visitor<'tcx> for UsedGenericParametersVisitor<'a, 'tcx> {
+    fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
+        debug!("visit_local_decl: local_decl={:?}", local_decl);
+        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!("visit_local_decl: skipping closure substs");
+                return;
+            }
+        }
+
+        self.super_local_decl(local, local_decl);
+    }
+
+    fn visit_const(&mut self, c: &&'tcx 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 UsedGenericParametersVisitor<'a, 'tcx> {
+    fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> bool {
+        debug!("visit_const: c={:?}", c);
+        if !c.has_param_types_or_consts() {
+            return false;
+        }
+
+        match c.val {
+            ty::ConstKind::Param(param) => {
+                debug!("visit_const: param={:?}", param);
+                self.unused_parameters.clear(param.index);
+                false
+            }
+            _ => c.super_visit_with(self),
+        }
+    }
+
+    fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool {
+        debug!("visit_ty: ty={:?}", ty);
+        if !ty.has_param_types_or_consts() {
+            return false;
+        }
+
+        match ty.kind {
+            ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => {
+                debug!("visit_ty: def_id={:?}", def_id);
+                // Avoid cycle errors with generators.
+                if def_id == self.def_id {
+                    return false;
+                }
+
+                // Consider any generic parameters used by any closures/generators as used in the
+                // parent.
+                let unused = self.tcx.unused_generic_params(def_id);
+                debug!(
+                    "visit_ty: unused_parameters={:?} unused={:?}",
+                    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!("visit_ty: unused_parameters={:?}", self.unused_parameters);
+
+                false
+            }
+            ty::Param(param) => {
+                debug!("visit_ty: param={:?}", param);
+                self.unused_parameters.clear(param.index);
+                false
+            }
+            _ => ty.super_visit_with(self),
+        }
+    }
+}
diff --git a/src/librustc_mir/shim.rs b/src/librustc_mir/shim.rs
index 98286cddea6..bfa9bb9e0f0 100644
--- a/src/librustc_mir/shim.rs
+++ b/src/librustc_mir/shim.rs
@@ -4,7 +4,7 @@ use rustc_hir::lang_items::FnMutTraitLangItem;
 use rustc_middle::mir::*;
 use rustc_middle::ty::query::Providers;
 use rustc_middle::ty::subst::{InternalSubsts, Subst};
-use rustc_middle::ty::{self, Ty, TyCtxt, TypeFoldable};
+use rustc_middle::ty::{self, Ty, TyCtxt};
 use rustc_target::abi::VariantIdx;
 
 use rustc_index::vec::{Idx, IndexVec};
@@ -36,11 +36,6 @@ fn make_shim<'tcx>(tcx: TyCtxt<'tcx>, instance: ty::InstanceDef<'tcx>) -> Body<'
             build_call_shim(tcx, instance, Some(Adjustment::Deref), CallKind::Direct(def_id), None)
         }
         ty::InstanceDef::FnPtrShim(def_id, ty) => {
-            // FIXME(eddyb) support generating shims for a "shallow type",
-            // e.g. `Foo<_>` or `[_]` instead of requiring a fully monomorphic
-            // `Foo<Bar>` or `[String]` etc.
-            assert!(!ty.needs_subst());
-
             let trait_ = tcx.trait_of_item(def_id).unwrap();
             let adjustment = match tcx.fn_trait_kind_from_lang_item(trait_) {
                 Some(ty::ClosureKind::FnOnce) => Adjustment::Identity,
@@ -83,22 +78,8 @@ fn make_shim<'tcx>(tcx: TyCtxt<'tcx>, instance: ty::InstanceDef<'tcx>) -> Body<'
                 None,
             )
         }
-        ty::InstanceDef::DropGlue(def_id, ty) => {
-            // FIXME(eddyb) support generating shims for a "shallow type",
-            // e.g. `Foo<_>` or `[_]` instead of requiring a fully monomorphic
-            // `Foo<Bar>` or `[String]` etc.
-            assert!(!ty.needs_subst());
-
-            build_drop_shim(tcx, def_id, ty)
-        }
-        ty::InstanceDef::CloneShim(def_id, ty) => {
-            // FIXME(eddyb) support generating shims for a "shallow type",
-            // e.g. `Foo<_>` or `[_]` instead of requiring a fully monomorphic
-            // `Foo<Bar>` or `[String]` etc.
-            assert!(!ty.needs_subst());
-
-            build_clone_shim(tcx, def_id, ty)
-        }
+        ty::InstanceDef::DropGlue(def_id, ty) => build_drop_shim(tcx, def_id, ty),
+        ty::InstanceDef::CloneShim(def_id, ty) => build_clone_shim(tcx, def_id, ty),
         ty::InstanceDef::Virtual(..) => {
             bug!("InstanceDef::Virtual ({:?}) is for direct calls only", instance)
         }
diff --git a/src/librustc_mir/transform/const_prop.rs b/src/librustc_mir/transform/const_prop.rs
index 237a5a64f8b..3073bf53afd 100644
--- a/src/librustc_mir/transform/const_prop.rs
+++ b/src/librustc_mir/transform/const_prop.rs
@@ -116,7 +116,7 @@ impl<'tcx> MirPass<'tcx> for ConstProp {
             .predicates
             .iter()
             .filter_map(|(p, _)| if p.is_global() { Some(*p) } else { None });
-        if !traits::normalize_and_test_predicates(
+        if traits::impossible_predicates(
             tcx,
             traits::elaborate_predicates(tcx, predicates).map(|o| o.predicate).collect(),
         ) {
diff --git a/src/librustc_session/options.rs b/src/librustc_session/options.rs
index 8c1f6a77497..6b2097240e2 100644
--- a/src/librustc_session/options.rs
+++ b/src/librustc_session/options.rs
@@ -949,6 +949,8 @@ options! {DebuggingOptions, DebuggingSetter, basic_debugging_options,
         (default: PLT is disabled if full relro is enabled)"),
     polonius: bool = (false, parse_bool, [UNTRACKED],
         "enable polonius-based borrow-checker (default: no)"),
+    polymorphize: bool = (true, parse_bool, [TRACKED],
+          "perform polymorphization analysis"),
     pre_link_arg: (/* redirected to pre_link_args */) = ((), parse_string_push, [UNTRACKED],
         "a single extra argument to prepend the linker invocation (can be used several times)"),
     pre_link_args: Vec<String> = (Vec::new(), parse_list, [UNTRACKED],
diff --git a/src/librustc_span/symbol.rs b/src/librustc_span/symbol.rs
index 5d332ddf5f3..22a5115c7f5 100644
--- a/src/librustc_span/symbol.rs
+++ b/src/librustc_span/symbol.rs
@@ -921,6 +921,7 @@ symbols! {
         rustc_peek_liveness,
         rustc_peek_maybe_init,
         rustc_peek_maybe_uninit,
+        rustc_polymorphize_error,
         rustc_private,
         rustc_proc_macro_decls,
         rustc_promotable,
diff --git a/src/librustc_symbol_mangling/legacy.rs b/src/librustc_symbol_mangling/legacy.rs
index 3038b0c6bd7..90c89ea6b0a 100644
--- a/src/librustc_symbol_mangling/legacy.rs
+++ b/src/librustc_symbol_mangling/legacy.rs
@@ -116,7 +116,6 @@ fn get_symbol_hash<'tcx>(
 
         // also include any type parameters (for generic items)
         assert!(!substs.has_erasable_regions());
-        assert!(!substs.needs_subst());
         substs.hash_stable(&mut hcx, &mut hasher);
 
         if let Some(instantiating_crate) = instantiating_crate {
diff --git a/src/librustc_trait_selection/traits/mod.rs b/src/librustc_trait_selection/traits/mod.rs
index e8006129e3e..1c375522249 100644
--- a/src/librustc_trait_selection/traits/mod.rs
+++ b/src/librustc_trait_selection/traits/mod.rs
@@ -418,15 +418,14 @@ where
     Ok(resolved_value)
 }
 
-/// Normalizes the predicates and checks whether they hold in an empty
-/// environment. If this returns false, then either normalize
-/// encountered an error or one of the predicates did not hold. Used
-/// when creating vtables to check for unsatisfiable methods.
-pub fn normalize_and_test_predicates<'tcx>(
+/// Normalizes the predicates and checks whether they hold in an empty environment. If this
+/// returns true, then either normalize encountered an error or one of the predicates did not
+/// hold. Used when creating vtables to check for unsatisfiable methods.
+pub fn impossible_predicates<'tcx>(
     tcx: TyCtxt<'tcx>,
     predicates: Vec<ty::Predicate<'tcx>>,
 ) -> bool {
-    debug!("normalize_and_test_predicates(predicates={:?})", predicates);
+    debug!("impossible_predicates(predicates={:?})", predicates);
 
     let result = tcx.infer_ctxt().enter(|infcx| {
         let param_env = ty::ParamEnv::reveal_all();
@@ -443,22 +442,23 @@ pub fn normalize_and_test_predicates<'tcx>(
             fulfill_cx.register_predicate_obligation(&infcx, obligation);
         }
 
-        fulfill_cx.select_all_or_error(&infcx).is_ok()
+        fulfill_cx.select_all_or_error(&infcx).is_err()
     });
-    debug!("normalize_and_test_predicates(predicates={:?}) = {:?}", predicates, result);
+    debug!("impossible_predicates(predicates={:?}) = {:?}", predicates, result);
     result
 }
 
-fn substitute_normalize_and_test_predicates<'tcx>(
+fn subst_and_check_impossible_predicates<'tcx>(
     tcx: TyCtxt<'tcx>,
     key: (DefId, SubstsRef<'tcx>),
 ) -> bool {
-    debug!("substitute_normalize_and_test_predicates(key={:?})", key);
+    debug!("subst_and_check_impossible_predicates(key={:?})", key);
 
-    let predicates = tcx.predicates_of(key.0).instantiate(tcx, key.1).predicates;
-    let result = normalize_and_test_predicates(tcx, predicates);
+    let mut predicates = tcx.predicates_of(key.0).instantiate(tcx, key.1).predicates;
+    predicates.retain(|predicate| !predicate.needs_subst());
+    let result = impossible_predicates(tcx, predicates);
 
-    debug!("substitute_normalize_and_test_predicates(key={:?}) = {:?}", key, result);
+    debug!("subst_and_check_impossible_predicates(key={:?}) = {:?}", key, result);
     result
 }
 
@@ -510,7 +510,7 @@ fn vtable_methods<'tcx>(
             // Note that this method could then never be called, so we
             // do not want to try and codegen it, in that case (see #23435).
             let predicates = tcx.predicates_of(def_id).instantiate_own(tcx, substs);
-            if !normalize_and_test_predicates(tcx, predicates.predicates) {
+            if impossible_predicates(tcx, predicates.predicates) {
                 debug!("vtable_methods: predicates do not hold");
                 return None;
             }
@@ -558,8 +558,8 @@ pub fn provide(providers: &mut ty::query::Providers) {
         specializes: specialize::specializes,
         codegen_fulfill_obligation: codegen::codegen_fulfill_obligation,
         vtable_methods,
-        substitute_normalize_and_test_predicates,
         type_implements_trait,
+        subst_and_check_impossible_predicates,
         ..*providers
     };
 }
diff --git a/src/librustc_ty/instance.rs b/src/librustc_ty/instance.rs
index 0bc6c470978..324ae4ec29e 100644
--- a/src/librustc_ty/instance.rs
+++ b/src/librustc_ty/instance.rs
@@ -3,7 +3,7 @@ use rustc_hir::def_id::{DefId, LocalDefId};
 use rustc_infer::infer::TyCtxtInferExt;
 use rustc_middle::ty::subst::SubstsRef;
 use rustc_middle::ty::{self, Instance, TyCtxt, TypeFoldable};
-use rustc_span::sym;
+use rustc_span::{sym, DUMMY_SP};
 use rustc_target::spec::abi::Abi;
 use rustc_trait_selection::traits;
 use traits::{translate_substs, Reveal};
@@ -67,12 +67,19 @@ fn inner_resolve_instance<'tcx>(
                 let ty = substs.type_at(0);
 
                 if ty.needs_drop(tcx, param_env) {
-                    // `DropGlue` requires a monomorphic aka concrete type.
-                    if ty.needs_subst() {
-                        return Ok(None);
+                    debug!(" => nontrivial drop glue");
+                    match ty.kind {
+                        ty::Closure(..)
+                        | ty::Generator(..)
+                        | ty::Tuple(..)
+                        | ty::Adt(..)
+                        | ty::Dynamic(..)
+                        | ty::Array(..)
+                        | ty::Slice(..) => {}
+                        // Drop shims can only be built from ADTs.
+                        _ => return Ok(None),
                     }
 
-                    debug!(" => nontrivial drop glue");
                     ty::InstanceDef::DropGlue(def_id, Some(ty))
                 } else {
                     debug!(" => trivial drop glue");
@@ -224,17 +231,13 @@ fn resolve_associated_item<'tcx>(
                 trait_closure_kind,
             ))
         }
-        traits::ImplSourceFnPointer(ref data) => {
-            // `FnPtrShim` requires a monomorphic aka concrete type.
-            if data.fn_ty.needs_subst() {
-                return Ok(None);
-            }
-
-            Some(Instance {
+        traits::ImplSourceFnPointer(ref data) => match data.fn_ty.kind {
+            ty::FnDef(..) | ty::FnPtr(..) => Some(Instance {
                 def: ty::InstanceDef::FnPtrShim(trait_item.def_id, data.fn_ty),
                 substs: rcvr_substs,
-            })
-        }
+            }),
+            _ => None,
+        },
         traits::ImplSourceObject(ref data) => {
             let index = traits::get_vtable_index_of_object_method(tcx, data, def_id);
             Some(Instance { def: ty::InstanceDef::Virtual(def_id, index), substs: rcvr_substs })
@@ -246,10 +249,12 @@ fn resolve_associated_item<'tcx>(
                 if name == sym::clone {
                     let self_ty = trait_ref.self_ty();
 
-                    // `CloneShim` requires a monomorphic aka concrete type.
-                    if self_ty.needs_subst() {
-                        return Ok(None);
-                    }
+                    let is_copy = self_ty.is_copy_modulo_regions(tcx.at(DUMMY_SP), param_env);
+                    match self_ty.kind {
+                        _ if is_copy => (),
+                        ty::Array(..) | ty::Closure(..) | ty::Tuple(..) => {}
+                        _ => return Ok(None),
+                    };
 
                     Some(Instance {
                         def: ty::InstanceDef::CloneShim(def_id, self_ty),
diff --git a/src/test/codegen-units/item-collection/static-init.rs b/src/test/codegen-units/item-collection/static-init.rs
index f6005eed43c..aebccff01fc 100644
--- a/src/test/codegen-units/item-collection/static-init.rs
+++ b/src/test/codegen-units/item-collection/static-init.rs
@@ -6,7 +6,7 @@ pub static FN : fn() = foo::<i32>;
 
 pub fn foo<T>() { }
 
-//~ MONO_ITEM fn static_init::foo[0]<i32>
+//~ MONO_ITEM fn static_init::foo[0]<T>
 //~ MONO_ITEM static static_init::FN[0]
 
 //~ MONO_ITEM fn static_init::start[0]
diff --git a/src/test/codegen-units/item-collection/trait-method-default-impl.rs b/src/test/codegen-units/item-collection/trait-method-default-impl.rs
index 11f6cc62d49..abe2d108eae 100644
--- a/src/test/codegen-units/item-collection/trait-method-default-impl.rs
+++ b/src/test/codegen-units/item-collection/trait-method-default-impl.rs
@@ -27,7 +27,7 @@ impl SomeGenericTrait<u64> for i32 {
 
     // For the non-generic foo(), we should generate a codegen-item even if it
     // is not called anywhere
-    //~ MONO_ITEM fn trait_method_default_impl::SomeGenericTrait[0]::foo[0]<i32, u64>
+    //~ MONO_ITEM fn trait_method_default_impl::SomeGenericTrait[0]::foo[0]<i32, T1>
 }
 
 // Non-generic impl of generic trait
diff --git a/src/test/codegen-units/polymorphization/unused_type_parameters.rs b/src/test/codegen-units/polymorphization/unused_type_parameters.rs
new file mode 100644
index 00000000000..dc2ad0559b3
--- /dev/null
+++ b/src/test/codegen-units/polymorphization/unused_type_parameters.rs
@@ -0,0 +1,323 @@
+// compile-flags:-Zprint-mono-items=lazy -Copt-level=1
+// ignore-tidy-linelength
+
+#![crate_type = "rlib"]
+
+// This test checks that the polymorphization analysis correctly reduces the
+// generated mono items.
+
+mod functions {
+    // Function doesn't have any type parameters to be unused.
+    pub fn no_parameters() {}
+
+//~ MONO_ITEM fn unused_type_parameters::functions[0]::no_parameters[0]
+
+    // Function has an unused type parameter.
+    pub fn unused<T>() {
+    }
+
+//~ MONO_ITEM fn unused_type_parameters::functions[0]::unused[0]<T>
+
+    // Function uses type parameter in value of a binding.
+    pub fn used_binding_value<T: Default>() {
+        let _: T = Default::default();
+    }
+
+//~ MONO_ITEM fn unused_type_parameters::functions[0]::used_binding_value[0]<u32>
+//~ MONO_ITEM fn unused_type_parameters::functions[0]::used_binding_value[0]<u64>
+
+    // Function uses type parameter in type of a binding.
+    pub fn used_binding_type<T>() {
+        let _: Option<T> = None;
+    }
+
+//~ MONO_ITEM fn unused_type_parameters::functions[0]::used_binding_type[0]<u32>
+//~ MONO_ITEM fn unused_type_parameters::functions[0]::used_binding_type[0]<u64>
+
+    // Function uses type parameter in argument.
+    pub fn used_argument<T>(_: T) {
+    }
+
+//~ MONO_ITEM fn unused_type_parameters::functions[0]::used_argument[0]<u32>
+//~ MONO_ITEM fn unused_type_parameters::functions[0]::used_argument[0]<u64>
+//
+    // Function uses type parameter in substitutions to another function.
+    pub fn used_substs<T>() {
+        unused::<T>()
+    }
+
+//~ MONO_ITEM fn unused_type_parameters::functions[0]::used_substs[0]<u32>
+//~ MONO_ITEM fn unused_type_parameters::functions[0]::used_substs[0]<u64>
+}
+
+
+mod closures {
+    // Function doesn't have any type parameters to be unused.
+    pub fn no_parameters() {
+        let _ = || {};
+    }
+
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::no_parameters[0]
+
+    // Function has an unused type parameter in parent and closure.
+    pub fn unused<T>() -> u32 {
+        let add_one = |x: u32| x + 1;
+        add_one(3)
+    }
+
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::unused[0]::{{closure}}[0]<T, i8, extern "rust-call" fn((u32)) -> u32, ()>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::unused[0]<T>
+
+    // Function has an unused type parameter in closure, but not in parent.
+    pub fn used_parent<T: Default>() -> u32 {
+        let _: T = Default::default();
+        let add_one = |x: u32| x + 1;
+        add_one(3)
+    }
+
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_parent[0]::{{closure}}[0]<T, i8, extern "rust-call" fn((u32)) -> u32, ()>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_parent[0]<u32>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_parent[0]<u64>
+
+    // Function uses type parameter in value of a binding in closure.
+    pub fn used_binding_value<T: Default>() -> T {
+        let x = || {
+            let y: T = Default::default();
+            y
+        };
+
+        x()
+    }
+
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_binding_value[0]::{{closure}}[0]<u32, i8, extern "rust-call" fn(()) -> u32, ()>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_binding_value[0]::{{closure}}[0]<u64, i8, extern "rust-call" fn(()) -> u64, ()>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_binding_value[0]<u32>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_binding_value[0]<u64>
+
+    // Function uses type parameter in type of a binding in closure.
+    pub fn used_binding_type<T>() -> Option<T> {
+        let x = || {
+            let y: Option<T> = None;
+            y
+        };
+
+        x()
+    }
+
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_binding_type[0]::{{closure}}[0]<u32, i8, extern "rust-call" fn(()) -> core::option[0]::Option[0]<u32>, ()>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_binding_type[0]::{{closure}}[0]<u64, i8, extern "rust-call" fn(()) -> core::option[0]::Option[0]<u64>, ()>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_binding_type[0]<u32>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_binding_type[0]<u64>
+
+    // Function and closure uses type parameter in argument.
+    pub fn used_argument<T>(t: T) -> u32 {
+        let x = |_: T| 3;
+        x(t)
+    }
+
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_argument[0]::{{closure}}[0]<u32, i8, extern "rust-call" fn((u32)) -> u32, ()>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_argument[0]::{{closure}}[0]<u64, i8, extern "rust-call" fn((u64)) -> u32, ()>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_argument[0]<u32>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_argument[0]<u64>
+
+    // Closure uses type parameter in argument.
+    pub fn used_argument_closure<T: Default>() -> u32 {
+        let t: T = Default::default();
+        let x = |_: T| 3;
+        x(t)
+    }
+
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_argument_closure[0]::{{closure}}[0]<u32, i8, extern "rust-call" fn((u32)) -> u32, ()>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_argument_closure[0]::{{closure}}[0]<u64, i8, extern "rust-call" fn((u64)) -> u32, ()>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_argument_closure[0]<u32>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_argument_closure[0]<u64>
+
+    // Closure uses type parameter as upvar.
+    pub fn used_upvar<T: Default>() -> T {
+        let x: T = Default::default();
+        let y = || x;
+        y()
+    }
+
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_upvar[0]::{{closure}}[0]<u32, i32, extern "rust-call" fn(()) -> u32, (u32)>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_upvar[0]::{{closure}}[0]<u64, i32, extern "rust-call" fn(()) -> u64, (u64)>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_upvar[0]<u32>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_upvar[0]<u64>
+
+    // Closure uses type parameter in substitutions to another function.
+    pub fn used_substs<T>() {
+        let x = || super::functions::unused::<T>();
+        x()
+    }
+
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_substs[0]::{{closure}}[0]<u32, i8, extern "rust-call" fn(()), ()>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_substs[0]::{{closure}}[0]<u64, i8, extern "rust-call" fn(()), ()>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_substs[0]<u32>
+//~ MONO_ITEM fn unused_type_parameters::closures[0]::used_substs[0]<u64>
+}
+
+mod methods {
+    pub struct Foo<F>(F);
+
+    impl<F: Default> Foo<F> {
+        // Function has an unused type parameter from impl.
+        pub fn unused_impl() {
+        }
+
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::unused_impl[0]<F>
+
+        // Function has an unused type parameter from impl and fn.
+        pub fn unused_both<G: Default>() {
+        }
+
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::unused_both[0]<F, G>
+
+        // Function uses type parameter from impl.
+        pub fn used_impl() {
+            let _: F = Default::default();
+        }
+
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::used_impl[0]<u32>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::used_impl[0]<u64>
+
+        // Function uses type parameter from impl.
+        pub fn used_fn<G: Default>() {
+            let _: G = Default::default();
+        }
+
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::used_fn[0]<F, u32>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::used_fn[0]<F, u64>
+
+        // Function uses type parameter from impl.
+        pub fn used_both<G: Default>() {
+            let _: F = Default::default();
+            let _: G = Default::default();
+        }
+
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::used_both[0]<u32, u32>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::used_both[0]<u64, u64>
+
+        // Function uses type parameter in substitutions to another function.
+        pub fn used_substs() {
+            super::functions::unused::<F>()
+        }
+
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::used_substs[0]<u32>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::used_substs[0]<u64>
+
+        // Function has an unused type parameter from impl and fn.
+        pub fn closure_unused_all<G: Default>() -> u32 {
+            let add_one = |x: u32| x + 1;
+            add_one(3)
+        }
+
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_unused_all[0]::{{closure}}[0]<F, G, i8, extern "rust-call" fn((u32)) -> u32, ()>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_unused_all[0]<F, G>
+
+        // Function uses type parameter from impl and fn in closure.
+        pub fn closure_used_both<G: Default>() -> u32 {
+            let add_one = |x: u32| {
+                let _: F = Default::default();
+                let _: G = Default::default();
+                x + 1
+            };
+
+            add_one(3)
+        }
+
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_both[0]::{{closure}}[0]<u32, u32, i8, extern "rust-call" fn((u32)) -> u32, ()>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_both[0]::{{closure}}[0]<u64, u64, i8, extern "rust-call" fn((u32)) -> u32, ()>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_both[0]<u32, u32>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_both[0]<u64, u64>
+
+        // Function uses type parameter from fn in closure.
+        pub fn closure_used_fn<G: Default>() -> u32 {
+            let add_one = |x: u32| {
+                let _: G = Default::default();
+                x + 1
+            };
+
+            add_one(3)
+        }
+
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_fn[0]::{{closure}}[0]<F, u32, i8, extern "rust-call" fn((u32)) -> u32, ()>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_fn[0]::{{closure}}[0]<F, u64, i8, extern "rust-call" fn((u32)) -> u32, ()>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_fn[0]<F, u32>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_fn[0]<F, u64>
+
+        // Function uses type parameter from impl in closure.
+        pub fn closure_used_impl<G: Default>() -> u32 {
+            let add_one = |x: u32| {
+                let _: F = Default::default();
+                x + 1
+            };
+
+            add_one(3)
+        }
+
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_impl[0]::{{closure}}[0]<u32, G, i8, extern "rust-call" fn((u32)) -> u32, ()>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_impl[0]::{{closure}}[0]<u64, G, i8, extern "rust-call" fn((u32)) -> u32, ()>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_impl[0]<u32, G>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_impl[0]<u64, G>
+
+        // Closure uses type parameter in substitutions to another function.
+        pub fn closure_used_substs() {
+            let x = || super::functions::unused::<F>();
+            x()
+        }
+
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_substs[0]::{{closure}}[0]<u32, i8, extern "rust-call" fn(()), ()>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_substs[0]::{{closure}}[0]<u64, i8, extern "rust-call" fn(()), ()>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_substs[0]<u32>
+//~ MONO_ITEM fn unused_type_parameters::methods[0]::{{impl}}[0]::closure_used_substs[0]<u64>
+    }
+}
+
+
+
+fn dispatch<T: Default>() {
+    functions::no_parameters();
+    functions::unused::<T>();
+    functions::used_binding_value::<T>();
+    functions::used_binding_type::<T>();
+    functions::used_argument::<T>(Default::default());
+    functions::used_substs::<T>();
+
+    closures::no_parameters();
+    let _ = closures::unused::<T>();
+    let _ = closures::used_parent::<T>();
+    let _ = closures::used_binding_value::<T>();
+    let _ = closures::used_binding_type::<T>();
+    let _ = closures::used_argument::<T>(Default::default());
+    let _ = closures::used_argument_closure::<T>();
+    let _ = closures::used_upvar::<T>();
+    let _ = closures::used_substs::<T>();
+
+    methods::Foo::<T>::unused_impl();
+    methods::Foo::<T>::unused_both::<T>();
+    methods::Foo::<T>::used_impl();
+    methods::Foo::<T>::used_fn::<T>();
+    methods::Foo::<T>::used_both::<T>();
+    methods::Foo::<T>::used_substs();
+    let _ = methods::Foo::<T>::closure_unused_all::<T>();
+    let _ = methods::Foo::<T>::closure_used_both::<T>();
+    let _ = methods::Foo::<T>::closure_used_impl::<T>();
+    let _ = methods::Foo::<T>::closure_used_fn::<T>();
+    let _ = methods::Foo::<T>::closure_used_substs();
+}
+
+//~ MONO_ITEM fn unused_type_parameters::dispatch[0]<u32>
+//~ MONO_ITEM fn unused_type_parameters::dispatch[0]<u64>
+
+pub fn foo() {
+    // Generate two copies of each function to check that where the type parameter is unused,
+    // there is only a single copy.
+    dispatch::<u32>();
+    dispatch::<u64>();
+}
+
+//~ MONO_ITEM fn unused_type_parameters::foo[0] @@ unused_type_parameters-cgu.0[External]
+
+// These are all the items that aren't relevant to the test.
+//~ MONO_ITEM fn core::default[0]::{{impl}}[6]::default[0]
+//~ MONO_ITEM fn core::default[0]::{{impl}}[7]::default[0]
diff --git a/src/test/ui/polymorphization/const_parameters/closures.rs b/src/test/ui/polymorphization/const_parameters/closures.rs
new file mode 100644
index 00000000000..7bbcaebea01
--- /dev/null
+++ b/src/test/ui/polymorphization/const_parameters/closures.rs
@@ -0,0 +1,66 @@
+// build-fail
+#![feature(const_generics, rustc_attrs)]
+//~^ WARN the feature `const_generics` is incomplete
+
+// This test checks that the polymorphization analysis correctly detects unused const
+// parameters in closures.
+
+// Function doesn't have any generic parameters to be unused.
+#[rustc_polymorphize_error]
+pub fn no_parameters() {
+    let _ = || {};
+}
+
+// Function has an unused generic parameter in parent and closure.
+#[rustc_polymorphize_error]
+pub fn unused<const T: usize>() -> usize {
+    //~^ ERROR item has unused generic parameters
+    let add_one = |x: usize| x + 1;
+    //~^ ERROR item has unused generic parameters
+    add_one(3)
+}
+
+// Function has an unused generic parameter in closure, but not in parent.
+#[rustc_polymorphize_error]
+pub fn used_parent<const T: usize>() -> usize {
+    let x: usize = T;
+    let add_one = |x: usize| x + 1;
+    //~^ ERROR item has unused generic parameters
+    x + add_one(3)
+}
+
+// Function uses generic parameter in value of a binding in closure.
+#[rustc_polymorphize_error]
+pub fn used_binding<const T: usize>() -> usize {
+    let x = || {
+        let y: usize = T;
+        y
+    };
+
+    x()
+}
+
+// Closure uses a value as an upvar, which used the generic parameter.
+#[rustc_polymorphize_error]
+pub fn unused_upvar<const T: usize>() -> usize {
+    let x: usize = T;
+    let y = || x;
+    //~^ ERROR item has unused generic parameters
+    y()
+}
+
+// Closure uses generic parameter in substitutions to another function.
+#[rustc_polymorphize_error]
+pub fn used_substs<const T: usize>() -> usize {
+    let x = || unused::<T>();
+    x()
+}
+
+fn main() {
+    no_parameters();
+    let _ = unused::<1>();
+    let _ = used_parent::<1>();
+    let _ = used_binding::<1>();
+    let _ = unused_upvar::<1>();
+    let _ = used_substs::<1>();
+}
diff --git a/src/test/ui/polymorphization/const_parameters/closures.stderr b/src/test/ui/polymorphization/const_parameters/closures.stderr
new file mode 100644
index 00000000000..eb872eac74c
--- /dev/null
+++ b/src/test/ui/polymorphization/const_parameters/closures.stderr
@@ -0,0 +1,44 @@
+warning: the feature `const_generics` is incomplete and may not be safe to use and/or cause compiler crashes
+  --> $DIR/closures.rs:2:12
+   |
+LL | #![feature(const_generics, rustc_attrs)]
+   |            ^^^^^^^^^^^^^^
+   |
+   = note: `#[warn(incomplete_features)]` on by default
+   = note: see issue #44580 <https://github.com/rust-lang/rust/issues/44580> for more information
+
+error: item has unused generic parameters
+  --> $DIR/closures.rs:18:19
+   |
+LL | pub fn unused<const T: usize>() -> usize {
+   |                     - generic parameter `T` is unused
+LL |
+LL |     let add_one = |x: usize| x + 1;
+   |                   ^^^^^^^^^^^^^^^^
+
+error: item has unused generic parameters
+  --> $DIR/closures.rs:16:8
+   |
+LL | pub fn unused<const T: usize>() -> usize {
+   |        ^^^^^^       - generic parameter `T` is unused
+
+error: item has unused generic parameters
+  --> $DIR/closures.rs:27:19
+   |
+LL | pub fn used_parent<const T: usize>() -> usize {
+   |                          - generic parameter `T` is unused
+LL |     let x: usize = T;
+LL |     let add_one = |x: usize| x + 1;
+   |                   ^^^^^^^^^^^^^^^^
+
+error: item has unused generic parameters
+  --> $DIR/closures.rs:47:13
+   |
+LL | pub fn unused_upvar<const T: usize>() -> usize {
+   |                           - generic parameter `T` is unused
+LL |     let x: usize = T;
+LL |     let y = || x;
+   |             ^^^^
+
+error: aborting due to 4 previous errors; 1 warning emitted
+
diff --git a/src/test/ui/polymorphization/const_parameters/functions.rs b/src/test/ui/polymorphization/const_parameters/functions.rs
new file mode 100644
index 00000000000..77539b94e48
--- /dev/null
+++ b/src/test/ui/polymorphization/const_parameters/functions.rs
@@ -0,0 +1,36 @@
+// build-fail
+#![feature(const_generics, rustc_attrs)]
+//~^ WARN the feature `const_generics` is incomplete
+
+// This test checks that the polymorphization analysis correctly detects unused const
+// parameters in functions.
+
+// Function doesn't have any generic parameters to be unused.
+#[rustc_polymorphize_error]
+pub fn no_parameters() {}
+
+// Function has an unused generic parameter.
+#[rustc_polymorphize_error]
+pub fn unused<const T: usize>() {
+    //~^ ERROR item has unused generic parameters
+}
+
+// Function uses generic parameter in value of a binding.
+#[rustc_polymorphize_error]
+pub fn used_binding<const T: usize>() -> usize {
+    let x: usize = T;
+    x
+}
+
+// Function uses generic parameter in substitutions to another function.
+#[rustc_polymorphize_error]
+pub fn used_substs<const T: usize>() {
+    unused::<T>()
+}
+
+fn main() {
+    no_parameters();
+    unused::<1>();
+    used_binding::<1>();
+    used_substs::<1>();
+}
diff --git a/src/test/ui/polymorphization/const_parameters/functions.stderr b/src/test/ui/polymorphization/const_parameters/functions.stderr
new file mode 100644
index 00000000000..c99a9b788eb
--- /dev/null
+++ b/src/test/ui/polymorphization/const_parameters/functions.stderr
@@ -0,0 +1,17 @@
+warning: the feature `const_generics` is incomplete and may not be safe to use and/or cause compiler crashes
+  --> $DIR/functions.rs:2:12
+   |
+LL | #![feature(const_generics, rustc_attrs)]
+   |            ^^^^^^^^^^^^^^
+   |
+   = note: `#[warn(incomplete_features)]` on by default
+   = note: see issue #44580 <https://github.com/rust-lang/rust/issues/44580> for more information
+
+error: item has unused generic parameters
+  --> $DIR/functions.rs:14:8
+   |
+LL | pub fn unused<const T: usize>() {
+   |        ^^^^^^       - generic parameter `T` is unused
+
+error: aborting due to previous error; 1 warning emitted
+
diff --git a/src/test/ui/polymorphization/drop_shims/simple.rs b/src/test/ui/polymorphization/drop_shims/simple.rs
new file mode 100644
index 00000000000..ce56b7a3588
--- /dev/null
+++ b/src/test/ui/polymorphization/drop_shims/simple.rs
@@ -0,0 +1,21 @@
+// check-pass
+
+pub struct OnDrop<F: Fn()>(pub F);
+
+impl<F: Fn()> Drop for OnDrop<F> {
+    fn drop(&mut self) { }
+}
+
+fn foo<R, S: FnOnce()>(
+    _: R,
+    _: S,
+) {
+    let bar = || {
+        let _ = OnDrop(|| ());
+    };
+    let _ = bar();
+}
+
+fn main() {
+    foo(3u32, || {});
+}
diff --git a/src/test/ui/polymorphization/drop_shims/transitive.rs b/src/test/ui/polymorphization/drop_shims/transitive.rs
new file mode 100644
index 00000000000..b7ea07b6bc6
--- /dev/null
+++ b/src/test/ui/polymorphization/drop_shims/transitive.rs
@@ -0,0 +1,26 @@
+// check-pass
+
+pub struct OnDrop<F: Fn()>(pub F);
+
+impl<F: Fn()> Drop for OnDrop<F> {
+    fn drop(&mut self) { }
+}
+
+fn bar<F: FnOnce()>(f: F) {
+    let _ = OnDrop(|| ());
+    f()
+}
+
+fn foo<R, S: FnOnce()>(
+    _: R,
+    _: S,
+) {
+    let bar = || {
+        bar(|| {})
+    };
+    let _ = bar();
+}
+
+fn main() {
+    foo(3u32, || {});
+}
diff --git a/src/test/ui/polymorphization/generators.rs b/src/test/ui/polymorphization/generators.rs
new file mode 100644
index 00000000000..1acba7c8bf1
--- /dev/null
+++ b/src/test/ui/polymorphization/generators.rs
@@ -0,0 +1,93 @@
+// build-fail
+#![feature(const_generics, generators, generator_trait, rustc_attrs)]
+//~^ WARN the feature `const_generics` is incomplete
+
+use std::marker::Unpin;
+use std::ops::{Generator, GeneratorState};
+use std::pin::Pin;
+
+enum YieldOrReturn<Y, R> {
+    Yield(Y),
+    Return(R),
+}
+
+fn finish<T, Y, R>(mut t: T) -> Vec<YieldOrReturn<Y, R>>
+where
+    T: Generator<(), Yield = Y, Return = R> + Unpin,
+{
+    let mut results = Vec::new();
+    loop {
+        match Pin::new(&mut t).resume(()) {
+            GeneratorState::Yielded(yielded) => results.push(YieldOrReturn::Yield(yielded)),
+            GeneratorState::Complete(returned) => {
+                results.push(YieldOrReturn::Return(returned));
+                return results;
+            }
+        }
+    }
+}
+
+// This test checks that the polymorphization analysis functions on generators.
+
+#[rustc_polymorphize_error]
+pub fn unused_type<T>() -> impl Generator<(), Yield = u32, Return = u32> + Unpin {
+    //~^ ERROR item has unused generic parameters
+    || {
+        //~^ ERROR item has unused generic parameters
+        yield 1;
+        2
+    }
+}
+
+#[rustc_polymorphize_error]
+pub fn used_type_in_yield<Y: Default>() -> impl Generator<(), Yield = Y, Return = u32> + Unpin {
+    || {
+        yield Y::default();
+        2
+    }
+}
+
+#[rustc_polymorphize_error]
+pub fn used_type_in_return<R: Default>() -> impl Generator<(), Yield = u32, Return = R> + Unpin {
+    || {
+        yield 3;
+        R::default()
+    }
+}
+
+#[rustc_polymorphize_error]
+pub fn unused_const<const T: u32>() -> impl Generator<(), Yield = u32, Return = u32> + Unpin {
+    //~^ ERROR item has unused generic parameters
+    || {
+        //~^ ERROR item has unused generic parameters
+        yield 1;
+        2
+    }
+}
+
+#[rustc_polymorphize_error]
+pub fn used_const_in_yield<const Y: u32>() -> impl Generator<(), Yield = u32, Return = u32> + Unpin
+{
+    || {
+        yield Y;
+        2
+    }
+}
+
+#[rustc_polymorphize_error]
+pub fn used_const_in_return<const R: u32>() -> impl Generator<(), Yield = u32, Return = u32> + Unpin
+{
+    || {
+        yield 4;
+        R
+    }
+}
+
+fn main() {
+    finish(unused_type::<u32>());
+    finish(used_type_in_yield::<u32>());
+    finish(used_type_in_return::<u32>());
+    finish(unused_const::<1u32>());
+    finish(used_const_in_yield::<1u32>());
+    finish(used_const_in_return::<1u32>());
+}
diff --git a/src/test/ui/polymorphization/generators.stderr b/src/test/ui/polymorphization/generators.stderr
new file mode 100644
index 00000000000..b3e5a2de027
--- /dev/null
+++ b/src/test/ui/polymorphization/generators.stderr
@@ -0,0 +1,49 @@
+warning: the feature `const_generics` is incomplete and may not be safe to use and/or cause compiler crashes
+  --> $DIR/generators.rs:2:12
+   |
+LL | #![feature(const_generics, generators, generator_trait, rustc_attrs)]
+   |            ^^^^^^^^^^^^^^
+   |
+   = note: `#[warn(incomplete_features)]` on by default
+   = note: see issue #44580 <https://github.com/rust-lang/rust/issues/44580> for more information
+
+error: item has unused generic parameters
+  --> $DIR/generators.rs:35:5
+   |
+LL |   pub fn unused_type<T>() -> impl Generator<(), Yield = u32, Return = u32> + Unpin {
+   |                      - generic parameter `T` is unused
+LL |
+LL | /     || {
+LL | |
+LL | |         yield 1;
+LL | |         2
+LL | |     }
+   | |_____^
+
+error: item has unused generic parameters
+  --> $DIR/generators.rs:33:8
+   |
+LL | pub fn unused_type<T>() -> impl Generator<(), Yield = u32, Return = u32> + Unpin {
+   |        ^^^^^^^^^^^ - generic parameter `T` is unused
+
+error: item has unused generic parameters
+  --> $DIR/generators.rs:61:5
+   |
+LL |   pub fn unused_const<const T: u32>() -> impl Generator<(), Yield = u32, Return = u32> + Unpin {
+   |                             - generic parameter `T` is unused
+LL |
+LL | /     || {
+LL | |
+LL | |         yield 1;
+LL | |         2
+LL | |     }
+   | |_____^
+
+error: item has unused generic parameters
+  --> $DIR/generators.rs:59:8
+   |
+LL | pub fn unused_const<const T: u32>() -> impl Generator<(), Yield = u32, Return = u32> + Unpin {
+   |        ^^^^^^^^^^^^       - generic parameter `T` is unused
+
+error: aborting due to 4 previous errors; 1 warning emitted
+
diff --git a/src/test/ui/polymorphization/lifetimes.rs b/src/test/ui/polymorphization/lifetimes.rs
new file mode 100644
index 00000000000..4bde349a336
--- /dev/null
+++ b/src/test/ui/polymorphization/lifetimes.rs
@@ -0,0 +1,24 @@
+// build-fail
+#![feature(rustc_attrs)]
+
+// This test checks that the polymorphization analysis doesn't break when the
+// function/closure doesn't just have generic parameters.
+
+// Function has an unused generic parameter.
+#[rustc_polymorphize_error]
+pub fn unused<'a, T>(_: &'a u32) {
+    //~^ ERROR item has unused generic parameters
+}
+
+#[rustc_polymorphize_error]
+pub fn used<'a, T: Default>(_: &'a u32) -> u32 {
+    let _: T = Default::default();
+    let add_one = |x: u32| x + 1;
+    //~^ ERROR item has unused generic parameters
+    add_one(3)
+}
+
+fn main() {
+    unused::<u32>(&3);
+    used::<u32>(&3);
+}
diff --git a/src/test/ui/polymorphization/lifetimes.stderr b/src/test/ui/polymorphization/lifetimes.stderr
new file mode 100644
index 00000000000..6c85e4f2916
--- /dev/null
+++ b/src/test/ui/polymorphization/lifetimes.stderr
@@ -0,0 +1,17 @@
+error: item has unused generic parameters
+  --> $DIR/lifetimes.rs:9:8
+   |
+LL | pub fn unused<'a, T>(_: &'a u32) {
+   |        ^^^^^^     - generic parameter `T` is unused
+
+error: item has unused generic parameters
+  --> $DIR/lifetimes.rs:16:19
+   |
+LL | pub fn used<'a, T: Default>(_: &'a u32) -> u32 {
+   |                 - generic parameter `T` is unused
+LL |     let _: T = Default::default();
+LL |     let add_one = |x: u32| x + 1;
+   |                   ^^^^^^^^^^^^^^
+
+error: aborting due to 2 previous errors
+
diff --git a/src/test/ui/polymorphization/normalized_sig_types.rs b/src/test/ui/polymorphization/normalized_sig_types.rs
new file mode 100644
index 00000000000..fa76b7201e8
--- /dev/null
+++ b/src/test/ui/polymorphization/normalized_sig_types.rs
@@ -0,0 +1,25 @@
+// build-pass
+
+pub trait ParallelIterator: Sized {
+    fn drive<C: Consumer<()>>(_: C) {
+        C::into_folder();
+    }
+}
+
+pub trait Consumer<T>: Sized {
+    type Result;
+    fn into_folder() -> Self::Result;
+}
+
+impl ParallelIterator for () {}
+
+impl<F: Fn(), T> Consumer<T> for F {
+    type Result = ();
+    fn into_folder() -> Self::Result {
+        unimplemented!()
+    }
+}
+
+fn main() {
+    <()>::drive(|| ());
+}
diff --git a/src/test/ui/polymorphization/predicates.rs b/src/test/ui/polymorphization/predicates.rs
new file mode 100644
index 00000000000..390ac983aa0
--- /dev/null
+++ b/src/test/ui/polymorphization/predicates.rs
@@ -0,0 +1,23 @@
+// build-fail
+#![feature(rustc_attrs)]
+
+// This test checks that `T` is considered used in `foo`, because it is used in a predicate for
+// `I`, which is used.
+
+#[rustc_polymorphize_error]
+fn bar<I>() {
+    //~^ ERROR item has unused generic parameters
+}
+
+#[rustc_polymorphize_error]
+fn foo<I, T>(_: I)
+where
+    I: Iterator<Item = T>,
+{
+    bar::<I>()
+}
+
+fn main() {
+    let x = &[2u32];
+    foo(x.iter());
+}
diff --git a/src/test/ui/polymorphization/predicates.stderr b/src/test/ui/polymorphization/predicates.stderr
new file mode 100644
index 00000000000..1b266083463
--- /dev/null
+++ b/src/test/ui/polymorphization/predicates.stderr
@@ -0,0 +1,8 @@
+error: item has unused generic parameters
+  --> $DIR/predicates.rs:8:4
+   |
+LL | fn bar<I>() {
+   |    ^^^ - generic parameter `I` is unused
+
+error: aborting due to previous error
+
diff --git a/src/test/ui/polymorphization/too-many-generic-params.rs b/src/test/ui/polymorphization/too-many-generic-params.rs
new file mode 100644
index 00000000000..ec6244630fd
--- /dev/null
+++ b/src/test/ui/polymorphization/too-many-generic-params.rs
@@ -0,0 +1,85 @@
+// build-pass
+#![feature(rustc_attrs)]
+
+// This test checks that the analysis doesn't panic when there are >64 generic parameters, but
+// instead considers those parameters used.
+
+#[rustc_polymorphize_error]
+fn bar<A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, AA,
+       AB, AC, AD, AE, AF, AG, AH, AI, AJ, AK, AL, AM, AN, AO, AP, AQ, AR, AS, AT, AU, AV, AW,
+       AX, AY, AZ, BA, BB, BC, BD, BE, BF, BG, BH, BI, BJ, BK, BL, BM>()
+{
+    let _: Option<A> = None;
+    let _: Option<B> = None;
+    let _: Option<C> = None;
+    let _: Option<D> = None;
+    let _: Option<E> = None;
+    let _: Option<F> = None;
+    let _: Option<G> = None;
+    let _: Option<H> = None;
+    let _: Option<I> = None;
+    let _: Option<J> = None;
+    let _: Option<K> = None;
+    let _: Option<L> = None;
+    let _: Option<M> = None;
+    let _: Option<N> = None;
+    let _: Option<O> = None;
+    let _: Option<P> = None;
+    let _: Option<Q> = None;
+    let _: Option<R> = None;
+    let _: Option<S> = None;
+    let _: Option<T> = None;
+    let _: Option<U> = None;
+    let _: Option<V> = None;
+    let _: Option<W> = None;
+    let _: Option<X> = None;
+    let _: Option<Y> = None;
+    let _: Option<Z> = None;
+    let _: Option<AA> = None;
+    let _: Option<AB> = None;
+    let _: Option<AC> = None;
+    let _: Option<AD> = None;
+    let _: Option<AE> = None;
+    let _: Option<AF> = None;
+    let _: Option<AG> = None;
+    let _: Option<AH> = None;
+    let _: Option<AI> = None;
+    let _: Option<AJ> = None;
+    let _: Option<AK> = None;
+    let _: Option<AL> = None;
+    let _: Option<AM> = None;
+    let _: Option<AN> = None;
+    let _: Option<AO> = None;
+    let _: Option<AP> = None;
+    let _: Option<AQ> = None;
+    let _: Option<AR> = None;
+    let _: Option<AS> = None;
+    let _: Option<AT> = None;
+    let _: Option<AU> = None;
+    let _: Option<AV> = None;
+    let _: Option<AW> = None;
+    let _: Option<AX> = None;
+    let _: Option<AY> = None;
+    let _: Option<AZ> = None;
+    let _: Option<BA> = None;
+    let _: Option<BB> = None;
+    let _: Option<BC> = None;
+    let _: Option<BD> = None;
+    let _: Option<BE> = None;
+    let _: Option<BF> = None;
+    let _: Option<BG> = None;
+    let _: Option<BH> = None;
+    let _: Option<BI> = None;
+    let _: Option<BJ> = None;
+    let _: Option<BK> = None;
+    let _: Option<BL> = None;
+    let _: Option<BM> = None;
+}
+
+fn main() {
+    bar::<u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32,
+          u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32,
+          u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32,
+          u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32, u32,
+          u32>();
+}
diff --git a/src/test/ui/polymorphization/type_parameters/closures.rs b/src/test/ui/polymorphization/type_parameters/closures.rs
new file mode 100644
index 00000000000..1fbe13380b5
--- /dev/null
+++ b/src/test/ui/polymorphization/type_parameters/closures.rs
@@ -0,0 +1,160 @@
+// build-fail
+#![feature(stmt_expr_attributes, rustc_attrs)]
+
+// This test checks that the polymorphization analysis correctly detects unused type
+// parameters in closures.
+
+// Function doesn't have any generic parameters to be unused.
+#[rustc_polymorphize_error]
+pub fn no_parameters() {
+    let _ = || {};
+}
+
+// Function has an unused generic parameter in parent and closure.
+#[rustc_polymorphize_error]
+pub fn unused<T>() -> u32 {
+    //~^ ERROR item has unused generic parameters
+
+    let add_one = |x: u32| x + 1;
+    //~^ ERROR item has unused generic parameters
+    add_one(3)
+}
+
+// Function has an unused generic parameter in closure, but not in parent.
+#[rustc_polymorphize_error]
+pub fn used_parent<T: Default>() -> u32 {
+    let _: T = Default::default();
+    let add_one = |x: u32| x + 1;
+    //~^ ERROR item has unused generic parameters
+    add_one(3)
+}
+
+// Function uses generic parameter in value of a binding in closure.
+#[rustc_polymorphize_error]
+pub fn used_binding_value<T: Default>() -> T {
+    let x = || {
+        let y: T = Default::default();
+        y
+    };
+
+    x()
+}
+
+// Function uses generic parameter in generic of a binding in closure.
+#[rustc_polymorphize_error]
+pub fn used_binding_generic<T>() -> Option<T> {
+    let x = || {
+        let y: Option<T> = None;
+        y
+    };
+
+    x()
+}
+
+// Function and closure uses generic parameter in argument.
+#[rustc_polymorphize_error]
+pub fn used_argument<T>(t: T) -> u32 {
+    let x = |_: T| 3;
+    x(t)
+}
+
+// Closure uses generic parameter in argument.
+#[rustc_polymorphize_error]
+pub fn used_argument_closure<T: Default>() -> u32 {
+    let t: T = Default::default();
+
+    let x = |_: T| 3;
+    x(t)
+}
+
+// Closure uses generic parameter as upvar.
+#[rustc_polymorphize_error]
+pub fn used_upvar<T: Default>() -> T {
+    let x: T = Default::default();
+
+    let y = || x;
+    y()
+}
+
+// Closure uses generic parameter in substitutions to another function.
+#[rustc_polymorphize_error]
+pub fn used_substs<T>() -> u32 {
+    let x = || unused::<T>();
+    x()
+}
+
+struct Foo<F>(F);
+
+impl<F: Default> Foo<F> {
+    // Function has an unused generic parameter from impl and fn.
+    #[rustc_polymorphize_error]
+    pub fn unused_all<G: Default>() -> u32 {
+        //~^ ERROR item has unused generic parameters
+        let add_one = |x: u32| x + 1;
+        //~^ ERROR item has unused generic parameters
+        add_one(3)
+    }
+
+    // Function uses generic parameter from impl and fn in closure.
+    #[rustc_polymorphize_error]
+    pub fn used_both<G: Default>() -> u32 {
+        let add_one = |x: u32| {
+            let _: F = Default::default();
+            let _: G = Default::default();
+            x + 1
+        };
+
+        add_one(3)
+    }
+
+    // Function uses generic parameter from fn in closure.
+    #[rustc_polymorphize_error]
+    pub fn used_fn<G: Default>() -> u32 {
+        //~^ ERROR item has unused generic parameters
+        let add_one = |x: u32| {
+            //~^ ERROR item has unused generic parameters
+            let _: G = Default::default();
+            x + 1
+        };
+
+        add_one(3)
+    }
+
+    // Function uses generic parameter from impl in closure.
+    #[rustc_polymorphize_error]
+    pub fn used_impl<G: Default>() -> u32 {
+        //~^ ERROR item has unused generic parameters
+        let add_one = |x: u32| {
+            //~^ ERROR item has unused generic parameters
+            let _: F = Default::default();
+            x + 1
+        };
+
+        add_one(3)
+    }
+
+    // Closure uses generic parameter in substitutions to another function.
+    #[rustc_polymorphize_error]
+    pub fn used_substs() -> u32 {
+        let x = || unused::<F>();
+        x()
+    }
+}
+
+fn main() {
+    no_parameters();
+    let _ = unused::<u32>();
+    let _ = used_parent::<u32>();
+    let _ = used_binding_value::<u32>();
+    let _ = used_binding_generic::<u32>();
+    let _ = used_argument(3u32);
+    let _ = used_argument_closure::<u32>();
+    let _ = used_upvar::<u32>();
+    let _ = used_substs::<u32>();
+
+    let _ = Foo::<u32>::unused_all::<u32>();
+    let _ = Foo::<u32>::used_both::<u32>();
+    let _ = Foo::<u32>::used_impl::<u32>();
+    let _ = Foo::<u32>::used_fn::<u32>();
+    let _ = Foo::<u32>::used_substs();
+}
diff --git a/src/test/ui/polymorphization/type_parameters/closures.stderr b/src/test/ui/polymorphization/type_parameters/closures.stderr
new file mode 100644
index 00000000000..d68e6e25a1e
--- /dev/null
+++ b/src/test/ui/polymorphization/type_parameters/closures.stderr
@@ -0,0 +1,90 @@
+error: item has unused generic parameters
+  --> $DIR/closures.rs:18:19
+   |
+LL | pub fn unused<T>() -> u32 {
+   |               - generic parameter `T` is unused
+...
+LL |     let add_one = |x: u32| x + 1;
+   |                   ^^^^^^^^^^^^^^
+
+error: item has unused generic parameters
+  --> $DIR/closures.rs:15:8
+   |
+LL | pub fn unused<T>() -> u32 {
+   |        ^^^^^^ - generic parameter `T` is unused
+
+error: item has unused generic parameters
+  --> $DIR/closures.rs:27:19
+   |
+LL | pub fn used_parent<T: Default>() -> u32 {
+   |                    - generic parameter `T` is unused
+LL |     let _: T = Default::default();
+LL |     let add_one = |x: u32| x + 1;
+   |                   ^^^^^^^^^^^^^^
+
+error: item has unused generic parameters
+  --> $DIR/closures.rs:93:23
+   |
+LL | impl<F: Default> Foo<F> {
+   |      - generic parameter `F` is unused
+...
+LL |     pub fn unused_all<G: Default>() -> u32 {
+   |                       - generic parameter `G` is unused
+LL |
+LL |         let add_one = |x: u32| x + 1;
+   |                       ^^^^^^^^^^^^^^
+
+error: item has unused generic parameters
+  --> $DIR/closures.rs:91:12
+   |
+LL | impl<F: Default> Foo<F> {
+   |      - generic parameter `F` is unused
+...
+LL |     pub fn unused_all<G: Default>() -> u32 {
+   |            ^^^^^^^^^^ - generic parameter `G` is unused
+
+error: item has unused generic parameters
+  --> $DIR/closures.rs:127:23
+   |
+LL |       pub fn used_impl<G: Default>() -> u32 {
+   |                        - generic parameter `G` is unused
+LL |
+LL |           let add_one = |x: u32| {
+   |  _______________________^
+LL | |
+LL | |             let _: F = Default::default();
+LL | |             x + 1
+LL | |         };
+   | |_________^
+
+error: item has unused generic parameters
+  --> $DIR/closures.rs:125:12
+   |
+LL |     pub fn used_impl<G: Default>() -> u32 {
+   |            ^^^^^^^^^ - generic parameter `G` is unused
+
+error: item has unused generic parameters
+  --> $DIR/closures.rs:114:23
+   |
+LL |   impl<F: Default> Foo<F> {
+   |        - generic parameter `F` is unused
+...
+LL |           let add_one = |x: u32| {
+   |  _______________________^
+LL | |
+LL | |             let _: G = Default::default();
+LL | |             x + 1
+LL | |         };
+   | |_________^
+
+error: item has unused generic parameters
+  --> $DIR/closures.rs:112:12
+   |
+LL | impl<F: Default> Foo<F> {
+   |      - generic parameter `F` is unused
+...
+LL |     pub fn used_fn<G: Default>() -> u32 {
+   |            ^^^^^^^
+
+error: aborting due to 9 previous errors
+
diff --git a/src/test/ui/polymorphization/type_parameters/functions.rs b/src/test/ui/polymorphization/type_parameters/functions.rs
new file mode 100644
index 00000000000..38f10148c2c
--- /dev/null
+++ b/src/test/ui/polymorphization/type_parameters/functions.rs
@@ -0,0 +1,95 @@
+// build-fail
+#![feature(rustc_attrs)]
+
+// This test checks that the polymorphization analysis correctly detects unused type
+// parameters in functions.
+
+// Function doesn't have any generic parameters to be unused.
+#[rustc_polymorphize_error]
+pub fn no_parameters() {}
+
+// Function has an unused generic parameter.
+#[rustc_polymorphize_error]
+pub fn unused<T>() {
+    //~^ ERROR item has unused generic parameters
+}
+
+// Function uses generic parameter in value of a binding.
+#[rustc_polymorphize_error]
+pub fn used_binding_value<T: Default>() {
+    let _: T = Default::default();
+}
+
+// Function uses generic parameter in generic of a binding.
+#[rustc_polymorphize_error]
+pub fn used_binding_generic<T>() {
+    let _: Option<T> = None;
+}
+
+// Function uses generic parameter in argument.
+#[rustc_polymorphize_error]
+pub fn used_argument<T>(_: T) {}
+
+// Function uses generic parameter in substitutions to another function.
+#[rustc_polymorphize_error]
+pub fn used_substs<T>() {
+    unused::<T>()
+}
+
+struct Foo<F>(F);
+
+impl<F: Default> Foo<F> {
+    // Function has an unused generic parameter from impl.
+    #[rustc_polymorphize_error]
+    pub fn unused_impl() {
+        //~^ ERROR item has unused generic parameters
+    }
+
+    // Function has an unused generic parameter from impl and fn.
+    #[rustc_polymorphize_error]
+    pub fn unused_both<G: Default>() {
+        //~^ ERROR item has unused generic parameters
+    }
+
+    // Function uses generic parameter from impl.
+    #[rustc_polymorphize_error]
+    pub fn used_impl() {
+        let _: F = Default::default();
+    }
+
+    // Function uses generic parameter from impl.
+    #[rustc_polymorphize_error]
+    pub fn used_fn<G: Default>() {
+        //~^ ERROR item has unused generic parameters
+        let _: G = Default::default();
+    }
+
+    // Function uses generic parameter from impl.
+    #[rustc_polymorphize_error]
+    pub fn used_both<G: Default>() {
+        let _: F = Default::default();
+        let _: G = Default::default();
+    }
+
+    // Function uses generic parameter in substitutions to another function.
+    #[rustc_polymorphize_error]
+    pub fn used_substs() {
+        unused::<F>()
+    }
+}
+
+fn main() {
+    no_parameters();
+    unused::<u32>();
+    used_binding_value::<u32>();
+    used_binding_generic::<u32>();
+    used_argument(3u32);
+    used_substs::<u32>();
+
+    Foo::<u32>::unused_impl();
+    Foo::<u32>::unused_both::<u32>();
+    Foo::<u32>::used_impl();
+    Foo::<u32>::used_fn::<u32>();
+    Foo::<u32>::used_both::<u32>();
+    Foo::<u32>::used_substs();
+}
diff --git a/src/test/ui/polymorphization/type_parameters/functions.stderr b/src/test/ui/polymorphization/type_parameters/functions.stderr
new file mode 100644
index 00000000000..be4c6576e96
--- /dev/null
+++ b/src/test/ui/polymorphization/type_parameters/functions.stderr
@@ -0,0 +1,35 @@
+error: item has unused generic parameters
+  --> $DIR/functions.rs:13:8
+   |
+LL | pub fn unused<T>() {
+   |        ^^^^^^ - generic parameter `T` is unused
+
+error: item has unused generic parameters
+  --> $DIR/functions.rs:44:12
+   |
+LL | impl<F: Default> Foo<F> {
+   |      - generic parameter `F` is unused
+...
+LL |     pub fn unused_impl() {
+   |            ^^^^^^^^^^^
+
+error: item has unused generic parameters
+  --> $DIR/functions.rs:50:12
+   |
+LL | impl<F: Default> Foo<F> {
+   |      - generic parameter `F` is unused
+...
+LL |     pub fn unused_both<G: Default>() {
+   |            ^^^^^^^^^^^ - generic parameter `G` is unused
+
+error: item has unused generic parameters
+  --> $DIR/functions.rs:62:12
+   |
+LL | impl<F: Default> Foo<F> {
+   |      - generic parameter `F` is unused
+...
+LL |     pub fn used_fn<G: Default>() {
+   |            ^^^^^^^
+
+error: aborting due to 4 previous errors
+
diff --git a/src/test/ui/polymorphization/unsized_cast.rs b/src/test/ui/polymorphization/unsized_cast.rs
new file mode 100644
index 00000000000..d2f3d4f13cd
--- /dev/null
+++ b/src/test/ui/polymorphization/unsized_cast.rs
@@ -0,0 +1,28 @@
+// build-fail
+#![feature(fn_traits, rustc_attrs, unboxed_closures)]
+
+// This test checks that the polymorphization analysis considers a closure
+// as using all generic parameters if it does an unsizing cast.
+
+#[rustc_polymorphize_error]
+fn foo<T: Default>() {
+    let _: T = Default::default();
+    (|| Box::new(|| {}) as Box<dyn Fn()>)();
+    //~^ ERROR item has unused generic parameters
+    //~^^ ERROR item has unused generic parameters
+}
+
+#[rustc_polymorphize_error]
+fn foo2<T: Default>() {
+    let _: T = Default::default();
+    (|| {
+        let call: extern "rust-call" fn(_, _) = Fn::call;
+        call(&|| {}, ());
+        //~^ ERROR item has unused generic parameters
+    })();
+}
+
+fn main() {
+    foo::<u32>();
+    foo2::<u32>();
+}
diff --git a/src/test/ui/polymorphization/unsized_cast.stderr b/src/test/ui/polymorphization/unsized_cast.stderr
new file mode 100644
index 00000000000..b8b96bbdf15
--- /dev/null
+++ b/src/test/ui/polymorphization/unsized_cast.stderr
@@ -0,0 +1,29 @@
+error: item has unused generic parameters
+  --> $DIR/unsized_cast.rs:10:18
+   |
+LL | fn foo<T: Default>() {
+   |        - generic parameter `T` is unused
+LL |     let _: T = Default::default();
+LL |     (|| Box::new(|| {}) as Box<dyn Fn()>)();
+   |                  ^^^^^
+
+error: item has unused generic parameters
+  --> $DIR/unsized_cast.rs:10:5
+   |
+LL | fn foo<T: Default>() {
+   |        - generic parameter `T` is unused
+LL |     let _: T = Default::default();
+LL |     (|| Box::new(|| {}) as Box<dyn Fn()>)();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: item has unused generic parameters
+  --> $DIR/unsized_cast.rs:20:15
+   |
+LL | fn foo2<T: Default>() {
+   |         - generic parameter `T` is unused
+...
+LL |         call(&|| {}, ());
+   |               ^^^^^
+
+error: aborting due to 3 previous errors
+
diff --git a/src/tools/clippy/clippy_lints/src/utils/mod.rs b/src/tools/clippy/clippy_lints/src/utils/mod.rs
index 4b163fba528..a4bee1c2780 100644
--- a/src/tools/clippy/clippy_lints/src/utils/mod.rs
+++ b/src/tools/clippy/clippy_lints/src/utils/mod.rs
@@ -1346,7 +1346,7 @@ pub fn fn_has_unsatisfiable_preds(cx: &LateContext<'_>, did: DefId) -> bool {
             .predicates
             .iter()
             .filter_map(|(p, _)| if p.is_global() { Some(*p) } else { None });
-    !traits::normalize_and_test_predicates(
+    traits::impossible_predicates(
         cx.tcx,
         traits::elaborate_predicates(cx.tcx, predicates)
             .map(|o| o.predicate)