Rollup merge of #135205 - lqd:bitsets, r=Mark-Simulacrum

Rename `BitSet` to `DenseBitSet`

r? `@Mark-Simulacrum` as you requested this in https://github.com/rust-lang/rust/pull/134438#discussion_r1890659739 after such a confusion.

This PR renames `BitSet` to `DenseBitSet` to make it less obvious as the go-to solution for bitmap needs, as well as make its representation (and positives/negatives) clearer. It also expands the comments there to hopefully make it clearer when it's not a good fit, with some alternative bitsets types.

(This migrates the subtrees cg_gcc and clippy to use the new name in separate commits, for easier review by their respective owners, but they can obvs be squashed)

73 files changed, 397 insertions, 380 deletions

diff --git a/compiler/rustc_borrowck/src/borrow_set.rs b/compiler/rustc_borrowck/src/borrow_set.rs
index a29833464fb..303fa469332 100644
--- a/compiler/rustc_borrowck/src/borrow_set.rs
+++ b/compiler/rustc_borrowck/src/borrow_set.rs
@@ -2,7 +2,7 @@ use std::fmt;
 use std::ops::Index;
 
 use rustc_data_structures::fx::{FxIndexMap, FxIndexSet};
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::visit::{MutatingUseContext, NonUseContext, PlaceContext, Visitor};
 use rustc_middle::mir::{self, Body, Local, Location, traversal};
 use rustc_middle::span_bug;
