compiler/rustc_query_system/src/query/caches.rs

   1 use crate::dep_graph::DepNodeIndex;
   2
   3 use rustc_data_structures::fx::FxHashMap;
   4 use rustc_data_structures::sharded;
   5 #[cfg(parallel_compiler)]
   6 use rustc_data_structures::sharded::Sharded;
   7 use rustc_data_structures::sync::Lock;
   8 use rustc_index::vec::{Idx, IndexVec};
   9 use std::fmt::Debug;
  10 use std::hash::Hash;
  11 use std::marker::PhantomData;
  12
  13 pub trait CacheSelector<'tcx, V> {
  14     type Cache
  15     where
  16         V: Copy;
  17 }
  18
  19 pub trait QueryStorage {
  20     type Value: Copy;
  21 }
  22
  23 pub trait QueryCache: QueryStorage + Sized {
  24     type Key: Hash + Eq + Copy + Debug;
  25
  26     /// Checks if the query is already computed and in the cache.
  27     /// It returns the shard index and a lock guard to the shard,
  28     /// which will be used if the query is not in the cache and we need
  29     /// to compute it.
  30     fn lookup(&self, key: &Self::Key) -> Option<(Self::Value, DepNodeIndex)>;
  31
  32     fn complete(&self, key: Self::Key, value: Self::Value, index: DepNodeIndex);
  33
  34     fn iter(&self, f: &mut dyn FnMut(&Self::Key, &Self::Value, DepNodeIndex));
  35 }
  36
  37 pub struct DefaultCacheSelector<K>(PhantomData<K>);
  38
  39 impl<'tcx, K: Eq + Hash, V: 'tcx> CacheSelector<'tcx, V> for DefaultCacheSelector<K> {
  40     type Cache = DefaultCache<K, V>
  41     where
  42         V: Copy;
  43 }
  44
  45 pub struct DefaultCache<K, V> {
  46     #[cfg(parallel_compiler)]
  47     cache: Sharded<FxHashMap<K, (V, DepNodeIndex)>>,
  48     #[cfg(not(parallel_compiler))]
  49     cache: Lock<FxHashMap<K, (V, DepNodeIndex)>>,
  50 }
  51
  52 impl<K, V> Default for DefaultCache<K, V> {
  53     fn default() -> Self {
  54         DefaultCache { cache: Default::default() }
  55     }
  56 }
  57
  58 impl<K: Eq + Hash, V: Copy + Debug> QueryStorage for DefaultCache<K, V> {
  59     type Value = V;
  60 }
  61
  62 impl<K, V> QueryCache for DefaultCache<K, V>
  63 where
  64     K: Eq + Hash + Copy + Debug,
  65     V: Copy + Debug,
  66 {
  67     type Key = K;
  68
  69     #[inline(always)]
  70     fn lookup(&self, key: &K) -> Option<(V, DepNodeIndex)> {
  71         let key_hash = sharded::make_hash(key);
  72         #[cfg(parallel_compiler)]
  73         let lock = self.cache.get_shard_by_hash(key_hash).lock();
  74         #[cfg(not(parallel_compiler))]
  75         let lock = self.cache.lock();
  76         let result = lock.raw_entry().from_key_hashed_nocheck(key_hash, key);
  77
  78         if let Some((_, value)) = result { Some(*value) } else { None }
  79     }
  80
  81     #[inline]
  82     fn complete(&self, key: K, value: V, index: DepNodeIndex) {
  83         #[cfg(parallel_compiler)]
  84         let mut lock = self.cache.get_shard_by_value(&key).lock();
  85         #[cfg(not(parallel_compiler))]
  86         let mut lock = self.cache.lock();
  87         // We may be overwriting another value. This is all right, since the dep-graph
  88         // will check that the fingerprint matches.
  89         lock.insert(key, (value, index));
  90     }
  91
  92     fn iter(&self, f: &mut dyn FnMut(&Self::Key, &Self::Value, DepNodeIndex)) {
  93         #[cfg(parallel_compiler)]
  94         {
  95             let shards = self.cache.lock_shards();
  96             for shard in shards.iter() {
  97                 for (k, v) in shard.iter() {
  98                     f(k, &v.0, v.1);
  99                 }
 100             }
 101         }
 102         #[cfg(not(parallel_compiler))]
 103         {
 104             let map = self.cache.lock();
 105             for (k, v) in map.iter() {
 106                 f(k, &v.0, v.1);
 107             }
 108         }
 109     }
 110 }
 111
 112 pub struct SingleCacheSelector;
 113
 114 impl<'tcx, V: 'tcx> CacheSelector<'tcx, V> for SingleCacheSelector {
 115     type Cache = SingleCache<V>
 116     where
 117         V: Copy;
 118 }
 119
 120 pub struct SingleCache<V> {
 121     cache: Lock<Option<(V, DepNodeIndex)>>,
 122 }
 123
 124 impl<V> Default for SingleCache<V> {
 125     fn default() -> Self {
 126         SingleCache { cache: Lock::new(None) }
 127     }
 128 }
 129
 130 impl<V: Copy + Debug> QueryStorage for SingleCache<V> {
 131     type Value = V;
 132 }
 133
 134 impl<V> QueryCache for SingleCache<V>
 135 where
 136     V: Copy + Debug,
 137 {
 138     type Key = ();
 139
 140     #[inline(always)]
 141     fn lookup(&self, _key: &()) -> Option<(V, DepNodeIndex)> {
 142         *self.cache.lock()
 143     }
 144
 145     #[inline]
 146     fn complete(&self, _key: (), value: V, index: DepNodeIndex) {
 147         *self.cache.lock() = Some((value, index));
 148     }
 149
 150     fn iter(&self, f: &mut dyn FnMut(&Self::Key, &Self::Value, DepNodeIndex)) {
 151         self.cache.lock().as_ref().map(|value| f(&(), &value.0, value.1));
 152     }
 153 }
 154
 155 pub struct VecCacheSelector<K>(PhantomData<K>);
 156
 157 impl<'tcx, K: Idx, V: 'tcx> CacheSelector<'tcx, V> for VecCacheSelector<K> {
 158     type Cache = VecCache<K, V>
 159     where
 160         V: Copy;
 161 }
 162
 163 pub struct VecCache<K: Idx, V> {
 164     #[cfg(parallel_compiler)]
 165     cache: Sharded<IndexVec<K, Option<(V, DepNodeIndex)>>>,
 166     #[cfg(not(parallel_compiler))]
 167     cache: Lock<IndexVec<K, Option<(V, DepNodeIndex)>>>,
 168 }
 169
 170 impl<K: Idx, V> Default for VecCache<K, V> {
 171     fn default() -> Self {
 172         VecCache { cache: Default::default() }
 173     }
 174 }
 175
 176 impl<K: Eq + Idx, V: Copy + Debug> QueryStorage for VecCache<K, V> {
 177     type Value = V;
 178 }
 179
 180 impl<K, V> QueryCache for VecCache<K, V>
 181 where
 182     K: Eq + Idx + Copy + Debug,
 183     V: Copy + Debug,
 184 {
 185     type Key = K;
 186
 187     #[inline(always)]
 188     fn lookup(&self, key: &K) -> Option<(V, DepNodeIndex)> {
 189         #[cfg(parallel_compiler)]
 190         let lock = self.cache.get_shard_by_hash(key.index() as u64).lock();
 191         #[cfg(not(parallel_compiler))]
 192         let lock = self.cache.lock();
 193         if let Some(Some(value)) = lock.get(*key) { Some(*value) } else { None }
 194     }
 195
 196     #[inline]
 197     fn complete(&self, key: K, value: V, index: DepNodeIndex) {
 198         #[cfg(parallel_compiler)]
 199         let mut lock = self.cache.get_shard_by_hash(key.index() as u64).lock();
 200         #[cfg(not(parallel_compiler))]
 201         let mut lock = self.cache.lock();
 202         lock.insert(key, (value, index));
 203     }
 204
 205     fn iter(&self, f: &mut dyn FnMut(&Self::Key, &Self::Value, DepNodeIndex)) {
 206         #[cfg(parallel_compiler)]
 207         {
 208             let shards = self.cache.lock_shards();
 209             for shard in shards.iter() {
 210                 for (k, v) in shard.iter_enumerated() {
 211                     if let Some(v) = v {
 212                         f(&k, &v.0, v.1);
 213                     }
 214                 }
 215             }
 216         }
 217         #[cfg(not(parallel_compiler))]
 218         {
 219             let map = self.cache.lock();
 220             for (k, v) in map.iter_enumerated() {
 221                 if let Some(v) = v {
 222                     f(&k, &v.0, v.1);
 223                 }
 224             }
 225         }
 226     }
 227 }