From a13354bea05968799a5be5521691322274fa6a9e Mon Sep 17 00:00:00 2001 From: Rémy Rakic Date: Tue, 7 Jan 2025 15:19:05 +0000 Subject: rename `BitSet` to `DenseBitSet` This should make it clearer that this bitset is dense, with the advantages and disadvantages that it entails. --- .../rustc_mir_transform/src/coverage/counters.rs | 11 +++++---- compiler/rustc_mir_transform/src/coverage/graph.rs | 6 ++--- .../rustc_mir_transform/src/coverage/mappings.rs | 10 ++++---- compiler/rustc_mir_transform/src/coverage/query.rs | 28 +++++++++++----------- 4 files changed, 29 insertions(+), 26 deletions(-) (limited to 'compiler/rustc_mir_transform/src/coverage') 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, + bcb_needs_counter: &DenseBitSet, ) -> 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, + bcb_needs_counter: &'a DenseBitSet, site_counters: FxHashMap, } impl<'a> CountersBuilder<'a> { - fn new(graph: &'a CoverageGraph, bcb_needs_counter: &'a BitSet) -> Self { + fn new( + graph: &'a CoverageGraph, + bcb_needs_counter: &'a DenseBitSet, + ) -> 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, /// A loop header is a node that dominates one or more of its predecessors. - is_loop_header: BitSet, + is_loop_header: DenseBitSet, /// 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>, @@ -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 { + pub(super) fn all_bcbs_with_counter_mappings(&self) -> DenseBitSet { // 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 { - let mut bcbs = BitSet::new_empty(self.num_bcbs); + pub(super) fn bcbs_with_ordinary_code_mappings(&self) -> DenseBitSet { + 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, - expressions_seen: &BitSet, -) -> BitSet { + counters_seen: &DenseBitSet, + expressions_seen: &DenseBitSet, +) -> DenseBitSet { // 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, - zero_expressions: &BitSet, + counters_seen: &DenseBitSet, + zero_expressions: &DenseBitSet, term: CovTerm, ) -> bool { match term { -- cgit 1.4.1-3-g733a5