Auto merge of #106977 - michaelwoerister:unord_id_collections, r=oli-obk

Use UnordMap and UnordSet for id collections (DefIdMap, LocalDefIdMap, etc)

This PR changes the `rustc_data_structures::define_id_collections!` macro to use `UnordMap` and `UnordSet` instead of `FxHashMap` and `FxHashSet`. This should account for a large portion of hash-maps being used in places where they can cause trouble.

The changes required are moderate but non-zero:
- In some places the collections are extracted into sorted vecs.
- There are a few instances where for-loops have been changed to extends.

~~Let's see what the performance impact is. With a bit more refactoring, we might be able to get rid of some of the additional sorting -- but the change set is already big enough. Unless there's a performance impact, I'd like to do further changes in subsequent PRs.~~

Performance does not seem to be negatively affected ([perf-run here](https://github.com/rust-lang/rust/pull/106977#issuecomment-1396776699)).

Part of [MCP 533](https://github.com/rust-lang/compiler-team/issues/533).

r? `@ghost`

18 files changed, 394 insertions, 119 deletions

diff --git a/compiler/rustc_codegen_llvm/src/coverageinfo/mapgen.rs b/compiler/rustc_codegen_llvm/src/coverageinfo/mapgen.rs
index 393bf30e9f8..22c61248b7d 100644
--- a/compiler/rustc_codegen_llvm/src/coverageinfo/mapgen.rs
+++ b/compiler/rustc_codegen_llvm/src/coverageinfo/mapgen.rs
@@ -8,7 +8,7 @@ use rustc_codegen_ssa::coverageinfo::map::{Counter, CounterExpression};
 use rustc_codegen_ssa::traits::{ConstMethods, CoverageInfoMethods};
 use rustc_data_structures::fx::FxIndexSet;
 use rustc_hir::def::DefKind;
-use rustc_hir::def_id::DefIdSet;
+use rustc_hir::def_id::DefId;
 use rustc_llvm::RustString;
 use rustc_middle::bug;
 use rustc_middle::middle::codegen_fn_attrs::CodegenFnAttrFlags;
@@ -291,7 +291,7 @@ fn add_unused_functions(cx: &CodegenCx<'_, '_>) {
 
     let ignore_unused_generics = tcx.sess.instrument_coverage_except_unused_generics();
 
-    let eligible_def_ids: DefIdSet = tcx
+    let eligible_def_ids: Vec<DefId> = tcx
         .mir_keys(())
         .iter()
         .filter_map(|local_def_id| {
@@ -317,7 +317,9 @@ fn add_unused_functions(cx: &CodegenCx<'_, '_>) {
 
     let codegenned_def_ids = tcx.codegened_and_inlined_items(());
 
-    for &non_codegenned_def_id in eligible_def_ids.difference(codegenned_def_ids) {
+    for non_codegenned_def_id in
+        eligible_def_ids.into_iter().filter(|id| !codegenned_def_ids.contains(id))
+    {
         let codegen_fn_attrs = tcx.codegen_fn_attrs(non_codegenned_def_id);
 
         // If a function is marked `#[no_coverage]`, then skip generating a
diff --git a/compiler/rustc_codegen_ssa/src/back/symbol_export.rs b/compiler/rustc_codegen_ssa/src/back/symbol_export.rs
index 8cb7d74b90d..57a99e74c21 100644
--- a/compiler/rustc_codegen_ssa/src/back/symbol_export.rs
+++ b/compiler/rustc_codegen_ssa/src/back/symbol_export.rs
@@ -173,11 +173,15 @@ fn exported_symbols_provider_local(
         return &[];
     }
 
-    let mut symbols: Vec<_> = tcx
-        .reachable_non_generics(LOCAL_CRATE)
-        .iter()
-        .map(|(&def_id, &info)| (ExportedSymbol::NonGeneric(def_id), info))
-        .collect();
+    // FIXME: Sorting this is unnecessary since we are sorting later anyway.
+    //        Can we skip the later sorting?
+    let mut symbols: Vec<_> = tcx.with_stable_hashing_context(|hcx| {
+        tcx.reachable_non_generics(LOCAL_CRATE)
+            .to_sorted(&hcx, true)
+            .into_iter()
+            .map(|(&def_id, &info)| (ExportedSymbol::NonGeneric(def_id), info))
+            .collect()
+    });
 
     if tcx.entry_fn(()).is_some() {
         let exported_symbol =
diff --git a/compiler/rustc_codegen_ssa/src/base.rs b/compiler/rustc_codegen_ssa/src/base.rs
index f7312f6fcda..32d3cfe6fc6 100644
--- a/compiler/rustc_codegen_ssa/src/base.rs
+++ b/compiler/rustc_codegen_ssa/src/base.rs
@@ -964,16 +964,19 @@ pub fn provide(providers: &mut Providers) {
         };
 
         let (defids, _) = tcx.collect_and_partition_mono_items(cratenum);
-        for id in &*defids {
+
+        let any_for_speed = defids.items().any(|id| {
             let CodegenFnAttrs { optimize, .. } = tcx.codegen_fn_attrs(*id);
             match optimize {
-                attr::OptimizeAttr::None => continue,
-                attr::OptimizeAttr::Size => continue,
-                attr::OptimizeAttr::Speed => {
-                    return for_speed;
-                }
+                attr::OptimizeAttr::None | attr::OptimizeAttr::Size => false,
+                attr::OptimizeAttr::Speed => true,
             }
+        });
+
+        if any_for_speed {
+            return for_speed;
         }
+
         tcx.sess.opts.optimize
     };
 }
diff --git a/compiler/rustc_data_structures/src/fx.rs b/compiler/rustc_data_structures/src/fx.rs
index 0d0c51b6819..9fce0e1e65c 100644
--- a/compiler/rustc_data_structures/src/fx.rs
+++ b/compiler/rustc_data_structures/src/fx.rs
@@ -11,8 +11,8 @@ pub type IndexEntry<'a, K, V> = indexmap::map::Entry<'a, K, V>;
 #[macro_export]
 macro_rules! define_id_collections {
     ($map_name:ident, $set_name:ident, $entry_name:ident, $key:ty) => {
-        pub type $map_name<T> = $crate::fx::FxHashMap<$key, T>;
-        pub type $set_name = $crate::fx::FxHashSet<$key>;
+        pub type $map_name<T> = $crate::unord::UnordMap<$key, T>;
+        pub type $set_name = $crate::unord::UnordSet<$key>;
         pub type $entry_name<'a, T> = $crate::fx::StdEntry<'a, $key, T>;
     };
 }
diff --git a/compiler/rustc_data_structures/src/unord.rs b/compiler/rustc_data_structures/src/unord.rs
index 14257e4d5c6..f35f18e51cb 100644
--- a/compiler/rustc_data_structures/src/unord.rs
+++ b/compiler/rustc_data_structures/src/unord.rs
@@ -6,13 +6,15 @@ use rustc_hash::{FxHashMap, FxHashSet};
 use smallvec::SmallVec;
 use std::{
     borrow::Borrow,
+    collections::hash_map::Entry,
     hash::Hash,
     iter::{Product, Sum},
+    ops::Index,
 };
 
 use crate::{
     fingerprint::Fingerprint,
-    stable_hasher::{HashStable, StableHasher, ToStableHashKey},
+    stable_hasher::{HashStable, StableHasher, StableOrd, ToStableHashKey},
 };
 
 /// `UnordItems` is the order-less version of `Iterator`. It only contains methods
@@ -38,17 +40,17 @@ impl<T, I: Iterator<Item = T>> UnordItems<T, I> {
     }
 
     #[inline]
-    pub fn all<U, F: Fn(T) -> bool>(mut self, f: F) -> bool {
+    pub fn all<F: Fn(T) -> bool>(mut self, f: F) -> bool {
         self.0.all(f)
     }
 
     #[inline]
-    pub fn any<U, F: Fn(T) -> bool>(mut self, f: F) -> bool {
+    pub fn any<F: Fn(T) -> bool>(mut self, f: F) -> bool {
         self.0.any(f)
     }
 
     #[inline]
-    pub fn filter<U, F: Fn(&T) -> bool>(self, f: F) -> UnordItems<T, impl Iterator<Item = T>> {
+    pub fn filter<F: Fn(&T) -> bool>(self, f: F) -> UnordItems<T, impl Iterator<Item = T>> {
         UnordItems(self.0.filter(f))
     }
 
@@ -96,6 +98,15 @@ impl<T, I: Iterator<Item = T>> UnordItems<T, I> {
     pub fn count(self) -> usize {
         self.0.count()
     }
+
+    #[inline]
+    pub fn flat_map<U, F, O>(self, f: F) -> UnordItems<O, impl Iterator<Item = O>>
+    where
+        U: IntoIterator<Item = O>,
+        F: Fn(T) -> U,
+    {
+        UnordItems(self.0.flat_map(f))
+    }
 }
 
 impl<'a, T: Clone + 'a, I: Iterator<Item = &'a T>> UnordItems<&'a T, I> {
@@ -147,6 +158,7 @@ pub struct UnordSet<V: Eq + Hash> {
 }
 
 impl<V: Eq + Hash> Default for UnordSet<V> {
+    #[inline]
     fn default() -> Self {
         Self { inner: FxHashSet::default() }
     }
@@ -178,7 +190,16 @@ impl<V: Eq + Hash> UnordSet<V> {
     }
 
     #[inline]
-    pub fn items(&self) -> UnordItems<&V, impl Iterator<Item = &V>> {
+    pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> bool
+    where
+        V: Borrow<Q>,
+        Q: Hash + Eq,
+    {
+        self.inner.remove(k)
+    }
+
+    #[inline]
+    pub fn items<'a>(&'a self) -> UnordItems<&'a V, impl Iterator<Item = &'a V>> {
         UnordItems(self.inner.iter())
     }
 
@@ -187,20 +208,75 @@ impl<V: Eq + Hash> UnordSet<V> {
         UnordItems(self.inner.into_iter())
     }
 
+    /// Returns the items of this set in stable sort order (as defined by `ToStableHashKey`).
+    ///
+    /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
+    /// [slice::sort_unstable_by_key] will be used for sorting the vec. Use
+    /// `cache_sort_key` when the [ToStableHashKey::to_stable_hash_key] implementation
+    /// for `V` is expensive (e.g. a `DefId -> DefPathHash` lookup).
+    #[inline]
+    pub fn to_sorted<HCX>(&self, hcx: &HCX, cache_sort_key: bool) -> Vec<&V>
+    where
+        V: ToStableHashKey<HCX>,
+    {
+        to_sorted_vec(hcx, self.inner.iter(), cache_sort_key, |&x| x)
+    }
+
+    /// Returns the items of this set in stable sort order (as defined by
+    /// `StableOrd`). This method is much more efficient than
+    /// `into_sorted` because it does not need to transform keys to their
+    /// `ToStableHashKey` equivalent.
+    #[inline]
+    pub fn to_sorted_stable_ord(&self) -> Vec<V>
+    where
+        V: Ord + StableOrd + Copy,
+    {
+        let mut items: Vec<V> = self.inner.iter().copied().collect();
+        items.sort_unstable();
+        items
+    }
+
+    /// Returns the items of this set in stable sort order (as defined by `ToStableHashKey`).
+    ///
+    /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
+    /// [slice::sort_unstable_by_key] will be used for sorting the vec. Use
+    /// `cache_sort_key` when the [ToStableHashKey::to_stable_hash_key] implementation
+    /// for `V` is expensive (e.g. a `DefId -> DefPathHash` lookup).
+    #[inline]
+    pub fn into_sorted<HCX>(self, hcx: &HCX, cache_sort_key: bool) -> Vec<V>
+    where
+        V: ToStableHashKey<HCX>,
+    {
+        to_sorted_vec(hcx, self.inner.into_iter(), cache_sort_key, |x| x)
+    }
+
     // We can safely extend this UnordSet from a set of unordered values because that
     // won't expose the internal ordering anywhere.
     #[inline]
     pub fn extend<I: Iterator<Item = V>>(&mut self, items: UnordItems<V, I>) {
         self.inner.extend(items.0)
     }
+
+    #[inline]
+    pub fn clear(&mut self) {
+        self.inner.clear();
+    }
 }
 
 impl<V: Hash + Eq> Extend<V> for UnordSet<V> {
+    #[inline]
     fn extend<T: IntoIterator<Item = V>>(&mut self, iter: T) {
         self.inner.extend(iter)
     }
 }
 
+impl<V: Hash + Eq> FromIterator<V> for UnordSet<V> {
+    #[inline]
+    fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
+        UnordSet { inner: FxHashSet::from_iter(iter) }
+    }
+}
+
 impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordSet<V> {
     #[inline]
     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
@@ -223,17 +299,33 @@ pub struct UnordMap<K: Eq + Hash, V> {
 }
 
 impl<K: Eq + Hash, V> Default for UnordMap<K, V> {
+    #[inline]
     fn default() -> Self {
         Self { inner: FxHashMap::default() }
     }
 }
 
 impl<K: Hash + Eq, V> Extend<(K, V)> for UnordMap<K, V> {
+    #[inline]
     fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
         self.inner.extend(iter)
     }
 }
 
+impl<K: Hash + Eq, V> FromIterator<(K, V)> for UnordMap<K, V> {
+    #[inline]
+    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
+        UnordMap { inner: FxHashMap::from_iter(iter) }
+    }
+}
+
+impl<K: Hash + Eq, V, I: Iterator<Item = (K, V)>> From<UnordItems<(K, V), I>> for UnordMap<K, V> {
+    #[inline]
+    fn from(items: UnordItems<(K, V), I>) -> Self {
+        UnordMap { inner: FxHashMap::from_iter(items.0) }
+    }
+}
+
 impl<K: Eq + Hash, V> UnordMap<K, V> {
     #[inline]
     pub fn len(&self) -> usize {
@@ -255,7 +347,44 @@ impl<K: Eq + Hash, V> UnordMap<K, V> {
     }
 
     #[inline]
-    pub fn items(&self) -> UnordItems<(&K, &V), impl Iterator<Item = (&K, &V)>> {
+    pub fn is_empty(&self) -> bool {
+        self.inner.is_empty()
+    }
+
+    #[inline]
+    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
+        self.inner.entry(key)
+    }
+
+    #[inline]
+    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
+    where
+        K: Borrow<Q>,
+        Q: Hash + Eq,
+    {
+        self.inner.get(k)
+    }
+
+    #[inline]
+    pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
+    where
+        K: Borrow<Q>,
+        Q: Hash + Eq,
+    {
+        self.inner.get_mut(k)
+    }
+
+    #[inline]
+    pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
+    where
+        K: Borrow<Q>,
+        Q: Hash + Eq,
+    {
+        self.inner.remove(k)
+    }
+
+    #[inline]
+    pub fn items<'a>(&'a self) -> UnordItems<(&'a K, &'a V), impl Iterator<Item = (&'a K, &'a V)>> {
         UnordItems(self.inner.iter())
     }
 
@@ -270,6 +399,77 @@ impl<K: Eq + Hash, V> UnordMap<K, V> {
     pub fn extend<I: Iterator<Item = (K, V)>>(&mut self, items: UnordItems<(K, V), I>) {
         self.inner.extend(items.0)
     }
+
+    /// Returns the entries of this map in stable sort order (as defined by `ToStableHashKey`).
+    ///
+    /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
+    /// [slice::sort_unstable_by_key] will be used for sorting the vec. Use
+    /// `cache_sort_key` when the [ToStableHashKey::to_stable_hash_key] implementation
+    /// for `K` is expensive (e.g. a `DefId -> DefPathHash` lookup).
+    #[inline]
+    pub fn to_sorted<HCX>(&self, hcx: &HCX, cache_sort_key: bool) -> Vec<(&K, &V)>
+    where
+        K: ToStableHashKey<HCX>,
+    {
+        to_sorted_vec(hcx, self.inner.iter(), cache_sort_key, |&(k, _)| k)
+    }
+
+    /// Returns the entries of this map in stable sort order (as defined by `StableOrd`).
+    /// This method can be much more efficient than `into_sorted` because it does not need
+    /// to transform keys to their `ToStableHashKey` equivalent.
+    #[inline]
+    pub fn to_sorted_stable_ord(&self) -> Vec<(K, &V)>
+    where
+        K: Ord + StableOrd + Copy,
+    {
+        let mut items: Vec<(K, &V)> = self.inner.iter().map(|(&k, v)| (k, v)).collect();
+        items.sort_unstable_by_key(|&(k, _)| k);
+        items
+    }
+
+    /// Returns the entries of this map in stable sort order (as defined by `ToStableHashKey`).
+    ///
+    /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
+    /// [slice::sort_unstable_by_key] will be used for sorting the vec. Use
+    /// `cache_sort_key` when the [ToStableHashKey::to_stable_hash_key] implementation
+    /// for `K` is expensive (e.g. a `DefId -> DefPathHash` lookup).
+    #[inline]
+    pub fn into_sorted<HCX>(self, hcx: &HCX, cache_sort_key: bool) -> Vec<(K, V)>
+    where
+        K: ToStableHashKey<HCX>,
+    {
+        to_sorted_vec(hcx, self.inner.into_iter(), cache_sort_key, |(k, _)| k)
+    }
+
+    /// Returns the values of this map in stable sort order (as defined by K's
+    /// `ToStableHashKey` implementation).
+    ///
+    /// The `cache_sort_key` parameter controls if [slice::sort_by_cached_key] or
+    /// [slice::sort_unstable_by_key] will be used for sorting the vec. Use
+    /// `cache_sort_key` when the [ToStableHashKey::to_stable_hash_key] implementation
+    /// for `K` is expensive (e.g. a `DefId -> DefPathHash` lookup).
+    #[inline]
+    pub fn values_sorted<HCX>(&self, hcx: &HCX, cache_sort_key: bool) -> impl Iterator<Item = &V>
+    where
+        K: ToStableHashKey<HCX>,
+    {
+        to_sorted_vec(hcx, self.inner.iter(), cache_sort_key, |&(k, _)| k)
+            .into_iter()
+            .map(|(_, v)| v)
+    }
+}
+
+impl<K, Q: ?Sized, V> Index<&Q> for UnordMap<K, V>
+where
+    K: Eq + Hash + Borrow<Q>,
+    Q: Eq + Hash,
+{
+    type Output = V;
+
+    #[inline]
+    fn index(&self, key: &Q) -> &V {
+        &self.inner[key]
+    }
 }
 
 impl<HCX, K: Hash + Eq + HashStable<HCX>, V: HashStable<HCX>> HashStable<HCX> for UnordMap<K, V> {
@@ -334,6 +534,12 @@ impl<T> Extend<T> for UnordBag<T> {
     }
 }
 
+impl<T, I: Iterator<Item = T>> From<UnordItems<T, I>> for UnordBag<T> {
+    fn from(value: UnordItems<T, I>) -> Self {
+        UnordBag { inner: Vec::from_iter(value.0) }
+    }
+}
+
 impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordBag<V> {
     #[inline]
     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
@@ -341,6 +547,27 @@ impl<HCX, V: Hash + Eq + HashStable<HCX>> HashStable<HCX> for UnordBag<V> {
     }
 }
 
+#[inline]
+fn to_sorted_vec<HCX, T, K, I>(
+    hcx: &HCX,
+    iter: I,
+    cache_sort_key: bool,
+    extract_key: fn(&T) -> &K,
+) -> Vec<T>
+where
+    I: Iterator<Item = T>,
+    K: ToStableHashKey<HCX>,
+{
+    let mut items: Vec<T> = iter.collect();
+    if cache_sort_key {
+        items.sort_by_cached_key(|x| extract_key(x).to_stable_hash_key(hcx));
+    } else {
+        items.sort_unstable_by_key(|x| extract_key(x).to_stable_hash_key(hcx));
+    }
+
+    items
+}
+
 fn hash_iter_order_independent<
     HCX,
     T: HashStable<HCX>,
diff --git a/compiler/rustc_hir_analysis/src/variance/solve.rs b/compiler/rustc_hir_analysis/src/variance/solve.rs
index eab01b20094..a17edb598ad 100644
--- a/compiler/rustc_hir_analysis/src/variance/solve.rs
+++ b/compiler/rustc_hir_analysis/src/variance/solve.rs
@@ -5,8 +5,7 @@
 //! optimal solution to the constraints. The final variance for each
 //! inferred is then written into the `variance_map` in the tcx.
 
-use rustc_data_structures::fx::FxHashMap;
-use rustc_hir::def_id::DefId;
+use rustc_hir::def_id::DefIdMap;
 use rustc_middle::ty;
 
 use super::constraints::*;
@@ -89,14 +88,12 @@ impl<'a, 'tcx> SolveContext<'a, 'tcx> {
         }
     }
 
-    fn create_map(&self) -> FxHashMap<DefId, &'tcx [ty::Variance]> {
+    fn create_map(&self) -> DefIdMap<&'tcx [ty::Variance]> {
         let tcx = self.terms_cx.tcx;
 
         let solutions = &self.solutions;
-        self.terms_cx
-            .inferred_starts
-            .iter()
-            .map(|(&def_id, &InferredIndex(start))| {
+        DefIdMap::from(self.terms_cx.inferred_starts.items().map(
+            |(&def_id, &InferredIndex(start))| {
                 let generics = tcx.generics_of(def_id);
                 let count = generics.count();
 
@@ -115,8 +112,8 @@ impl<'a, 'tcx> SolveContext<'a, 'tcx> {
                 }
 
                 (def_id.to_def_id(), &*variances)
-            })
-            .collect()
+            },
+        ))
     }
 
     fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance {
diff --git a/compiler/rustc_hir_typeck/src/writeback.rs b/compiler/rustc_hir_typeck/src/writeback.rs
index 30ef7f3ba29..250f4cd3f65 100644
--- a/compiler/rustc_hir_typeck/src/writeback.rs
+++ b/compiler/rustc_hir_typeck/src/writeback.rs
@@ -448,8 +448,11 @@ impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
         assert_eq!(fcx_typeck_results.hir_owner, self.typeck_results.hir_owner);
         let common_hir_owner = fcx_typeck_results.hir_owner;
 
-        for (id, origin) in fcx_typeck_results.closure_kind_origins().iter() {
-            let hir_id = hir::HirId { owner: common_hir_owner, local_id: *id };
+        let fcx_closure_kind_origins =
+            fcx_typeck_results.closure_kind_origins().items_in_stable_order();
+
+        for (local_id, origin) in fcx_closure_kind_origins {
+            let hir_id = hir::HirId { owner: common_hir_owner, local_id };
             let place_span = origin.0;
             let place = self.resolve(origin.1.clone(), &place_span);
             self.typeck_results.closure_kind_origins_mut().insert(hir_id, (place_span, place));
@@ -458,11 +461,12 @@ impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
 
     fn visit_coercion_casts(&mut self) {
         let fcx_typeck_results = self.fcx.typeck_results.borrow();
-        let fcx_coercion_casts = fcx_typeck_results.coercion_casts();
+
         assert_eq!(fcx_typeck_results.hir_owner, self.typeck_results.hir_owner);
 
+        let fcx_coercion_casts = fcx_typeck_results.coercion_casts().to_sorted_stable_ord();
         for local_id in fcx_coercion_casts {
-            self.typeck_results.set_coercion_cast(*local_id);
+            self.typeck_results.set_coercion_cast(local_id);
         }
     }
 
@@ -471,22 +475,15 @@ impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
         assert_eq!(fcx_typeck_results.hir_owner, self.typeck_results.hir_owner);
         let common_hir_owner = fcx_typeck_results.hir_owner;
 
-        let mut errors_buffer = Vec::new();
-        for (&local_id, c_ty) in fcx_typeck_results.user_provided_types().iter() {
-            let hir_id = hir::HirId { owner: common_hir_owner, local_id };
-
-            if cfg!(debug_assertions) && c_ty.needs_infer() {
-                span_bug!(
-                    hir_id.to_span(self.fcx.tcx),
-                    "writeback: `{:?}` has inference variables",
-                    c_ty
-                );
-            };
+        if self.rustc_dump_user_substs {
+            let sorted_user_provided_types =
+                fcx_typeck_results.user_provided_types().items_in_stable_order();
 
-            self.typeck_results.user_provided_types_mut().insert(hir_id, *c_ty);
+            let mut errors_buffer = Vec::new();
+            for (local_id, c_ty) in sorted_user_provided_types {
+                let hir_id = hir::HirId { owner: common_hir_owner, local_id };
 
-            if let ty::UserType::TypeOf(_, user_substs) = c_ty.value {
-                if self.rustc_dump_user_substs {
+                if let ty::UserType::TypeOf(_, user_substs) = c_ty.value {
                     // This is a unit-testing mechanism.
                     let span = self.tcx().hir().span(hir_id);
                     // We need to buffer the errors in order to guarantee a consistent
@@ -498,31 +495,49 @@ impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
                     err.buffer(&mut errors_buffer);
                 }
             }
-        }
 
-        if !errors_buffer.is_empty() {
-            errors_buffer.sort_by_key(|diag| diag.span.primary_span());
-            for mut diag in errors_buffer {
-                self.tcx().sess.diagnostic().emit_diagnostic(&mut diag);
+            if !errors_buffer.is_empty() {
+                errors_buffer.sort_by_key(|diag| diag.span.primary_span());
+                for mut diag in errors_buffer {
+                    self.tcx().sess.diagnostic().emit_diagnostic(&mut diag);
+                }
             }
         }
+
+        self.typeck_results.user_provided_types_mut().extend(
+            fcx_typeck_results.user_provided_types().items().map(|(local_id, c_ty)| {
+                let hir_id = hir::HirId { owner: common_hir_owner, local_id };
+
+                if cfg!(debug_assertions) && c_ty.needs_infer() {
+                    span_bug!(
+                        hir_id.to_span(self.fcx.tcx),
+                        "writeback: `{:?}` has inference variables",
+                        c_ty
+                    );
+                };
+
+                (hir_id, *c_ty)
+            }),
+        );
     }
 
     fn visit_user_provided_sigs(&mut self) {
         let fcx_typeck_results = self.fcx.typeck_results.borrow();
         assert_eq!(fcx_typeck_results.hir_owner, self.typeck_results.hir_owner);
 
-        for (&def_id, c_sig) in fcx_typeck_results.user_provided_sigs.iter() {
-            if cfg!(debug_assertions) && c_sig.needs_infer() {
-                span_bug!(
-                    self.fcx.tcx.def_span(def_id),
-                    "writeback: `{:?}` has inference variables",
-                    c_sig
-                );
-            };
-
-            self.typeck_results.user_provided_sigs.insert(def_id, *c_sig);
-        }
+        self.typeck_results.user_provided_sigs.extend(
+            fcx_typeck_results.user_provided_sigs.items().map(|(&def_id, c_sig)| {
+                if cfg!(debug_assertions) && c_sig.needs_infer() {
+                    span_bug!(
+                        self.fcx.tcx.def_span(def_id),
+                        "writeback: `{:?}` has inference variables",
+                        c_sig
+                    );
+                };
+
+                (def_id, *c_sig)
+            }),
+        );
     }
 
     fn visit_generator_interior_types(&mut self) {
@@ -641,7 +656,9 @@ impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
         assert_eq!(fcx_typeck_results.hir_owner, self.typeck_results.hir_owner);
         let common_hir_owner = fcx_typeck_results.hir_owner;
 
-        for (&local_id, &fn_sig) in fcx_typeck_results.liberated_fn_sigs().iter() {
+        let fcx_liberated_fn_sigs = fcx_typeck_results.liberated_fn_sigs().items_in_stable_order();
+
+        for (local_id, &fn_sig) in fcx_liberated_fn_sigs {
             let hir_id = hir::HirId { owner: common_hir_owner, local_id };
             let fn_sig = self.resolve(fn_sig, &hir_id);
             self.typeck_results.liberated_fn_sigs_mut().insert(hir_id, fn_sig);
@@ -653,7 +670,9 @@ impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
         assert_eq!(fcx_typeck_results.hir_owner, self.typeck_results.hir_owner);
         let common_hir_owner = fcx_typeck_results.hir_owner;
 
-        for (&local_id, ftys) in fcx_typeck_results.fru_field_types().iter() {
+        let fcx_fru_field_types = fcx_typeck_results.fru_field_types().items_in_stable_order();
+
+        for (local_id, ftys) in fcx_fru_field_types {
             let hir_id = hir::HirId { owner: common_hir_owner, local_id };
             let ftys = self.resolve(ftys.clone(), &hir_id);
             self.typeck_results.fru_field_types_mut().insert(hir_id, ftys);
diff --git a/compiler/rustc_lint_defs/src/lib.rs b/compiler/rustc_lint_defs/src/lib.rs
index f4b4c5168bf..9aca485e502 100644
--- a/compiler/rustc_lint_defs/src/lib.rs
+++ b/compiler/rustc_lint_defs/src/lib.rs
@@ -6,8 +6,9 @@
 extern crate rustc_macros;
 
 pub use self::Level::*;
-use rustc_ast::node_id::{NodeId, NodeMap};
+use rustc_ast::node_id::NodeId;
 use rustc_ast::{AttrId, Attribute};
+use rustc_data_structures::fx::FxIndexMap;
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher, ToStableHashKey};
 use rustc_error_messages::{DiagnosticMessage, MultiSpan};
 use rustc_hir::HashStableContext;
@@ -544,7 +545,7 @@ pub struct BufferedEarlyLint {
 
 #[derive(Default)]
 pub struct LintBuffer {
-    pub map: NodeMap<Vec<BufferedEarlyLint>>,
+    pub map: FxIndexMap<NodeId, Vec<BufferedEarlyLint>>,
 }
 
 impl LintBuffer {
diff --git a/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs b/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs
index 0d924f27c21..6fd5bd52abe 100644
--- a/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs
+++ b/compiler/rustc_metadata/src/rmeta/decoder/cstore_impl.rs
@@ -391,7 +391,7 @@ pub(in crate::rmeta) fn provide(providers: &mut Providers) {
             // keys from the former.
             // This is a rudimentary check that does not catch all cases,
             // just the easiest.
-            let mut fallback_map: DefIdMap<DefId> = Default::default();
+            let mut fallback_map: Vec<(DefId, DefId)> = Default::default();
 
             // Issue 46112: We want the map to prefer the shortest
             // paths when reporting the path to an item. Therefore we
@@ -421,12 +421,12 @@ pub(in crate::rmeta) fn provide(providers: &mut Providers) {
 
                 if let Some(def_id) = child.res.opt_def_id() {
                     if child.ident.name == kw::Underscore {
-                        fallback_map.insert(def_id, parent);
+                        fallback_map.push((def_id, parent));
                         return;
                     }
 
                     if ty::util::is_doc_hidden(tcx, parent) {
-                        fallback_map.insert(def_id, parent);
+                        fallback_map.push((def_id, parent));
                         return;
                     }
 
@@ -460,6 +460,7 @@ pub(in crate::rmeta) fn provide(providers: &mut Providers) {
             // Fill in any missing entries with the less preferable path.
             // If this path re-exports the child as `_`, we still use this
             // path in a diagnostic that suggests importing `::*`.
+
             for (child, parent) in fallback_map {
                 visible_parent_map.entry(child).or_insert(parent);
             }
diff --git a/compiler/rustc_metadata/src/rmeta/encoder.rs b/compiler/rustc_metadata/src/rmeta/encoder.rs
index ab2ad79b876..8f7a61b72f8 100644
--- a/compiler/rustc_metadata/src/rmeta/encoder.rs
+++ b/compiler/rustc_metadata/src/rmeta/encoder.rs
@@ -1187,8 +1187,11 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
                 record!(self.tables.trait_impl_trait_tys[def_id] <- table);
             }
         }
-        let inherent_impls = tcx.crate_inherent_impls(());
-        for (def_id, implementations) in inherent_impls.inherent_impls.iter() {
+        let inherent_impls = tcx.with_stable_hashing_context(|hcx| {
+            tcx.crate_inherent_impls(()).inherent_impls.to_sorted(&hcx, true)
+        });
+
+        for (def_id, implementations) in inherent_impls {
             if implementations.is_empty() {
                 continue;
             }
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index d681df14af1..7dfcd1bb507 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -38,7 +38,7 @@ use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_data_structures::tagged_ptr::CopyTaggedPtr;
 use rustc_hir as hir;
 use rustc_hir::def::{CtorKind, CtorOf, DefKind, LifetimeRes, Res};
-use rustc_hir::def_id::{CrateNum, DefId, LocalDefId, LocalDefIdMap};
+use rustc_hir::def_id::{CrateNum, DefId, DefIdMap, LocalDefId, LocalDefIdMap};
 use rustc_hir::Node;
 use rustc_index::vec::IndexVec;
 use rustc_macros::HashStable;
@@ -436,7 +436,7 @@ pub struct CrateVariancesMap<'tcx> {
     /// For each item with generics, maps to a vector of the variance
     /// of its generics. If an item has no generics, it will have no
     /// entry.
-    pub variances: FxHashMap<DefId, &'tcx [ty::Variance]>,
+    pub variances: DefIdMap<&'tcx [ty::Variance]>,
 }
 
 // Contains information needed to resolve types and (in the future) look up
diff --git a/compiler/rustc_middle/src/ty/typeck_results.rs b/compiler/rustc_middle/src/ty/typeck_results.rs
index 18281b5175c..2902c6dc556 100644
--- a/compiler/rustc_middle/src/ty/typeck_results.rs
+++ b/compiler/rustc_middle/src/ty/typeck_results.rs
@@ -6,7 +6,12 @@ use crate::{
         GenericArgKind, InternalSubsts, SubstsRef, Ty, UserSubsts,
     },
 };
-use rustc_data_structures::{fx::FxHashMap, sync::Lrc, unord::UnordSet, vec_map::VecMap};
+use rustc_data_structures::{
+    fx::FxHashMap,
+    sync::Lrc,
+    unord::{UnordItems, UnordSet},
+    vec_map::VecMap,
+};
 use rustc_errors::ErrorGuaranteed;
 use rustc_hir as hir;
 use rustc_hir::{
@@ -20,11 +25,7 @@ use rustc_macros::HashStable;
 use rustc_middle::mir::FakeReadCause;
 use rustc_session::Session;
 use rustc_span::Span;
-use std::{
-    collections::hash_map::{self, Entry},
-    hash::Hash,
-    iter,
-};
+use std::{collections::hash_map::Entry, hash::Hash, iter};
 
 use super::RvalueScopes;
 
@@ -567,8 +568,15 @@ impl<'a, V> LocalTableInContext<'a, V> {
         self.data.get(&id.local_id)
     }
 
-    pub fn iter(&self) -> hash_map::Iter<'_, hir::ItemLocalId, V> {
-        self.data.iter()
+    pub fn items(
+        &'a self,
+    ) -> UnordItems<(hir::ItemLocalId, &'a V), impl Iterator<Item = (hir::ItemLocalId, &'a V)>>
+    {
+        self.data.items().map(|(id, value)| (*id, value))
+    }
+
+    pub fn items_in_stable_order(&self) -> Vec<(ItemLocalId, &'a V)> {
+        self.data.to_sorted_stable_ord()
     }
 }
 
@@ -605,6 +613,16 @@ impl<'a, V> LocalTableInContextMut<'a, V> {
         validate_hir_id_for_typeck_results(self.hir_owner, id);
         self.data.remove(&id.local_id)
     }
+
+    pub fn extend(
+        &mut self,
+        items: UnordItems<(hir::HirId, V), impl Iterator<Item = (hir::HirId, V)>>,
+    ) {
+        self.data.extend(items.map(|(id, value)| {
+            validate_hir_id_for_typeck_results(self.hir_owner, id);
+            (id.local_id, value)
+        }))
+    }
 }
 
 rustc_index::newtype_index! {
diff --git a/compiler/rustc_resolve/src/check_unused.rs b/compiler/rustc_resolve/src/check_unused.rs
index 32fb5e18276..eae4c9992eb 100644
--- a/compiler/rustc_resolve/src/check_unused.rs
+++ b/compiler/rustc_resolve/src/check_unused.rs
@@ -28,9 +28,9 @@ use crate::module_to_string;
 use crate::Resolver;
 
 use rustc_ast as ast;
-use rustc_ast::node_id::NodeMap;
 use rustc_ast::visit::{self, Visitor};
-use rustc_data_structures::fx::FxHashSet;
+use rustc_data_structures::fx::FxIndexMap;
+use rustc_data_structures::unord::UnordSet;
 use rustc_errors::{pluralize, MultiSpan};
 use rustc_session::lint::builtin::{MACRO_USE_EXTERN_CRATE, UNUSED_IMPORTS};
 use rustc_session::lint::BuiltinLintDiagnostics;
@@ -40,7 +40,7 @@ struct UnusedImport<'a> {
     use_tree: &'a ast::UseTree,
     use_tree_id: ast::NodeId,
     item_span: Span,
-    unused: FxHashSet<ast::NodeId>,
+    unused: UnordSet<ast::NodeId>,
 }
 
 impl<'a> UnusedImport<'a> {
@@ -52,7 +52,7 @@ impl<'a> UnusedImport<'a> {
 struct UnusedImportCheckVisitor<'a, 'b> {
     r: &'a mut Resolver<'b>,
     /// All the (so far) unused imports, grouped path list
-    unused_imports: NodeMap<UnusedImport<'a>>,
+    unused_imports: FxIndexMap<ast::NodeId, UnusedImport<'a>>,
     base_use_tree: Option<&'a ast::UseTree>,
     base_id: ast::NodeId,
     item_span: Span,
@@ -89,7 +89,7 @@ impl<'a, 'b> UnusedImportCheckVisitor<'a, 'b> {
             use_tree,
             use_tree_id,
             item_span,
-            unused: FxHashSet::default(),
+            unused: Default::default(),
         })
     }
 }
diff --git a/src/tools/clippy/clippy_lints/src/inherent_impl.rs b/src/tools/clippy/clippy_lints/src/inherent_impl.rs
index c5abcc46254..e9b2e31a769 100644
--- a/src/tools/clippy/clippy_lints/src/inherent_impl.rs
+++ b/src/tools/clippy/clippy_lints/src/inherent_impl.rs
@@ -52,21 +52,19 @@ impl<'tcx> LateLintPass<'tcx> for MultipleInherentImpl {
         // List of spans to lint. (lint_span, first_span)
         let mut lint_spans = Vec::new();
 
-        for (_, impl_ids) in cx
+        let inherent_impls = cx
             .tcx
-            .crate_inherent_impls(())
-            .inherent_impls
-            .iter()
-            .filter(|(&id, impls)| {
-                impls.len() > 1
-                    // Check for `#[allow]` on the type definition
-                    && !is_lint_allowed(
-                        cx,
-                        MULTIPLE_INHERENT_IMPL,
-                        cx.tcx.hir().local_def_id_to_hir_id(id),
-                    )
-            })
-        {
+            .with_stable_hashing_context(|hcx| cx.tcx.crate_inherent_impls(()).inherent_impls.to_sorted(&hcx, true));
+
+        for (_, impl_ids) in inherent_impls.into_iter().filter(|(&id, impls)| {
+            impls.len() > 1
+            // Check for `#[allow]` on the type definition
+            && !is_lint_allowed(
+                cx,
+                MULTIPLE_INHERENT_IMPL,
+                cx.tcx.hir().local_def_id_to_hir_id(id),
+            )
+        }) {
             for impl_id in impl_ids.iter().map(|id| id.expect_local()) {
                 match type_map.entry(cx.tcx.type_of(impl_id)) {
                     Entry::Vacant(e) => {
diff --git a/src/tools/clippy/clippy_lints/src/len_zero.rs b/src/tools/clippy/clippy_lints/src/len_zero.rs
index 9eba4675629..3c70c9cf19a 100644
--- a/src/tools/clippy/clippy_lints/src/len_zero.rs
+++ b/src/tools/clippy/clippy_lints/src/len_zero.rs
@@ -219,7 +219,7 @@ fn check_trait_items(cx: &LateContext<'_>, visited_trait: &Item<'_>, trait_items
         let is_empty = sym!(is_empty);
 
         let is_empty_method_found = current_and_super_traits
-            .iter()
+            .items()
             .flat_map(|&i| cx.tcx.associated_items(i).filter_by_name_unhygienic(is_empty))
             .any(|i| {
                 i.kind == ty::AssocKind::Fn
diff --git a/src/tools/clippy/clippy_lints/src/loops/while_immutable_condition.rs b/src/tools/clippy/clippy_lints/src/loops/while_immutable_condition.rs
index a63422d2a36..d1a1f773f87 100644
--- a/src/tools/clippy/clippy_lints/src/loops/while_immutable_condition.rs
+++ b/src/tools/clippy/clippy_lints/src/loops/while_immutable_condition.rs
@@ -35,7 +35,7 @@ pub(super) fn check<'tcx>(cx: &LateContext<'tcx>, cond: &'tcx Expr<'_>, expr: &'
         } else {
             return;
         };
-    let mutable_static_in_cond = var_visitor.def_ids.iter().any(|(_, v)| *v);
+    let mutable_static_in_cond = var_visitor.def_ids.items().any(|(_, v)| *v);
 
     let mut has_break_or_return_visitor = HasBreakOrReturnVisitor {
         has_break_or_return: false,
diff --git a/src/tools/clippy/clippy_lints/src/missing_trait_methods.rs b/src/tools/clippy/clippy_lints/src/missing_trait_methods.rs
index 68af8a672f6..3371b4cce32 100644
--- a/src/tools/clippy/clippy_lints/src/missing_trait_methods.rs
+++ b/src/tools/clippy/clippy_lints/src/missing_trait_methods.rs
@@ -80,19 +80,21 @@ impl<'tcx> LateLintPass<'tcx> for MissingTraitMethods {
                 }
             }
 
-            for assoc in provided.values() {
-                let source_map = cx.tcx.sess.source_map();
-                let definition_span = source_map.guess_head_span(cx.tcx.def_span(assoc.def_id));
+            cx.tcx.with_stable_hashing_context(|hcx| {
+                for assoc in provided.values_sorted(&hcx, true) {
+                    let source_map = cx.tcx.sess.source_map();
+                    let definition_span = source_map.guess_head_span(cx.tcx.def_span(assoc.def_id));
 
-                span_lint_and_help(
-                    cx,
-                    MISSING_TRAIT_METHODS,
-                    source_map.guess_head_span(item.span),
-                    &format!("missing trait method provided by default: `{}`", assoc.name),
-                    Some(definition_span),
-                    "implement the method",
-                );
-            }
+                    span_lint_and_help(
+                        cx,
+                        MISSING_TRAIT_METHODS,
+                        source_map.guess_head_span(item.span),
+                        &format!("missing trait method provided by default: `{}`", assoc.name),
+                        Some(definition_span),
+                        "implement the method",
+                    );
+                }
+            })
         }
     }
 }
diff --git a/src/tools/clippy/clippy_lints/src/pass_by_ref_or_value.rs b/src/tools/clippy/clippy_lints/src/pass_by_ref_or_value.rs
index 870a1c7d88d..2d21aaa4f7f 100644
--- a/src/tools/clippy/clippy_lints/src/pass_by_ref_or_value.rs
+++ b/src/tools/clippy/clippy_lints/src/pass_by_ref_or_value.rs
@@ -190,10 +190,10 @@ impl<'tcx> PassByRefOrValue {
                             // Don't lint if an unsafe pointer is created.
                             // TODO: Limit the check only to unsafe pointers to the argument (or part of the argument)
                             //       which escape the current function.
-                            if typeck.node_types().iter().any(|(_, &ty)| ty.is_unsafe_ptr())
+                            if typeck.node_types().items().any(|(_, &ty)| ty.is_unsafe_ptr())
                                 || typeck
                                     .adjustments()
-                                    .iter()
+                                    .items()
                                     .flat_map(|(_, a)| a)
                                     .any(|a| matches!(a.kind, Adjust::Pointer(PointerCast::UnsafeFnPointer)))
                             {