Optimizing: Speed up SSA Liveness Analysis.

Add some functions from `BitVector` to `BitVectorView<>`
and use this to speed up the `SsaLivenessAnalysis` pass.

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

4 files changed, 67 insertions, 56 deletions

diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc
index 0b421cf9e6..1e4ef8f867 100644
--- a/compiler/optimizing/liveness_test.cc
+++ b/compiler/optimizing/liveness_test.cc
@@ -33,14 +33,14 @@ class LivenessTest : public CommonCompilerTest, public OptimizingUnitTestHelper
   void TestCode(const std::vector<uint16_t>& data, const char* expected);
 };
 
-static void DumpBitVector(BitVector* vector,
+static void DumpBitVector(BitVectorView<size_t> vector,
                           std::ostream& buffer,
                           size_t count,
                           const char* prefix) {
   buffer << prefix;
   buffer << '(';
   for (size_t i = 0; i < count; ++i) {
-    buffer << vector->IsBitSet(i);
+    buffer << vector.IsBitSet(i);
   }
   buffer << ")\n";
 }
@@ -59,11 +59,11 @@ void LivenessTest::TestCode(const std::vector<uint16_t>& data, const char* expec
   for (HBasicBlock* block : graph->GetBlocks()) {
     buffer << "Block " << block->GetBlockId() << std::endl;
     size_t ssa_values = liveness.GetNumberOfSsaValues();
-    BitVector* live_in = liveness.GetLiveInSet(*block);
+    BitVectorView<size_t> live_in = liveness.GetLiveInSet(*block);
     DumpBitVector(live_in, buffer, ssa_values, "  live in: ");
-    BitVector* live_out = liveness.GetLiveOutSet(*block);
+    BitVectorView<size_t> live_out = liveness.GetLiveOutSet(*block);
     DumpBitVector(live_out, buffer, ssa_values, "  live out: ");
-    BitVector* kill = liveness.GetKillSet(*block);
+    BitVectorView<size_t> kill = liveness.GetKillSet(*block);
     DumpBitVector(kill, buffer, ssa_values, "  kill: ");
   }
   ASSERT_STREQ(expected, buffer.str().c_str());
diff --git a/compiler/optimizing/register_allocation_resolver.cc b/compiler/optimizing/register_allocation_resolver.cc
index a4b1698b8d..e847755978 100644
--- a/compiler/optimizing/register_allocation_resolver.cc
+++ b/compiler/optimizing/register_allocation_resolver.cc
@@ -155,8 +155,8 @@ void RegisterAllocationResolver::Resolve(ArrayRef<HInstruction* const> safepoint
       // Instructions live at the top of catch blocks or irreducible loop header
       // were forced to spill.
       if (kIsDebugBuild) {
-        BitVector* live = liveness_.GetLiveInSet(*block);
-        for (uint32_t idx : live->Indexes()) {
+        BitVectorView<size_t> live = liveness_.GetLiveInSet(*block);
+        for (uint32_t idx : live.Indexes()) {
           LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval();
           LiveInterval* sibling = interval->GetSiblingAt(block->GetLifetimeStart());
           // `GetSiblingAt` returns the sibling that contains a position, but there could be
@@ -168,8 +168,8 @@ void RegisterAllocationResolver::Resolve(ArrayRef<HInstruction* const> safepoint
         }
       }
     } else {
-      BitVector* live = liveness_.GetLiveInSet(*block);
-      for (uint32_t idx : live->Indexes()) {
+      BitVectorView<size_t> live = liveness_.GetLiveInSet(*block);
+      for (uint32_t idx : live.Indexes()) {
         LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval();
         for (HBasicBlock* predecessor : block->GetPredecessors()) {
           ConnectSplitSiblings(interval, predecessor, block);
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 317e0999d7..8d727a660a 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -105,7 +105,7 @@ void SsaLivenessAnalysis::ComputeLiveness() {
 
 void SsaLivenessAnalysis::RecursivelyProcessInputs(HInstruction* current,
                                                    HInstruction* actual_user,
-                                                   BitVector* live_in) {
+                                                   BitVectorView<size_t> live_in) {
   HInputsRef inputs = current->GetInputs();
   for (size_t i = 0; i < inputs.size(); ++i) {
     HInstruction* input = inputs[i];
@@ -121,7 +121,7 @@ void SsaLivenessAnalysis::RecursivelyProcessInputs(HInstruction* current,
       // `input` generates a result used by `current`. Add use and update
       // the live-in set.
       input->GetLiveInterval()->AddUse(current, /* environment= */ nullptr, i, actual_user);
-      live_in->SetBit(input->GetSsaIndex());
+      live_in.SetBit(input->GetSsaIndex());
     } else if (has_out_location) {
       // `input` generates a result but it is not used by `current`.
     } else {
@@ -139,7 +139,7 @@ void SsaLivenessAnalysis::RecursivelyProcessInputs(HInstruction* current,
 
 void SsaLivenessAnalysis::ProcessEnvironment(HInstruction* current,
                                              HInstruction* actual_user,
-                                             BitVector* live_in) {
+                                             BitVectorView<size_t> live_in) {
   for (HEnvironment* environment = current->GetEnvironment();
        environment != nullptr;
        environment = environment->GetParent()) {
@@ -155,7 +155,7 @@ void SsaLivenessAnalysis::ProcessEnvironment(HInstruction* current,
       // affect the live range of that instruction.
       if (should_be_live) {
         CHECK(instruction->HasSsaIndex()) << instruction->DebugName();
-        live_in->SetBit(instruction->GetSsaIndex());
+        live_in.SetBit(instruction->GetSsaIndex());
         instruction->GetLiveInterval()->AddUse(current,
                                                environment,
                                                i,
@@ -169,13 +169,13 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
   // Do a post order visit, adding inputs of instructions live in the block where
   // that instruction is defined, and killing instructions that are being visited.
   for (HBasicBlock* block : ReverseRange(graph_->GetLinearOrder())) {
-    BitVector* kill = GetKillSet(*block);
-    BitVector* live_in = GetLiveInSet(*block);
+    BitVectorView kill = GetKillSet(*block);
+    BitVectorView live_in = GetLiveInSet(*block);
 
     // Set phi inputs of successors of this block corresponding to this block
     // as live_in.
     for (HBasicBlock* successor : block->GetSuccessors()) {
-      live_in->Union(GetLiveInSet(*successor));
+      live_in.Union(GetLiveInSet(*successor));
       if (successor->IsCatchBlock()) {
         // Inputs of catch phis will be kept alive through their environment
         // uses, allowing the runtime to copy their values to the corresponding
@@ -193,14 +193,14 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
           input->GetLiveInterval()->AddPhiUse(phi, phi_input_index, block);
           // A phi input whose last user is the phi dies at the end of the predecessor block,
           // and not at the phi's lifetime position.
-          live_in->SetBit(input->GetSsaIndex());
+          live_in.SetBit(input->GetSsaIndex());
         }
       }
     }
 
     // Add a range that covers this block to all instructions live_in because of successors.
     // Instructions defined in this block will have their start of the range adjusted.
-    for (uint32_t idx : live_in->Indexes()) {
+    for (uint32_t idx : live_in.Indexes()) {
       HInstruction* current = GetInstructionFromSsaIndex(idx);
       current->GetLiveInterval()->AddRange(block->GetLifetimeStart(), block->GetLifetimeEnd());
     }
@@ -210,8 +210,8 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
       HInstruction* current = back_it.Current();
       if (current->HasSsaIndex()) {
         // Kill the instruction and shorten its interval.
-        kill->SetBit(current->GetSsaIndex());
-        live_in->ClearBit(current->GetSsaIndex());
+        kill.SetBit(current->GetSsaIndex());
+        live_in.ClearBit(current->GetSsaIndex());
         current->GetLiveInterval()->SetFrom(current->GetLifetimePosition());
       }
 
@@ -245,8 +245,8 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
     for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
       HInstruction* current = inst_it.Current();
       if (current->HasSsaIndex()) {
-        kill->SetBit(current->GetSsaIndex());
-        live_in->ClearBit(current->GetSsaIndex());
+        kill.SetBit(current->GetSsaIndex());
+        live_in.ClearBit(current->GetSsaIndex());
         LiveInterval* interval = current->GetLiveInterval();
         DCHECK((interval->GetFirstRange() == nullptr)
                || (interval->GetStart() == current->GetLifetimePosition()));
@@ -261,7 +261,7 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
       size_t last_position = block->GetLoopInformation()->GetLifetimeEnd();
       // For all live_in instructions at the loop header, we need to create a range
       // that covers the full loop.
-      for (uint32_t idx : live_in->Indexes()) {
+      for (uint32_t idx : live_in.Indexes()) {
         HInstruction* current = GetInstructionFromSsaIndex(idx);
         current->GetLiveInterval()->AddLoopRange(block->GetLifetimeStart(), last_position);
       }
@@ -289,26 +289,41 @@ void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() {
 }
 
 bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) {
-  BitVector* live_out = GetLiveOutSet(block);
+  BitVectorView<size_t> live_out = GetLiveOutSet(block);
   bool changed = false;
   // The live_out set of a block is the union of live_in sets of its successors.
   for (HBasicBlock* successor : block.GetSuccessors()) {
-    if (live_out->Union(GetLiveInSet(*successor))) {
+    if (live_out.Union(GetLiveInSet(*successor))) {
       changed = true;
     }
   }
   return changed;
 }
 
-
 bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) {
-  BitVector* live_out = GetLiveOutSet(block);
-  BitVector* kill = GetKillSet(block);
-  BitVector* live_in = GetLiveInSet(block);
+  BitVectorView<size_t> live_out = GetLiveOutSet(block);
+  BitVectorView<size_t> kill = GetKillSet(block);
+  BitVectorView<size_t> live_in = GetLiveInSet(block);
   // If live_out is updated (because of backward branches), we need to make
   // sure instructions in live_out are also in live_in, unless they are killed
   // by this block.
-  return live_in->UnionIfNotIn(live_out, kill);
+  return live_in.UnionIfNotIn(live_out, kill);
+}
+
+void SsaLivenessAnalysis::DoCheckNoLiveInIrreducibleLoop(const HBasicBlock& block) const {
+  DCHECK(block.IsLoopHeader());
+  DCHECK(block.GetLoopInformation()->IsIrreducible());
+  BitVectorView<size_t> live_in = GetLiveInSet(block);
+  // To satisfy our liveness algorithm, we need to ensure loop headers of
+  // irreducible loops do not have any live-in instructions, except constants
+  // and the current method, which can be trivially re-materialized.
+  for (uint32_t idx : live_in.Indexes()) {
+    HInstruction* instruction = GetInstructionFromSsaIndex(idx);
+    DCHECK(instruction->GetBlock()->IsEntryBlock()) << instruction->DebugName();
+    DCHECK(!instruction->IsParameterValue());
+    DCHECK(instruction->IsCurrentMethod() || instruction->IsConstant())
+        << instruction->DebugName();
+  }
 }
 
 void LiveInterval::DumpWithContext(std::ostream& stream,
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 21b7831f10..5a6ad84915 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -19,7 +19,8 @@
 
 #include <iostream>
 
-#include "base/bit_vector-inl.h"
+#include "base/arena_bit_vector.h"
+#include "base/bit_vector.h"
 #include "base/intrusive_forward_list.h"
 #include "base/iteration_range.h"
 #include "base/macros.h"
@@ -38,17 +39,20 @@ class BlockInfo : public ArenaObject<kArenaAllocSsaLiveness> {
  public:
   BlockInfo(ScopedArenaAllocator* allocator, const HBasicBlock& block, size_t number_of_ssa_values)
       : block_(block),
-        live_in_(allocator, number_of_ssa_values, false, kArenaAllocSsaLiveness),
-        live_out_(allocator, number_of_ssa_values, false, kArenaAllocSsaLiveness),
-        kill_(allocator, number_of_ssa_values, false, kArenaAllocSsaLiveness) {
+        live_in_(ArenaBitVector::CreateFixedSize(
+            allocator, number_of_ssa_values, kArenaAllocSsaLiveness)),
+        live_out_(ArenaBitVector::CreateFixedSize(
+            allocator, number_of_ssa_values, kArenaAllocSsaLiveness)),
+        kill_(ArenaBitVector::CreateFixedSize(
+            allocator, number_of_ssa_values, kArenaAllocSsaLiveness)) {
     UNUSED(block_);
   }
 
  private:
   const HBasicBlock& block_;
-  ArenaBitVector live_in_;
-  ArenaBitVector live_out_;
-  ArenaBitVector kill_;
+  BitVectorView<size_t> live_in_;
+  BitVectorView<size_t> live_out_;
+  BitVectorView<size_t> kill_;
 
   friend class SsaLivenessAnalysis;
 
@@ -1185,16 +1189,16 @@ class SsaLivenessAnalysis : public ValueObject {
 
   void Analyze();
 
-  BitVector* GetLiveInSet(const HBasicBlock& block) const {
-    return &block_infos_[block.GetBlockId()]->live_in_;
+  BitVectorView<size_t> GetLiveInSet(const HBasicBlock& block) const {
+    return block_infos_[block.GetBlockId()]->live_in_;
   }
 
-  BitVector* GetLiveOutSet(const HBasicBlock& block) const {
-    return &block_infos_[block.GetBlockId()]->live_out_;
+  BitVectorView<size_t> GetLiveOutSet(const HBasicBlock& block) const {
+    return block_infos_[block.GetBlockId()]->live_out_;
   }
 
-  BitVector* GetKillSet(const HBasicBlock& block) const {
-    return &block_infos_[block.GetBlockId()]->kill_;
+  BitVectorView<size_t> GetKillSet(const HBasicBlock& block) const {
+    return block_infos_[block.GetBlockId()]->kill_;
   }
 
   HInstruction* GetInstructionFromSsaIndex(size_t index) const {
@@ -1267,10 +1271,10 @@ class SsaLivenessAnalysis : public ValueObject {
 
   static void ProcessEnvironment(HInstruction* instruction,
                                  HInstruction* actual_user,
-                                 BitVector* live_in);
+                                 BitVectorView<size_t> live_in);
   static void RecursivelyProcessInputs(HInstruction* instruction,
                                        HInstruction* actual_user,
-                                       BitVector* live_in);
+                                       BitVectorView<size_t> live_in);
 
   // Returns whether `instruction` in an HEnvironment held by `env_holder`
   // should be kept live by the HEnvironment.
@@ -1295,19 +1299,11 @@ class SsaLivenessAnalysis : public ValueObject {
     if (!block.IsLoopHeader() || !block.GetLoopInformation()->IsIrreducible()) {
       return;
     }
-    BitVector* live_in = GetLiveInSet(block);
-    // To satisfy our liveness algorithm, we need to ensure loop headers of
-    // irreducible loops do not have any live-in instructions, except constants
-    // and the current method, which can be trivially re-materialized.
-    for (uint32_t idx : live_in->Indexes()) {
-      HInstruction* instruction = GetInstructionFromSsaIndex(idx);
-      DCHECK(instruction->GetBlock()->IsEntryBlock()) << instruction->DebugName();
-      DCHECK(!instruction->IsParameterValue());
-      DCHECK(instruction->IsCurrentMethod() || instruction->IsConstant())
-          << instruction->DebugName();
-    }
+    DoCheckNoLiveInIrreducibleLoop(block);
   }
 
+  void DoCheckNoLiveInIrreducibleLoop(const HBasicBlock& block) const;
+
   HGraph* const graph_;
   CodeGenerator* const codegen_;