Auto merge of #81744 - rylev:overlapping-early-exit2, r=lcnr

Try fast_reject::simplify_type in coherence before doing full check

This is a reattempt at landing #69010 (by `@jonas-schievink).` The change adds a fast path for coherence checking to see if there's no way for types to unify since full coherence checking can be somewhat expensive.

This has big effects on code generated by the [`windows`](https://github.com/microsoft/windows-rs) which in some cases spends as much as 20% of compilation time in the `specialization_graph_of` query. In local benchmarks this took a compilation that previously took ~500 seconds down to ~380 seconds.

This is surely not going to make a difference on much smaller crates, so the question is whether it will have a negative impact. #69010 was closed because some of the perf suite crates did show small regressions.

Additional discussion of this issue is happening [here](https://rust-lang.zulipchat.com/#narrow/stream/247081-t-compiler.2Fperformance/topic/windows-rs.20perf).

2 files changed, 38 insertions, 1 deletions

diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs
index c1fa84dcb25..04cc4db0bcf 100644
--- a/compiler/rustc_middle/src/ty/sty.rs
+++ b/compiler/rustc_middle/src/ty/sty.rs
@@ -1845,6 +1845,15 @@ impl<'tcx> TyS<'tcx> {
         )
     }
 
+    /// Get the mutability of the reference or `None` when not a reference
+    #[inline]
+    pub fn ref_mutability(&self) -> Option<hir::Mutability> {
+        match self.kind() {
+            Ref(_, _, mutability) => Some(*mutability),
+            _ => None,
+        }
+    }
+
     #[inline]
     pub fn is_unsafe_ptr(&self) -> bool {
         matches!(self.kind(), RawPtr(_))
diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index 99b96f60964..e8ae1f44a36 100644
--- a/compiler/rustc_trait_selection/src/traits/coherence.rs
+++ b/compiler/rustc_trait_selection/src/traits/coherence.rs
@@ -11,7 +11,7 @@ use crate::traits::{self, Normalized, Obligation, ObligationCause, SelectionCont
 use rustc_hir::def_id::{DefId, LOCAL_CRATE};
 use rustc_middle::ty::fold::TypeFoldable;
 use rustc_middle::ty::subst::Subst;
-use rustc_middle::ty::{self, Ty, TyCtxt};
+use rustc_middle::ty::{self, fast_reject, Ty, TyCtxt};
 use rustc_span::symbol::sym;
 use rustc_span::DUMMY_SP;
 use std::iter;
@@ -67,6 +67,34 @@ where
            impl2_def_id={:?})",
         impl1_def_id, impl2_def_id,
     );
+    // Before doing expensive operations like entering an inference context, do
+    // a quick check via fast_reject to tell if the impl headers could possibly
+    // unify.
+    let impl1_ref = tcx.impl_trait_ref(impl1_def_id);
+    let impl2_ref = tcx.impl_trait_ref(impl2_def_id);
+
+    // Check if any of the input types definitely do not unify.
+    if impl1_ref
+        .iter()
+        .flat_map(|tref| tref.substs.types())
+        .zip(impl2_ref.iter().flat_map(|tref| tref.substs.types()))
+        .any(|(ty1, ty2)| {
+            let t1 = fast_reject::simplify_type(tcx, ty1, false);
+            let t2 = fast_reject::simplify_type(tcx, ty2, false);
+            if let (Some(t1), Some(t2)) = (t1, t2) {
+                // Simplified successfully
+                // Types cannot unify if they differ in their reference mutability or simplify to different types
+                t1 != t2 || ty1.ref_mutability() != ty2.ref_mutability()
+            } else {
+                // Types might unify
+                false
+            }
+        })
+    {
+        // Some types involved are definitely different, so the impls couldn't possibly overlap.
+        debug!("overlapping_impls: fast_reject early-exit");
+        return no_overlap();
+    }
 
     let overlaps = tcx.infer_ctxt().enter(|infcx| {
         let selcx = &mut SelectionContext::intercrate(&infcx);