Auto merge of #89514 - davidtwco:polymorphize-shims-and-predicates, r=lcnr

polymorphization: shims and predicates

Supersedes #75737 and #75414. This pull request includes up some changes to polymorphization which hadn't landed previously and gets stage2 bootstrapping and the test suite passing when polymorphization is enabled. There are still issues with `type_id` and polymorphization to investigate but this should get polymorphization in a reasonable state to work on.

- #75737 and #75414 both worked but were blocked on having the rest of the test suite pass (with polymorphization enabled) with and without the PRs. It makes more sense to just land these so that the changes are in.
- #75737's changes remove the restriction of `InstanceDef::Item` on polymorphization, so that shims can now be polymorphized. This won't have much of an effect until polymorphization's analysis is more advanced, but it doesn't hurt.
- #75414's changes remove all logic which marks parameters as used based on their presence in predicates - given #75675, this will enable more polymorphization and avoid the symbol clashes that predicate logic previously sidestepped.
- Polymorphization now explicitly checks (and skips) foreign items, this is necessary for stage2 bootstrapping to work when polymorphization is enabled.
- The conditional determining the emission of a note adding context to a post-monomorphization error has been modified. Polymorphization results in `optimized_mir` running for shims during collection where that wouldn't happen previously, some errors are emitted during `optimized_mir` and these were considered post-monomorphization errors with the existing logic (more errors and shims have a `DefId` coming from the std crate, not the local crate), adding a note that resulted in tests failing. It isn't particularly feasible to change where polymorphization runs or prevent it from using `optimized_mir`, so it seemed more reasonable to not change the conditional.
- `characteristic_def_id_of_type` was being invoked during partitioning for self types of impl blocks which had projections that depended on the value of unused generic parameters of a function - this caused a ICE in a debuginfo test. If partitioning is enabled and the instance needs substitution then this is skipped. That test still fails for me locally, but not with an ICE, but it fails in a fresh checkout too, so 🤷‍♂️.

r? `@lcnr`

9 files changed, 139 insertions, 107 deletions

diff --git a/compiler/rustc_const_eval/src/interpret/util.rs b/compiler/rustc_const_eval/src/interpret/util.rs
index eb0fdebb665..a16388d5de2 100644
--- a/compiler/rustc_const_eval/src/interpret/util.rs
+++ b/compiler/rustc_const_eval/src/interpret/util.rs
@@ -35,7 +35,8 @@ where
                 ty::Closure(def_id, substs)
                 | ty::Generator(def_id, substs, ..)
                 | ty::FnDef(def_id, substs) => {
-                    let unused_params = self.tcx.unused_generic_params(def_id);
+                    let instance = ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id));
+                    let unused_params = self.tcx.unused_generic_params(instance);
                     for (index, subst) in substs.into_iter().enumerate() {
                         let index = index
                             .try_into()
diff --git a/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs b/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs
index 4e7f85d2c37..e12f049a90b 100644
--- a/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs
+++ b/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs
@@ -83,6 +83,12 @@ impl IntoArgs for (CrateNum, DefId) {
     }
 }
 
+impl IntoArgs for ty::InstanceDef<'tcx> {
+    fn into_args(self) -> (DefId, DefId) {
+        (self.def_id(), self.def_id())
+    }
+}
+
 provide! { <'tcx> tcx, def_id, other, cdata,
     type_of => { cdata.get_type(def_id.index, tcx) }
     generics_of => { cdata.get_generics(def_id.index, tcx.sess) }
diff --git a/compiler/rustc_metadata/src/rmeta/encoder.rs b/compiler/rustc_metadata/src/rmeta/encoder.rs
index dacb1e4029c..20f7b059b56 100644
--- a/compiler/rustc_metadata/src/rmeta/encoder.rs
+++ b/compiler/rustc_metadata/src/rmeta/encoder.rs
@@ -1319,7 +1319,9 @@ impl EncodeContext<'a, 'tcx> {
             }
             record!(self.tables.promoted_mir[def_id.to_def_id()] <- self.tcx.promoted_mir(def_id));
 
-            let unused = self.tcx.unused_generic_params(def_id);
+            let instance =
+                ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id.to_def_id()));
+            let unused = self.tcx.unused_generic_params(instance);
             if !unused.is_empty() {
                 record!(self.tables.unused_generic_params[def_id.to_def_id()] <- unused);
             }
