Auto merge of #3083 - saethlin:gc-history, r=oli-obk

GC the Stacked Borrows allocation history

This handles the biggest contributor to https://github.com/rust-lang/miri/issues/3080

The benchmark that this adds demonstrates the memory improvement here, but our benchmark setup doesn't record memory usage, and `hyperfine` doesn't support emitting memory usage stats. I ran this benchmark manually with `/usr/bin/time -v cargo +miri miri run` :shrug:

5 files changed, 27 insertions, 0 deletions

diff --git a/src/tools/miri/bench-cargo-miri/invalidate/Cargo.lock b/src/tools/miri/bench-cargo-miri/invalidate/Cargo.lock
new file mode 100644
index 00000000000..7bf23225ea5
--- /dev/null
+++ b/src/tools/miri/bench-cargo-miri/invalidate/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "invalidate"
+version = "0.1.0"
diff --git a/src/tools/miri/bench-cargo-miri/invalidate/Cargo.toml b/src/tools/miri/bench-cargo-miri/invalidate/Cargo.toml
new file mode 100644
index 00000000000..14cf0882f0b
--- /dev/null
+++ b/src/tools/miri/bench-cargo-miri/invalidate/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "invalidate"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/src/tools/miri/bench-cargo-miri/invalidate/src/main.rs b/src/tools/miri/bench-cargo-miri/invalidate/src/main.rs
new file mode 100644
index 00000000000..fa8deb851c3
--- /dev/null
+++ b/src/tools/miri/bench-cargo-miri/invalidate/src/main.rs
@@ -0,0 +1,4 @@
+fn main() {
+    // The end of the range is just chosen to make the benchmark run for a few seconds.
+    for _ in 0..200_000 {}
+}
diff --git a/src/tools/miri/src/borrow_tracker/stacked_borrows/diagnostics.rs b/src/tools/miri/src/borrow_tracker/stacked_borrows/diagnostics.rs
index 9b0f13dd62c..1ef30cb9fad 100644
--- a/src/tools/miri/src/borrow_tracker/stacked_borrows/diagnostics.rs
+++ b/src/tools/miri/src/borrow_tracker/stacked_borrows/diagnostics.rs
@@ -1,6 +1,7 @@
 use smallvec::SmallVec;
 use std::fmt;
 
+use rustc_data_structures::fx::FxHashSet;
 use rustc_middle::mir::interpret::{alloc_range, AllocId, AllocRange, InterpError};
 use rustc_span::{Span, SpanData};
 use rustc_target::abi::Size;
@@ -233,6 +234,12 @@ impl AllocHistory {
             protectors: SmallVec::new(),
         }
     }
+
+    pub fn retain(&mut self, live_tags: &FxHashSet<BorTag>) {
+        self.invalidations.retain(|event| live_tags.contains(&event.tag));
+        self.creations.retain(|event| live_tags.contains(&event.retag.new_tag));
+        self.protectors.retain(|event| live_tags.contains(&event.tag));
+    }
 }
 
 impl<'history, 'ecx, 'mir, 'tcx> DiagnosticCx<'history, 'ecx, 'mir, 'tcx> {
diff --git a/src/tools/miri/src/borrow_tracker/stacked_borrows/mod.rs b/src/tools/miri/src/borrow_tracker/stacked_borrows/mod.rs
index a54bd32cd40..e670dcef330 100644
--- a/src/tools/miri/src/borrow_tracker/stacked_borrows/mod.rs
+++ b/src/tools/miri/src/borrow_tracker/stacked_borrows/mod.rs
@@ -456,6 +456,7 @@ impl Stacks {
                     stack.retain(live_tags);
                 }
             }
+            self.history.retain(live_tags);
             self.modified_since_last_gc = false;
         }
     }