@@ -131,7 +131,7 @@ impl<'tcx> fmt::Display for BorrowData<'tcx> {
 
 pub enum LocalsStateAtExit {
     AllAreInvalidated,
-    SomeAreInvalidated { has_storage_dead_or_moved: BitSet<Local> },
+    SomeAreInvalidated { has_storage_dead_or_moved: DenseBitSet<Local> },
 }
 
 impl LocalsStateAtExit {
@@ -140,7 +140,7 @@ impl LocalsStateAtExit {
         body: &Body<'tcx>,
         move_data: &MoveData<'tcx>,
     ) -> Self {
-        struct HasStorageDead(BitSet<Local>);
+        struct HasStorageDead(DenseBitSet<Local>);
 
         impl<'tcx> Visitor<'tcx> for HasStorageDead {
             fn visit_local(&mut self, local: Local, ctx: PlaceContext, _: Location) {
@@ -153,7 +153,8 @@ impl LocalsStateAtExit {
         if locals_are_invalidated_at_exit {
             LocalsStateAtExit::AllAreInvalidated
         } else {
-            let mut has_storage_dead = HasStorageDead(BitSet::new_empty(body.local_decls.len()));
+            let mut has_storage_dead =
+                HasStorageDead(DenseBitSet::new_empty(body.local_decls.len()));
             has_storage_dead.visit_body(body);
             let mut has_storage_dead_or_moved = has_storage_dead.0;
             for move_out in &move_data.moves {
diff --git a/compiler/rustc_borrowck/src/dataflow.rs b/compiler/rustc_borrowck/src/dataflow.rs
index abe4d4f20ec..a7a6f2da509 100644
--- a/compiler/rustc_borrowck/src/dataflow.rs
+++ b/compiler/rustc_borrowck/src/dataflow.rs
@@ -2,7 +2,7 @@ use std::fmt;
 
 use rustc_data_structures::fx::FxIndexMap;
 use rustc_data_structures::graph;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::{
     self, BasicBlock, Body, CallReturnPlaces, Location, Place, TerminatorEdges,
 };
@@ -180,7 +180,7 @@ pub struct Borrows<'a, 'tcx> {
 }
 
 struct OutOfScopePrecomputer<'a, 'tcx> {
-    visited: BitSet<mir::BasicBlock>,
+    visited: DenseBitSet<mir::BasicBlock>,
     visit_stack: Vec<mir::BasicBlock>,
     body: &'a Body<'tcx>,
     regioncx: &'a RegionInferenceContext<'tcx>,
@@ -190,7 +190,7 @@ struct OutOfScopePrecomputer<'a, 'tcx> {
 impl<'a, 'tcx> OutOfScopePrecomputer<'a, 'tcx> {
     fn new(body: &'a Body<'tcx>, regioncx: &'a RegionInferenceContext<'tcx>) -> Self {
         OutOfScopePrecomputer {
-            visited: BitSet::new_empty(body.basic_blocks.len()),
+            visited: DenseBitSet::new_empty(body.basic_blocks.len()),
             visit_stack: vec![],
             body,
             regioncx,
@@ -292,7 +292,7 @@ pub fn calculate_borrows_out_of_scope_at_location<'tcx>(
 }
 
 struct PoloniusOutOfScopePrecomputer<'a, 'tcx> {
-    visited: BitSet<mir::BasicBlock>,
+    visited: DenseBitSet<mir::BasicBlock>,
     visit_stack: Vec<mir::BasicBlock>,
     body: &'a Body<'tcx>,
     regioncx: &'a RegionInferenceContext<'tcx>,
@@ -303,7 +303,7 @@ struct PoloniusOutOfScopePrecomputer<'a, 'tcx> {
 impl<'a, 'tcx> PoloniusOutOfScopePrecomputer<'a, 'tcx> {
     fn new(body: &'a Body<'tcx>, regioncx: &'a RegionInferenceContext<'tcx>) -> Self {
         Self {
-            visited: BitSet::new_empty(body.basic_blocks.len()),
+            visited: DenseBitSet::new_empty(body.basic_blocks.len()),
             visit_stack: vec![],
             body,
             regioncx,
@@ -559,7 +559,7 @@ impl<'a, 'tcx> Borrows<'a, 'tcx> {
     }
 }
 
-type BorrowsDomain = BitSet<BorrowIndex>;
+type BorrowsDomain = DenseBitSet<BorrowIndex>;
 
 /// Forward dataflow computation of the set of borrows that are in scope at a particular location.
 /// - we gen the introduced loans
@@ -575,7 +575,7 @@ impl<'tcx> rustc_mir_dataflow::Analysis<'tcx> for Borrows<'_, 'tcx> {
 
     fn bottom_value(&self, _: &mir::Body<'tcx>) -> Self::Domain {
         // bottom = nothing is reserved or activated yet;
-        BitSet::new_empty(self.borrow_set.len())
+        DenseBitSet::new_empty(self.borrow_set.len())
     }
 
     fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
diff --git a/compiler/rustc_borrowck/src/lib.rs b/compiler/rustc_borrowck/src/lib.rs
index 4f46a2cef7c..45764f9c6b8 100644
--- a/compiler/rustc_borrowck/src/lib.rs
+++ b/compiler/rustc_borrowck/src/lib.rs
@@ -28,7 +28,7 @@ use rustc_errors::LintDiagnostic;
 use rustc_hir as hir;
 use rustc_hir::CRATE_HIR_ID;
 use rustc_hir::def_id::LocalDefId;
-use rustc_index::bit_set::{BitSet, MixedBitSet};
+use rustc_index::bit_set::{DenseBitSet, MixedBitSet};
 use rustc_index::{IndexSlice, IndexVec};
 use rustc_infer::infer::{
     InferCtxt, NllRegionVariableOrigin, RegionVariableOrigin, TyCtxtInferExt,
@@ -1017,11 +1017,11 @@ impl<'a, 'tcx> MirBorrowckCtxt<'a, '_, 'tcx> {
         &self,
         location: Location,
         state: &'s BorrowckDomain,
-    ) -> Cow<'s, BitSet<BorrowIndex>> {
+    ) -> Cow<'s, DenseBitSet<BorrowIndex>> {
         if let Some(polonius) = &self.polonius_output {
             // Use polonius output if it has been enabled.
             let location = self.location_table.start_index(location);
-            let mut polonius_output = BitSet::new_empty(self.borrow_set.len());
+            let mut polonius_output = DenseBitSet::new_empty(self.borrow_set.len());
             for &idx in polonius.errors_at(location) {
                 polonius_output.insert(idx);
             }
diff --git a/compiler/rustc_borrowck/src/type_check/liveness/trace.rs b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs
index 7fce49fd16b..4c0d3138f2d 100644
--- a/compiler/rustc_borrowck/src/type_check/liveness/trace.rs
+++ b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs
@@ -1,5 +1,5 @@
 use rustc_data_structures::fx::{FxIndexMap, FxIndexSet};
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_index::interval::IntervalSet;
 use rustc_infer::infer::canonical::QueryRegionConstraints;
 use rustc_infer::infer::outlives::for_liveness;
@@ -129,7 +129,7 @@ struct LivenessResults<'a, 'typeck, 'b, 'tcx> {
     cx: LivenessContext<'a, 'typeck, 'b, 'tcx>,
 
     /// Set of points that define the current local.
-    defs: BitSet<PointIndex>,
+    defs: DenseBitSet<PointIndex>,
 
     /// Points where the current variable is "use live" -- meaning
     /// that there is a future "full use" that may use its value.
@@ -152,7 +152,7 @@ impl<'a, 'typeck, 'b, 'tcx> LivenessResults<'a, 'typeck, 'b, 'tcx> {
         let num_points = cx.location_map.num_points();
         LivenessResults {
             cx,
-            defs: BitSet::new_empty(num_points),
+            defs: DenseBitSet::new_empty(num_points),
             use_live_at: IntervalSet::new(num_points),
             drop_live_at: IntervalSet::new(num_points),
             drop_locations: vec![],
diff --git a/compiler/rustc_codegen_gcc/src/debuginfo.rs b/compiler/rustc_codegen_gcc/src/debuginfo.rs
index 6aeb656c1ab..d3aeb7f3bde 100644
--- a/compiler/rustc_codegen_gcc/src/debuginfo.rs
+++ b/compiler/rustc_codegen_gcc/src/debuginfo.rs
@@ -4,7 +4,7 @@ use gccjit::{Location, RValue};
 use rustc_codegen_ssa::mir::debuginfo::{DebugScope, FunctionDebugContext, VariableKind};
 use rustc_codegen_ssa::traits::{DebugInfoBuilderMethods, DebugInfoCodegenMethods};
 use rustc_data_structures::sync::Lrc;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_index::{Idx, IndexVec};
 use rustc_middle::mir::{self, Body, SourceScope};
 use rustc_middle::ty::{Instance, PolyExistentialTraitRef, Ty};
@@ -69,7 +69,7 @@ fn compute_mir_scopes<'gcc, 'tcx>(
 ) {
     // Find all scopes with variables defined in them.
     let variables = if cx.sess().opts.debuginfo == DebugInfo::Full {
-        let mut vars = BitSet::new_empty(mir.source_scopes.len());
+        let mut vars = DenseBitSet::new_empty(mir.source_scopes.len());
         // FIXME(eddyb) take into account that arguments always have debuginfo,
         // irrespective of their name (assuming full debuginfo is enabled).
         // NOTE(eddyb) actually, on second thought, those are always in the
@@ -82,7 +82,7 @@ fn compute_mir_scopes<'gcc, 'tcx>(
         // Nothing to emit, of course.
         None
     };
-    let mut instantiated = BitSet::new_empty(mir.source_scopes.len());
+    let mut instantiated = DenseBitSet::new_empty(mir.source_scopes.len());
     // Instantiate all scopes.
     for idx in 0..mir.source_scopes.len() {
         let scope = SourceScope::new(idx);
@@ -101,9 +101,9 @@ fn make_mir_scope<'gcc, 'tcx>(
     cx: &CodegenCx<'gcc, 'tcx>,
     _instance: Instance<'tcx>,
     mir: &Body<'tcx>,
-    variables: &Option<BitSet<SourceScope>>,
+    variables: &Option<DenseBitSet<SourceScope>>,
     debug_context: &mut FunctionDebugContext<'tcx, (), Location<'gcc>>,
-    instantiated: &mut BitSet<SourceScope>,
+    instantiated: &mut DenseBitSet<SourceScope>,
     scope: SourceScope,
 ) {
     if instantiated.contains(scope) {
diff --git a/compiler/rustc_codegen_llvm/src/debuginfo/create_scope_map.rs b/compiler/rustc_codegen_llvm/src/debuginfo/create_scope_map.rs
index 07bd0f4d1c1..e545ce386ed 100644
--- a/compiler/rustc_codegen_llvm/src/debuginfo/create_scope_map.rs
+++ b/compiler/rustc_codegen_llvm/src/debuginfo/create_scope_map.rs
@@ -4,7 +4,7 @@ use rustc_codegen_ssa::mir::debuginfo::{DebugScope, FunctionDebugContext};
 use rustc_codegen_ssa::traits::*;
 use rustc_data_structures::fx::FxHashMap;
 use rustc_index::Idx;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::{Body, SourceScope};
 use rustc_middle::ty::layout::{FnAbiOf, HasTypingEnv};
 use rustc_middle::ty::{self, Instance};
@@ -27,7 +27,7 @@ pub(crate) fn compute_mir_scopes<'ll, 'tcx>(
 ) {
     // Find all scopes with variables defined in them.
     let variables = if cx.sess().opts.debuginfo == DebugInfo::Full {
-        let mut vars = BitSet::new_empty(mir.source_scopes.len());
+        let mut vars = DenseBitSet::new_empty(mir.source_scopes.len());
         // FIXME(eddyb) take into account that arguments always have debuginfo,
         // irrespective of their name (assuming full debuginfo is enabled).
         // NOTE(eddyb) actually, on second thought, those are always in the
@@ -40,7 +40,7 @@ pub(crate) fn compute_mir_scopes<'ll, 'tcx>(
         // Nothing to emit, of course.
         None
     };
-    let mut instantiated = BitSet::new_empty(mir.source_scopes.len());
+    let mut instantiated = DenseBitSet::new_empty(mir.source_scopes.len());
     let mut discriminators = FxHashMap::default();
     // Instantiate all scopes.
     for idx in 0..mir.source_scopes.len() {
@@ -63,9 +63,9 @@ fn make_mir_scope<'ll, 'tcx>(
     cx: &CodegenCx<'ll, 'tcx>,
     instance: Instance<'tcx>,
     mir: &Body<'tcx>,
-    variables: &Option<BitSet<SourceScope>>,
+    variables: &Option<DenseBitSet<SourceScope>>,
     debug_context: &mut FunctionDebugContext<'tcx, &'ll DIScope, &'ll DILocation>,
-    instantiated: &mut BitSet<SourceScope>,
+    instantiated: &mut DenseBitSet<SourceScope>,
     discriminators: &mut FxHashMap<BytePos, u32>,
     scope: SourceScope,
 ) {
diff --git a/compiler/rustc_codegen_ssa/src/mir/analyze.rs b/compiler/rustc_codegen_ssa/src/mir/analyze.rs
index 43b8230c679..23baab3124e 100644
--- a/compiler/rustc_codegen_ssa/src/mir/analyze.rs
+++ b/compiler/rustc_codegen_ssa/src/mir/analyze.rs
@@ -2,7 +2,7 @@
 //! which do not.
 
 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::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor};
 use rustc_middle::mir::{self, DefLocation, Location, TerminatorKind, traversal};
@@ -16,7 +16,7 @@ use crate::traits::*;
 pub(crate) fn non_ssa_locals<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
     fx: &FunctionCx<'a, 'tcx, Bx>,
     traversal_order: &[mir::BasicBlock],
-) -> BitSet<mir::Local> {
+) -> DenseBitSet<mir::Local> {
     let mir = fx.mir;
     let dominators = mir.basic_blocks.dominators();
     let locals = mir
@@ -44,7 +44,7 @@ pub(crate) fn non_ssa_locals<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
         analyzer.visit_basic_block_data(bb, data);
     }
 
-    let mut non_ssa_locals = BitSet::new_empty(analyzer.locals.len());
+    let mut non_ssa_locals = DenseBitSet::new_empty(analyzer.locals.len());
     for (local, kind) in analyzer.locals.iter_enumerated() {
         if matches!(kind, LocalKind::Memory) {
             non_ssa_locals.insert(local);
diff --git a/compiler/rustc_codegen_ssa/src/mir/mod.rs b/compiler/rustc_codegen_ssa/src/mir/mod.rs
index 62f69af3f2f..3a896071bc6 100644
--- a/compiler/rustc_codegen_ssa/src/mir/mod.rs
+++ b/compiler/rustc_codegen_ssa/src/mir/mod.rs
@@ -1,7 +1,7 @@
 use std::iter;
 
 use rustc_index::IndexVec;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::middle::codegen_fn_attrs::CodegenFnAttrFlags;
 use rustc_middle::mir::{UnwindTerminateReason, traversal};
 use rustc_middle::ty::layout::{FnAbiOf, HasTyCtxt, HasTypingEnv, TyAndLayout};
@@ -293,7 +293,7 @@ pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
     // So drop the builder of `start_llbb` to avoid having two at the same time.
     drop(start_bx);
 
-    let mut unreached_blocks = BitSet::new_filled(mir.basic_blocks.len());
+    let mut unreached_blocks = DenseBitSet::new_filled(mir.basic_blocks.len());
     // Codegen the body of each reachable block using our reverse postorder list.
     for bb in traversal_order {
         fx.codegen_block(bb);
@@ -316,7 +316,7 @@ pub fn codegen_mir<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
 fn arg_local_refs<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
     bx: &mut Bx,
     fx: &mut FunctionCx<'a, 'tcx, Bx>,
-    memory_locals: &BitSet<mir::Local>,
+    memory_locals: &DenseBitSet<mir::Local>,
 ) -> Vec<LocalRef<'tcx, Bx::Value>> {
     let mir = fx.mir;
     let mut idx = 0;
diff --git a/compiler/rustc_const_eval/src/check_consts/check.rs b/compiler/rustc_const_eval/src/check_consts/check.rs
index 015e1671682..7a5f6c17268 100644
--- a/compiler/rustc_const_eval/src/check_consts/check.rs
+++ b/compiler/rustc_const_eval/src/check_consts/check.rs
@@ -10,7 +10,7 @@ use rustc_attr_parsing::{ConstStability, StabilityLevel};
 use rustc_errors::{Diag, ErrorGuaranteed};
 use rustc_hir::def_id::DefId;
 use rustc_hir::{self as hir, LangItem};
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_infer::infer::TyCtxtInferExt;
 use rustc_middle::mir::visit::Visitor;
 use rustc_middle::mir::*;
@@ -172,7 +172,7 @@ pub struct Checker<'mir, 'tcx> {
 
     /// A set that stores for each local whether it is "transient", i.e. guaranteed to be dead
     /// when this MIR body returns.
-    transient_locals: Option<BitSet<Local>>,
+    transient_locals: Option<DenseBitSet<Local>>,
 
     error_emitted: Option<ErrorGuaranteed>,
     secondary_errors: Vec<Diag<'tcx>>,
@@ -242,7 +242,7 @@ impl<'mir, 'tcx> Checker<'mir, 'tcx> {
 
                 // And then check all `Return` in the MIR, and if a local is "maybe live" at a
                 // `Return` then it is definitely not transient.
-                let mut transient = BitSet::new_filled(ccx.body.local_decls.len());
+                let mut transient = DenseBitSet::new_filled(ccx.body.local_decls.len());
                 // Make sure to only visit reachable blocks, the dataflow engine can ICE otherwise.
                 for (bb, data) in traversal::reachable(&ccx.body) {
                     if matches!(data.terminator().kind, TerminatorKind::Return) {
diff --git a/compiler/rustc_data_structures/src/graph/implementation/mod.rs b/compiler/rustc_data_structures/src/graph/implementation/mod.rs
index 43fdfe6ee0d..7724e9347d8 100644
--- a/compiler/rustc_data_structures/src/graph/implementation/mod.rs
+++ b/compiler/rustc_data_structures/src/graph/implementation/mod.rs
@@ -22,7 +22,7 @@
 
 use std::fmt::Debug;
 
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use tracing::debug;
 
 #[cfg(test)]
@@ -214,7 +214,7 @@ impl<N: Debug, E: Debug> Graph<N, E> {
         direction: Direction,
         entry_node: NodeIndex,
     ) -> Vec<NodeIndex> {
-        let mut visited = BitSet::new_empty(self.len_nodes());
+        let mut visited = DenseBitSet::new_empty(self.len_nodes());
         let mut stack = vec![];
         let mut result = Vec::with_capacity(self.len_nodes());
         let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| {
@@ -287,7 +287,7 @@ impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> {
 pub struct DepthFirstTraversal<'g, N, E> {
     graph: &'g Graph<N, E>,
     stack: Vec<NodeIndex>,
-    visited: BitSet<usize>,
+    visited: DenseBitSet<usize>,
     direction: Direction,
 }
 
@@ -297,7 +297,7 @@ impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> {
         start_node: NodeIndex,
         direction: Direction,
     ) -> Self {
-        let mut visited = BitSet::new_empty(graph.len_nodes());
+        let mut visited = DenseBitSet::new_empty(graph.len_nodes());
         visited.insert(start_node.node_id());
         DepthFirstTraversal { graph, stack: vec![start_node], visited, direction }
     }
diff --git a/compiler/rustc_data_structures/src/graph/iterate/mod.rs b/compiler/rustc_data_structures/src/graph/iterate/mod.rs
index cbc6664d853..ecda7d3fba8 100644
--- a/compiler/rustc_data_structures/src/graph/iterate/mod.rs
+++ b/compiler/rustc_data_structures/src/graph/iterate/mod.rs
@@ -1,6 +1,6 @@
 use std::ops::ControlFlow;
 
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_index::{IndexSlice, IndexVec};
 
 use super::{DirectedGraph, StartNode, Successors};
@@ -78,7 +78,7 @@ where
 {
     graph: G,
     stack: Vec<G::Node>,
-    visited: BitSet<G::Node>,
+    visited: DenseBitSet<G::Node>,
 }
 
 impl<G> DepthFirstSearch<G>
@@ -86,7 +86,7 @@ where
     G: DirectedGraph + Successors,
 {
     pub fn new(graph: G) -> Self {
-        Self { stack: vec![], visited: BitSet::new_empty(graph.num_nodes()), graph }
+        Self { stack: vec![], visited: DenseBitSet::new_empty(graph.num_nodes()), graph }
     }
 
     /// Version of `push_start_node` that is convenient for chained
@@ -207,8 +207,8 @@ where
 {
     graph: &'graph G,
     stack: Vec<Event<G::Node>>,
-    visited: BitSet<G::Node>,
-    settled: BitSet<G::Node>,
+    visited: DenseBitSet<G::Node>,
+    settled: DenseBitSet<G::Node>,
 }
 
 impl<'graph, G> TriColorDepthFirstSearch<'graph, G>
@@ -219,8 +219,8 @@ where
         TriColorDepthFirstSearch {
             graph,
             stack: vec![],
-            visited: BitSet::new_empty(graph.num_nodes()),
-            settled: BitSet::new_empty(graph.num_nodes()),
+            visited: DenseBitSet::new_empty(graph.num_nodes()),
+            settled: DenseBitSet::new_empty(graph.num_nodes()),
         }
     }
 
diff --git a/compiler/rustc_data_structures/src/stable_hasher.rs b/compiler/rustc_data_structures/src/stable_hasher.rs
index 0872bd2c9ac..9cd0cc499ca 100644
--- a/compiler/rustc_data_structures/src/stable_hasher.rs
+++ b/compiler/rustc_data_structures/src/stable_hasher.rs
@@ -3,7 +3,7 @@ use std::marker::PhantomData;
 use std::mem;
 use std::num::NonZero;
 
-use rustc_index::bit_set::{self, BitSet};
+use rustc_index::bit_set::{self, DenseBitSet};
 use rustc_index::{Idx, IndexSlice, IndexVec};
 use smallvec::SmallVec;
 
@@ -544,7 +544,7 @@ where
     }
 }
 
-impl<I: Idx, CTX> HashStable<CTX> for BitSet<I> {
+impl<I: Idx, CTX> HashStable<CTX> for DenseBitSet<I> {
     fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) {
         ::std::hash::Hash::hash(self, hasher);
     }
diff --git a/compiler/rustc_data_structures/src/stable_hasher/tests.rs b/compiler/rustc_data_structures/src/stable_hasher/tests.rs
index aab50a13af0..635f241847c 100644
--- a/compiler/rustc_data_structures/src/stable_hasher/tests.rs
+++ b/compiler/rustc_data_structures/src/stable_hasher/tests.rs
@@ -17,9 +17,9 @@ fn hash<T: HashStable<()>>(t: &T) -> Hash128 {
 // Check that bit set hash includes the domain size.
 #[test]
 fn test_hash_bit_set() {
-    use rustc_index::bit_set::BitSet;
-    let a: BitSet<usize> = BitSet::new_empty(1);
-    let b: BitSet<usize> = BitSet::new_empty(2);
+    use rustc_index::bit_set::DenseBitSet;
+    let a: DenseBitSet<usize> = DenseBitSet::new_empty(1);
+    let b: DenseBitSet<usize> = DenseBitSet::new_empty(2);
     assert_ne!(a, b);
     assert_ne!(hash(&a), hash(&b));
 }
diff --git a/compiler/rustc_data_structures/src/work_queue.rs b/compiler/rustc_data_structures/src/work_queue.rs
index ca052e2eac6..815756edfeb 100644
--- a/compiler/rustc_data_structures/src/work_queue.rs
+++ b/compiler/rustc_data_structures/src/work_queue.rs
@@ -1,7 +1,7 @@
 use std::collections::VecDeque;
 
 use rustc_index::Idx;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 
 /// A work queue is a handy data structure for tracking work left to
 /// do. (For example, basic blocks left to process.) It is basically a
@@ -11,14 +11,14 @@ use rustc_index::bit_set::BitSet;
 /// and also use a bit set to track occupancy.
 pub struct WorkQueue<T: Idx> {
     deque: VecDeque<T>,
-    set: BitSet<T>,
+    set: DenseBitSet<T>,
 }
 
 impl<T: Idx> WorkQueue<T> {
     /// Creates a new work queue that starts empty, where elements range from (0..len).
     #[inline]
     pub fn with_none(len: usize) -> Self {
-        WorkQueue { deque: VecDeque::with_capacity(len), set: BitSet::new_empty(len) }
+        WorkQueue { deque: VecDeque::with_capacity(len), set: DenseBitSet::new_empty(len) }
     }
 
     /// Attempt to enqueue `element` in the work queue. Returns false if it was already present.
diff --git a/compiler/rustc_hir_analysis/src/check/check.rs b/compiler/rustc_hir_analysis/src/check/check.rs
index 8c6059d49a8..821829455d9 100644
--- a/compiler/rustc_hir_analysis/src/check/check.rs
+++ b/compiler/rustc_hir_analysis/src/check/check.rs
@@ -1666,7 +1666,7 @@ fn check_type_alias_type_params_are_used<'tcx>(tcx: TyCtxt<'tcx>, def_id: LocalD
             .collect::<FxIndexMap<_, _>>()
     });
 
-    let mut params_used = BitSet::new_empty(generics.own_params.len());
+    let mut params_used = DenseBitSet::new_empty(generics.own_params.len());
     for leaf in ty.walk() {
         if let GenericArgKind::Type(leaf_ty) = leaf.unpack()
             && let ty::Param(param) = leaf_ty.kind()
diff --git a/compiler/rustc_hir_analysis/src/check/mod.rs b/compiler/rustc_hir_analysis/src/check/mod.rs
index 0b0c92a726d..92b18c80fd8 100644
--- a/compiler/rustc_hir_analysis/src/check/mod.rs
+++ b/compiler/rustc_hir_analysis/src/check/mod.rs
@@ -79,7 +79,7 @@ use rustc_data_structures::fx::{FxHashSet, FxIndexMap};
 use rustc_errors::{Diag, ErrorGuaranteed, pluralize, struct_span_code_err};
 use rustc_hir::def_id::{DefId, LocalDefId};
 use rustc_hir::intravisit::Visitor;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_infer::infer::outlives::env::OutlivesEnvironment;
 use rustc_infer::infer::{self, TyCtxtInferExt as _};
 use rustc_infer::traits::ObligationCause;
diff --git a/compiler/rustc_index/src/bit_set.rs b/compiler/rustc_index/src/bit_set.rs
index 38e2dbbde7d..d93707b745d 100644
--- a/compiler/rustc_index/src/bit_set.rs
+++ b/compiler/rustc_index/src/bit_set.rs
@@ -97,7 +97,13 @@ macro_rules! bit_relations_inherent_impls {
 
 /// A fixed-size bitset type with a dense representation.
 ///
-/// NOTE: Use [`GrowableBitSet`] if you need support for resizing after creation.
+/// Note 1: Since this bitset is dense, if your domain is big, and/or relatively
+/// homogeneous (for example, with long runs of bits set or unset), then it may
+/// be preferable to instead use a [MixedBitSet], or an
+/// [IntervalSet](crate::interval::IntervalSet). They should be more suited to
+/// sparse, or highly-compressible, domains.
+///
+/// Note 2: Use [`GrowableBitSet`] if you need support for resizing after creation.
 ///
 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
 /// just be `usize`.
@@ -108,33 +114,33 @@ macro_rules! bit_relations_inherent_impls {
 ///
 #[cfg_attr(feature = "nightly", derive(Decodable_Generic, Encodable_Generic))]
 #[derive(Eq, PartialEq, Hash)]
-pub struct BitSet<T> {
+pub struct DenseBitSet<T> {
     domain_size: usize,
     words: SmallVec<[Word; 2]>,
     marker: PhantomData<T>,
 }
 
-impl<T> BitSet<T> {
+impl<T> DenseBitSet<T> {
     /// Gets the domain size.
     pub fn domain_size(&self) -> usize {
         self.domain_size
     }
 }
 
-impl<T: Idx> BitSet<T> {
+impl<T: Idx> DenseBitSet<T> {
     /// Creates a new, empty bitset with a given `domain_size`.
     #[inline]
-    pub fn new_empty(domain_size: usize) -> BitSet<T> {
+    pub fn new_empty(domain_size: usize) -> DenseBitSet<T> {
         let num_words = num_words(domain_size);
-        BitSet { domain_size, words: smallvec![0; num_words], marker: PhantomData }
+        DenseBitSet { domain_size, words: smallvec![0; num_words], marker: PhantomData }
     }
 
     /// Creates a new, filled bitset with a given `domain_size`.
     #[inline]
-    pub fn new_filled(domain_size: usize) -> BitSet<T> {
+    pub fn new_filled(domain_size: usize) -> DenseBitSet<T> {
         let num_words = num_words(domain_size);
         let mut result =
-            BitSet { domain_size, words: smallvec![!0; num_words], marker: PhantomData };
+            DenseBitSet { domain_size, words: smallvec![!0; num_words], marker: PhantomData };
         result.clear_excess_bits();
         result
     }
@@ -165,7 +171,7 @@ impl<T: Idx> BitSet<T> {
 
     /// Is `self` is a (non-strict) superset of `other`?
     #[inline]
-    pub fn superset(&self, other: &BitSet<T>) -> bool {
+    pub fn superset(&self, other: &DenseBitSet<T>) -> bool {
         assert_eq!(self.domain_size, other.domain_size);
         self.words.iter().zip(&other.words).all(|(a, b)| (a & b) == *b)
     }
@@ -278,32 +284,36 @@ impl<T: Idx> BitSet<T> {
 }
 
 // dense REL dense
-impl<T: Idx> BitRelations<BitSet<T>> for BitSet<T> {
-    fn union(&mut self, other: &BitSet<T>) -> bool {
+impl<T: Idx> BitRelations<DenseBitSet<T>> for DenseBitSet<T> {
+    fn union(&mut self, other: &DenseBitSet<T>) -> bool {
         assert_eq!(self.domain_size, other.domain_size);
         bitwise(&mut self.words, &other.words, |a, b| a | b)
     }
 
-    fn subtract(&mut self, other: &BitSet<T>) -> bool {
+    fn subtract(&mut self, other: &DenseBitSet<T>) -> bool {
         assert_eq!(self.domain_size, other.domain_size);
         bitwise(&mut self.words, &other.words, |a, b| a & !b)
     }
 
-    fn intersect(&mut self, other: &BitSet<T>) -> bool {
+    fn intersect(&mut self, other: &DenseBitSet<T>) -> bool {
         assert_eq!(self.domain_size, other.domain_size);
         bitwise(&mut self.words, &other.words, |a, b| a & b)
     }
 }
 
-impl<T: Idx> From<GrowableBitSet<T>> for BitSet<T> {
+impl<T: Idx> From<GrowableBitSet<T>> for DenseBitSet<T> {
     fn from(bit_set: GrowableBitSet<T>) -> Self {
         bit_set.bit_set
     }
 }
 
-impl<T> Clone for BitSet<T> {
+impl<T> Clone for DenseBitSet<T> {
     fn clone(&self) -> Self {
-        BitSet { domain_size: self.domain_size, words: self.words.clone(), marker: PhantomData }
+        DenseBitSet {
+            domain_size: self.domain_size,
+            words: self.words.clone(),
+            marker: PhantomData,
+        }
     }
 
     fn clone_from(&mut self, from: &Self) {
@@ -312,13 +322,13 @@ impl<T> Clone for BitSet<T> {
     }
 }
 
-impl<T: Idx> fmt::Debug for BitSet<T> {
+impl<T: Idx> fmt::Debug for DenseBitSet<T> {
     fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result {
         w.debug_list().entries(self.iter()).finish()
     }
 }
 
-impl<T: Idx> ToString for BitSet<T> {
+impl<T: Idx> ToString for DenseBitSet<T> {
     fn to_string(&self) -> String {
         let mut result = String::new();
         let mut sep = '[';
@@ -902,7 +912,7 @@ impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<T> {
     }
 }
 
-impl<T: Idx> BitRelations<ChunkedBitSet<T>> for BitSet<T> {
+impl<T: Idx> BitRelations<ChunkedBitSet<T>> for DenseBitSet<T> {
     fn union(&mut self, other: &ChunkedBitSet<T>) -> bool {
         sequential_update(|elem| self.insert(elem), other.iter())
     }
@@ -1114,10 +1124,10 @@ where
     false
 }
 
-/// A bitset with a mixed representation, using `BitSet` for small and medium
-/// bitsets, and `ChunkedBitSet` for large bitsets, i.e. those with enough bits
-/// for at least two chunks. This is a good choice for many bitsets that can
-/// have large domain sizes (e.g. 5000+).
+/// A bitset with a mixed representation, using `DenseBitSet` for small and
+/// medium bitsets, and `ChunkedBitSet` for large bitsets, i.e. those with
+/// enough bits for at least two chunks. This is a good choice for many bitsets
+/// that can have large domain sizes (e.g. 5000+).
 ///
 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
 /// just be `usize`.
@@ -1127,7 +1137,7 @@ where
 /// will panic if the bitsets have differing domain sizes.
 #[derive(PartialEq, Eq)]
 pub enum MixedBitSet<T> {
-    Small(BitSet<T>),
+    Small(DenseBitSet<T>),
     Large(ChunkedBitSet<T>),
 }
 
@@ -1144,7 +1154,7 @@ impl<T: Idx> MixedBitSet<T> {
     #[inline]
     pub fn new_empty(domain_size: usize) -> MixedBitSet<T> {
         if domain_size <= CHUNK_BITS {
-            MixedBitSet::Small(BitSet::new_empty(domain_size))
+            MixedBitSet::Small(DenseBitSet::new_empty(domain_size))
         } else {
             MixedBitSet::Large(ChunkedBitSet::new_empty(domain_size))
         }
@@ -1283,7 +1293,7 @@ impl<'a, T: Idx> Iterator for MixedBitIter<'a, T> {
 /// to or greater than the domain size.
 #[derive(Clone, Debug, PartialEq)]
 pub struct GrowableBitSet<T: Idx> {
-    bit_set: BitSet<T>,
+    bit_set: DenseBitSet<T>,
 }
 
 impl<T: Idx> Default for GrowableBitSet<T> {
@@ -1306,11 +1316,11 @@ impl<T: Idx> GrowableBitSet<T> {
     }
 
     pub fn new_empty() -> GrowableBitSet<T> {
-        GrowableBitSet { bit_set: BitSet::new_empty(0) }
+        GrowableBitSet { bit_set: DenseBitSet::new_empty(0) }
     }
 
     pub fn with_capacity(capacity: usize) -> GrowableBitSet<T> {
-        GrowableBitSet { bit_set: BitSet::new_empty(capacity) }
+        GrowableBitSet { bit_set: DenseBitSet::new_empty(capacity) }
     }
 
     /// Returns `true` if the set has changed.
@@ -1349,8 +1359,8 @@ impl<T: Idx> GrowableBitSet<T> {
     }
 }
 
-impl<T: Idx> From<BitSet<T>> for GrowableBitSet<T> {
-    fn from(bit_set: BitSet<T>) -> Self {
+impl<T: Idx> From<DenseBitSet<T>> for GrowableBitSet<T> {
+    fn from(bit_set: DenseBitSet<T>) -> Self {
         Self { bit_set }
     }
 }
@@ -1386,7 +1396,7 @@ impl<R: Idx, C: Idx> BitMatrix<R, C> {
     }
 
     /// Creates a new matrix, with `row` used as the value for every row.
-    pub fn from_row_n(row: &BitSet<C>, num_rows: usize) -> BitMatrix<R, C> {
+    pub fn from_row_n(row: &DenseBitSet<C>, num_rows: usize) -> BitMatrix<R, C> {
         let num_columns = row.domain_size();
         let words_per_row = num_words(num_columns);
         assert_eq!(words_per_row, row.words.len());
@@ -1484,7 +1494,7 @@ impl<R: Idx, C: Idx> BitMatrix<R, C> {
 
     /// Adds the bits from `with` to the bits from row `write`, and
     /// returns `true` if anything changed.
-    pub fn union_row_with(&mut self, with: &BitSet<C>, write: R) -> bool {
+    pub fn union_row_with(&mut self, with: &DenseBitSet<C>, write: R) -> bool {
         assert!(write.index() < self.num_rows);
         assert_eq!(with.domain_size(), self.num_columns);
         let (write_start, write_end) = self.range(write);
@@ -1541,8 +1551,8 @@ impl<R: Idx, C: Idx> fmt::Debug for BitMatrix<R, C> {
 /// A fixed-column-size, variable-row-size 2D bit matrix with a moderately
 /// sparse representation.
 ///
-/// Initially, every row has no explicit representation. If any bit within a
-/// row is set, the entire row is instantiated as `Some(<BitSet>)`.
+/// Initially, every row has no explicit representation. If any bit within a row
+/// is set, the entire row is instantiated as `Some(<DenseBitSet>)`.
 /// Furthermore, any previously uninstantiated rows prior to it will be
 /// instantiated as `None`. Those prior rows may themselves become fully
 /// instantiated later on if any of their bits are set.
@@ -1556,7 +1566,7 @@ where
     C: Idx,
 {
     num_columns: usize,
-    rows: IndexVec<R, Option<BitSet<C>>>,
+    rows: IndexVec<R, Option<DenseBitSet<C>>>,
 }
 
 impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
@@ -1565,10 +1575,10 @@ impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
         Self { num_columns, rows: IndexVec::new() }
     }
 
-    fn ensure_row(&mut self, row: R) -> &mut BitSet<C> {
-        // Instantiate any missing rows up to and including row `row` with an empty `BitSet`.
-        // Then replace row `row` with a full `BitSet` if necessary.
-        self.rows.get_or_insert_with(row, || BitSet::new_empty(self.num_columns))
+    fn ensure_row(&mut self, row: R) -> &mut DenseBitSet<C> {
+        // Instantiate any missing rows up to and including row `row` with an empty `DenseBitSet`.
+        // Then replace row `row` with a full `DenseBitSet` if necessary.
+        self.rows.get_or_insert_with(row, || DenseBitSet::new_empty(self.num_columns))
     }
 
     /// Sets the cell at `(row, column)` to true. Put another way, insert
@@ -1642,17 +1652,17 @@ impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
         self.row(row).into_iter().flat_map(|r| r.iter())
     }
 
-    pub fn row(&self, row: R) -> Option<&BitSet<C>> {
+    pub fn row(&self, row: R) -> Option<&DenseBitSet<C>> {
         self.rows.get(row)?.as_ref()
     }
 
-    /// Intersects `row` with `set`. `set` can be either `BitSet` or
+    /// Intersects `row` with `set`. `set` can be either `DenseBitSet` or
     /// `ChunkedBitSet`. Has no effect if `row` does not exist.
     ///
     /// Returns true if the row was changed.
     pub fn intersect_row<Set>(&mut self, row: R, set: &Set) -> bool
     where
-        BitSet<C>: BitRelations<Set>,
+        DenseBitSet<C>: BitRelations<Set>,
     {
         match self.rows.get_mut(row) {
             Some(Some(row)) => row.intersect(set),
@@ -1660,13 +1670,13 @@ impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
         }
     }
 
-    /// Subtracts `set` from `row`. `set` can be either `BitSet` or
+    /// Subtracts `set` from `row`. `set` can be either `DenseBitSet` or
     /// `ChunkedBitSet`. Has no effect if `row` does not exist.
     ///
     /// Returns true if the row was changed.
     pub fn subtract_row<Set>(&mut self, row: R, set: &Set) -> bool
     where
-        BitSet<C>: BitRelations<Set>,
+        DenseBitSet<C>: BitRelations<Set>,
     {
         match self.rows.get_mut(row) {
             Some(Some(row)) => row.subtract(set),
@@ -1674,13 +1684,13 @@ impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
         }
     }
 
-    /// Unions `row` with `set`. `set` can be either `BitSet` or
+    /// Unions `row` with `set`. `set` can be either `DenseBitSet` or
     /// `ChunkedBitSet`.
     ///
     /// Returns true if the row was changed.
     pub fn union_row<Set>(&mut self, row: R, set: &Set) -> bool
     where
-        BitSet<C>: BitRelations<Set>,
+        DenseBitSet<C>: BitRelations<Set>,
     {
         self.ensure_row(row).union(set)
     }
diff --git a/compiler/rustc_index/src/bit_set/tests.rs b/compiler/rustc_index/src/bit_set/tests.rs
index f6142323979..0350740aa81 100644
--- a/compiler/rustc_index/src/bit_set/tests.rs
+++ b/compiler/rustc_index/src/bit_set/tests.rs
@@ -8,7 +8,7 @@ use test::Bencher;
 #[test]
 fn test_new_filled() {
     for i in 0..128 {
-        let idx_buf = BitSet::new_filled(i);
+        let idx_buf = DenseBitSet::new_filled(i);
         let elems: Vec<usize> = idx_buf.iter().collect();
         let expected: Vec<usize> = (0..i).collect();
         assert_eq!(elems, expected);
@@ -17,7 +17,7 @@ fn test_new_filled() {
 
 #[test]
 fn bitset_iter_works() {
-    let mut bitset: BitSet<usize> = BitSet::new_empty(100);
+    let mut bitset: DenseBitSet<usize> = DenseBitSet::new_empty(100);
     bitset.insert(1);
     bitset.insert(10);
     bitset.insert(19);
@@ -32,7 +32,7 @@ fn bitset_iter_works() {
 
 #[test]
 fn bitset_iter_works_2() {
-    let mut bitset: BitSet<usize> = BitSet::new_empty(320);
+    let mut bitset: DenseBitSet<usize> = DenseBitSet::new_empty(320);
     bitset.insert(0);
     bitset.insert(127);
     bitset.insert(191);
@@ -43,25 +43,25 @@ fn bitset_iter_works_2() {
 
 #[test]
 fn bitset_clone_from() {
-    let mut a: BitSet<usize> = BitSet::new_empty(10);
+    let mut a: DenseBitSet<usize> = DenseBitSet::new_empty(10);
     a.insert(4);
     a.insert(7);
     a.insert(9);
 
-    let mut b = BitSet::new_empty(2);
+    let mut b = DenseBitSet::new_empty(2);
     b.clone_from(&a);
     assert_eq!(b.domain_size(), 10);
     assert_eq!(b.iter().collect::<Vec<_>>(), [4, 7, 9]);
 
-    b.clone_from(&BitSet::new_empty(40));
+    b.clone_from(&DenseBitSet::new_empty(40));
     assert_eq!(b.domain_size(), 40);
     assert_eq!(b.iter().collect::<Vec<_>>(), []);
 }
 
 #[test]
 fn union_two_sets() {
-    let mut set1: BitSet<usize> = BitSet::new_empty(65);
-    let mut set2: BitSet<usize> = BitSet::new_empty(65);
+    let mut set1: DenseBitSet<usize> = DenseBitSet::new_empty(65);
+    let mut set2: DenseBitSet<usize> = DenseBitSet::new_empty(65);
     assert!(set1.insert(3));
     assert!(!set1.insert(3));
     assert!(set2.insert(5));
@@ -268,8 +268,8 @@ fn with_elements_chunked(elements: &[usize], domain_size: usize) -> ChunkedBitSe
     s
 }
 
-fn with_elements_standard(elements: &[usize], domain_size: usize) -> BitSet<usize> {
-    let mut s = BitSet::new_empty(domain_size);
+fn with_elements_standard(elements: &[usize], domain_size: usize) -> DenseBitSet<usize> {
+    let mut s = DenseBitSet::new_empty(domain_size);
     for &e in elements {
         assert!(s.insert(e));
     }
@@ -503,15 +503,15 @@ fn sparse_matrix_operations() {
     matrix.insert(2, 99);
     matrix.insert(4, 0);
 
-    let mut disjoint: BitSet<usize> = BitSet::new_empty(100);
+    let mut disjoint: DenseBitSet<usize> = DenseBitSet::new_empty(100);
     disjoint.insert(33);
 
-    let mut superset = BitSet::new_empty(100);
+    let mut superset = DenseBitSet::new_empty(100);
     superset.insert(22);
     superset.insert(75);
     superset.insert(33);
 
-    let mut subset = BitSet::new_empty(100);
+    let mut subset = DenseBitSet::new_empty(100);
     subset.insert(22);
 
     // SparseBitMatrix::remove
@@ -568,7 +568,7 @@ fn dense_insert_range() {
     where
         R: RangeBounds<usize> + Clone + IntoIterator<Item = usize> + std::fmt::Debug,
     {
-        let mut set = BitSet::new_empty(domain);
+        let mut set = DenseBitSet::new_empty(domain);
         set.insert_range(range.clone());
         for i in set.iter() {
             assert!(range.contains(&i));
@@ -609,7 +609,7 @@ fn dense_insert_range() {
 
 #[test]
 fn dense_last_set_before() {
-    fn easy(set: &BitSet<usize>, needle: impl RangeBounds<usize>) -> Option<usize> {
+    fn easy(set: &DenseBitSet<usize>, needle: impl RangeBounds<usize>) -> Option<usize> {
         let mut last_leq = None;
         for e in set.iter() {
             if needle.contains(&e) {
@@ -620,7 +620,7 @@ fn dense_last_set_before() {
     }
 
     #[track_caller]
-    fn cmp(set: &BitSet<usize>, needle: impl RangeBounds<usize> + Clone + std::fmt::Debug) {
+    fn cmp(set: &DenseBitSet<usize>, needle: impl RangeBounds<usize> + Clone + std::fmt::Debug) {
         assert_eq!(
             set.last_set_in(needle.clone()),
             easy(set, needle.clone()),
@@ -629,7 +629,7 @@ fn dense_last_set_before() {
             set
         );
     }
-    let mut set = BitSet::new_empty(300);
+    let mut set = DenseBitSet::new_empty(300);
     cmp(&set, 50..=50);
     set.insert(WORD_BITS);
     cmp(&set, WORD_BITS..=WORD_BITS);
@@ -645,7 +645,7 @@ fn dense_last_set_before() {
     for i in 0..=WORD_BITS * 2 {
         for j in i..=WORD_BITS * 2 {
             for k in 0..WORD_BITS * 2 {
-                let mut set = BitSet::new_empty(300);
+                let mut set = DenseBitSet::new_empty(300);
                 cmp(&set, i..j);
                 cmp(&set, i..=j);
                 set.insert(k);
@@ -658,7 +658,7 @@ fn dense_last_set_before() {
 
 #[bench]
 fn bench_insert(b: &mut Bencher) {
-    let mut bs = BitSet::new_filled(99999usize);
+    let mut bs = DenseBitSet::new_filled(99999usize);
     b.iter(|| {
         black_box(bs.insert(black_box(100u32)));
     });
@@ -666,7 +666,7 @@ fn bench_insert(b: &mut Bencher) {
 
 #[bench]
 fn bench_remove(b: &mut Bencher) {
-    let mut bs = BitSet::new_filled(99999usize);
+    let mut bs = DenseBitSet::new_filled(99999usize);
     b.iter(|| {
         black_box(bs.remove(black_box(100u32)));
     });
@@ -674,7 +674,7 @@ fn bench_remove(b: &mut Bencher) {
 
 #[bench]
 fn bench_iter(b: &mut Bencher) {
-    let bs = BitSet::new_filled(99999usize);
+    let bs = DenseBitSet::new_filled(99999usize);
     b.iter(|| {
         bs.iter().map(|b: usize| black_box(b)).for_each(drop);
     });
@@ -682,8 +682,8 @@ fn bench_iter(b: &mut Bencher) {
 
 #[bench]
 fn bench_intersect(b: &mut Bencher) {
-    let mut ba: BitSet<u32> = BitSet::new_filled(99999usize);
-    let bb = BitSet::new_filled(99999usize);
+    let mut ba: DenseBitSet<u32> = DenseBitSet::new_filled(99999usize);
+    let bb = DenseBitSet::new_filled(99999usize);
     b.iter(|| {
         ba.intersect(black_box(&bb));
     });
diff --git a/compiler/rustc_metadata/src/rmeta/mod.rs b/compiler/rustc_metadata/src/rmeta/mod.rs
index 4fe8f73efd6..4f9cdc9a474 100644
--- a/compiler/rustc_metadata/src/rmeta/mod.rs
+++ b/compiler/rustc_metadata/src/rmeta/mod.rs
@@ -15,7 +15,7 @@ use rustc_hir::def_id::{CrateNum, DefId, DefIdMap, DefIndex, DefPathHash, Stable
 use rustc_hir::definitions::DefKey;
 use rustc_hir::lang_items::LangItem;
 use rustc_index::IndexVec;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_macros::{
     Decodable, Encodable, MetadataDecodable, MetadataEncodable, TyDecodable, TyEncodable,
 };
@@ -450,7 +450,7 @@ define_tables! {
     trait_item_def_id: Table<DefIndex, RawDefId>,
     expn_that_defined: Table<DefIndex, LazyValue<ExpnId>>,
     default_fields: Table<DefIndex, LazyValue<DefId>>,
-    params_in_repr: Table<DefIndex, LazyValue<BitSet<u32>>>,
+    params_in_repr: Table<DefIndex, LazyValue<DenseBitSet<u32>>>,
     repr_options: Table<DefIndex, LazyValue<ReprOptions>>,
     // `def_keys` and `def_path_hashes` represent a lazy version of a
     // `DefPathTable`. This allows us to avoid deserializing an entire
diff --git a/compiler/rustc_middle/src/mir/coverage.rs b/compiler/rustc_middle/src/mir/coverage.rs
index 29f26180c97..cd6b2d65bf1 100644
--- a/compiler/rustc_middle/src/mir/coverage.rs
+++ b/compiler/rustc_middle/src/mir/coverage.rs
@@ -3,7 +3,7 @@
 use std::fmt::{self, Debug, Formatter};
 
 use rustc_index::IndexVec;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeFoldable, TypeVisitable};
 use rustc_span::Span;
 
@@ -303,8 +303,8 @@ pub struct MCDCDecisionSpan {
 /// Used by the `coverage_ids_info` query.
 #[derive(Clone, TyEncodable, TyDecodable, Debug, HashStable)]
 pub struct CoverageIdsInfo {
-    pub counters_seen: BitSet<CounterId>,
-    pub zero_expressions: BitSet<ExpressionId>,
+    pub counters_seen: DenseBitSet<CounterId>,
+    pub zero_expressions: DenseBitSet<ExpressionId>,
 }
 
 impl CoverageIdsInfo {
diff --git a/compiler/rustc_middle/src/mir/mod.rs b/compiler/rustc_middle/src/mir/mod.rs
index 98ef7d58a50..bbb8bdce4a0 100644
--- a/compiler/rustc_middle/src/mir/mod.rs
+++ b/compiler/rustc_middle/src/mir/mod.rs
@@ -21,7 +21,7 @@ use rustc_hir::def_id::{CRATE_DEF_ID, DefId};
 use rustc_hir::{
     self as hir, BindingMode, ByRef, CoroutineDesugaring, CoroutineKind, HirId, ImplicitSelfKind,
 };
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_index::{Idx, IndexSlice, IndexVec};
 use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeFoldable, TypeVisitable};
 use rustc_serialize::{Decodable, Encodable};
diff --git a/compiler/rustc_middle/src/mir/traversal.rs b/compiler/rustc_middle/src/mir/traversal.rs
index b8b74da401c..0e7dcc24daf 100644
--- a/compiler/rustc_middle/src/mir/traversal.rs
+++ b/compiler/rustc_middle/src/mir/traversal.rs
@@ -21,7 +21,7 @@ use super::*;
 #[derive(Clone)]
 pub struct Preorder<'a, 'tcx> {
     body: &'a Body<'tcx>,
-    visited: BitSet<BasicBlock>,
+    visited: DenseBitSet<BasicBlock>,
     worklist: Vec<BasicBlock>,
     root_is_start_block: bool,
 }
@@ -32,7 +32,7 @@ impl<'a, 'tcx> Preorder<'a, 'tcx> {
 
         Preorder {
             body,
-            visited: BitSet::new_empty(body.basic_blocks.len()),
+            visited: DenseBitSet::new_empty(body.basic_blocks.len()),
             worklist,
             root_is_start_block: root == START_BLOCK,
         }
@@ -106,7 +106,7 @@ impl<'a, 'tcx> Iterator for Preorder<'a, 'tcx> {
 /// A Postorder traversal of this graph is `D B C A` or `D C B A`
 pub struct Postorder<'a, 'tcx, C> {
     basic_blocks: &'a IndexSlice<BasicBlock, BasicBlockData<'tcx>>,
-    visited: BitSet<BasicBlock>,
+    visited: DenseBitSet<BasicBlock>,
     visit_stack: Vec<(BasicBlock, Successors<'a>)>,
     root_is_start_block: bool,
     extra: C,
@@ -123,7 +123,7 @@ where
     ) -> Postorder<'a, 'tcx, C> {
         let mut po = Postorder {
             basic_blocks,
-            visited: BitSet::new_empty(basic_blocks.len()),
+            visited: DenseBitSet::new_empty(basic_blocks.len()),
             visit_stack: Vec::new(),
             root_is_start_block: root == START_BLOCK,
             extra,
@@ -285,8 +285,8 @@ pub fn reachable<'a, 'tcx>(
     preorder(body)
 }
 
-/// Returns a `BitSet` containing all basic blocks reachable from the `START_BLOCK`.
-pub fn reachable_as_bitset(body: &Body<'_>) -> BitSet<BasicBlock> {
+/// Returns a `DenseBitSet` containing all basic blocks reachable from the `START_BLOCK`.
+pub fn reachable_as_bitset(body: &Body<'_>) -> DenseBitSet<BasicBlock> {
     let mut iter = preorder(body);
     while let Some(_) = iter.next() {}
     iter.visited
@@ -340,13 +340,13 @@ pub fn mono_reachable<'a, 'tcx>(
     MonoReachable::new(body, tcx, instance)
 }
 
-/// [`MonoReachable`] internally accumulates a [`BitSet`] of visited blocks. This is just a
+/// [`MonoReachable`] internally accumulates a [`DenseBitSet`] of visited blocks. This is just a
 /// convenience function to run that traversal then extract its set of reached blocks.
 pub fn mono_reachable_as_bitset<'a, 'tcx>(
     body: &'a Body<'tcx>,
     tcx: TyCtxt<'tcx>,
     instance: Instance<'tcx>,
-) -> BitSet<BasicBlock> {
+) -> DenseBitSet<BasicBlock> {
     let mut iter = mono_reachable(body, tcx, instance);
     while let Some(_) = iter.next() {}
     iter.visited
@@ -356,11 +356,11 @@ pub struct MonoReachable<'a, 'tcx> {
     body: &'a Body<'tcx>,
     tcx: TyCtxt<'tcx>,
     instance: Instance<'tcx>,
-    visited: BitSet<BasicBlock>,
+    visited: DenseBitSet<BasicBlock>,
     // Other traversers track their worklist in a Vec. But we don't care about order, so we can
-    // store ours in a BitSet and thus save allocations because BitSet has a small size
+    // store ours in a DenseBitSet and thus save allocations because DenseBitSet has a small size
     // optimization.
-    worklist: BitSet<BasicBlock>,
+    worklist: DenseBitSet<BasicBlock>,
 }
 
 impl<'a, 'tcx> MonoReachable<'a, 'tcx> {
@@ -369,13 +369,13 @@ impl<'a, 'tcx> MonoReachable<'a, 'tcx> {
         tcx: TyCtxt<'tcx>,
         instance: Instance<'tcx>,
     ) -> MonoReachable<'a, 'tcx> {
-        let mut worklist = BitSet::new_empty(body.basic_blocks.len());
+        let mut worklist = DenseBitSet::new_empty(body.basic_blocks.len());
         worklist.insert(START_BLOCK);
         MonoReachable {
             body,
             tcx,
             instance,
-            visited: BitSet::new_empty(body.basic_blocks.len()),
+            visited: DenseBitSet::new_empty(body.basic_blocks.len()),
             worklist,
         }
     }
diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs
index 283675573d4..7d334847d44 100644
--- a/compiler/rustc_middle/src/query/mod.rs
+++ b/compiler/rustc_middle/src/query/mod.rs
@@ -297,7 +297,7 @@ rustc_queries! {
         separate_provide_extern
     }
 
-    query unsizing_params_for_adt(key: DefId) -> &'tcx rustc_index::bit_set::BitSet<u32>
+    query unsizing_params_for_adt(key: DefId) -> &'tcx rustc_index::bit_set::DenseBitSet<u32>
     {
         arena_cache
         desc { |tcx|
@@ -494,7 +494,7 @@ rustc_queries! {
     }
 
     /// Set of param indexes for type params that are in the type's representation
-    query params_in_repr(key: DefId) -> &'tcx rustc_index::bit_set::BitSet<u32> {
+    query params_in_repr(key: DefId) -> &'tcx rustc_index::bit_set::DenseBitSet<u32> {
         desc { "finding type parameters in the representation" }
         arena_cache
         no_hash
diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index d26c007d227..24f10b4fbe7 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -613,7 +613,7 @@ impl<'tcx> Interner for TyCtxt<'tcx> {
         self.coroutine_is_async_gen(coroutine_def_id)
     }
 
-    type UnsizingParams = &'tcx rustc_index::bit_set::BitSet<u32>;
+    type UnsizingParams = &'tcx rustc_index::bit_set::DenseBitSet<u32>;
     fn unsizing_params_for_adt(self, adt_def_id: DefId) -> Self::UnsizingParams {
         self.unsizing_params_for_adt(adt_def_id)
     }
diff --git a/compiler/rustc_middle/src/ty/parameterized.rs b/compiler/rustc_middle/src/ty/parameterized.rs
index 86a95827e84..6b6c6f3c72f 100644
--- a/compiler/rustc_middle/src/ty/parameterized.rs
+++ b/compiler/rustc_middle/src/ty/parameterized.rs
@@ -96,7 +96,7 @@ trivially_parameterized_over_tcx! {
     rustc_hir::def_id::DefIndex,
     rustc_hir::definitions::DefKey,
     rustc_hir::OpaqueTyOrigin<rustc_hir::def_id::DefId>,
-    rustc_index::bit_set::BitSet<u32>,
+    rustc_index::bit_set::DenseBitSet<u32>,
     rustc_index::bit_set::FiniteBitSet<u32>,
     rustc_session::cstore::ForeignModule,
     rustc_session::cstore::LinkagePreference,
diff --git a/compiler/rustc_mir_dataflow/src/debuginfo.rs b/compiler/rustc_mir_dataflow/src/debuginfo.rs
index fd5e8cf2955..0d25ce91c9a 100644
--- a/compiler/rustc_mir_dataflow/src/debuginfo.rs
+++ b/compiler/rustc_mir_dataflow/src/debuginfo.rs
@@ -1,17 +1,17 @@
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::visit::*;
 use rustc_middle::mir::*;
 
 /// Return the set of locals that appear in debuginfo.
-pub fn debuginfo_locals(body: &Body<'_>) -> BitSet<Local> {
-    let mut visitor = DebuginfoLocals(BitSet::new_empty(body.local_decls.len()));
+pub fn debuginfo_locals(body: &Body<'_>) -> DenseBitSet<Local> {
+    let mut visitor = DebuginfoLocals(DenseBitSet::new_empty(body.local_decls.len()));
     for debuginfo in body.var_debug_info.iter() {
         visitor.visit_var_debug_info(debuginfo);
     }
     visitor.0
 }
 
-struct DebuginfoLocals(BitSet<Local>);
+struct DebuginfoLocals(DenseBitSet<Local>);
 
 impl Visitor<'_> for DebuginfoLocals {
     fn visit_local(&mut self, local: Local, _: PlaceContext, _: Location) {
diff --git a/compiler/rustc_mir_dataflow/src/framework/cursor.rs b/compiler/rustc_mir_dataflow/src/framework/cursor.rs
index 89ff93d9943..c46ae9775cf 100644
--- a/compiler/rustc_mir_dataflow/src/framework/cursor.rs
+++ b/compiler/rustc_mir_dataflow/src/framework/cursor.rs
@@ -4,7 +4,7 @@ use std::cmp::Ordering;
 use std::ops::{Deref, DerefMut};
 
 #[cfg(debug_assertions)]
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::{self, BasicBlock, Location};
 
 use super::{Analysis, Direction, Effect, EffectIndex, Results};
@@ -71,7 +71,7 @@ where
     state_needs_reset: bool,
 
     #[cfg(debug_assertions)]
-    reachable_blocks: BitSet<BasicBlock>,
+    reachable_blocks: DenseBitSet<BasicBlock>,
 }
 
 impl<'mir, 'tcx, A> ResultsCursor<'mir, 'tcx, A>
diff --git a/compiler/rustc_mir_dataflow/src/framework/fmt.rs b/compiler/rustc_mir_dataflow/src/framework/fmt.rs
index faf2c411dde..38599cd0949 100644
--- a/compiler/rustc_mir_dataflow/src/framework/fmt.rs
+++ b/compiler/rustc_mir_dataflow/src/framework/fmt.rs
@@ -4,7 +4,7 @@
 use std::fmt;
 
 use rustc_index::Idx;
-use rustc_index::bit_set::{BitSet, ChunkedBitSet, MixedBitSet};
+use rustc_index::bit_set::{ChunkedBitSet, DenseBitSet, MixedBitSet};
 
 use super::lattice::MaybeReachable;
 
@@ -73,7 +73,7 @@ where
 
 // Impls
 
-impl<T, C> DebugWithContext<C> for BitSet<T>
+impl<T, C> DebugWithContext<C> for DenseBitSet<T>
 where
     T: Idx + DebugWithContext<C>,
 {
diff --git a/compiler/rustc_mir_dataflow/src/framework/graphviz.rs b/compiler/rustc_mir_dataflow/src/framework/graphviz.rs
index 60c97710c7f..e457b514936 100644
--- a/compiler/rustc_mir_dataflow/src/framework/graphviz.rs
+++ b/compiler/rustc_mir_dataflow/src/framework/graphviz.rs
@@ -9,7 +9,7 @@ use std::{io, ops, str};
 
 use regex::Regex;
 use rustc_hir::def_id::DefId;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::{
     self, BasicBlock, Body, Location, create_dump_file, dump_enabled, graphviz_safe_def_name,
     traversal,
@@ -205,7 +205,7 @@ where
     // the operations that involve the mutation, i.e. within the `borrow_mut`.
     cursor: RefCell<ResultsCursor<'mir, 'tcx, A>>,
     style: OutputStyle,
-    reachable: BitSet<BasicBlock>,
+    reachable: DenseBitSet<BasicBlock>,
 }
 
 impl<'mir, 'tcx, A> Formatter<'mir, 'tcx, A>
diff --git a/compiler/rustc_mir_dataflow/src/framework/lattice.rs b/compiler/rustc_mir_dataflow/src/framework/lattice.rs
index cb8159ce37b..919e346bda7 100644
--- a/compiler/rustc_mir_dataflow/src/framework/lattice.rs
+++ b/compiler/rustc_mir_dataflow/src/framework/lattice.rs
@@ -39,7 +39,7 @@
 //! [poset]: https://en.wikipedia.org/wiki/Partially_ordered_set
 
 use rustc_index::Idx;
-use rustc_index::bit_set::{BitSet, MixedBitSet};
+use rustc_index::bit_set::{DenseBitSet, MixedBitSet};
 
 use crate::framework::BitSetExt;
 
@@ -68,10 +68,10 @@ pub trait HasTop {
     const TOP: Self;
 }
 
-/// A `BitSet` represents the lattice formed by the powerset of all possible values of
-/// the index type `T` ordered by inclusion. Equivalently, it is a tuple of "two-point" lattices,
-/// one for each possible value of `T`.
-impl<T: Idx> JoinSemiLattice for BitSet<T> {
+/// A `DenseBitSet` represents the lattice formed by the powerset of all possible values of the
+/// index type `T` ordered by inclusion. Equivalently, it is a tuple of "two-point" lattices, one
+/// for each possible value of `T`.
+impl<T: Idx> JoinSemiLattice for DenseBitSet<T> {
     fn join(&mut self, other: &Self) -> bool {
         self.union(other)
     }
diff --git a/compiler/rustc_mir_dataflow/src/framework/mod.rs b/compiler/rustc_mir_dataflow/src/framework/mod.rs
index 3de2c6e3f47..60c5cb0cae8 100644
--- a/compiler/rustc_mir_dataflow/src/framework/mod.rs
+++ b/compiler/rustc_mir_dataflow/src/framework/mod.rs
@@ -35,7 +35,7 @@
 use std::cmp::Ordering;
 
 use rustc_data_structures::work_queue::WorkQueue;
-use rustc_index::bit_set::{BitSet, MixedBitSet};
+use rustc_index::bit_set::{DenseBitSet, MixedBitSet};
 use rustc_index::{Idx, IndexVec};
 use rustc_middle::bug;
 use rustc_middle::mir::{self, BasicBlock, CallReturnPlaces, Location, TerminatorEdges, traversal};
@@ -65,7 +65,7 @@ pub trait BitSetExt<T> {
     fn contains(&self, elem: T) -> bool;
 }
 
-impl<T: Idx> BitSetExt<T> for BitSet<T> {
+impl<T: Idx> BitSetExt<T> for DenseBitSet<T> {
     fn contains(&self, elem: T) -> bool {
         self.contains(elem)
     }
@@ -334,7 +334,7 @@ pub trait GenKill<T> {
     }
 }
 
-impl<T: Idx> GenKill<T> for BitSet<T> {
+impl<T: Idx> GenKill<T> for DenseBitSet<T> {
     fn gen_(&mut self, elem: T) {
         self.insert(elem);
     }
diff --git a/compiler/rustc_mir_dataflow/src/framework/tests.rs b/compiler/rustc_mir_dataflow/src/framework/tests.rs
index 8e7d4ab0fa3..5b3a9ccba69 100644
--- a/compiler/rustc_mir_dataflow/src/framework/tests.rs
+++ b/compiler/rustc_mir_dataflow/src/framework/tests.rs
@@ -84,13 +84,13 @@ impl<D: Direction> MockAnalysis<'_, D> {
 
     /// The entry set for each `BasicBlock` is the ID of that block offset by a fixed amount to
     /// avoid colliding with the statement/terminator effects.
-    fn mock_entry_set(&self, bb: BasicBlock) -> BitSet<usize> {
+    fn mock_entry_set(&self, bb: BasicBlock) -> DenseBitSet<usize> {
         let mut ret = self.bottom_value(self.body);
         ret.insert(Self::BASIC_BLOCK_OFFSET + bb.index());
         ret
     }
 
-    fn mock_entry_states(&self) -> IndexVec<BasicBlock, BitSet<usize>> {
+    fn mock_entry_states(&self) -> IndexVec<BasicBlock, DenseBitSet<usize>> {
         let empty = self.bottom_value(self.body);
         let mut ret = IndexVec::from_elem(empty, &self.body.basic_blocks);
 
@@ -121,7 +121,7 @@ impl<D: Direction> MockAnalysis<'_, D> {
     /// For example, the expected state when calling
     /// `seek_before_primary_effect(Location { block: 2, statement_index: 2 })`
     /// would be `[102, 0, 1, 2, 3, 4]`.
-    fn expected_state_at_target(&self, target: SeekTarget) -> BitSet<usize> {
+    fn expected_state_at_target(&self, target: SeekTarget) -> DenseBitSet<usize> {
         let block = target.block();
         let mut ret = self.bottom_value(self.body);
         ret.insert(Self::BASIC_BLOCK_OFFSET + block.index());
@@ -155,13 +155,13 @@ impl<D: Direction> MockAnalysis<'_, D> {
 }
 
 impl<'tcx, D: Direction> Analysis<'tcx> for MockAnalysis<'tcx, D> {
-    type Domain = BitSet<usize>;
+    type Domain = DenseBitSet<usize>;
     type Direction = D;
 
     const NAME: &'static str = "mock";
 
     fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
-        BitSet::new_empty(Self::BASIC_BLOCK_OFFSET + body.basic_blocks.len())
+        DenseBitSet::new_empty(Self::BASIC_BLOCK_OFFSET + body.basic_blocks.len())
     }
 
     fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
diff --git a/compiler/rustc_mir_dataflow/src/impls/borrowed_locals.rs b/compiler/rustc_mir_dataflow/src/impls/borrowed_locals.rs
index 217594b3238..f2ef5018c49 100644
--- a/compiler/rustc_mir_dataflow/src/impls/borrowed_locals.rs
+++ b/compiler/rustc_mir_dataflow/src/impls/borrowed_locals.rs
@@ -1,4 +1,4 @@
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::visit::Visitor;
 use rustc_middle::mir::*;
 
@@ -21,12 +21,12 @@ impl MaybeBorrowedLocals {
 }
 
 impl<'tcx> Analysis<'tcx> for MaybeBorrowedLocals {
-    type Domain = BitSet<Local>;
+    type Domain = DenseBitSet<Local>;
     const NAME: &'static str = "maybe_borrowed_locals";
 
     fn bottom_value(&self, body: &Body<'tcx>) -> Self::Domain {
         // bottom = unborrowed
-        BitSet::new_empty(body.local_decls().len())
+        DenseBitSet::new_empty(body.local_decls().len())
     }
 
     fn initialize_start_block(&self, _: &Body<'tcx>, _: &mut Self::Domain) {
@@ -137,8 +137,8 @@ where
 }
 
 /// The set of locals that are borrowed at some point in the MIR body.
-pub fn borrowed_locals(body: &Body<'_>) -> BitSet<Local> {
-    struct Borrowed(BitSet<Local>);
+pub fn borrowed_locals(body: &Body<'_>) -> DenseBitSet<Local> {
+    struct Borrowed(DenseBitSet<Local>);
 
     impl GenKill<Local> for Borrowed {
         #[inline]
@@ -151,7 +151,7 @@ pub fn borrowed_locals(body: &Body<'_>) -> BitSet<Local> {
         }
     }
 
-    let mut borrowed = Borrowed(BitSet::new_empty(body.local_decls.len()));
+    let mut borrowed = Borrowed(DenseBitSet::new_empty(body.local_decls.len()));
     TransferFunction { trans: &mut borrowed }.visit_body(body);
     borrowed.0
 }
diff --git a/compiler/rustc_mir_dataflow/src/impls/initialized.rs b/compiler/rustc_mir_dataflow/src/impls/initialized.rs
index 769f9c7cfc3..760f94af52d 100644
--- a/compiler/rustc_mir_dataflow/src/impls/initialized.rs
+++ b/compiler/rustc_mir_dataflow/src/impls/initialized.rs
@@ -2,7 +2,7 @@ use std::assert_matches::assert_matches;
 
 use rustc_abi::VariantIdx;
 use rustc_index::Idx;
-use rustc_index::bit_set::{BitSet, MixedBitSet};
+use rustc_index::bit_set::{DenseBitSet, MixedBitSet};
 use rustc_middle::bug;
 use rustc_middle::mir::{self, Body, CallReturnPlaces, Location, TerminatorEdges};
 use rustc_middle::ty::util::Discr;
@@ -207,7 +207,7 @@ pub struct MaybeUninitializedPlaces<'a, 'tcx> {
     move_data: &'a MoveData<'tcx>,
 
     mark_inactive_variants_as_uninit: bool,
-    skip_unreachable_unwind: BitSet<mir::BasicBlock>,
+    skip_unreachable_unwind: DenseBitSet<mir::BasicBlock>,
 }
 
 impl<'a, 'tcx> MaybeUninitializedPlaces<'a, 'tcx> {
@@ -217,7 +217,7 @@ impl<'a, 'tcx> MaybeUninitializedPlaces<'a, 'tcx> {
             body,
             move_data,
             mark_inactive_variants_as_uninit: false,
-            skip_unreachable_unwind: BitSet::new_empty(body.basic_blocks.len()),
+            skip_unreachable_unwind: DenseBitSet::new_empty(body.basic_blocks.len()),
         }
     }
 
@@ -233,7 +233,7 @@ impl<'a, 'tcx> MaybeUninitializedPlaces<'a, 'tcx> {
 
     pub fn skipping_unreachable_unwind(
         mut self,
-        unreachable_unwind: BitSet<mir::BasicBlock>,
+        unreachable_unwind: DenseBitSet<mir::BasicBlock>,
     ) -> Self {
         self.skip_unreachable_unwind = unreachable_unwind;
         self
diff --git a/compiler/rustc_mir_dataflow/src/impls/liveness.rs b/compiler/rustc_mir_dataflow/src/impls/liveness.rs
index b2050a6adf9..6ec1b03a34e 100644
--- a/compiler/rustc_mir_dataflow/src/impls/liveness.rs
+++ b/compiler/rustc_mir_dataflow/src/impls/liveness.rs
@@ -1,4 +1,4 @@
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor};
 use rustc_middle::mir::{
     self, CallReturnPlaces, Local, Location, Place, StatementKind, TerminatorEdges,
@@ -26,14 +26,14 @@ use crate::{Analysis, Backward, GenKill};
 pub struct MaybeLiveLocals;
 
 impl<'tcx> Analysis<'tcx> for MaybeLiveLocals {
-    type Domain = BitSet<Local>;
+    type Domain = DenseBitSet<Local>;
     type Direction = Backward;
 
     const NAME: &'static str = "liveness";
 
     fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
         // bottom = not live
-        BitSet::new_empty(body.local_decls.len())
+        DenseBitSet::new_empty(body.local_decls.len())
     }
 
     fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
@@ -81,7 +81,7 @@ impl<'tcx> Analysis<'tcx> for MaybeLiveLocals {
     }
 }
 
-pub struct TransferFunction<'a>(pub &'a mut BitSet<Local>);
+pub struct TransferFunction<'a>(pub &'a mut DenseBitSet<Local>);
 
 impl<'tcx> Visitor<'tcx> for TransferFunction<'_> {
     fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) {
@@ -117,7 +117,7 @@ impl<'tcx> Visitor<'tcx> for TransferFunction<'_> {
     }
 }
 
-struct YieldResumeEffect<'a>(&'a mut BitSet<Local>);
+struct YieldResumeEffect<'a>(&'a mut DenseBitSet<Local>);
 
 impl<'tcx> Visitor<'tcx> for YieldResumeEffect<'_> {
     fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) {
@@ -137,7 +137,7 @@ enum DefUse {
 }
 
 impl DefUse {
-    fn apply(state: &mut BitSet<Local>, place: Place<'_>, context: PlaceContext) {
+    fn apply(state: &mut DenseBitSet<Local>, place: Place<'_>, context: PlaceContext) {
         match DefUse::for_place(place, context) {
             Some(DefUse::Def) => state.kill(place.local),
             Some(DefUse::Use) => state.gen_(place.local),
@@ -204,7 +204,7 @@ impl DefUse {
 ///
 /// All of the caveats of `MaybeLiveLocals` apply.
 pub struct MaybeTransitiveLiveLocals<'a> {
-    always_live: &'a BitSet<Local>,
+    always_live: &'a DenseBitSet<Local>,
 }
 
 impl<'a> MaybeTransitiveLiveLocals<'a> {
@@ -212,20 +212,20 @@ impl<'a> MaybeTransitiveLiveLocals<'a> {
     /// considered live.
     ///
     /// This should include at least all locals that are ever borrowed.
-    pub fn new(always_live: &'a BitSet<Local>) -> Self {
+    pub fn new(always_live: &'a DenseBitSet<Local>) -> Self {
         MaybeTransitiveLiveLocals { always_live }
     }
 }
 
 impl<'a, 'tcx> Analysis<'tcx> for MaybeTransitiveLiveLocals<'a> {
-    type Domain = BitSet<Local>;
+    type Domain = DenseBitSet<Local>;
     type Direction = Backward;
 
     const NAME: &'static str = "transitive liveness";
 
     fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
         // bottom = not live
-        BitSet::new_empty(body.local_decls.len())
+        DenseBitSet::new_empty(body.local_decls.len())
     }
 
     fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
diff --git a/compiler/rustc_mir_dataflow/src/impls/storage_liveness.rs b/compiler/rustc_mir_dataflow/src/impls/storage_liveness.rs
index 65b480d3a5e..e3aa8f5a620 100644
--- a/compiler/rustc_mir_dataflow/src/impls/storage_liveness.rs
+++ b/compiler/rustc_mir_dataflow/src/impls/storage_liveness.rs
@@ -1,6 +1,6 @@
 use std::borrow::Cow;
 
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::visit::{NonMutatingUseContext, PlaceContext, Visitor};
 use rustc_middle::mir::*;
 
@@ -10,8 +10,8 @@ use crate::{Analysis, GenKill, ResultsCursor};
 /// The set of locals in a MIR body that do not have `StorageLive`/`StorageDead` annotations.
 ///
 /// These locals have fixed storage for the duration of the body.
-pub fn always_storage_live_locals(body: &Body<'_>) -> BitSet<Local> {
-    let mut always_live_locals = BitSet::new_filled(body.local_decls.len());
+pub fn always_storage_live_locals(body: &Body<'_>) -> DenseBitSet<Local> {
+    let mut always_live_locals = DenseBitSet::new_filled(body.local_decls.len());
 
     for block in &*body.basic_blocks {
         for statement in &block.statements {
@@ -25,23 +25,23 @@ pub fn always_storage_live_locals(body: &Body<'_>) -> BitSet<Local> {
 }
 
 pub struct MaybeStorageLive<'a> {
-    always_live_locals: Cow<'a, BitSet<Local>>,
+    always_live_locals: Cow<'a, DenseBitSet<Local>>,
 }
 
 impl<'a> MaybeStorageLive<'a> {
-    pub fn new(always_live_locals: Cow<'a, BitSet<Local>>) -> Self {
+    pub fn new(always_live_locals: Cow<'a, DenseBitSet<Local>>) -> Self {
         MaybeStorageLive { always_live_locals }
     }
 }
 
 impl<'a, 'tcx> Analysis<'tcx> for MaybeStorageLive<'a> {
-    type Domain = BitSet<Local>;
+    type Domain = DenseBitSet<Local>;
 
     const NAME: &'static str = "maybe_storage_live";
 
     fn bottom_value(&self, body: &Body<'tcx>) -> Self::Domain {
         // bottom = dead
-        BitSet::new_empty(body.local_decls.len())
+        DenseBitSet::new_empty(body.local_decls.len())
     }
 
     fn initialize_start_block(&self, body: &Body<'tcx>, state: &mut Self::Domain) {
@@ -67,23 +67,23 @@ impl<'a, 'tcx> Analysis<'tcx> for MaybeStorageLive<'a> {
 }
 
 pub struct MaybeStorageDead<'a> {
-    always_live_locals: Cow<'a, BitSet<Local>>,
+    always_live_locals: Cow<'a, DenseBitSet<Local>>,
 }
 
 impl<'a> MaybeStorageDead<'a> {
-    pub fn new(always_live_locals: Cow<'a, BitSet<Local>>) -> Self {
+    pub fn new(always_live_locals: Cow<'a, DenseBitSet<Local>>) -> Self {
         MaybeStorageDead { always_live_locals }
     }
 }
 
 impl<'a, 'tcx> Analysis<'tcx> for MaybeStorageDead<'a> {
-    type Domain = BitSet<Local>;
+    type Domain = DenseBitSet<Local>;
 
     const NAME: &'static str = "maybe_storage_dead";
 
     fn bottom_value(&self, body: &Body<'tcx>) -> Self::Domain {
         // bottom = live
-        BitSet::new_empty(body.local_decls.len())
+        DenseBitSet::new_empty(body.local_decls.len())
     }
 
     fn initialize_start_block(&self, body: &Body<'tcx>, state: &mut Self::Domain) {
@@ -125,13 +125,13 @@ impl<'mir, 'tcx> MaybeRequiresStorage<'mir, 'tcx> {
 }
 
 impl<'tcx> Analysis<'tcx> for MaybeRequiresStorage<'_, 'tcx> {
-    type Domain = BitSet<Local>;
+    type Domain = DenseBitSet<Local>;
 
     const NAME: &'static str = "requires_storage";
 
     fn bottom_value(&self, body: &Body<'tcx>) -> Self::Domain {
         // bottom = dead
-        BitSet::new_empty(body.local_decls.len())
+        DenseBitSet::new_empty(body.local_decls.len())
     }
 
     fn initialize_start_block(&self, body: &Body<'tcx>, state: &mut Self::Domain) {
@@ -304,7 +304,7 @@ impl<'tcx> MaybeRequiresStorage<'_, 'tcx> {
 
 struct MoveVisitor<'a, 'mir, 'tcx> {
     borrowed_locals: &'a mut BorrowedLocalsResults<'mir, 'tcx>,
-    state: &'a mut BitSet<Local>,
+    state: &'a mut DenseBitSet<Local>,
 }
 
 impl<'tcx> Visitor<'tcx> for MoveVisitor<'_, '_, 'tcx> {
diff --git a/compiler/rustc_mir_dataflow/src/points.rs b/compiler/rustc_mir_dataflow/src/points.rs
index 74209da876a..5d2a78acbf5 100644
--- a/compiler/rustc_mir_dataflow/src/points.rs
+++ b/compiler/rustc_mir_dataflow/src/points.rs
@@ -1,4 +1,4 @@
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_index::interval::SparseIntervalMatrix;
 use rustc_index::{Idx, IndexVec};
 use rustc_middle::mir::{self, BasicBlock, Body, Location};
@@ -102,7 +102,7 @@ pub fn save_as_intervals<'tcx, N, A>(
 ) -> SparseIntervalMatrix<N, PointIndex>
 where
     N: Idx,
-    A: Analysis<'tcx, Domain = BitSet<N>>,
+    A: Analysis<'tcx, Domain = DenseBitSet<N>>,
 {
     let values = SparseIntervalMatrix::new(elements.num_points());
     let mut visitor = Visitor { elements, values };
@@ -122,7 +122,7 @@ struct Visitor<'a, N: Idx> {
 
 impl<'mir, 'tcx, A, N> ResultsVisitor<'mir, 'tcx, A> for Visitor<'_, N>
 where
-    A: Analysis<'tcx, Domain = BitSet<N>>,
+    A: Analysis<'tcx, Domain = DenseBitSet<N>>,
     N: Idx,
 {
     fn visit_after_primary_statement_effect(
diff --git a/compiler/rustc_mir_dataflow/src/value_analysis.rs b/compiler/rustc_mir_dataflow/src/value_analysis.rs
index 9328870c7ae..a51af8c40fd 100644
--- a/compiler/rustc_mir_dataflow/src/value_analysis.rs
+++ b/compiler/rustc_mir_dataflow/src/value_analysis.rs
@@ -6,7 +6,7 @@ use rustc_data_structures::captures::Captures;
 use rustc_data_structures::fx::{FxHashMap, FxIndexSet, StdEntry};
 use rustc_data_structures::stack::ensure_sufficient_stack;
 use rustc_index::IndexVec;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::tcx::PlaceTy;
 use rustc_middle::mir::visit::{MutatingUseContext, PlaceContext, Visitor};
 use rustc_middle::mir::*;
@@ -399,7 +399,7 @@ impl<'tcx> Map<'tcx> {
         &mut self,
         tcx: TyCtxt<'tcx>,
         body: &Body<'tcx>,
-        exclude: BitSet<Local>,
+        exclude: DenseBitSet<Local>,
         value_limit: Option<usize>,
     ) {
         // Start by constructing the places for each bare local.
@@ -912,9 +912,9 @@ pub fn iter_fields<'tcx>(
 }
 
 /// Returns all locals with projections that have their reference or address taken.
-pub fn excluded_locals(body: &Body<'_>) -> BitSet<Local> {
+pub fn excluded_locals(body: &Body<'_>) -> DenseBitSet<Local> {
     struct Collector {
-        result: BitSet<Local>,
+        result: DenseBitSet<Local>,
     }
 
     impl<'tcx> Visitor<'tcx> for Collector {
@@ -932,7 +932,7 @@ pub fn excluded_locals(body: &Body<'_>) -> BitSet<Local> {
         }
     }
 
-    let mut collector = Collector { result: BitSet::new_empty(body.local_decls.len()) };
+    let mut collector = Collector { result: DenseBitSet::new_empty(body.local_decls.len()) };
     collector.visit_body(body);
     collector.result
 }
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`.
diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs
index 8fce4266345..4ce868f014f 100644
--- a/compiler/rustc_pattern_analysis/src/constructor.rs
+++ b/compiler/rustc_pattern_analysis/src/constructor.rs
@@ -182,7 +182,7 @@ use std::iter::once;
 
 use rustc_apfloat::ieee::{DoubleS, HalfS, IeeeFloat, QuadS, SingleS};
 use rustc_index::IndexVec;
-use rustc_index::bit_set::{BitSet, GrowableBitSet};
+use rustc_index::bit_set::{DenseBitSet, GrowableBitSet};
 use smallvec::SmallVec;
 
 use self::Constructor::*;
@@ -1072,7 +1072,7 @@ impl<Cx: PatCx> ConstructorSet<Cx> {
                 }
             }
             ConstructorSet::Variants { variants, non_exhaustive } => {
-                let mut seen_set = BitSet::new_empty(variants.len());
+                let mut seen_set = DenseBitSet::new_empty(variants.len());
                 for idx in seen.iter().filter_map(|c| c.as_variant()) {
                     seen_set.insert(idx);
                 }
diff --git a/compiler/rustc_pattern_analysis/src/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs
index 99261eaa95c..cc09cd491af 100644
--- a/compiler/rustc_pattern_analysis/src/usefulness.rs
+++ b/compiler/rustc_pattern_analysis/src/usefulness.rs
@@ -712,7 +712,7 @@ use std::fmt;
 #[cfg(feature = "rustc")]
 use rustc_data_structures::stack::ensure_sufficient_stack;
 use rustc_hash::{FxHashMap, FxHashSet};
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use smallvec::{SmallVec, smallvec};
 use tracing::{debug, instrument};
 
@@ -1129,7 +1129,7 @@ struct MatrixRow<'p, Cx: PatCx> {
     /// ```
     /// Here the `(true, true)` case is irrelevant. Since we skip it, we will not detect that row 0
     /// intersects rows 1 and 2.
-    intersects_at_least: BitSet<usize>,
+    intersects_at_least: DenseBitSet<usize>,
     /// Whether the head pattern is a branch (see definition of "branch pattern" at
     /// [`BranchPatUsefulness`])
     head_is_branch: bool,
@@ -1142,7 +1142,7 @@ impl<'p, Cx: PatCx> MatrixRow<'p, Cx> {
             parent_row: arm_id,
             is_under_guard: arm.has_guard,
             useful: false,
-            intersects_at_least: BitSet::new_empty(0), // Initialized in `Matrix::push`.
+            intersects_at_least: DenseBitSet::new_empty(0), // Initialized in `Matrix::push`.
             // This pattern is a branch because it comes from a match arm.
             head_is_branch: true,
         }
@@ -1171,7 +1171,7 @@ impl<'p, Cx: PatCx> MatrixRow<'p, Cx> {
             parent_row,
             is_under_guard: self.is_under_guard,
             useful: false,
-            intersects_at_least: BitSet::new_empty(0), // Initialized in `Matrix::push`.
+            intersects_at_least: DenseBitSet::new_empty(0), // Initialized in `Matrix::push`.
             head_is_branch: is_or_pat,
         })
     }
@@ -1191,7 +1191,7 @@ impl<'p, Cx: PatCx> MatrixRow<'p, Cx> {
             parent_row,
             is_under_guard: self.is_under_guard,
             useful: false,
-            intersects_at_least: BitSet::new_empty(0), // Initialized in `Matrix::push`.
+            intersects_at_least: DenseBitSet::new_empty(0), // Initialized in `Matrix::push`.
             head_is_branch: false,
         })
     }
@@ -1230,7 +1230,7 @@ struct Matrix<'p, Cx: PatCx> {
 impl<'p, Cx: PatCx> Matrix<'p, Cx> {
     /// Pushes a new row to the matrix. Internal method, prefer [`Matrix::new`].
     fn push(&mut self, mut row: MatrixRow<'p, Cx>) {
-        row.intersects_at_least = BitSet::new_empty(self.rows.len());
+        row.intersects_at_least = DenseBitSet::new_empty(self.rows.len());
         self.rows.push(row);
     }
 
@@ -1824,7 +1824,7 @@ pub struct UsefulnessReport<'p, Cx: PatCx> {
     pub non_exhaustiveness_witnesses: Vec<WitnessPat<Cx>>,
     /// For each arm, a set of indices of arms above it that have non-empty intersection, i.e. there
     /// is a value matched by both arms. This may miss real intersections.
-    pub arm_intersections: Vec<BitSet<usize>>,
+    pub arm_intersections: Vec<DenseBitSet<usize>>,
 }
 
 /// Computes whether a match is exhaustive and which of its arms are useful.
diff --git a/compiler/rustc_ty_utils/src/layout.rs b/compiler/rustc_ty_utils/src/layout.rs
index fae787f9a40..ab606478c51 100644
--- a/compiler/rustc_ty_utils/src/layout.rs
+++ b/compiler/rustc_ty_utils/src/layout.rs
@@ -9,7 +9,7 @@ use rustc_abi::{
     HasDataLayout, Layout, LayoutCalculatorError, LayoutData, Niche, ReprOptions, Scalar, Size,
     StructKind, TagEncoding, VariantIdx, Variants, WrappingRange,
 };
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_index::{IndexSlice, IndexVec};
 use rustc_middle::bug;
 use rustc_middle::mir::{CoroutineLayout, CoroutineSavedLocal};
@@ -724,7 +724,7 @@ enum SavedLocalEligibility {
 /// Compute the eligibility and assignment of each local.
 fn coroutine_saved_local_eligibility(
     info: &CoroutineLayout<'_>,
-) -> (BitSet<CoroutineSavedLocal>, IndexVec<CoroutineSavedLocal, SavedLocalEligibility>) {
+) -> (DenseBitSet<CoroutineSavedLocal>, IndexVec<CoroutineSavedLocal, SavedLocalEligibility>) {
     use SavedLocalEligibility::*;
 
     let mut assignments: IndexVec<CoroutineSavedLocal, SavedLocalEligibility> =
@@ -732,7 +732,7 @@ fn coroutine_saved_local_eligibility(
 
     // The saved locals not eligible for overlap. These will get
     // "promoted" to the prefix of our coroutine.
-    let mut ineligible_locals = BitSet::new_empty(info.field_tys.len());
+    let mut ineligible_locals = DenseBitSet::new_empty(info.field_tys.len());
 
     // Figure out which of our saved locals are fields in only
     // one variant. The rest are deemed ineligible for overlap.
@@ -792,7 +792,7 @@ fn coroutine_saved_local_eligibility(
     // lay them out with the other locals in the prefix and eliminate
     // unnecessary padding bytes.
     {
-        let mut used_variants = BitSet::new_empty(info.variant_fields.len());
+        let mut used_variants = DenseBitSet::new_empty(info.variant_fields.len());
         for assignment in &assignments {
             if let Assigned(idx) = assignment {
                 used_variants.insert(*idx);
diff --git a/compiler/rustc_ty_utils/src/representability.rs b/compiler/rustc_ty_utils/src/representability.rs
index 0ffb7f62496..98b1550e1a3 100644
--- a/compiler/rustc_ty_utils/src/representability.rs
+++ b/compiler/rustc_ty_utils/src/representability.rs
@@ -1,5 +1,5 @@
 use rustc_hir::def::DefKind;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::bug;
 use rustc_middle::query::Providers;
 use rustc_middle::ty::{self, Representability, Ty, TyCtxt};
@@ -83,10 +83,10 @@ fn representability_adt_ty<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Representab
     Representability::Representable
 }
 
-fn params_in_repr(tcx: TyCtxt<'_>, def_id: LocalDefId) -> BitSet<u32> {
+fn params_in_repr(tcx: TyCtxt<'_>, def_id: LocalDefId) -> DenseBitSet<u32> {
     let adt_def = tcx.adt_def(def_id);
     let generics = tcx.generics_of(def_id);
-    let mut params_in_repr = BitSet::new_empty(generics.own_params.len());
+    let mut params_in_repr = DenseBitSet::new_empty(generics.own_params.len());
     for variant in adt_def.variants() {
         for field in variant.fields.iter() {
             params_in_repr_ty(
@@ -99,7 +99,7 @@ fn params_in_repr(tcx: TyCtxt<'_>, def_id: LocalDefId) -> BitSet<u32> {
     params_in_repr
 }
 
-fn params_in_repr_ty<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>, params_in_repr: &mut BitSet<u32>) {
+fn params_in_repr_ty<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>, params_in_repr: &mut DenseBitSet<u32>) {
     match *ty.kind() {
         ty::Adt(adt, args) => {
             let inner_params_in_repr = tcx.params_in_repr(adt.did());
diff --git a/compiler/rustc_ty_utils/src/ty.rs b/compiler/rustc_ty_utils/src/ty.rs
index 7eed32e3a33..8ed45b4e541 100644
--- a/compiler/rustc_ty_utils/src/ty.rs
+++ b/compiler/rustc_ty_utils/src/ty.rs
@@ -2,7 +2,7 @@ use rustc_data_structures::fx::FxHashSet;
 use rustc_hir as hir;
 use rustc_hir::LangItem;
 use rustc_hir::def::DefKind;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::bug;
 use rustc_middle::query::Providers;
 use rustc_middle::ty::fold::fold_regions;
@@ -317,7 +317,7 @@ fn asyncness(tcx: TyCtxt<'_>, def_id: LocalDefId) -> ty::Asyncness {
     })
 }
 
-fn unsizing_params_for_adt<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> BitSet<u32> {
+fn unsizing_params_for_adt<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> DenseBitSet<u32> {
     let def = tcx.adt_def(def_id);
     let num_params = tcx.generics_of(def_id).count();
 
@@ -338,10 +338,10 @@ fn unsizing_params_for_adt<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> BitSet<u32
 
     // The last field of the structure has to exist and contain type/const parameters.
     let Some((tail_field, prefix_fields)) = def.non_enum_variant().fields.raw.split_last() else {
-        return BitSet::new_empty(num_params);
+        return DenseBitSet::new_empty(num_params);
     };
 
-    let mut unsizing_params = BitSet::new_empty(num_params);
+    let mut unsizing_params = DenseBitSet::new_empty(num_params);
     for arg in tcx.type_of(tail_field.did).instantiate_identity().walk() {
         if let Some(i) = maybe_unsizing_param_idx(arg) {
             unsizing_params.insert(i);
diff --git a/compiler/rustc_type_ir/src/interner.rs b/compiler/rustc_type_ir/src/interner.rs
index 025ec7ae896..4fec606a831 100644
--- a/compiler/rustc_type_ir/src/interner.rs
+++ b/compiler/rustc_type_ir/src/interner.rs
@@ -3,7 +3,7 @@ use std::hash::Hash;
 use std::ops::Deref;
 
 use rustc_ast_ir::Movability;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use smallvec::SmallVec;
 
 use crate::fold::TypeFoldable;
@@ -282,7 +282,7 @@ pub trait Interner:
     fn coroutine_is_gen(self, coroutine_def_id: Self::DefId) -> bool;
     fn coroutine_is_async_gen(self, coroutine_def_id: Self::DefId) -> bool;
 
-    type UnsizingParams: Deref<Target = BitSet<u32>>;
+    type UnsizingParams: Deref<Target = DenseBitSet<u32>>;
     fn unsizing_params_for_adt(self, adt_def_id: Self::DefId) -> Self::UnsizingParams;
 
     fn find_const_ty_from_env(
diff --git a/src/tools/clippy/clippy_lints/src/needless_borrows_for_generic_args.rs b/src/tools/clippy/clippy_lints/src/needless_borrows_for_generic_args.rs
index f69913ddbfd..7f91e555054 100644
--- a/src/tools/clippy/clippy_lints/src/needless_borrows_for_generic_args.rs
+++ b/src/tools/clippy/clippy_lints/src/needless_borrows_for_generic_args.rs
@@ -9,7 +9,7 @@ use rustc_errors::Applicability;
 use rustc_hir::def::{DefKind, Res};
 use rustc_hir::def_id::{DefId, LocalDefId};
 use rustc_hir::{Body, Expr, ExprKind, Mutability, Path, QPath};
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_infer::infer::TyCtxtInferExt;
 use rustc_lint::{LateContext, LateLintPass};
 use rustc_middle::mir::{Rvalue, StatementKind};
@@ -390,7 +390,7 @@ fn replace_types<'tcx>(
     projection_predicates: &[ProjectionPredicate<'tcx>],
     args: &mut [GenericArg<'tcx>],
 ) -> bool {
-    let mut replaced = BitSet::new_empty(args.len());
+    let mut replaced = DenseBitSet::new_empty(args.len());
 
     let mut deque = VecDeque::with_capacity(args.len());
     deque.push_back((param_ty, new_ty));
diff --git a/src/tools/clippy/clippy_utils/src/mir/mod.rs b/src/tools/clippy/clippy_utils/src/mir/mod.rs
index 3924e384c37..ccbbccd0dbf 100644
--- a/src/tools/clippy/clippy_utils/src/mir/mod.rs
+++ b/src/tools/clippy/clippy_utils/src/mir/mod.rs
@@ -1,5 +1,5 @@
 use rustc_hir::{Expr, HirId};
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor};
 use rustc_middle::mir::{
     BasicBlock, Body, InlineAsmOperand, Local, Location, Place, START_BLOCK, StatementKind, TerminatorKind, traversal,
@@ -88,7 +88,7 @@ impl<'tcx> Visitor<'tcx> for V<'_> {
 
 /// Checks if the block is part of a cycle
 pub fn block_in_cycle(body: &Body<'_>, block: BasicBlock) -> bool {
-    let mut seen = BitSet::new_empty(body.basic_blocks.len());
+    let mut seen = DenseBitSet::new_empty(body.basic_blocks.len());
     let mut to_visit = Vec::with_capacity(body.basic_blocks.len() / 2);
 
     seen.insert(block);
diff --git a/src/tools/clippy/clippy_utils/src/mir/possible_borrower.rs b/src/tools/clippy/clippy_utils/src/mir/possible_borrower.rs
index cf73bae2583..5eb9b3b8f22 100644
--- a/src/tools/clippy/clippy_utils/src/mir/possible_borrower.rs
+++ b/src/tools/clippy/clippy_utils/src/mir/possible_borrower.rs
@@ -2,7 +2,7 @@ use super::possible_origin::PossibleOriginVisitor;
 use super::transitive_relation::TransitiveRelation;
 use crate::ty::is_copy;
 use rustc_data_structures::fx::FxHashMap;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_lint::LateContext;
 use rustc_middle::mir::visit::Visitor as _;
 use rustc_middle::mir::{self, Mutability};
@@ -21,14 +21,14 @@ struct PossibleBorrowerVisitor<'a, 'b, 'tcx> {
     possible_borrower: TransitiveRelation,
     body: &'b mir::Body<'tcx>,
     cx: &'a LateContext<'tcx>,
-    possible_origin: FxHashMap<mir::Local, BitSet<mir::Local>>,
+    possible_origin: FxHashMap<mir::Local, DenseBitSet<mir::Local>>,
 }
 
 impl<'a, 'b, 'tcx> PossibleBorrowerVisitor<'a, 'b, 'tcx> {
     fn new(
         cx: &'a LateContext<'tcx>,
         body: &'b mir::Body<'tcx>,
-        possible_origin: FxHashMap<mir::Local, BitSet<mir::Local>>,
+        possible_origin: FxHashMap<mir::Local, DenseBitSet<mir::Local>>,
     ) -> Self {
         Self {
             possible_borrower: TransitiveRelation::default(),
@@ -56,7 +56,7 @@ impl<'a, 'b, 'tcx> PossibleBorrowerVisitor<'a, 'b, 'tcx> {
             }
         }
 
-        let bs = BitSet::new_empty(self.body.local_decls.len());
+        let bs = DenseBitSet::new_empty(self.body.local_decls.len());
         PossibleBorrowerMap {
             map,
             maybe_live,
@@ -119,7 +119,7 @@ impl<'tcx> mir::visit::Visitor<'tcx> for PossibleBorrowerVisitor<'_, '_, 'tcx> {
             let mut mutable_variables: Vec<mir::Local> = mutable_borrowers
                 .iter()
                 .filter_map(|r| self.possible_origin.get(r))
-                .flat_map(BitSet::iter)
+                .flat_map(DenseBitSet::iter)
                 .collect();
 
             if ContainsRegion.visit_ty(self.body.local_decls[*dest].ty).is_break() {
@@ -171,10 +171,10 @@ fn rvalue_locals(rvalue: &mir::Rvalue<'_>, mut visit: impl FnMut(mir::Local)) {
 #[allow(clippy::module_name_repetitions)]
 pub struct PossibleBorrowerMap<'b, 'tcx> {
     /// Mapping `Local -> its possible borrowers`
-    pub map: FxHashMap<mir::Local, BitSet<mir::Local>>,
+    pub map: FxHashMap<mir::Local, DenseBitSet<mir::Local>>,
     maybe_live: ResultsCursor<'b, 'tcx, MaybeStorageLive<'tcx>>,
-    // Caches to avoid allocation of `BitSet` on every query
-    pub bitset: (BitSet<mir::Local>, BitSet<mir::Local>),
+    // Caches to avoid allocation of `DenseBitSet` on every query
+    pub bitset: (DenseBitSet<mir::Local>, DenseBitSet<mir::Local>),
 }
 
 impl<'b, 'tcx> PossibleBorrowerMap<'b, 'tcx> {
@@ -184,7 +184,7 @@ impl<'b, 'tcx> PossibleBorrowerMap<'b, 'tcx> {
             vis.visit_body(mir);
             vis.into_map(cx)
         };
-        let maybe_storage_live_result = MaybeStorageLive::new(Cow::Owned(BitSet::new_empty(mir.local_decls.len())))
+        let maybe_storage_live_result = MaybeStorageLive::new(Cow::Owned(DenseBitSet::new_empty(mir.local_decls.len())))
             .iterate_to_fixpoint(cx.tcx, mir, Some("redundant_clone"))
             .into_results_cursor(mir);
         let mut vis = PossibleBorrowerVisitor::new(cx, mir, possible_origin);
diff --git a/src/tools/clippy/clippy_utils/src/mir/possible_origin.rs b/src/tools/clippy/clippy_utils/src/mir/possible_origin.rs
index 47b93aad20c..3d253fd2bb1 100644
--- a/src/tools/clippy/clippy_utils/src/mir/possible_origin.rs
+++ b/src/tools/clippy/clippy_utils/src/mir/possible_origin.rs
@@ -1,7 +1,7 @@
 use super::transitive_relation::TransitiveRelation;
 use crate::ty::is_copy;
 use rustc_data_structures::fx::FxHashMap;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_lint::LateContext;
 use rustc_middle::mir;
 
@@ -22,7 +22,7 @@ impl<'a, 'tcx> PossibleOriginVisitor<'a, 'tcx> {
         }
     }
 
-    pub fn into_map(self, cx: &LateContext<'tcx>) -> FxHashMap<mir::Local, BitSet<mir::Local>> {
+    pub fn into_map(self, cx: &LateContext<'tcx>) -> FxHashMap<mir::Local, DenseBitSet<mir::Local>> {
         let mut map = FxHashMap::default();
         for row in (1..self.body.local_decls.len()).map(mir::Local::from_usize) {
             if is_copy(cx, self.body.local_decls[row].ty) {
diff --git a/src/tools/clippy/clippy_utils/src/mir/transitive_relation.rs b/src/tools/clippy/clippy_utils/src/mir/transitive_relation.rs
index 74d1f60af71..da44829a4c8 100644
--- a/src/tools/clippy/clippy_utils/src/mir/transitive_relation.rs
+++ b/src/tools/clippy/clippy_utils/src/mir/transitive_relation.rs
@@ -1,5 +1,5 @@
 use rustc_data_structures::fx::FxHashMap;
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::DenseBitSet;
 use rustc_middle::mir;
 
 #[derive(Default)]
@@ -12,8 +12,8 @@ impl TransitiveRelation {
         self.relations.entry(a).or_default().push(b);
     }
 
-    pub fn reachable_from(&self, a: mir::Local, domain_size: usize) -> BitSet<mir::Local> {
-        let mut seen = BitSet::new_empty(domain_size);
+    pub fn reachable_from(&self, a: mir::Local, domain_size: usize) -> DenseBitSet<mir::Local> {
+        let mut seen = DenseBitSet::new_empty(domain_size);
         let mut stack = vec![a];
         while let Some(u) = stack.pop() {
             if let Some(edges) = self.relations.get(&u) {