Speed up DCE, CFRE and `ReplaceUsesDominatedBy()`...

... by using `BitViewVector<>`.

Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Bug: 331194861
Change-Id: If22934aeae82b21ebf9fc20e817d0958bd6edec8

3 files changed, 33 insertions, 30 deletions

diff --git a/compiler/optimizing/constructor_fence_redundancy_elimination.cc b/compiler/optimizing/constructor_fence_redundancy_elimination.cc
index 71fc39a956..c89ec171d9 100644
--- a/compiler/optimizing/constructor_fence_redundancy_elimination.cc
+++ b/compiler/optimizing/constructor_fence_redundancy_elimination.cc
@@ -33,7 +33,7 @@ class CFREVisitor final : public HGraphVisitor {
       : HGraphVisitor(graph),
         scoped_allocator_(graph->GetArenaStack()),
         candidate_fences_(scoped_allocator_.Adapter(kArenaAllocCFRE)),
-        candidate_fence_targets_(std::nullopt),
+        candidate_fence_targets_(),
         stats_(stats) {}
 
   void VisitBasicBlock(HBasicBlock* block) override {
@@ -48,14 +48,17 @@ class CFREVisitor final : public HGraphVisitor {
   void VisitConstructorFence(HConstructorFence* constructor_fence) override {
     candidate_fences_.push_back(constructor_fence);
 
-    if (!candidate_fence_targets_.has_value()) {
+    if (candidate_fence_targets_.SizeInBits() == 0u) {
       size_t number_of_instructions = GetGraph()->GetCurrentInstructionId();
-      candidate_fence_targets_.emplace(
-          &scoped_allocator_, number_of_instructions, /*expandable=*/ false, kArenaAllocCFRE);
+      candidate_fence_targets_ = ArenaBitVector::CreateFixedSize(
+          &scoped_allocator_, number_of_instructions, kArenaAllocCFRE);
+    } else {
+      DCHECK_EQ(candidate_fence_targets_.SizeInBits(),
+                static_cast<size_t>(GetGraph()->GetCurrentInstructionId()));
     }
 
     for (HInstruction* input : constructor_fence->GetInputs()) {
-      candidate_fence_targets_->SetBit(input->GetId());
+      candidate_fence_targets_.SetBit(input->GetId());
     }
   }
 
@@ -162,8 +165,7 @@ class CFREVisitor final : public HGraphVisitor {
   void VisitSetLocation([[maybe_unused]] HInstruction* inst, HInstruction* store_input) {
     if (candidate_fences_.empty()) {
       // There is no need to look at inputs if there are no candidate fence targets.
-      DCHECK_IMPLIES(candidate_fence_targets_.has_value(),
-                     !candidate_fence_targets_->IsAnyBitSet());
+      DCHECK(!candidate_fence_targets_.IsAnyBitSet());
       return;
     }
     // An object is considered "published" if it's stored onto the heap.
@@ -179,8 +181,7 @@ class CFREVisitor final : public HGraphVisitor {
   bool HasInterestingPublishTargetAsInput(HInstruction* inst) {
     if (candidate_fences_.empty()) {
       // There is no need to look at inputs if there are no candidate fence targets.
-      DCHECK_IMPLIES(candidate_fence_targets_.has_value(),
-                     !candidate_fence_targets_->IsAnyBitSet());
+      DCHECK(!candidate_fence_targets_.IsAnyBitSet());
       return false;
     }
     for (HInstruction* input : inst->GetInputs()) {
@@ -221,15 +222,17 @@ class CFREVisitor final : public HGraphVisitor {
     // there is no benefit to this extra complexity unless we also reordered
     // the stores to come later.
     candidate_fences_.clear();
-    DCHECK(candidate_fence_targets_.has_value());
-    candidate_fence_targets_->ClearAllBits();
+    DCHECK_EQ(candidate_fence_targets_.SizeInBits(),
+              static_cast<size_t>(GetGraph()->GetCurrentInstructionId()));
+    candidate_fence_targets_.ClearAllBits();
   }
 
   // A publishing 'store' is only interesting if the value being stored
   // is one of the fence `targets` in `candidate_fences`.
   bool IsInterestingPublishTarget(HInstruction* store_input) const {
-    DCHECK(candidate_fence_targets_.has_value());
-    return candidate_fence_targets_->IsBitSet(store_input->GetId());
+    DCHECK_EQ(candidate_fence_targets_.SizeInBits(),
+              static_cast<size_t>(GetGraph()->GetCurrentInstructionId()));
+    return candidate_fence_targets_.IsBitSet(store_input->GetId());
   }
 
   // Phase-local heap memory allocator for CFRE optimizer.
@@ -245,7 +248,7 @@ class CFREVisitor final : public HGraphVisitor {
 
   // Stores a set of the fence targets, to allow faster lookup of whether
   // a detected publish is a target of one of the candidate fences.
-  std::optional<ArenaBitVector> candidate_fence_targets_;
+  BitVectorView<size_t> candidate_fence_targets_;
 
   // Used to record stats about the optimization.
   OptimizingCompilerStats* const stats_;
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 9955982309..486625a71e 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -591,14 +591,15 @@ void HDeadCodeElimination::ConnectSuccessiveBlocks() {
 
 struct HDeadCodeElimination::TryBelongingInformation {
   TryBelongingInformation(HGraph* graph, ScopedArenaAllocator* allocator)
-      : blocks_in_try(allocator, graph->GetBlocks().size(), /*expandable=*/false, kArenaAllocDCE),
-        coalesced_try_entries(
-            allocator, graph->GetBlocks().size(), /*expandable=*/false, kArenaAllocDCE) {}
+      : blocks_in_try(ArenaBitVector::CreateFixedSize(
+            allocator, graph->GetBlocks().size(), kArenaAllocDCE)),
+        coalesced_try_entries(ArenaBitVector::CreateFixedSize(
+            allocator, graph->GetBlocks().size(), kArenaAllocDCE)) {}
 
   // Which blocks belong in the try.
-  ArenaBitVector blocks_in_try;
+  BitVectorView<size_t> blocks_in_try;
   // Which other try entries are referencing this same try.
-  ArenaBitVector coalesced_try_entries;
+  BitVectorView<size_t> coalesced_try_entries;
 };
 
 bool HDeadCodeElimination::CanPerformTryRemoval(const TryBelongingInformation& try_belonging_info) {
@@ -725,7 +726,7 @@ bool HDeadCodeElimination::RemoveUnneededTries() {
       if (try_boundary->HasSameExceptionHandlersAs(*other_try_boundary)) {
         // Merge the entries as they are really the same one.
         // Block merging.
-        it->second.blocks_in_try.Union(&other_it->second.blocks_in_try);
+        it->second.blocks_in_try.Union(other_it->second.blocks_in_try);
 
         // Add the coalesced try entry to update it too.
         it->second.coalesced_try_entries.SetBit(other_block->GetBlockId());
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 752e8b10d1..6b74e7246e 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1457,18 +1457,17 @@ void HInstruction::ReplaceUsesDominatedBy(HInstruction* dominator,
                                           HInstruction* replacement,
                                           bool strictly_dominated) {
   HBasicBlock* dominator_block = dominator->GetBlock();
-  std::optional<ArenaBitVector> visited_blocks;
+  BitVectorView<size_t> visited_blocks;
 
   // Lazily compute the dominated blocks to faster calculation of domination afterwards.
   auto maybe_generate_visited_blocks = [&visited_blocks, this, dominator_block]() {
-    if (visited_blocks.has_value()) {
+    if (visited_blocks.SizeInBits() != 0u) {
+      DCHECK_EQ(visited_blocks.SizeInBits(), GetBlock()->GetGraph()->GetBlocks().size());
       return;
     }
     HGraph* graph = GetBlock()->GetGraph();
-    visited_blocks.emplace(graph->GetAllocator(),
-                           graph->GetBlocks().size(),
-                           /* expandable= */ false,
-                           kArenaAllocMisc);
+    visited_blocks = ArenaBitVector::CreateFixedSize(
+        graph->GetAllocator(), graph->GetBlocks().size(), kArenaAllocMisc);
     ScopedArenaAllocator allocator(graph->GetArenaStack());
     ScopedArenaQueue<const HBasicBlock*> worklist(allocator.Adapter(kArenaAllocMisc));
     worklist.push(dominator_block);
@@ -1476,9 +1475,9 @@ void HInstruction::ReplaceUsesDominatedBy(HInstruction* dominator,
     while (!worklist.empty()) {
       const HBasicBlock* current = worklist.front();
       worklist.pop();
-      visited_blocks->SetBit(current->GetBlockId());
+      visited_blocks.SetBit(current->GetBlockId());
       for (HBasicBlock* dominated : current->GetDominatedBlocks()) {
-        if (visited_blocks->IsBitSet(dominated->GetBlockId())) {
+        if (visited_blocks.IsBitSet(dominated->GetBlockId())) {
           continue;
         }
         worklist.push(dominated);
@@ -1501,7 +1500,7 @@ void HInstruction::ReplaceUsesDominatedBy(HInstruction* dominator,
     } else {
       // Block domination.
       maybe_generate_visited_blocks();
-      dominated = visited_blocks->IsBitSet(block->GetBlockId());
+      dominated = visited_blocks.IsBitSet(block->GetBlockId());
     }
 
     if (dominated) {
@@ -1512,7 +1511,7 @@ void HInstruction::ReplaceUsesDominatedBy(HInstruction* dominator,
       // for their inputs.
       HBasicBlock* predecessor = block->GetPredecessors()[index];
       maybe_generate_visited_blocks();
-      if (visited_blocks->IsBitSet(predecessor->GetBlockId())) {
+      if (visited_blocks.IsBitSet(predecessor->GetBlockId())) {
         user->ReplaceInput(replacement, index);
       }
     }