Revert^2 "Partial LSE analysis & store removal"

A ScopedArenaAllocator in a single test was accidentally loaded using
operator new which is not supported. This caused a memory leak.

This reverts commit fe270426c8a2a69a8f669339e83b86fbf40e25a1.
This unreverts commit bb6cda60e4418c0ab557ea4090e046bed8206763.

Bug: 67037140

Reason for revert: Fixed memory leak in
LoadStoreAnalysisTest.PartialEscape test case

Test: SANITIZE_HOST=address ASAN_OPTIONS=detect_leaks=0 m test-art-host-gtest-dependencies
      Run art_compiler_tests

Change-Id: I34fa2079df946ae54b8c91fa771a44d56438a719

1 files changed, 12 insertions, 0 deletions

diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index ad56d31667..9fa21d5006 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -21,6 +21,7 @@
 #include <array>
 #include <type_traits>
 
+#include "base/arena_allocator.h"
 #include "base/arena_bit_vector.h"
 #include "base/arena_containers.h"
 #include "base/arena_object.h"
@@ -387,6 +388,7 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
         blocks_(allocator->Adapter(kArenaAllocBlockList)),
         reverse_post_order_(allocator->Adapter(kArenaAllocReversePostOrder)),
         linear_order_(allocator->Adapter(kArenaAllocLinearOrder)),
+        reachability_graph_(allocator, 0, 0, true, kArenaAllocReachabilityGraph),
         entry_block_(nullptr),
         exit_block_(nullptr),
         maximum_number_of_out_vregs_(0),
@@ -442,6 +444,8 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
 
   void ComputeDominanceInformation();
   void ClearDominanceInformation();
+  void ComputeReachabilityInformation();
+  void ClearReachabilityInformation();
   void ClearLoopInformation();
   void FindBackEdges(ArenaBitVector* visited);
   GraphAnalysisResult BuildDominatorTree();
@@ -590,6 +594,10 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
     has_bounds_checks_ = value;
   }
 
+  // Returns true if dest is reachable from source, using either blocks or block-ids.
+  bool PathBetween(const HBasicBlock* source, const HBasicBlock* dest) const;
+  bool PathBetween(uint32_t source_id, uint32_t dest_id) const;
+
   // Is the code known to be robust against eliminating dead references
   // and the effects of early finalization?
   bool IsDeadReferenceSafe() const { return dead_reference_safe_; }
@@ -746,6 +754,10 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
   // post order, this order is not incrementally kept up-to-date.
   ArenaVector<HBasicBlock*> linear_order_;
 
+  // Reachability graph for checking connectedness between nodes. Acts as a partitioned vector where
+  // each RoundUp(blocks_.size(), BitVector::kWordBits) is the reachability of each node.
+  ArenaBitVectorArray reachability_graph_;
+
   HBasicBlock* entry_block_;
   HBasicBlock* exit_block_;