Revert^4 "Partial LSE analysis & store removal"

We incorrectly handled merging unknowns in some situations.
Specifically in cases where we are unable to materialize loop-phis we
could end up with PureUnknowns which could end up hiding stores that
need to be kept.

In an unrelated issue we were incorrectly considering some values as
escapes when live at the point of an invoke. Since
SearchPhiPlaceholdersForKeptStores used a more precise notion of
escapes we could end up removing stores without being able to replace
the values.

This reverts commit 2316b3a0779f3721a78681f5c70ed6624ecaebef.
This unreverts commit b6837f0350ff66c13582b0e94178dd5ca283ff0a
This reverts commit fe270426c8a2a69a8f669339e83b86fbf40e25a1.
This unreverts commit bb6cda60e4418c0ab557ea4090e046bed8206763.

Bug: 67037140
Bug: 173120044

Reason for revert: Fixed issue causing incorrect store elimination
Test: ./test.py --host
Test: Boot cuttlefish
      atest FrameworksServicesTests:com.android.server.job.BackgroundRestrictionsTest#testPowerWhiteList

Change-Id: I2ebae9ccfaf5169d551c5019b547589d0fce1dc9

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_;