rename `BitSet` to `DenseBitSet`

This should make it clearer that this bitset is dense, with the
advantages and disadvantages that it entails.

24 files changed, 131 insertions, 125 deletions

diff --git a/compiler/rustc_mir_transform/src/copy_prop.rs b/compiler/rustc_mir_transform/src/copy_prop.rs
index 9b3443d3209..f149bf97cde 100644
--- a/compiler/rustc_mir_transform/src/copy_prop.rs
+++ b/compiler/rustc_mir_transform/src/copy_prop.rs
@@ -1,5 +1,5 @@
 use rustc_index::IndexSlice;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::visit::*;
 use rustc_middle::mir::*;
 use rustc_middle::ty::TyCtxt;
@@ -34,7 +34,7 @@ impl<'tcx> crate::MirPass<'tcx> for CopyProp {
         let fully_moved = fully_moved_locals(&ssa, body);
         debug!(?fully_moved);
 
-        let mut storage_to_remove = BitSet::new_empty(fully_moved.domain_size());
+        let mut storage_to_remove = DenseBitSet::new_empty(fully_moved.domain_size());
         for (local, &head) in ssa.copy_classes().iter_enumerated() {
             if local != head {
                 storage_to_remove.insert(head);
@@ -68,8 +68,8 @@ impl<'tcx> crate::MirPass<'tcx> for CopyProp {
 /// This means that replacing it by a copy of `_a` if ok, since this copy happens before `_c` is
 /// moved, and therefore that `_d` is moved.
 #[instrument(level = "trace", skip(ssa, body))]
-fn fully_moved_locals(ssa: &SsaLocals, body: &Body<'_>) -> BitSet<Local> {
-    let mut fully_moved = BitSet::new_filled(body.local_decls.len());
+fn fully_moved_locals(ssa: &SsaLocals, body: &Body<'_>) -> DenseBitSet<Local> {
+    let mut fully_moved = DenseBitSet::new_filled(body.local_decls.len());
 
     for (_, rvalue, _) in ssa.assignments(body) {
         let (Rvalue::Use(Operand::Copy(place) | Operand::Move(place))
@@ -96,9 +96,9 @@ fn fully_moved_locals(ssa: &SsaLocals, body: &Body<'_>) -> BitSet<Local> {
 /// Utility to help performing substitution of `*pattern` by `target`.
 struct Replacer<'a, 'tcx> {
     tcx: TyCtxt<'tcx>,
-    fully_moved: BitSet<Local>,
-    storage_to_remove: BitSet<Local>,
-    borrowed_locals: &'a BitSet<Local>,
+    fully_moved: DenseBitSet<Local>,
+    storage_to_remove: DenseBitSet<Local>,
+    borrowed_locals: &'a DenseBitSet<Local>,
     copy_classes: &'a IndexSlice<Local, Local>,
 }
 
diff --git a/compiler/rustc_mir_transform/src/coroutine.rs b/compiler/rustc_mir_transform/src/coroutine.rs
index f6536d78761..a3715b5d485 100644
--- a/compiler/rustc_mir_transform/src/coroutine.rs
+++ b/compiler/rustc_mir_transform/src/coroutine.rs
@@ -60,7 +60,7 @@ use rustc_errors::pluralize;
 use rustc_hir as hir;
 use rustc_hir::lang_items::LangItem;
 use rustc_hir::{CoroutineDesugaring, CoroutineKind};
-use rustc_index::bit_set::{BitMatrix, BitSet, GrowableBitSet};
+use rustc_index::bit_set::{BitMatrix, DenseBitSet, GrowableBitSet};
 use rustc_index::{Idx, IndexVec};
 use rustc_middle::mir::visit::{MutVisitor, PlaceContext, Visitor};
 use rustc_middle::mir::*;
@@ -185,13 +185,13 @@ struct TransformVisitor<'tcx> {
     remap: IndexVec<Local, Option<(Ty<'tcx>, VariantIdx, FieldIdx)>>,
 
     // A map from a suspension point in a block to the locals which have live storage at that point
-    storage_liveness: IndexVec<BasicBlock, Option<BitSet<Local>>>,
+    storage_liveness: IndexVec<BasicBlock, Option<DenseBitSet<Local>>>,
 
     // A list of suspension points, generated during the transform
     suspension_points: Vec<SuspensionPoint<'tcx>>,
 
     // The set of locals that have no `StorageLive`/`StorageDead` annotations.
-    always_live_locals: BitSet<Local>,
+    always_live_locals: DenseBitSet<Local>,
 
     // The original RETURN_PLACE local
     old_ret_local: Local,
@@ -633,7 +633,7 @@ struct LivenessInfo {
     saved_locals: CoroutineSavedLocals,
 
     /// The set of saved locals live at each suspension point.
-    live_locals_at_suspension_points: Vec<BitSet<CoroutineSavedLocal>>,
+    live_locals_at_suspension_points: Vec<DenseBitSet<CoroutineSavedLocal>>,
 
     /// Parallel vec to the above with SourceInfo for each yield terminator.
     source_info_at_suspension_points: Vec<SourceInfo>,
@@ -645,7 +645,7 @@ struct LivenessInfo {
 
     /// For every suspending block, the locals which are storage-live across
     /// that suspension point.
-    storage_liveness: IndexVec<BasicBlock, Option<BitSet<Local>>>,
+    storage_liveness: IndexVec<BasicBlock, Option<DenseBitSet<Local>>>,
 }
 
 /// Computes which locals have to be stored in the state-machine for the
@@ -659,7 +659,7 @@ struct LivenessInfo {
 fn locals_live_across_suspend_points<'tcx>(
     tcx: TyCtxt<'tcx>,
     body: &Body<'tcx>,
-    always_live_locals: &BitSet<Local>,
+    always_live_locals: &DenseBitSet<Local>,
     movable: bool,
 ) -> LivenessInfo {
     // Calculate when MIR locals have live storage. This gives us an upper bound of their
@@ -688,7 +688,7 @@ fn locals_live_across_suspend_points<'tcx>(
     let mut storage_liveness_map = IndexVec::from_elem(None, &body.basic_blocks);
     let mut live_locals_at_suspension_points = Vec::new();
     let mut source_info_at_suspension_points = Vec::new();
-    let mut live_locals_at_any_suspension_point = BitSet::new_empty(body.local_decls.len());
+    let mut live_locals_at_any_suspension_point = DenseBitSet::new_empty(body.local_decls.len());
 
     for (block, data) in body.basic_blocks.iter_enumerated() {
         if let TerminatorKind::Yield { .. } = data.terminator().kind {
@@ -768,7 +768,7 @@ fn locals_live_across_suspend_points<'tcx>(
 /// `CoroutineSavedLocal` is indexed in terms of the elements in this set;
 /// i.e. `CoroutineSavedLocal::new(1)` corresponds to the second local
 /// included in this set.
-struct CoroutineSavedLocals(BitSet<Local>);
+struct CoroutineSavedLocals(DenseBitSet<Local>);
 
 impl CoroutineSavedLocals {
     /// Returns an iterator over each `CoroutineSavedLocal` along with the `Local` it corresponds
@@ -777,11 +777,11 @@ impl CoroutineSavedLocals {
         self.iter().enumerate().map(|(i, l)| (CoroutineSavedLocal::from(i), l))
     }
 
-    /// Transforms a `BitSet<Local>` that contains only locals saved across yield points to the
-    /// equivalent `BitSet<CoroutineSavedLocal>`.
-    fn renumber_bitset(&self, input: &BitSet<Local>) -> BitSet<CoroutineSavedLocal> {
+    /// Transforms a `DenseBitSet<Local>` that contains only locals saved across yield points to the
+    /// equivalent `DenseBitSet<CoroutineSavedLocal>`.
+    fn renumber_bitset(&self, input: &DenseBitSet<Local>) -> DenseBitSet<CoroutineSavedLocal> {
         assert!(self.superset(input), "{:?} not a superset of {:?}", self.0, input);
-        let mut out = BitSet::new_empty(self.count());
+        let mut out = DenseBitSet::new_empty(self.count());
         for (saved_local, local) in self.iter_enumerated() {
             if input.contains(local) {
                 out.insert(saved_local);
@@ -801,7 +801,7 @@ impl CoroutineSavedLocals {
 }
 
 impl ops::Deref for CoroutineSavedLocals {
-    type Target = BitSet<Local>;
+    type Target = DenseBitSet<Local>;
 
     fn deref(&self) -> &Self::Target {
         &self.0
@@ -815,7 +815,7 @@ impl ops::Deref for CoroutineSavedLocals {
 fn compute_storage_conflicts<'mir, 'tcx>(
     body: &'mir Body<'tcx>,
     saved_locals: &'mir CoroutineSavedLocals,
-    always_live_locals: BitSet<Local>,
+    always_live_locals: DenseBitSet<Local>,
     mut requires_storage: Results<'tcx, MaybeRequiresStorage<'mir, 'tcx>>,
 ) -> BitMatrix<CoroutineSavedLocal, CoroutineSavedLocal> {
     assert_eq!(body.local_decls.len(), saved_locals.domain_size());
@@ -833,7 +833,7 @@ fn compute_storage_conflicts<'mir, 'tcx>(
         body,
         saved_locals,
         local_conflicts: BitMatrix::from_row_n(&ineligible_locals, body.local_decls.len()),
-        eligible_storage_live: BitSet::new_empty(body.local_decls.len()),
+        eligible_storage_live: DenseBitSet::new_empty(body.local_decls.len()),
     };
 
     requires_storage.visit_reachable_with(body, &mut visitor);
@@ -871,7 +871,7 @@ struct StorageConflictVisitor<'a, 'tcx> {
     // benchmarks for coroutines.
     local_conflicts: BitMatrix<Local, Local>,
     // We keep this bitset as a buffer to avoid reallocating memory.
-    eligible_storage_live: BitSet<Local>,
+    eligible_storage_live: DenseBitSet<Local>,
 }
 
 impl<'a, 'tcx> ResultsVisitor<'a, 'tcx, MaybeRequiresStorage<'a, 'tcx>>
@@ -880,7 +880,7 @@ impl<'a, 'tcx> ResultsVisitor<'a, 'tcx, MaybeRequiresStorage<'a, 'tcx>>
     fn visit_after_early_statement_effect(
         &mut self,
         _results: &mut Results<'tcx, MaybeRequiresStorage<'a, 'tcx>>,
-        state: &BitSet<Local>,
+        state: &DenseBitSet<Local>,
         _statement: &'a Statement<'tcx>,
         loc: Location,
     ) {
@@ -890,7 +890,7 @@ impl<'a, 'tcx> ResultsVisitor<'a, 'tcx, MaybeRequiresStorage<'a, 'tcx>>
     fn visit_after_early_terminator_effect(
         &mut self,
         _results: &mut Results<'tcx, MaybeRequiresStorage<'a, 'tcx>>,
-        state: &BitSet<Local>,
+        state: &DenseBitSet<Local>,
         _terminator: &'a Terminator<'tcx>,
         loc: Location,
     ) {
@@ -899,7 +899,7 @@ impl<'a, 'tcx> ResultsVisitor<'a, 'tcx, MaybeRequiresStorage<'a, 'tcx>>
 }
 
 impl StorageConflictVisitor<'_, '_> {
-    fn apply_state(&mut self, state: &BitSet<Local>, loc: Location) {
+    fn apply_state(&mut self, state: &DenseBitSet<Local>, loc: Location) {
         // Ignore unreachable blocks.
         if let TerminatorKind::Unreachable = self.body.basic_blocks[loc.block].terminator().kind {
             return;
@@ -924,7 +924,7 @@ fn compute_layout<'tcx>(
 ) -> (
     IndexVec<Local, Option<(Ty<'tcx>, VariantIdx, FieldIdx)>>,
     CoroutineLayout<'tcx>,
-    IndexVec<BasicBlock, Option<BitSet<Local>>>,
+    IndexVec<BasicBlock, Option<DenseBitSet<Local>>>,
 ) {
     let LivenessInfo {
         saved_locals,
diff --git a/compiler/rustc_mir_transform/src/coverage/counters.rs b/compiler/rustc_mir_transform/src/coverage/counters.rs
index 9e80f1f1c4a..a9111a5ef9b 100644
--- a/compiler/rustc_mir_transform/src/coverage/counters.rs
+++ b/compiler/rustc_mir_transform/src/coverage/counters.rs
@@ -5,7 +5,7 @@ use rustc_data_structures::captures::Captures;
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::graph::DirectedGraph;
 use rustc_index::IndexVec;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::coverage::{CounterId, CovTerm, Expression, ExpressionId, Op};
 use tracing::{debug, debug_span, instrument};
 
@@ -77,7 +77,7 @@ impl CoverageCounters {
     /// counters or counter expressions for nodes and edges as required.
     pub(super) fn make_bcb_counters(
         graph: &CoverageGraph,
-        bcb_needs_counter: &BitSet<BasicCoverageBlock>,
+        bcb_needs_counter: &DenseBitSet<BasicCoverageBlock>,
     ) -> Self {
         let mut builder = CountersBuilder::new(graph, bcb_needs_counter);
         builder.make_bcb_counters();
@@ -220,13 +220,16 @@ fn sibling_out_edge_targets(
 /// the set of nodes that need counters.
 struct CountersBuilder<'a> {
     graph: &'a CoverageGraph,
-    bcb_needs_counter: &'a BitSet<BasicCoverageBlock>,
+    bcb_needs_counter: &'a DenseBitSet<BasicCoverageBlock>,
 
     site_counters: FxHashMap<Site, SiteCounter>,
 }
 
 impl<'a> CountersBuilder<'a> {
-    fn new(graph: &'a CoverageGraph, bcb_needs_counter: &'a BitSet<BasicCoverageBlock>) -> Self {
+    fn new(
+        graph: &'a CoverageGraph,
+        bcb_needs_counter: &'a DenseBitSet<BasicCoverageBlock>,
+    ) -> Self {
         assert_eq!(graph.num_nodes(), bcb_needs_counter.domain_size());
         Self { graph, bcb_needs_counter, site_counters: FxHashMap::default() }
     }
diff --git a/compiler/rustc_mir_transform/src/coverage/graph.rs b/compiler/rustc_mir_transform/src/coverage/graph.rs
index ad6774fccd6..3fa8b063fa7 100644
--- a/compiler/rustc_mir_transform/src/coverage/graph.rs
+++ b/compiler/rustc_mir_transform/src/coverage/graph.rs
@@ -8,7 +8,7 @@ use rustc_data_structures::fx::FxHashSet;
 use rustc_data_structures::graph::dominators::Dominators;
 use rustc_data_structures::graph::{self, DirectedGraph, StartNode};
 use rustc_index::IndexVec;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::{self, BasicBlock, Terminator, TerminatorKind};
 use tracing::debug;
 
@@ -27,7 +27,7 @@ pub(crate) struct CoverageGraph {
     /// their relative order is consistent but arbitrary.
     dominator_order_rank: IndexVec<BasicCoverageBlock, u32>,
     /// A loop header is a node that dominates one or more of its predecessors.
-    is_loop_header: BitSet<BasicCoverageBlock>,
+    is_loop_header: DenseBitSet<BasicCoverageBlock>,
     /// For each node, the loop header node of its nearest enclosing loop.
     /// This forms a linked list that can be traversed to find all enclosing loops.
     enclosing_loop_header: IndexVec<BasicCoverageBlock, Option<BasicCoverageBlock>>,
@@ -72,7 +72,7 @@ impl CoverageGraph {
             predecessors,
             dominators: None,
             dominator_order_rank: IndexVec::from_elem_n(0, num_nodes),
-            is_loop_header: BitSet::new_empty(num_nodes),
+            is_loop_header: DenseBitSet::new_empty(num_nodes),
             enclosing_loop_header: IndexVec::from_elem_n(None, num_nodes),
         };
         assert_eq!(num_nodes, this.num_nodes());
diff --git a/compiler/rustc_mir_transform/src/coverage/mappings.rs b/compiler/rustc_mir_transform/src/coverage/mappings.rs
index 5bd20e00eb6..8d0d92dc367 100644
--- a/compiler/rustc_mir_transform/src/coverage/mappings.rs
+++ b/compiler/rustc_mir_transform/src/coverage/mappings.rs
@@ -3,7 +3,7 @@ use std::collections::BTreeSet;
 use rustc_data_structures::fx::FxIndexMap;
 use rustc_data_structures::graph::DirectedGraph;
 use rustc_index::IndexVec;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::coverage::{
     BlockMarkerId, BranchSpan, ConditionId, ConditionInfo, CoverageInfoHi, CoverageKind,
 };
@@ -128,7 +128,7 @@ pub(super) fn extract_all_mapping_info_from_mir<'tcx>(
 }
 
 impl ExtractedMappings {
-    pub(super) fn all_bcbs_with_counter_mappings(&self) -> BitSet<BasicCoverageBlock> {
+    pub(super) fn all_bcbs_with_counter_mappings(&self) -> DenseBitSet<BasicCoverageBlock> {
         // Fully destructure self to make sure we don't miss any fields that have mappings.
         let Self {
             num_bcbs,
@@ -140,7 +140,7 @@ impl ExtractedMappings {
         } = self;
 
         // Identify which BCBs have one or more mappings.
-        let mut bcbs_with_counter_mappings = BitSet::new_empty(*num_bcbs);
+        let mut bcbs_with_counter_mappings = DenseBitSet::new_empty(*num_bcbs);
         let mut insert = |bcb| {
             bcbs_with_counter_mappings.insert(bcb);
         };
@@ -172,8 +172,8 @@ impl ExtractedMappings {
     }
 
     /// Returns the set of BCBs that have one or more `Code` mappings.
-    pub(super) fn bcbs_with_ordinary_code_mappings(&self) -> BitSet<BasicCoverageBlock> {
-        let mut bcbs = BitSet::new_empty(self.num_bcbs);
+    pub(super) fn bcbs_with_ordinary_code_mappings(&self) -> DenseBitSet<BasicCoverageBlock> {
+        let mut bcbs = DenseBitSet::new_empty(self.num_bcbs);
         for &CodeMapping { span: _, bcb } in &self.code_mappings {
             bcbs.insert(bcb);
         }
diff --git a/compiler/rustc_mir_transform/src/coverage/query.rs b/compiler/rustc_mir_transform/src/coverage/query.rs
index edaec3c7965..3e7cf8541c2 100644
--- a/compiler/rustc_mir_transform/src/coverage/query.rs
+++ b/compiler/rustc_mir_transform/src/coverage/query.rs
@@ -1,5 +1,5 @@
 use rustc_data_structures::captures::Captures;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::middle::codegen_fn_attrs::CodegenFnAttrFlags;
 use rustc_middle::mir::coverage::{
     CounterId, CovTerm, CoverageIdsInfo, CoverageKind, Expression, ExpressionId,
@@ -92,13 +92,13 @@ fn coverage_ids_info<'tcx>(
 
     let Some(fn_cov_info) = mir_body.function_coverage_info.as_deref() else {
         return CoverageIdsInfo {
-            counters_seen: BitSet::new_empty(0),
-            zero_expressions: BitSet::new_empty(0),
+            counters_seen: DenseBitSet::new_empty(0),
+            zero_expressions: DenseBitSet::new_empty(0),
         };
     };
 
-    let mut counters_seen = BitSet::new_empty(fn_cov_info.num_counters);
-    let mut expressions_seen = BitSet::new_filled(fn_cov_info.expressions.len());
+    let mut counters_seen = DenseBitSet::new_empty(fn_cov_info.num_counters);
+    let mut expressions_seen = DenseBitSet::new_filled(fn_cov_info.expressions.len());
 
     // For each expression ID that is directly used by one or more mappings,
     // mark it as not-yet-seen. This indicates that we expect to see a
@@ -148,23 +148,23 @@ fn is_inlined(body: &Body<'_>, statement: &Statement<'_>) -> bool {
     scope_data.inlined.is_some() || scope_data.inlined_parent_scope.is_some()
 }
 
-/// Identify expressions that will always have a value of zero, and note
-/// their IDs in a `BitSet`. Mappings that refer to a zero expression
-/// can instead become mappings to a constant zero value.
+/// Identify expressions that will always have a value of zero, and note their
+/// IDs in a `DenseBitSet`. Mappings that refer to a zero expression can instead
+/// become mappings to a constant zero value.
 ///
 /// This function mainly exists to preserve the simplifications that were
 /// already being performed by the Rust-side expression renumbering, so that
 /// the resulting coverage mappings don't get worse.
 fn identify_zero_expressions(
     fn_cov_info: &FunctionCoverageInfo,
-    counters_seen: &BitSet<CounterId>,
-    expressions_seen: &BitSet<ExpressionId>,
-) -> BitSet<ExpressionId> {
+    counters_seen: &DenseBitSet<CounterId>,
+    expressions_seen: &DenseBitSet<ExpressionId>,
+) -> DenseBitSet<ExpressionId> {
     // The set of expressions that either were optimized out entirely, or
     // have zero as both of their operands, and will therefore always have
     // a value of zero. Other expressions that refer to these as operands
     // can have those operands replaced with `CovTerm::Zero`.
-    let mut zero_expressions = BitSet::new_empty(fn_cov_info.expressions.len());
+    let mut zero_expressions = DenseBitSet::new_empty(fn_cov_info.expressions.len());
 
     // Simplify a copy of each expression based on lower-numbered expressions,
     // and then update the set of always-zero expressions if necessary.
@@ -228,8 +228,8 @@ fn identify_zero_expressions(
 /// into account knowledge of which counters are unused and which expressions
 /// are always zero.
 fn is_zero_term(
-    counters_seen: &BitSet<CounterId>,
-    zero_expressions: &BitSet<ExpressionId>,
+    counters_seen: &DenseBitSet<CounterId>,
+    zero_expressions: &DenseBitSet<ExpressionId>,
     term: CovTerm,
 ) -> bool {
     match term {
diff --git a/compiler/rustc_mir_transform/src/dead_store_elimination.rs b/compiler/rustc_mir_transform/src/dead_store_elimination.rs
index 0c75cdadc92..434e921d439 100644
--- a/compiler/rustc_mir_transform/src/dead_store_elimination.rs
+++ b/compiler/rustc_mir_transform/src/dead_store_elimination.rs
@@ -26,8 +26,8 @@ use crate::util::is_within_packed;
 
 /// Performs the optimization on the body
 ///
-/// The `borrowed` set must be a `BitSet` of all the locals that are ever borrowed in this body. It
-/// can be generated via the [`borrowed_locals`] function.
+/// The `borrowed` set must be a `DenseBitSet` of all the locals that are ever borrowed in this
+/// body. It can be generated via the [`borrowed_locals`] function.
 fn eliminate<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
     let borrowed_locals = borrowed_locals(body);
 
diff --git a/compiler/rustc_mir_transform/src/deduce_param_attrs.rs b/compiler/rustc_mir_transform/src/deduce_param_attrs.rs
index 67b215c7c9d..049f13ce96d 100644
--- a/compiler/rustc_mir_transform/src/deduce_param_attrs.rs
+++ b/compiler/rustc_mir_transform/src/deduce_param_attrs.rs
@@ -6,7 +6,7 @@
 //! dependent crates can use them.
 
 use rustc_hir::def_id::LocalDefId;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::visit::{NonMutatingUseContext, PlaceContext, Visitor};
 use rustc_middle::mir::{Body, Location, Operand, Place, RETURN_PLACE, Terminator, TerminatorKind};
 use rustc_middle::ty::{self, DeducedParamAttrs, Ty, TyCtxt};
@@ -18,13 +18,13 @@ struct DeduceReadOnly {
     /// Each bit is indexed by argument number, starting at zero (so 0 corresponds to local decl
     /// 1). The bit is true if the argument may have been mutated or false if we know it hasn't
     /// been up to the point we're at.
-    mutable_args: BitSet<usize>,
+    mutable_args: DenseBitSet<usize>,
 }
 
 impl DeduceReadOnly {
     /// Returns a new DeduceReadOnly instance.
     fn new(arg_count: usize) -> Self {
-        Self { mutable_args: BitSet::new_empty(arg_count) }
+        Self { mutable_args: DenseBitSet::new_empty(arg_count) }
     }
 }
 
diff --git a/compiler/rustc_mir_transform/src/dest_prop.rs b/compiler/rustc_mir_transform/src/dest_prop.rs
index e99bee6a01f..1ac4d835946 100644
--- a/compiler/rustc_mir_transform/src/dest_prop.rs
+++ b/compiler/rustc_mir_transform/src/dest_prop.rs
@@ -132,7 +132,7 @@
 //! [attempt 3]: https://github.com/rust-lang/rust/pull/72632
 
 use rustc_data_structures::fx::{FxIndexMap, IndexEntry, IndexOccupiedEntry};
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_index::interval::SparseIntervalMatrix;
 use rustc_middle::bug;
 use rustc_middle::mir::visit::{MutVisitor, PlaceContext, Visitor};
@@ -204,7 +204,8 @@ impl<'tcx> crate::MirPass<'tcx> for DestinationPropagation {
             // Because we only filter once per round, it is unsound to use a local for more than
             // one merge operation within a single round of optimizations. We store here which ones
             // we have already used.
-            let mut merged_locals: BitSet<Local> = BitSet::new_empty(body.local_decls.len());
+            let mut merged_locals: DenseBitSet<Local> =
+                DenseBitSet::new_empty(body.local_decls.len());
 
             // This is the set of merges we will apply this round. It is a subset of the candidates.
             let mut merges = FxIndexMap::default();
@@ -274,7 +275,7 @@ fn apply_merges<'tcx>(
     body: &mut Body<'tcx>,
     tcx: TyCtxt<'tcx>,
     merges: FxIndexMap<Local, Local>,
-    merged_locals: BitSet<Local>,
+    merged_locals: DenseBitSet<Local>,
 ) {
     let mut merger = Merger { tcx, merges, merged_locals };
     merger.visit_body_preserves_cfg(body);
@@ -283,7 +284,7 @@ fn apply_merges<'tcx>(
 struct Merger<'tcx> {
     tcx: TyCtxt<'tcx>,
     merges: FxIndexMap<Local, Local>,
-    merged_locals: BitSet<Local>,
+    merged_locals: DenseBitSet<Local>,
 }
 
 impl<'tcx> MutVisitor<'tcx> for Merger<'tcx> {
@@ -351,7 +352,7 @@ impl Candidates {
     /// Collects the candidates for merging.
     ///
     /// This is responsible for enforcing the first and third bullet point.
-    fn reset_and_find<'tcx>(&mut self, body: &Body<'tcx>, borrowed: &BitSet<Local>) {
+    fn reset_and_find<'tcx>(&mut self, body: &Body<'tcx>, borrowed: &DenseBitSet<Local>) {
         self.c.clear();
         self.reverse.clear();
         let mut visitor = FindAssignments { body, candidates: &mut self.c, borrowed };
@@ -735,7 +736,7 @@ fn places_to_candidate_pair<'tcx>(
 struct FindAssignments<'a, 'tcx> {
     body: &'a Body<'tcx>,
     candidates: &'a mut FxIndexMap<Local, Vec<Local>>,
-    borrowed: &'a BitSet<Local>,
+    borrowed: &'a DenseBitSet<Local>,
 }
 
 impl<'tcx> Visitor<'tcx> for FindAssignments<'_, 'tcx> {
diff --git a/compiler/rustc_mir_transform/src/elaborate_drops.rs b/compiler/rustc_mir_transform/src/elaborate_drops.rs
index 3ebc9113725..988f1a25561 100644
--- a/compiler/rustc_mir_transform/src/elaborate_drops.rs
+++ b/compiler/rustc_mir_transform/src/elaborate_drops.rs
@@ -2,7 +2,7 @@ use std::fmt;
 
 use rustc_abi::{FieldIdx, VariantIdx};
 use rustc_index::IndexVec;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::patch::MirPatch;
 use rustc_middle::mir::*;
 use rustc_middle::ty::{self, TyCtxt};
@@ -96,10 +96,10 @@ impl<'tcx> crate::MirPass<'tcx> for ElaborateDrops {
 fn compute_dead_unwinds<'a, 'tcx>(
     body: &'a Body<'tcx>,
     flow_inits: &mut ResultsCursor<'a, 'tcx, MaybeInitializedPlaces<'a, 'tcx>>,
-) -> BitSet<BasicBlock> {
+) -> DenseBitSet<BasicBlock> {
     // We only need to do this pass once, because unwind edges can only
     // reach cleanup blocks, which can't have unwind edges themselves.
-    let mut dead_unwinds = BitSet::new_empty(body.basic_blocks.len());
+    let mut dead_unwinds = DenseBitSet::new_empty(body.basic_blocks.len());
     for (bb, bb_data) in body.basic_blocks.iter_enumerated() {
         let TerminatorKind::Drop { place, unwind: UnwindAction::Cleanup(_), .. } =
             bb_data.terminator().kind
diff --git a/compiler/rustc_mir_transform/src/gvn.rs b/compiler/rustc_mir_transform/src/gvn.rs
index 71bec38c405..affc4cf0afc 100644
--- a/compiler/rustc_mir_transform/src/gvn.rs
+++ b/compiler/rustc_mir_transform/src/gvn.rs
@@ -94,7 +94,7 @@ use rustc_const_eval::interpret::{
 use rustc_data_structures::fx::FxIndexSet;
 use rustc_data_structures::graph::dominators::Dominators;
 use rustc_hir::def::DefKind;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_index::{IndexVec, newtype_index};
 use rustc_middle::bug;
 use rustc_middle::mir::interpret::GlobalAlloc;
@@ -256,7 +256,7 @@ struct VnState<'body, 'tcx> {
     feature_unsized_locals: bool,
     ssa: &'body SsaLocals,
     dominators: Dominators<BasicBlock>,
-    reused_locals: BitSet<Local>,
+    reused_locals: DenseBitSet<Local>,
 }
 
 impl<'body, 'tcx> VnState<'body, 'tcx> {
@@ -287,7 +287,7 @@ impl<'body, 'tcx> VnState<'body, 'tcx> {
             feature_unsized_locals: tcx.features().unsized_locals(),
             ssa,
             dominators,
-            reused_locals: BitSet::new_empty(local_decls.len()),
+            reused_locals: DenseBitSet::new_empty(local_decls.len()),
         }
     }
 
@@ -1714,7 +1714,7 @@ impl<'tcx> MutVisitor<'tcx> for VnState<'_, 'tcx> {
 
 struct StorageRemover<'tcx> {
     tcx: TyCtxt<'tcx>,
-    reused_locals: BitSet<Local>,
+    reused_locals: DenseBitSet<Local>,
 }
 
 impl<'tcx> MutVisitor<'tcx> for StorageRemover<'tcx> {
diff --git a/compiler/rustc_mir_transform/src/inline.rs b/compiler/rustc_mir_transform/src/inline.rs
index e4daa2b9757..470393c9ae1 100644
--- a/compiler/rustc_mir_transform/src/inline.rs
+++ b/compiler/rustc_mir_transform/src/inline.rs
@@ -8,7 +8,7 @@ use rustc_attr_parsing::InlineAttr;
 use rustc_hir::def::DefKind;
 use rustc_hir::def_id::DefId;
 use rustc_index::Idx;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::bug;
 use rustc_middle::middle::codegen_fn_attrs::CodegenFnAttrs;
 use rustc_middle::mir::visit::*;
@@ -369,7 +369,7 @@ impl<'tcx> Inliner<'tcx> for NormalInliner<'tcx> {
 
         // Traverse the MIR manually so we can account for the effects of inlining on the CFG.
         let mut work_list = vec![START_BLOCK];
-        let mut visited = BitSet::new_empty(callee_body.basic_blocks.len());
+        let mut visited = DenseBitSet::new_empty(callee_body.basic_blocks.len());
         while let Some(bb) = work_list.pop() {
             if !visited.insert(bb.index()) {
                 continue;
@@ -885,7 +885,7 @@ fn inline_call<'tcx, I: Inliner<'tcx>>(
         in_cleanup_block: false,
         return_block,
         tcx,
-        always_live_locals: BitSet::new_filled(callee_body.local_decls.len()),
+        always_live_locals: DenseBitSet::new_filled(callee_body.local_decls.len()),
     };
 
     // Map all `Local`s, `SourceScope`s and `BasicBlock`s to new ones
@@ -1127,7 +1127,7 @@ struct Integrator<'a, 'tcx> {
     in_cleanup_block: bool,
     return_block: Option<BasicBlock>,
     tcx: TyCtxt<'tcx>,
-    always_live_locals: BitSet<Local>,
+    always_live_locals: DenseBitSet<Local>,
 }
 
 impl Integrator<'_, '_> {
diff --git a/compiler/rustc_mir_transform/src/jump_threading.rs b/compiler/rustc_mir_transform/src/jump_threading.rs
index 8feb90ff7a0..c73a03489c5 100644
--- a/compiler/rustc_mir_transform/src/jump_threading.rs
+++ b/compiler/rustc_mir_transform/src/jump_threading.rs
@@ -40,7 +40,7 @@ use rustc_const_eval::const_eval::DummyMachine;
 use rustc_const_eval::interpret::{ImmTy, Immediate, InterpCx, OpTy, Projectable};
 use rustc_data_structures::fx::FxHashSet;
 use rustc_index::IndexVec;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::bug;
 use rustc_middle::mir::interpret::Scalar;
 use rustc_middle::mir::visit::Visitor;
@@ -121,7 +121,7 @@ struct TOFinder<'a, 'tcx> {
     ecx: InterpCx<'tcx, DummyMachine>,
     body: &'a Body<'tcx>,
     map: Map<'tcx>,
-    loop_headers: BitSet<BasicBlock>,
+    loop_headers: DenseBitSet<BasicBlock>,
     /// We use an arena to avoid cloning the slices when cloning `state`.
     arena: &'a DroplessArena,
     opportunities: Vec<ThreadingOpportunity>,
@@ -832,8 +832,8 @@ enum Update {
 /// at least a predecessor which it dominates. This definition is only correct for reducible CFGs.
 /// But if the CFG is already irreducible, there is no point in trying much harder.
 /// is already irreducible.
-fn loop_headers(body: &Body<'_>) -> BitSet<BasicBlock> {
-    let mut loop_headers = BitSet::new_empty(body.basic_blocks.len());
+fn loop_headers(body: &Body<'_>) -> DenseBitSet<BasicBlock> {
+    let mut loop_headers = DenseBitSet::new_empty(body.basic_blocks.len());
     let dominators = body.basic_blocks.dominators();
     // Only visit reachable blocks.
     for (bb, bbdata) in traversal::preorder(body) {
diff --git a/compiler/rustc_mir_transform/src/known_panics_lint.rs b/compiler/rustc_mir_transform/src/known_panics_lint.rs
index f1705d0c831..9b3a0e67295 100644
--- a/compiler/rustc_mir_transform/src/known_panics_lint.rs
+++ b/compiler/rustc_mir_transform/src/known_panics_lint.rs
@@ -13,7 +13,7 @@ use rustc_data_structures::fx::FxHashSet;
 use rustc_hir::HirId;
 use rustc_hir::def::DefKind;
 use rustc_index::IndexVec;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::bug;
 use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor};
 use rustc_middle::mir::*;
@@ -67,7 +67,7 @@ struct ConstPropagator<'mir, 'tcx> {
     tcx: TyCtxt<'tcx>,
     typing_env: ty::TypingEnv<'tcx>,
     worklist: Vec<BasicBlock>,
-    visited_blocks: BitSet<BasicBlock>,
+    visited_blocks: DenseBitSet<BasicBlock>,
     locals: IndexVec<Local, Value<'tcx>>,
     body: &'mir Body<'tcx>,
     written_only_inside_own_block_locals: FxHashSet<Local>,
@@ -190,7 +190,7 @@ impl<'mir, 'tcx> ConstPropagator<'mir, 'tcx> {
             tcx,
             typing_env,
             worklist: vec![START_BLOCK],
-            visited_blocks: BitSet::new_empty(body.basic_blocks.len()),
+            visited_blocks: DenseBitSet::new_empty(body.basic_blocks.len()),
             locals: IndexVec::from_elem_n(Value::Uninit, body.local_decls.len()),
             body,
             can_const_prop,
@@ -852,7 +852,7 @@ enum ConstPropMode {
 struct CanConstProp {
     can_const_prop: IndexVec<Local, ConstPropMode>,
     // False at the beginning. Once set, no more assignments are allowed to that local.
-    found_assignment: BitSet<Local>,
+    found_assignment: DenseBitSet<Local>,
 }
 
 impl CanConstProp {
@@ -864,7 +864,7 @@ impl CanConstProp {
     ) -> IndexVec<Local, ConstPropMode> {
         let mut cpv = CanConstProp {
             can_const_prop: IndexVec::from_elem(ConstPropMode::FullConstProp, &body.local_decls),
-            found_assignment: BitSet::new_empty(body.local_decls.len()),
+            found_assignment: DenseBitSet::new_empty(body.local_decls.len()),
         };
         for (local, val) in cpv.can_const_prop.iter_enumerated_mut() {
             let ty = body.local_decls[local].ty;
diff --git a/compiler/rustc_mir_transform/src/lint.rs b/compiler/rustc_mir_transform/src/lint.rs
index 29e762af8de..f472c7cb493 100644
--- a/compiler/rustc_mir_transform/src/lint.rs
+++ b/compiler/rustc_mir_transform/src/lint.rs
@@ -5,7 +5,7 @@
 use std::borrow::Cow;
 
 use rustc_data_structures::fx::FxHashSet;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::visit::{PlaceContext, Visitor};
 use rustc_middle::mir::*;
 use rustc_middle::ty::TyCtxt;
@@ -43,7 +43,7 @@ struct Lint<'a, 'tcx> {
     when: String,
     body: &'a Body<'tcx>,
     is_fn_like: bool,
-    always_live_locals: &'a BitSet<Local>,
+    always_live_locals: &'a DenseBitSet<Local>,
     maybe_storage_live: ResultsCursor<'a, 'tcx, MaybeStorageLive<'a>>,
     maybe_storage_dead: ResultsCursor<'a, 'tcx, MaybeStorageDead<'a>>,
     places: FxHashSet<PlaceRef<'tcx>>,
diff --git a/compiler/rustc_mir_transform/src/multiple_return_terminators.rs b/compiler/rustc_mir_transform/src/multiple_return_terminators.rs
index a9227524ce5..6dfa14d6b52 100644
--- a/compiler/rustc_mir_transform/src/multiple_return_terminators.rs
+++ b/compiler/rustc_mir_transform/src/multiple_return_terminators.rs
@@ -1,7 +1,7 @@
 //! This pass removes jumps to basic blocks containing only a return, and replaces them with a
 //! return instead.
 
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::*;
 use rustc_middle::ty::TyCtxt;
 
@@ -16,7 +16,7 @@ impl<'tcx> crate::MirPass<'tcx> for MultipleReturnTerminators {
 
     fn run_pass(&self, _: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
         // find basic blocks with no statement and a return terminator
-        let mut bbs_simple_returns = BitSet::new_empty(body.basic_blocks.len());
+        let mut bbs_simple_returns = DenseBitSet::new_empty(body.basic_blocks.len());
         let bbs = body.basic_blocks_mut();
         for idx in bbs.indices() {
             if bbs[idx].statements.is_empty()
diff --git a/compiler/rustc_mir_transform/src/nrvo.rs b/compiler/rustc_mir_transform/src/nrvo.rs
index cd026ed6806..35872de3852 100644
--- a/compiler/rustc_mir_transform/src/nrvo.rs
+++ b/compiler/rustc_mir_transform/src/nrvo.rs
@@ -1,7 +1,7 @@
 //! See the docs for [`RenameReturnPlace`].
 
 use rustc_hir::Mutability;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::bug;
 use rustc_middle::mir::visit::{MutVisitor, NonUseContext, PlaceContext, Visitor};
 use rustc_middle::mir::{self, BasicBlock, Local, Location};
@@ -116,7 +116,7 @@ fn local_eligible_for_nrvo(body: &mir::Body<'_>) -> Option<Local> {
 
 fn find_local_assigned_to_return_place(start: BasicBlock, body: &mir::Body<'_>) -> Option<Local> {
     let mut block = start;
-    let mut seen = BitSet::new_empty(body.basic_blocks.len());
+    let mut seen = DenseBitSet::new_empty(body.basic_blocks.len());
 
     // Iterate as long as `block` has exactly one predecessor that we have not yet visited.
     while seen.insert(block) {
diff --git a/compiler/rustc_mir_transform/src/prettify.rs b/compiler/rustc_mir_transform/src/prettify.rs
index 937c207776b..51abd4da86e 100644
--- a/compiler/rustc_mir_transform/src/prettify.rs
+++ b/compiler/rustc_mir_transform/src/prettify.rs
@@ -4,7 +4,7 @@
 //! (`-Zmir-enable-passes=+ReorderBasicBlocks,+ReorderLocals`)
 //! to make the MIR easier to read for humans.
 
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_index::{IndexSlice, IndexVec};
 use rustc_middle::mir::visit::{MutVisitor, PlaceContext, Visitor};
 use rustc_middle::mir::*;
@@ -51,8 +51,10 @@ impl<'tcx> crate::MirPass<'tcx> for ReorderLocals {
     }
 
     fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
-        let mut finder =
-            LocalFinder { map: IndexVec::new(), seen: BitSet::new_empty(body.local_decls.len()) };
+        let mut finder = LocalFinder {
+            map: IndexVec::new(),
+            seen: DenseBitSet::new_empty(body.local_decls.len()),
+        };
 
         // We can't reorder the return place or the arguments
         for local in (0..=body.arg_count).map(Local::from_usize) {
@@ -113,7 +115,7 @@ impl<'tcx> MutVisitor<'tcx> for BasicBlockUpdater<'tcx> {
 
 struct LocalFinder {
     map: IndexVec<Local, Local>,
-    seen: BitSet<Local>,
+    seen: DenseBitSet<Local>,
 }
 
 impl LocalFinder {
diff --git a/compiler/rustc_mir_transform/src/ref_prop.rs b/compiler/rustc_mir_transform/src/ref_prop.rs
index 96bcdfa6fac..95b05f94270 100644
--- a/compiler/rustc_mir_transform/src/ref_prop.rs
+++ b/compiler/rustc_mir_transform/src/ref_prop.rs
@@ -2,7 +2,7 @@ use std::borrow::Cow;
 
 use rustc_data_structures::fx::FxHashSet;
 use rustc_index::IndexVec;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::bug;
 use rustc_middle::mir::visit::*;
 use rustc_middle::mir::*;
@@ -132,7 +132,7 @@ fn compute_replacement<'tcx>(
     let mut targets = IndexVec::from_elem(Value::Unknown, &body.local_decls);
     // Set of locals for which we will remove their storage statement. This is useful for
     // reborrowed references.
-    let mut storage_to_remove = BitSet::new_empty(body.local_decls.len());
+    let mut storage_to_remove = DenseBitSet::new_empty(body.local_decls.len());
 
     let fully_replacable_locals = fully_replacable_locals(ssa);
 
@@ -324,8 +324,8 @@ fn compute_replacement<'tcx>(
 ///
 /// We consider a local to be replacable iff it's only used in a `Deref` projection `*_local` or
 /// non-use position (like storage statements and debuginfo).
-fn fully_replacable_locals(ssa: &SsaLocals) -> BitSet<Local> {
-    let mut replacable = BitSet::new_empty(ssa.num_locals());
+fn fully_replacable_locals(ssa: &SsaLocals) -> DenseBitSet<Local> {
+    let mut replacable = DenseBitSet::new_empty(ssa.num_locals());
 
     // First pass: for each local, whether its uses can be fully replaced.
     for local in ssa.locals() {
@@ -344,7 +344,7 @@ fn fully_replacable_locals(ssa: &SsaLocals) -> BitSet<Local> {
 struct Replacer<'tcx> {
     tcx: TyCtxt<'tcx>,
     targets: IndexVec<Local, Value<'tcx>>,
-    storage_to_remove: BitSet<Local>,
+    storage_to_remove: DenseBitSet<Local>,
     allowed_replacements: FxHashSet<(Local, Location)>,
     any_replacement: bool,
 }
diff --git a/compiler/rustc_mir_transform/src/remove_noop_landing_pads.rs b/compiler/rustc_mir_transform/src/remove_noop_landing_pads.rs
index fd49e956f43..76a3edfe0be 100644
--- a/compiler/rustc_mir_transform/src/remove_noop_landing_pads.rs
+++ b/compiler/rustc_mir_transform/src/remove_noop_landing_pads.rs
@@ -1,4 +1,4 @@
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::patch::MirPatch;
 use rustc_middle::mir::*;
 use rustc_middle::ty::TyCtxt;
@@ -40,7 +40,7 @@ impl<'tcx> crate::MirPass<'tcx> for RemoveNoopLandingPads {
 
         let mut jumps_folded = 0;
         let mut landing_pads_removed = 0;
-        let mut nop_landing_pads = BitSet::new_empty(body.basic_blocks.len());
+        let mut nop_landing_pads = DenseBitSet::new_empty(body.basic_blocks.len());
 
         // This is a post-order traversal, so that if A post-dominates B
         // then A will be visited before B.
@@ -81,7 +81,7 @@ impl RemoveNoopLandingPads {
         &self,
         bb: BasicBlock,
         body: &Body<'_>,
-        nop_landing_pads: &BitSet<BasicBlock>,
+        nop_landing_pads: &DenseBitSet<BasicBlock>,
     ) -> bool {
         for stmt in &body[bb].statements {
             match &stmt.kind {
diff --git a/compiler/rustc_mir_transform/src/single_use_consts.rs b/compiler/rustc_mir_transform/src/single_use_consts.rs
index 277a33c0311..10b3c0ae94f 100644
--- a/compiler/rustc_mir_transform/src/single_use_consts.rs
+++ b/compiler/rustc_mir_transform/src/single_use_consts.rs
@@ -1,5 +1,5 @@
 use rustc_index::IndexVec;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::bug;
 use rustc_middle::mir::visit::{MutVisitor, PlaceContext, Visitor};
 use rustc_middle::mir::*;
@@ -28,9 +28,9 @@ impl<'tcx> crate::MirPass<'tcx> for SingleUseConsts {
 
     fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
         let mut finder = SingleUseConstsFinder {
-            ineligible_locals: BitSet::new_empty(body.local_decls.len()),
+            ineligible_locals: DenseBitSet::new_empty(body.local_decls.len()),
             locations: IndexVec::from_elem(LocationPair::new(), &body.local_decls),
-            locals_in_debug_info: BitSet::new_empty(body.local_decls.len()),
+            locals_in_debug_info: DenseBitSet::new_empty(body.local_decls.len()),
         };
 
         finder.ineligible_locals.insert_range(..=Local::from_usize(body.arg_count));
@@ -96,9 +96,9 @@ impl LocationPair {
 }
 
 struct SingleUseConstsFinder {
-    ineligible_locals: BitSet<Local>,
+    ineligible_locals: DenseBitSet<Local>,
     locations: IndexVec<Local, LocationPair>,
-    locals_in_debug_info: BitSet<Local>,
+    locals_in_debug_info: DenseBitSet<Local>,
 }
 
 impl<'tcx> Visitor<'tcx> for SingleUseConstsFinder {
diff --git a/compiler/rustc_mir_transform/src/sroa.rs b/compiler/rustc_mir_transform/src/sroa.rs
index 52b9ec1e0a3..d54ea3feab6 100644
--- a/compiler/rustc_mir_transform/src/sroa.rs
+++ b/compiler/rustc_mir_transform/src/sroa.rs
@@ -2,7 +2,7 @@ use rustc_abi::{FIRST_VARIANT, FieldIdx};
 use rustc_data_structures::flat_map_in_place::FlatMapInPlace;
 use rustc_hir::LangItem;
 use rustc_index::IndexVec;
-use rustc_index::bit_set::{BitSet, GrowableBitSet};
+use rustc_index::bit_set::{DenseBitSet, GrowableBitSet};
 use rustc_middle::bug;
 use rustc_middle::mir::patch::MirPatch;
 use rustc_middle::mir::visit::*;
@@ -60,9 +60,9 @@ impl<'tcx> crate::MirPass<'tcx> for ScalarReplacementOfAggregates {
 fn escaping_locals<'tcx>(
     tcx: TyCtxt<'tcx>,
     typing_env: ty::TypingEnv<'tcx>,
-    excluded: &BitSet<Local>,
+    excluded: &DenseBitSet<Local>,
     body: &Body<'tcx>,
-) -> BitSet<Local> {
+) -> DenseBitSet<Local> {
     let is_excluded_ty = |ty: Ty<'tcx>| {
         if ty.is_union() || ty.is_enum() {
             return true;
@@ -97,7 +97,7 @@ fn escaping_locals<'tcx>(
         false
     };
 
-    let mut set = BitSet::new_empty(body.local_decls.len());
+    let mut set = DenseBitSet::new_empty(body.local_decls.len());
     set.insert_range(RETURN_PLACE..=Local::from_usize(body.arg_count));
     for (local, decl) in body.local_decls().iter_enumerated() {
         if excluded.contains(local) || is_excluded_ty(decl.ty) {
@@ -109,7 +109,7 @@ fn escaping_locals<'tcx>(
     return visitor.set;
 
     struct EscapeVisitor {
-        set: BitSet<Local>,
+        set: DenseBitSet<Local>,
     }
 
     impl<'tcx> Visitor<'tcx> for EscapeVisitor {
@@ -198,7 +198,7 @@ fn compute_flattening<'tcx>(
     tcx: TyCtxt<'tcx>,
     typing_env: ty::TypingEnv<'tcx>,
     body: &mut Body<'tcx>,
-    escaping: BitSet<Local>,
+    escaping: DenseBitSet<Local>,
 ) -> ReplacementMap<'tcx> {
     let mut fragments = IndexVec::from_elem(None, &body.local_decls);
 
@@ -226,8 +226,8 @@ fn replace_flattened_locals<'tcx>(
     tcx: TyCtxt<'tcx>,
     body: &mut Body<'tcx>,
     replacements: ReplacementMap<'tcx>,
-) -> BitSet<Local> {
-    let mut all_dead_locals = BitSet::new_empty(replacements.fragments.len());
+) -> DenseBitSet<Local> {
+    let mut all_dead_locals = DenseBitSet::new_empty(replacements.fragments.len());
     for (local, replacements) in replacements.fragments.iter_enumerated() {
         if replacements.is_some() {
             all_dead_locals.insert(local);
@@ -267,7 +267,7 @@ struct ReplacementVisitor<'tcx, 'll> {
     /// Work to do.
     replacements: &'ll ReplacementMap<'tcx>,
     /// This is used to check that we are not leaving references to replaced locals behind.
-    all_dead_locals: BitSet<Local>,
+    all_dead_locals: DenseBitSet<Local>,
     patch: MirPatch<'tcx>,
 }
 
diff --git a/compiler/rustc_mir_transform/src/ssa.rs b/compiler/rustc_mir_transform/src/ssa.rs
index 5653aef0aae..a24b3b2e80f 100644
--- a/compiler/rustc_mir_transform/src/ssa.rs
+++ b/compiler/rustc_mir_transform/src/ssa.rs
@@ -7,7 +7,7 @@
 //! of a `Freeze` local. Those can still be considered to be SSA.
 
 use rustc_data_structures::graph::dominators::Dominators;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_index::{IndexSlice, IndexVec};
 use rustc_middle::bug;
 use rustc_middle::middle::resolve_bound_vars::Set1;
@@ -29,7 +29,7 @@ pub(super) struct SsaLocals {
     /// We ignore non-uses (Storage statements, debuginfo).
     direct_uses: IndexVec<Local, u32>,
     /// Set of SSA locals that are immutably borrowed.
-    borrowed_locals: BitSet<Local>,
+    borrowed_locals: DenseBitSet<Local>,
 }
 
 pub(super) enum AssignedValue<'a, 'tcx> {
@@ -50,7 +50,7 @@ impl SsaLocals {
         let dominators = body.basic_blocks.dominators();
 
         let direct_uses = IndexVec::from_elem(0, &body.local_decls);
-        let borrowed_locals = BitSet::new_empty(body.local_decls.len());
+        let borrowed_locals = DenseBitSet::new_empty(body.local_decls.len());
         let mut visitor = SsaVisitor {
             body,
             assignments,
@@ -202,12 +202,12 @@ impl SsaLocals {
     }
 
     /// Set of SSA locals that are immutably borrowed.
-    pub(super) fn borrowed_locals(&self) -> &BitSet<Local> {
+    pub(super) fn borrowed_locals(&self) -> &DenseBitSet<Local> {
         &self.borrowed_locals
     }
 
     /// Make a property uniform on a copy equivalence class by removing elements.
-    pub(super) fn meet_copy_equivalence(&self, property: &mut BitSet<Local>) {
+    pub(super) fn meet_copy_equivalence(&self, property: &mut DenseBitSet<Local>) {
         // Consolidate to have a local iff all its copies are.
         //
         // `copy_classes` defines equivalence classes between locals. The `local`s that recursively
@@ -241,7 +241,7 @@ struct SsaVisitor<'a, 'tcx> {
     assignment_order: Vec<Local>,
     direct_uses: IndexVec<Local, u32>,
     // Track locals that are immutably borrowed, so we can check their type is `Freeze` later.
-    borrowed_locals: BitSet<Local>,
+    borrowed_locals: DenseBitSet<Local>,
 }
 
 impl SsaVisitor<'_, '_> {
@@ -396,7 +396,7 @@ pub(crate) struct StorageLiveLocals {
 impl StorageLiveLocals {
     pub(crate) fn new(
         body: &Body<'_>,
-        always_storage_live_locals: &BitSet<Local>,
+        always_storage_live_locals: &DenseBitSet<Local>,
     ) -> StorageLiveLocals {
         let mut storage_live = IndexVec::from_elem(Set1::Empty, &body.local_decls);
         for local in always_storage_live_locals.iter() {
diff --git a/compiler/rustc_mir_transform/src/validate.rs b/compiler/rustc_mir_transform/src/validate.rs
index 035670d4903..414477d9004 100644
--- a/compiler/rustc_mir_transform/src/validate.rs
+++ b/compiler/rustc_mir_transform/src/validate.rs
@@ -5,7 +5,7 @@ use rustc_attr_parsing::InlineAttr;
 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use rustc_hir::LangItem;
 use rustc_index::IndexVec;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_infer::infer::TyCtxtInferExt;
 use rustc_infer::traits::{Obligation, ObligationCause};
 use rustc_middle::mir::coverage::CoverageKind;
@@ -98,7 +98,7 @@ struct CfgChecker<'a, 'tcx> {
     body: &'a Body<'tcx>,
     tcx: TyCtxt<'tcx>,
     unwind_edge_count: usize,
-    reachable_blocks: BitSet<BasicBlock>,
+    reachable_blocks: DenseBitSet<BasicBlock>,
     value_cache: FxHashSet<u128>,
     // If `false`, then the MIR must not contain `UnwindAction::Continue` or
     // `TerminatorKind::Resume`.