Auto merge of #2479 - saethlin:tag-gc, r=oli-obk

Implement a garbage collector for tags

The general approach here is to scan TLS, all locals, and the main memory map for all provenance, accumulating a `HashSet` of all pointer tags which are stored anywhere (we also have a special case for panic payloads). Then we iterate over every borrow stack and remove tags which are not in said `HashSet`, or which could be terminating a SRW block.

Runtime of benchmarks decreases by between 17% and 81%.

GC off:
```
Benchmark 1: cargo +miri miri run --manifest-path /home/ben/miri/bench-cargo-miri/backtraces/Cargo.toml
  Time (mean ± σ):      7.080 s ±  0.249 s    [User: 6.870 s, System: 0.202 s]
  Range (min … max):    6.933 s …  7.521 s    5 runs

  Warning: Statistical outliers were detected. Consider re-running this benchmark on a quiet PC without any interferences from other programs. It might help to use the '--warmup' or '--prepare' options.

Benchmark 1: cargo +miri miri run --manifest-path /home/ben/miri/bench-cargo-miri/mse/Cargo.toml
  Time (mean ± σ):      1.875 s ±  0.031 s    [User: 1.630 s, System: 0.245 s]
  Range (min … max):    1.825 s …  1.910 s    5 runs

Benchmark 1: cargo +miri miri run --manifest-path /home/ben/miri/bench-cargo-miri/serde1/Cargo.toml
  Time (mean ± σ):      2.785 s ±  0.075 s    [User: 2.536 s, System: 0.168 s]
  Range (min … max):    2.698 s …  2.851 s    5 runs

Benchmark 1: cargo +miri miri run --manifest-path /home/ben/miri/bench-cargo-miri/serde2/Cargo.toml
  Time (mean ± σ):      6.267 s ±  0.066 s    [User: 6.072 s, System: 0.190 s]
  Range (min … max):    6.152 s …  6.314 s    5 runs

Benchmark 1: cargo +miri miri run --manifest-path /home/ben/miri/bench-cargo-miri/slice-get-unchecked/Cargo.toml
  Time (mean ± σ):      4.733 s ±  0.080 s    [User: 4.177 s, System: 0.513 s]
  Range (min … max):    4.681 s …  4.874 s    5 runs

Benchmark 1: cargo +miri miri run --manifest-path /home/ben/miri/bench-cargo-miri/unicode/Cargo.toml
  Time (mean ± σ):      3.770 s ±  0.034 s    [User: 3.549 s, System: 0.211 s]
  Range (min … max):    3.724 s …  3.819 s    5 runs
```
GC on:
```
Benchmark 1: cargo +miri miri run --manifest-path /home/ben/miri/bench-cargo-miri/backtraces/Cargo.toml
  Time (mean ± σ):      5.886 s ±  0.054 s    [User: 5.696 s, System: 0.182 s]
  Range (min … max):    5.799 s …  5.937 s    5 runs

Benchmark 1: cargo +miri miri run --manifest-path /home/ben/miri/bench-cargo-miri/mse/Cargo.toml
  Time (mean ± σ):     936.4 ms ±   7.0 ms    [User: 815.4 ms, System: 119.6 ms]
  Range (min … max):   925.7 ms … 945.0 ms    5 runs

Benchmark 1: cargo +miri miri run --manifest-path /home/ben/miri/bench-cargo-miri/serde1/Cargo.toml
  Time (mean ± σ):      2.126 s ±  0.022 s    [User: 1.979 s, System: 0.146 s]
  Range (min … max):    2.089 s …  2.143 s    5 runs

Benchmark 1: cargo +miri miri run --manifest-path /home/ben/miri/bench-cargo-miri/serde2/Cargo.toml
  Time (mean ± σ):      4.242 s ±  0.066 s    [User: 4.051 s, System: 0.160 s]
  Range (min … max):    4.196 s …  4.357 s    5 runs

Benchmark 1: cargo +miri miri run --manifest-path /home/ben/miri/bench-cargo-miri/slice-get-unchecked/Cargo.toml
  Time (mean ± σ):     907.4 ms ±   2.4 ms    [User: 788.6 ms, System: 118.2 ms]
  Range (min … max):   903.5 ms … 909.4 ms    5 runs

Benchmark 1: cargo +miri miri run --manifest-path /home/ben/miri/bench-cargo-miri/unicode/Cargo.toml
  Time (mean ± σ):      1.821 s ±  0.011 s    [User: 1.687 s, System: 0.133 s]
  Range (min … max):    1.802 s …  1.831 s    5 runs
```

But much more importantly for me this drops the peak memory usage of the first 1 minute of running `regex`'s tests from 103  GB to 1.7 GB.

Thanks to `@oli-obk` for suggesting a while ago that this was possible and `@darksonn` for reminding me that we can just search through memory to find Provenance to locate pointers.

Fixes https://github.com/rust-lang/miri/issues/1367

0 files changed, 0 insertions, 0 deletions