Introduce `ChunkedBitSet` and use it for some dataflow analyses.

This reduces peak memory usage significantly for some programs with very
large functions, such as:
- `keccak`, `unicode_normalization`, and `match-stress-enum`, from
  the `rustc-perf` benchmark suite;
- `http-0.2.6` from crates.io.

The new type is used in the analyses where the bitsets can get huge
(e.g. 10s of thousands of bits): `MaybeInitializedPlaces`,
`MaybeUninitializedPlaces`, and `EverInitializedPlaces`.

Some refactoring was required in `rustc_mir_dataflow`. All existing
analysis domains are either `BitSet` or a trivial wrapper around
`BitSet`, and access in a few places is done via `Borrow<BitSet>` or
`BorrowMut<BitSet>`. Now that some of these domains are `ClusterBitSet`,
that no longer works. So this commit replaces the `Borrow`/`BorrowMut`
usage with a new trait `BitSetExt` containing the needed bitset
operations. The impls just forward these to the underlying bitset type.
This required fiddling with trait bounds in a few places.

The commit also:
- Moves `static_assert_size` from `rustc_data_structures` to
  `rustc_index` so it can be used in the latter; the former now
  re-exports it so existing users are unaffected.
- Factors out some common "clear excess bits in the final word"
  functionality in `bit_set.rs`.
- Uses `fill` in a few places instead of loops.

1 files changed, 27 insertions, 8 deletions

diff --git a/compiler/rustc_mir_dataflow/src/framework/lattice.rs b/compiler/rustc_mir_dataflow/src/framework/lattice.rs
index f937b31f4cf..9a462f6e1a4 100644
--- a/compiler/rustc_mir_dataflow/src/framework/lattice.rs
+++ b/compiler/rustc_mir_dataflow/src/framework/lattice.rs
@@ -38,7 +38,8 @@
 //! [Hasse diagram]: https://en.wikipedia.org/wiki/Hasse_diagram
 //! [poset]: https://en.wikipedia.org/wiki/Partially_ordered_set
 
-use rustc_index::bit_set::BitSet;
+use crate::framework::BitSetExt;
+use rustc_index::bit_set::{BitSet, ChunkedBitSet, HybridBitSet};
 use rustc_index::vec::{Idx, IndexVec};
 use std::iter;
 
@@ -145,6 +146,18 @@ impl<T: Idx> MeetSemiLattice for BitSet<T> {
     }
 }
 
+impl<T: Idx> JoinSemiLattice for ChunkedBitSet<T> {
+    fn join(&mut self, other: &Self) -> bool {
+        self.union(other)
+    }
+}
+
+impl<T: Idx> MeetSemiLattice for ChunkedBitSet<T> {
+    fn meet(&mut self, other: &Self) -> bool {
+        self.intersect(other)
+    }
+}
+
 /// The counterpart of a given semilattice `T` using the [inverse order].
 ///
 /// The dual of a join-semilattice is a meet-semilattice and vice versa. For example, the dual of a
@@ -155,15 +168,21 @@ impl<T: Idx> MeetSemiLattice for BitSet<T> {
 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
 pub struct Dual<T>(pub T);
 
-impl<T> std::borrow::Borrow<T> for Dual<T> {
-    fn borrow(&self) -> &T {
-        &self.0
+impl<T: Idx> BitSetExt<T> for Dual<BitSet<T>> {
+    fn domain_size(&self) -> usize {
+        self.0.domain_size()
+    }
+
+    fn contains(&self, elem: T) -> bool {
+        self.0.contains(elem)
+    }
+
+    fn union(&mut self, other: &HybridBitSet<T>) {
+        self.0.union(other);
     }
-}
 
-impl<T> std::borrow::BorrowMut<T> for Dual<T> {
-    fn borrow_mut(&mut self) -> &mut T {
-        &mut self.0
+    fn subtract(&mut self, other: &HybridBitSet<T>) {
+        self.0.subtract(other);
     }
 }