2 files changed, 18 insertions, 6 deletions

diff --git a/compiler/rustc_query_system/src/dep_graph/dep_node.rs b/compiler/rustc_query_system/src/dep_graph/dep_node.rs
index 9e1ca6ab5..39a4cb1b1 100644
--- a/compiler/rustc_query_system/src/dep_graph/dep_node.rs
+++ b/compiler/rustc_query_system/src/dep_graph/dep_node.rs
@@ -46,7 +46,7 @@ use super::{DepContext, DepKind, FingerprintStyle};
 use crate::ich::StableHashingContext;
 
 use rustc_data_structures::fingerprint::{Fingerprint, PackedFingerprint};
-use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher, StableOrd, ToStableHashKey};
 use rustc_hir::definitions::DefPathHash;
 use std::fmt;
 use std::hash::Hash;
@@ -247,3 +247,14 @@ impl<HCX> HashStable<HCX> for WorkProductId {
         self.hash.hash_stable(hcx, hasher)
     }
 }
+impl<HCX> ToStableHashKey<HCX> for WorkProductId {
+    type KeyType = Fingerprint;
+    #[inline]
+    fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
+        self.hash
+    }
+}
+unsafe impl StableOrd for WorkProductId {
+    // Fingerprint can use unstable (just a tuple of `u64`s), so WorkProductId can as well
+    const CAN_USE_UNSTABLE_SORT: bool = true;
+}
diff --git a/compiler/rustc_query_system/src/dep_graph/graph.rs b/compiler/rustc_query_system/src/dep_graph/graph.rs
index c0d7386dd..c9e80a6d9 100644
--- a/compiler/rustc_query_system/src/dep_graph/graph.rs
+++ b/compiler/rustc_query_system/src/dep_graph/graph.rs
@@ -1,11 +1,12 @@
 use parking_lot::Mutex;
 use rustc_data_structures::fingerprint::Fingerprint;
-use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexMap};
 use rustc_data_structures::profiling::{EventId, QueryInvocationId, SelfProfilerRef};
 use rustc_data_structures::sharded::{self, Sharded};
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_data_structures::steal::Steal;
 use rustc_data_structures::sync::{AtomicU32, AtomicU64, Lock, Lrc, Ordering};
+use rustc_data_structures::unord::UnordMap;
 use rustc_index::IndexVec;
 use rustc_serialize::opaque::{FileEncodeResult, FileEncoder};
 use smallvec::{smallvec, SmallVec};
@@ -93,7 +94,7 @@ pub struct DepGraphData<K: DepKind> {
     /// things available to us. If we find that they are not dirty, we
     /// load the path to the file storing those work-products here into
     /// this map. We can later look for and extract that data.
-    previous_work_products: FxHashMap<WorkProductId, WorkProduct>,
+    previous_work_products: FxIndexMap<WorkProductId, WorkProduct>,
 
     dep_node_debug: Lock<FxHashMap<DepNode<K>, String>>,
 
@@ -116,7 +117,7 @@ impl<K: DepKind> DepGraph<K> {
     pub fn new(
         profiler: &SelfProfilerRef,
         prev_graph: SerializedDepGraph<K>,
-        prev_work_products: FxHashMap<WorkProductId, WorkProduct>,
+        prev_work_products: FxIndexMap<WorkProductId, WorkProduct>,
         encoder: FileEncoder,
         record_graph: bool,
         record_stats: bool,
@@ -688,7 +689,7 @@ impl<K: DepKind> DepGraph<K> {
 
     /// Access the map of work-products created during the cached run. Only
     /// used during saving of the dep-graph.
-    pub fn previous_work_products(&self) -> &FxHashMap<WorkProductId, WorkProduct> {
+    pub fn previous_work_products(&self) -> &FxIndexMap<WorkProductId, WorkProduct> {
         &self.data.as_ref().unwrap().previous_work_products
     }
 
@@ -1048,7 +1049,7 @@ pub struct WorkProduct {
     ///
     /// By convention, file extensions are currently used as identifiers, i.e. the key "o" maps to
     /// the object file's path, and "dwo" to the dwarf object file's path.
-    pub saved_files: FxHashMap<String, String>,
+    pub saved_files: UnordMap<String, String>,
 }
 
 // Index type for `DepNodeData`'s edges.