1 use crate::stacked_borrows::{AccessKind, Item, Permission, SbTag, SbTagExtra};
2 use rustc_data_structures::fx::FxHashSet;
3 #[cfg(feature = "stack-cache")]
6 /// Exactly what cache size we should use is a difficult tradeoff. There will always be some
7 /// workload which has a `SbTag` working set which exceeds the size of the cache, and ends up
8 /// falling back to linear searches of the borrow stack very often.
9 /// The cost of making this value too large is that the loop in `Stack::insert` which ensures the
10 /// entries in the cache stay correct after an insert becomes expensive.
11 #[cfg(feature = "stack-cache")]
12 const CACHE_LEN: usize = 32;
14 /// Extra per-location state.
15 #[derive(Clone, Debug)]
17 /// Used *mostly* as a stack; never empty.
19 /// * Above a `SharedReadOnly` there can only be more `SharedReadOnly`.
20 /// * Except for `Untagged`, no tag occurs in the stack more than once.
22 /// If this is `Some(id)`, then the actual current stack is unknown. This can happen when
23 /// wildcard pointers are used to access this location. What we do know is that `borrows` are at
24 /// the top of the stack, and below it are arbitrarily many items whose `tag` is strictly less
26 /// When the bottom is unknown, `borrows` always has a `SharedReadOnly` or `Unique` at the bottom;
27 /// we never have the unknown-to-known boundary in an SRW group.
28 unknown_bottom: Option<SbTag>,
30 /// A small LRU cache of searches of the borrow stack. This only caches accesses of `Tagged`,
31 /// because those are unique in the stack.
32 #[cfg(feature = "stack-cache")]
34 /// On a read, we need to disable all `Unique` above the granting item. We can avoid most of
35 /// this scan by keeping track of the region of the borrow stack that may contain `Unique`s.
36 #[cfg(feature = "stack-cache")]
37 unique_range: Range<usize>,
40 /// A very small cache of searches of the borrow stack
41 /// This maps tags to locations in the borrow stack. Any use of this still needs to do a
42 /// probably-cold random access into the borrow stack to figure out what `Permission` an
43 /// `SbTag` grants. We could avoid this by also storing the `Permission` in the cache, but
44 /// most lookups into the cache are immediately followed by access of the full borrow stack anyway.
45 #[cfg(feature = "stack-cache")]
46 #[derive(Clone, Debug)]
48 tags: [SbTag; CACHE_LEN], // Hot in find_granting
49 idx: [usize; CACHE_LEN], // Hot in grant
52 #[cfg(feature = "stack-cache")]
54 /// When a tag is used, we call this function to add or refresh it in the cache.
56 /// We use the position in the cache to represent how recently a tag was used; the first position
57 /// is the most recently used tag. So an add shifts every element towards the end, and inserts
58 /// the new element at the start. We lose the last element.
59 /// This strategy is effective at keeping the most-accessed tags in the cache, but it costs a
60 /// linear shift across the entire cache when we add a new tag.
61 fn add(&mut self, idx: usize, tag: SbTag) {
62 self.tags.copy_within(0..CACHE_LEN - 1, 1);
64 self.idx.copy_within(0..CACHE_LEN - 1, 1);
69 impl PartialEq for Stack {
70 fn eq(&self, other: &Self) -> bool {
71 // All the semantics of Stack are in self.borrows, everything else is caching
72 self.borrows == other.borrows
79 /// Panics if any of the caching mechanisms have broken,
80 /// - The StackCache indices don't refer to the parallel tags,
81 /// - There are no Unique tags outside of first_unique..last_unique
82 #[cfg(feature = "expensive-debug-assertions")]
83 fn verify_cache_consistency(&self) {
84 if self.borrows.len() > CACHE_LEN {
85 for (tag, stack_idx) in self.cache.tags.iter().zip(self.cache.idx.iter()) {
86 assert_eq!(self.borrows[*stack_idx].tag, *tag);
90 for (idx, item) in self.borrows.iter().enumerate() {
91 if item.perm == Permission::Unique {
93 self.unique_range.contains(&idx),
102 /// Find the item granting the given kind of access to the given tag, and return where
103 /// it is on the stack. For wildcard tags, the given index is approximate, but if *no*
104 /// index is given it means the match was *not* in the known part of the stack.
105 /// `Ok(None)` indicates it matched the "unknown" part of the stack.
106 /// `Err` indicates it was not found.
107 pub(super) fn find_granting(
111 exposed_tags: &FxHashSet<SbTag>,
112 ) -> Result<Option<usize>, ()> {
113 #[cfg(feature = "expensive-debug-assertions")]
114 self.verify_cache_consistency();
116 let SbTagExtra::Concrete(tag) = tag else {
117 // Handle the wildcard case.
118 // Go search the stack for an exposed tag.
122 .enumerate() // we also need to know *where* in the stack
123 .rev() // search top-to-bottom
124 .find_map(|(idx, item)| {
125 // If the item fits and *might* be this wildcard, use it.
126 if item.perm.grants(access) && exposed_tags.contains(&item.tag) {
133 return Ok(Some(idx));
135 // If we couldn't find it in the stack, check the unknown bottom.
136 return if self.unknown_bottom.is_some() { Ok(None) } else { Err(()) };
139 if let Some(idx) = self.find_granting_tagged(access, tag) {
140 return Ok(Some(idx));
143 // Couldn't find it in the stack; but if there is an unknown bottom it might be there.
144 let found = self.unknown_bottom.is_some_and(|&unknown_limit| {
145 tag.0 < unknown_limit.0 // unknown_limit is an upper bound for what can be in the unknown bottom.
147 if found { Ok(None) } else { Err(()) }
150 fn find_granting_tagged(&mut self, access: AccessKind, tag: SbTag) -> Option<usize> {
151 #[cfg(feature = "stack-cache")]
152 if let Some(idx) = self.find_granting_cache(access, tag) {
156 // If we didn't find the tag in the cache, fall back to a linear search of the
157 // whole stack, and add the tag to the stack.
158 for (stack_idx, item) in self.borrows.iter().enumerate().rev() {
159 if tag == item.tag && item.perm.grants(access) {
160 #[cfg(feature = "stack-cache")]
161 self.cache.add(stack_idx, tag);
162 return Some(stack_idx);
168 #[cfg(feature = "stack-cache")]
169 fn find_granting_cache(&mut self, access: AccessKind, tag: SbTag) -> Option<usize> {
170 // This looks like a common-sense optimization; we're going to do a linear search of the
171 // cache or the borrow stack to scan the shorter of the two. This optimization is miniscule
172 // and this check actually ensures we do not access an invalid cache.
173 // When a stack is created and when tags are removed from the top of the borrow stack, we
174 // need some valid value to populate the cache. In both cases, we try to use the bottom
175 // item. But when the stack is cleared in `set_unknown_bottom` there is nothing we could
176 // place in the cache that is correct. But due to the way we populate the cache in
177 // `StackCache::add`, we know that when the borrow stack has grown larger than the cache,
178 // every slot in the cache is valid.
179 if self.borrows.len() <= CACHE_LEN {
182 // Search the cache for the tag we're looking up
183 let cache_idx = self.cache.tags.iter().position(|t| *t == tag)?;
184 let stack_idx = self.cache.idx[cache_idx];
185 // If we found the tag, look up its position in the stack to see if it grants
186 // the required permission
187 if self.borrows[stack_idx].perm.grants(access) {
188 // If it does, and it's not already in the most-recently-used position, move it there.
189 // Except if the tag is in position 1, this is equivalent to just a swap, so do that.
191 self.cache.tags.swap(0, 1);
192 self.cache.idx.swap(0, 1);
193 } else if cache_idx > 1 {
194 self.cache.add(stack_idx, tag);
198 // Tag is in the cache, but it doesn't grant the required permission
203 pub fn insert(&mut self, new_idx: usize, new: Item) {
204 self.borrows.insert(new_idx, new);
206 #[cfg(feature = "stack-cache")]
207 self.insert_cache(new_idx, new);
210 #[cfg(feature = "stack-cache")]
211 fn insert_cache(&mut self, new_idx: usize, new: Item) {
212 // Adjust the possibly-unique range if an insert occurs before or within it
213 if self.unique_range.start >= new_idx {
214 self.unique_range.start += 1;
216 if self.unique_range.end >= new_idx {
217 self.unique_range.end += 1;
219 if new.perm == Permission::Unique {
220 // Make sure the possibly-unique range contains the new borrow
221 self.unique_range.start = self.unique_range.start.min(new_idx);
222 self.unique_range.end = self.unique_range.end.max(new_idx + 1);
225 // The above insert changes the meaning of every index in the cache >= new_idx, so now
226 // we need to find every one of those indexes and increment it.
227 // But if the insert is at the end (equivalent to a push), we can skip this step because
228 // it didn't change the position of any other tags.
229 if new_idx != self.borrows.len() - 1 {
230 for idx in &mut self.cache.idx {
237 // This primes the cache for the next access, which is almost always the just-added tag.
238 self.cache.add(new_idx, new.tag);
240 #[cfg(feature = "expensive-debug-assertions")]
241 self.verify_cache_consistency();
244 /// Construct a new `Stack` using the passed `Item` as the base tag.
245 pub fn new(item: Item) -> Self {
248 unknown_bottom: None,
249 #[cfg(feature = "stack-cache")]
250 cache: StackCache { idx: [0; CACHE_LEN], tags: [item.tag; CACHE_LEN] },
251 #[cfg(feature = "stack-cache")]
252 unique_range: if item.perm == Permission::Unique { 0..1 } else { 0..0 },
256 pub fn get(&self, idx: usize) -> Option<Item> {
257 self.borrows.get(idx).cloned()
260 #[allow(clippy::len_without_is_empty)] // Stacks are never empty
261 pub fn len(&self) -> usize {
265 pub fn unknown_bottom(&self) -> Option<SbTag> {
269 pub fn set_unknown_bottom(&mut self, tag: SbTag) {
270 // We clear the borrow stack but the lookup cache doesn't support clearing per se. Instead,
271 // there is a check explained in `find_granting_cache` which protects against accessing the
272 // cache when it has been cleared and not yet refilled.
273 self.borrows.clear();
274 self.unknown_bottom = Some(tag);
277 /// Find all `Unique` elements in this borrow stack above `granting_idx`, pass a copy of them
278 /// to the `visitor`, then set their `Permission` to `Disabled`.
279 pub fn disable_uniques_starting_at<V: FnMut(Item) -> crate::InterpResult<'tcx>>(
281 disable_start: usize,
283 ) -> crate::InterpResult<'tcx> {
284 #[cfg(feature = "stack-cache")]
285 let unique_range = self.unique_range.clone();
286 #[cfg(not(feature = "stack-cache"))]
287 let unique_range = 0..self.len();
289 if disable_start <= unique_range.end {
290 // add 1 so we don't disable the granting item
291 let lower = unique_range.start.max(disable_start);
292 let upper = (unique_range.end + 1).min(self.borrows.len());
293 for item in &mut self.borrows[lower..upper] {
294 if item.perm == Permission::Unique {
295 log::trace!("access: disabling item {:?}", item);
297 item.perm = Permission::Disabled;
302 #[cfg(feature = "stack-cache")]
303 if disable_start < self.unique_range.start {
304 // We disabled all Unique items
305 self.unique_range.start = 0;
306 self.unique_range.end = 0;
308 // Truncate the range to disable_start. This is + 2 because we are only removing
309 // elements after disable_start, and this range does not include the end.
310 self.unique_range.end = self.unique_range.end.min(disable_start + 1);
313 #[cfg(feature = "expensive-debug-assertions")]
314 self.verify_cache_consistency();
319 /// Produces an iterator which iterates over `range` in reverse, and when dropped removes that
320 /// range of `Item`s from this `Stack`.
321 pub fn pop_items_after<V: FnMut(Item) -> crate::InterpResult<'tcx>>(
325 ) -> crate::InterpResult<'tcx> {
326 while self.borrows.len() > start {
327 let item = self.borrows.pop().unwrap();
331 #[cfg(feature = "stack-cache")]
332 if !self.borrows.is_empty() {
333 // After we remove from the borrow stack, every aspect of our caching may be invalid, but it is
334 // also possible that the whole cache is still valid. So we call this method to repair what
335 // aspects of the cache are now invalid, instead of resetting the whole thing to a trivially
336 // valid default state.
337 let base_tag = self.borrows[0].tag;
340 // Remove invalid entries from the cache by rotating them to the end of the cache, then
341 // keep track of how many invalid elements there are and overwrite them with the base tag.
342 // The base tag here serves as a harmless default value.
343 for _ in 0..CACHE_LEN - 1 {
344 if self.cache.idx[cursor] >= start {
345 self.cache.idx[cursor..CACHE_LEN - removed].rotate_left(1);
346 self.cache.tags[cursor..CACHE_LEN - removed].rotate_left(1);
352 for i in CACHE_LEN - removed - 1..CACHE_LEN {
353 self.cache.idx[i] = 0;
354 self.cache.tags[i] = base_tag;
357 if start < self.unique_range.start.saturating_sub(1) {
358 // We removed all the Unique items
359 self.unique_range = 0..0;
361 // Ensure the range doesn't extend past the new top of the stack
362 self.unique_range.end = self.unique_range.end.min(start + 1);
365 self.unique_range = 0..0;
368 #[cfg(feature = "expensive-debug-assertions")]
369 self.verify_cache_consistency();