diff --git a/compiler/rustc_middle/src/mir/mono.rs b/compiler/rustc_middle/src/mir/mono.rs
index 67a20d72905..06b42320049 100644
--- a/compiler/rustc_middle/src/mir/mono.rs
+++ b/compiler/rustc_middle/src/mir/mono.rs
@@ -47,6 +47,14 @@ pub enum MonoItem<'tcx> {
 }
 
 impl<'tcx> MonoItem<'tcx> {
+    /// Returns `true` if the mono item is user-defined (i.e. not compiler-generated, like shims).
+    pub fn is_user_defined(&self) -> bool {
+        match *self {
+            MonoItem::Fn(instance) => matches!(instance.def, InstanceDef::Item(..)),
+            MonoItem::Static(..) | MonoItem::GlobalAsm(..) => true,
+        }
+    }
+
     pub fn size_estimate(&self, tcx: TyCtxt<'tcx>) -> usize {
         match *self {
             MonoItem::Fn(instance) => {
diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs
index e3eda8483b6..4145cbd4249 100644
--- a/compiler/rustc_middle/src/query/mod.rs
+++ b/compiler/rustc_middle/src/query/mod.rs
@@ -1558,11 +1558,11 @@ rustc_queries! {
     query codegen_unit(_: Symbol) -> &'tcx CodegenUnit<'tcx> {
         desc { "codegen_unit" }
     }
-    query unused_generic_params(key: DefId) -> FiniteBitSet<u32> {
-        cache_on_disk_if { key.is_local() }
+    query unused_generic_params(key: ty::InstanceDef<'tcx>) -> FiniteBitSet<u32> {
+        cache_on_disk_if { key.def_id().is_local() }
         desc {
             |tcx| "determining which generic parameters are unused by `{}`",
-                tcx.def_path_str(key)
+                tcx.def_path_str(key.def_id())
         }
     }
     query backend_optimization_level(_: ()) -> OptLevel {
diff --git a/compiler/rustc_middle/src/ty/instance.rs b/compiler/rustc_middle/src/ty/instance.rs
index 9b8247fd028..4b38105e447 100644
--- a/compiler/rustc_middle/src/ty/instance.rs
+++ b/compiler/rustc_middle/src/ty/instance.rs
@@ -152,6 +152,22 @@ impl<'tcx> InstanceDef<'tcx> {
         }
     }
 
+    /// Returns the `DefId` of instances which might not require codegen locally.
+    pub fn def_id_if_not_guaranteed_local_codegen(self) -> Option<DefId> {
+        match self {
+            ty::InstanceDef::Item(def) => Some(def.did),
+            ty::InstanceDef::DropGlue(def_id, Some(_)) => Some(def_id),
+            InstanceDef::VtableShim(..)
+            | InstanceDef::ReifyShim(..)
+            | InstanceDef::FnPtrShim(..)
+            | InstanceDef::Virtual(..)
+            | InstanceDef::Intrinsic(..)
+            | InstanceDef::ClosureOnceShim { .. }
+            | InstanceDef::DropGlue(..)
+            | InstanceDef::CloneShim(..) => None,
+        }
+    }
+
     #[inline]
     pub fn with_opt_param(self) -> ty::WithOptConstParam<DefId> {
         match self {
@@ -567,29 +583,26 @@ impl<'tcx> Instance<'tcx> {
             return self;
         }
 
-        if let InstanceDef::Item(def) = self.def {
-            let polymorphized_substs = polymorphize(tcx, def.did, self.substs);
-            debug!("polymorphize: self={:?} polymorphized_substs={:?}", self, polymorphized_substs);
-            Self { def: self.def, substs: polymorphized_substs }
-        } else {
-            self
-        }
+        let polymorphized_substs = polymorphize(tcx, self.def, self.substs);
+        debug!("polymorphize: self={:?} polymorphized_substs={:?}", self, polymorphized_substs);
+        Self { def: self.def, substs: polymorphized_substs }
     }
 }
 
 fn polymorphize<'tcx>(
     tcx: TyCtxt<'tcx>,
-    def_id: DefId,
+    instance: ty::InstanceDef<'tcx>,
     substs: SubstsRef<'tcx>,
 ) -> SubstsRef<'tcx> {
-    debug!("polymorphize({:?}, {:?})", def_id, substs);
-    let unused = tcx.unused_generic_params(def_id);
+    debug!("polymorphize({:?}, {:?})", instance, substs);
+    let unused = tcx.unused_generic_params(instance);
     debug!("polymorphize: unused={:?}", unused);
 
     // If this is a closure or generator then we need to handle the case where another closure
     // from the function is captured as an upvar and hasn't been polymorphized. In this case,
     // the unpolymorphized upvar closure would result in a polymorphized closure producing
     // multiple mono items (and eventually symbol clashes).
+    let def_id = instance.def_id();
     let upvars_ty = if tcx.is_closure(def_id) {
         Some(substs.as_closure().tupled_upvars_ty())
     } else if tcx.type_of(def_id).is_generator() {
@@ -613,7 +626,11 @@ fn polymorphize<'tcx>(
             debug!("fold_ty: ty={:?}", ty);
             match ty.kind {
                 ty::Closure(def_id, substs) => {
-                    let polymorphized_substs = polymorphize(self.tcx, def_id, substs);
+                    let polymorphized_substs = polymorphize(
+                        self.tcx,
+                        ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id)),
+                        substs,
+                    );
                     if substs == polymorphized_substs {
                         ty
                     } else {
@@ -621,7 +638,11 @@ fn polymorphize<'tcx>(
                     }
                 }
                 ty::Generator(def_id, substs, movability) => {
-                    let polymorphized_substs = polymorphize(self.tcx, def_id, substs);
+                    let polymorphized_substs = polymorphize(
+                        self.tcx,
+                        ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id)),
+                        substs,
+                    );
                     if substs == polymorphized_substs {
                         ty
                     } else {
diff --git a/compiler/rustc_monomorphize/src/collector.rs b/compiler/rustc_monomorphize/src/collector.rs
index f06426308a2..5147408210e 100644
--- a/compiler/rustc_monomorphize/src/collector.rs
+++ b/compiler/rustc_monomorphize/src/collector.rs
@@ -450,7 +450,9 @@ fn collect_items_rec<'tcx>(
     // involving a dependency, and the lack of context is confusing) in this MVP, we focus on
     // diagnostics on edges crossing a crate boundary: the collected mono items which are not
     // defined in the local crate.
-    if tcx.sess.diagnostic().err_count() > error_count && starting_point.node.krate() != LOCAL_CRATE
+    if tcx.sess.diagnostic().err_count() > error_count
+        && starting_point.node.krate() != LOCAL_CRATE
+        && starting_point.node.is_user_defined()
     {
         let formatted_item = with_no_trimmed_paths(|| starting_point.node.to_string());
         tcx.sess.span_note_without_error(
@@ -934,21 +936,13 @@ 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.
+/// Returns `true` if we should codegen an instance in the local crate, or returns `false` if we
+/// can just link to the upstream crate and therefore don't need a mono item.
 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,
-        ty::InstanceDef::VtableShim(..)
-        | ty::InstanceDef::ReifyShim(..)
-        | ty::InstanceDef::ClosureOnceShim { .. }
-        | ty::InstanceDef::Virtual(..)
-        | ty::InstanceDef::FnPtrShim(..)
-        | ty::InstanceDef::DropGlue(..)
-        | ty::InstanceDef::Intrinsic(_)
-        | ty::InstanceDef::CloneShim(..) => return true,
+    let def_id = if let Some(def_id) = instance.def.def_id_if_not_guaranteed_local_codegen() {
+        def_id
+    } else {
+        return true;
     };
 
     if tcx.is_foreign_item(def_id) {
diff --git a/compiler/rustc_monomorphize/src/partitioning/default.rs b/compiler/rustc_monomorphize/src/partitioning/default.rs
index 429ed53d379..be682082258 100644
--- a/compiler/rustc_monomorphize/src/partitioning/default.rs
+++ b/compiler/rustc_monomorphize/src/partitioning/default.rs
@@ -9,7 +9,7 @@ use rustc_middle::middle::exported_symbols::SymbolExportLevel;
 use rustc_middle::mir::mono::{CodegenUnit, CodegenUnitNameBuilder, Linkage, Visibility};
 use rustc_middle::mir::mono::{InstantiationMode, MonoItem};
 use rustc_middle::ty::print::characteristic_def_id_of_type;
-use rustc_middle::ty::{self, DefIdTree, InstanceDef, TyCtxt};
+use rustc_middle::ty::{self, fold::TypeFoldable, DefIdTree, InstanceDef, TyCtxt};
 use rustc_span::symbol::Symbol;
 
 use super::PartitioningCx;
@@ -300,14 +300,21 @@ fn characteristic_def_id_of_mono_item<'tcx>(
                     // call it.
                     return None;
                 }
-                // This is a method within an impl, find out what the self-type is:
-                let impl_self_ty = tcx.subst_and_normalize_erasing_regions(
-                    instance.substs,
-                    ty::ParamEnv::reveal_all(),
-                    tcx.type_of(impl_def_id),
-                );
-                if let Some(def_id) = characteristic_def_id_of_type(impl_self_ty) {
-                    return Some(def_id);
+
+                // When polymorphization is enabled, methods which do not depend on their generic
+                // parameters, but the self-type of their impl block do will fail to normalize.
+                if !tcx.sess.opts.debugging_opts.polymorphize
+                    || !instance.definitely_needs_subst(tcx)
+                {
+                    // This is a method within an impl, find out what the self-type is:
+                    let impl_self_ty = tcx.subst_and_normalize_erasing_regions(
+                        instance.substs,
+                        ty::ParamEnv::reveal_all(),
+                        tcx.type_of(impl_def_id),
+                    );
+                    if let Some(def_id) = characteristic_def_id_of_type(impl_self_ty) {
+                        return Some(def_id);
+                    }
                 }
             }
 
diff --git a/compiler/rustc_monomorphize/src/polymorphize.rs b/compiler/rustc_monomorphize/src/polymorphize.rs
index 0f768b7819b..e6e4438b6d4 100644
--- a/compiler/rustc_monomorphize/src/polymorphize.rs
+++ b/compiler/rustc_monomorphize/src/polymorphize.rs
@@ -27,20 +27,23 @@ 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).
+/// Determine which generic parameters are used by the instance.
+///
+/// Returns a bitset where bits representing unused parameters are set (`is_empty` indicates all
+/// parameters are used).
 #[instrument(level = "debug", skip(tcx))]
-fn unused_generic_params(tcx: TyCtxt<'_>, def_id: DefId) -> FiniteBitSet<u32> {
+fn unused_generic_params<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    instance: ty::InstanceDef<'tcx>,
+) -> FiniteBitSet<u32> {
     if !tcx.sess.opts.debugging_opts.polymorphize {
         // If polymorphization disabled, then all parameters are used.
         return FiniteBitSet::new_empty();
     }
 
-    // Polymorphization results are stored in cross-crate metadata only when there are unused
-    // parameters, so assume that non-local items must have only used parameters (else this query
-    // would not be invoked, and the cross-crate metadata used instead).
-    if !def_id.is_local() {
+    let def_id = instance.def_id();
+    // Exit early if this instance should not be polymorphized.
+    if !should_polymorphize(tcx, def_id, instance) {
         return FiniteBitSet::new_empty();
     }
 
@@ -52,41 +55,25 @@ fn unused_generic_params(tcx: TyCtxt<'_>, def_id: DefId) -> FiniteBitSet<u32> {
         return FiniteBitSet::new_empty();
     }
 
-    // Exit early when there is no MIR available.
-    let context = tcx.hir().body_const_context(def_id.expect_local());
-    match context {
-        Some(ConstContext::ConstFn) | None if !tcx.is_mir_available(def_id) => {
-            debug!("no mir available");
-            return FiniteBitSet::new_empty();
-        }
-        Some(_) if !tcx.is_ctfe_mir_available(def_id) => {
-            debug!("no ctfe mir available");
-            return FiniteBitSet::new_empty();
-        }
-        _ => {}
-    }
-
     // Create a bitset with N rightmost ones for each parameter.
     let generics_count: u32 =
         generics.count().try_into().expect("more generic parameters than can fit into a `u32`");
     let mut unused_parameters = FiniteBitSet::<u32>::new_empty();
     unused_parameters.set_range(0..generics_count);
     debug!(?unused_parameters, "(start)");
+
     mark_used_by_default_parameters(tcx, def_id, generics, &mut unused_parameters);
     debug!(?unused_parameters, "(after default)");
 
     // Visit MIR and accumululate used generic parameters.
-    let body = match context {
+    let body = match tcx.hir().body_const_context(def_id.expect_local()) {
         // Const functions are actually called and should thus be considered for polymorphization
-        // via their runtime MIR
+        // via their runtime MIR.
         Some(ConstContext::ConstFn) | None => tcx.optimized_mir(def_id),
         Some(_) => tcx.mir_for_ctfe(def_id),
     };
     let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters: &mut unused_parameters };
     vis.visit_body(body);
-    debug!(?unused_parameters, "(after visitor)");
-
-    mark_used_by_predicates(tcx, def_id, &mut unused_parameters);
     debug!(?unused_parameters, "(end)");
 
     // Emit errors for debugging and testing if enabled.
@@ -97,6 +84,49 @@ fn unused_generic_params(tcx: TyCtxt<'_>, def_id: DefId) -> FiniteBitSet<u32> {
     unused_parameters
 }
 
+/// Returns `true` if the instance should be polymorphized.
+fn should_polymorphize<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    def_id: DefId,
+    instance: ty::InstanceDef<'tcx>,
+) -> bool {
+    // If an instance's MIR body is not polymorphic then the modified substitutions that are
+    // derived from polymorphization's result won't make any difference.
+    if !instance.has_polymorphic_mir_body() {
+        return false;
+    }
+
+    // Don't polymorphize intrinsics or virtual calls - calling `instance_mir` will panic.
+    if matches!(instance, ty::InstanceDef::Intrinsic(..) | ty::InstanceDef::Virtual(..)) {
+        return false;
+    }
+
+    // Polymorphization results are stored in cross-crate metadata only when there are unused
+    // parameters, so assume that non-local items must have only used parameters (else this query
+    // would not be invoked, and the cross-crate metadata used instead).
+    if !def_id.is_local() {
+        return false;
+    }
+
+    // Foreign items have no bodies to analyze.
+    if tcx.is_foreign_item(def_id) {
+        return false;
+    }
+
+    // Make sure there is MIR available.
+    match tcx.hir().body_const_context(def_id.expect_local()) {
+        Some(ConstContext::ConstFn) | None if !tcx.is_mir_available(def_id) => {
+            debug!("no mir available");
+            return false;
+        }
+        Some(_) if !tcx.is_ctfe_mir_available(def_id) => {
+            debug!("no ctfe mir available");
+            return false;
+        }
+        _ => true,
+    }
+}
+
 /// Some parameters are considered used-by-default, such as non-generic parameters and the dummy
 /// generic parameters from closures, this function marks them as used. `leaf_is_closure` should
 /// be `true` if the item that `unused_generic_params` was invoked on is a closure.
@@ -156,44 +186,6 @@ fn mark_used_by_default_parameters<'tcx>(
     }
 }
 
-/// Search the predicates on used generic parameters for any unused generic parameters, and mark
-/// those as used.
-#[instrument(level = "debug", skip(tcx, def_id))]
-fn mark_used_by_predicates<'tcx>(
-    tcx: TyCtxt<'tcx>,
-    def_id: DefId,
-    unused_parameters: &mut FiniteBitSet<u32>,
-) {
-    let def_id = tcx.closure_base_def_id(def_id);
-    let predicates = tcx.explicit_predicates_of(def_id);
-
-    let mut current_unused_parameters = FiniteBitSet::new_empty();
-    // Run to a fixed point to support `where T: Trait<U>, U: Trait<V>`, starting with an empty
-    // bit set so that this is skipped if all parameters are already used.
-    while current_unused_parameters != *unused_parameters {
-        debug!(?current_unused_parameters, ?unused_parameters);
-        current_unused_parameters = *unused_parameters;
-
-        for (predicate, _) in predicates.predicates {
-            // Consider all generic params in a predicate as used if any other parameter in the
-            // predicate is used.
-            let any_param_used = {
-                let mut vis = HasUsedGenericParams { tcx, unused_parameters };
-                predicate.visit_with(&mut vis).is_break()
-            };
-
-            if any_param_used {
-                let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters };
-                predicate.visit_with(&mut vis);
-            }
-        }
-    }
-
-    if let Some(parent) = predicates.parent {
-        mark_used_by_predicates(tcx, parent, unused_parameters);
-    }
-}
-
 /// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic
 /// parameter which was unused.
 #[instrument(level = "debug", skip(tcx, generics))]
@@ -243,7 +235,8 @@ impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> {
     /// a closure, generator or constant).
     #[instrument(level = "debug", skip(self, def_id, substs))]
     fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) {
-        let unused = self.tcx.unused_generic_params(def_id);
+        let instance = ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id));
+        let unused = self.tcx.unused_generic_params(instance);
         debug!(?self.unused_parameters, ?unused);
         for (i, arg) in substs.iter().enumerate() {
             let i = i.try_into().unwrap();