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, 152 insertions, 3 deletions

diff --git a/libartbase/base/bit_vector.h b/libartbase/base/bit_vector.h
index dc15874cbf..0c735cc58a 100644
--- a/libartbase/base/bit_vector.h
+++ b/libartbase/base/bit_vector.h
@@ -18,6 +18,7 @@
 #define ART_LIBARTBASE_BASE_BIT_VECTOR_H_
 
 #include <stdint.h>
+
 #include <iterator>
 
 #include "bit_utils.h"
@@ -26,6 +27,7 @@
 namespace art {
 
 class Allocator;
+class ArenaBitVector;
 
 /*
  * Expanding bitmap, used for tracking resources.  Bits are numbered starting
@@ -33,6 +35,9 @@ class Allocator;
  */
 class BitVector {
  public:
+  static constexpr uint32_t kWordBytes = sizeof(uint32_t);
+  static constexpr uint32_t kWordBits = kWordBytes * 8;
+
   class IndexContainer;
 
   /**
@@ -226,11 +231,22 @@ class BitVector {
     return storage_size_ * kWordBytes;
   }
 
+  size_t GetBitSizeOf() const {
+    return storage_size_ * kWordBits;
+  }
+
   /**
    * @return the highest bit set, -1 if none are set
    */
   int GetHighestBitSet() const;
 
+  /**
+   * @return true if there are any bits set, false otherwise.
+   */
+  bool IsAnyBitSet() const {
+    return GetHighestBitSet() != -1;
+  }
+
   // Minimum number of bits required to store this vector, 0 if none are set.
   size_t GetNumberOfBits() const {
     return GetHighestBitSet() + 1;
@@ -281,15 +297,148 @@ class BitVector {
     return 1 << (idx & 0x1f);
   }
 
-  static constexpr uint32_t kWordBytes = sizeof(uint32_t);
-  static constexpr uint32_t kWordBits = kWordBytes * 8;
-
   uint32_t*  storage_;            // The storage for the bit vector.
   uint32_t   storage_size_;       // Current size, in 32-bit words.
   Allocator* const allocator_;    // Allocator if expandable.
   const bool expandable_;         // Should the bitmap expand if too small?
 };
 
+// Helper for dealing with 2d bit-vector arrays packed into a single bit-vec
+class BaseBitVectorArray {
+ public:
+  BaseBitVectorArray(const BaseBitVectorArray& bv) = default;
+  BaseBitVectorArray& operator=(const BaseBitVectorArray& other) = default;
+
+  BaseBitVectorArray() : num_columns_(0), num_rows_(0) {}
+
+  BaseBitVectorArray(size_t num_rows, size_t num_columns)
+      : num_columns_(RoundUp(num_columns, BitVector::kWordBits)), num_rows_(num_rows) {}
+
+  virtual ~BaseBitVectorArray() {}
+
+  bool IsExpandable() const {
+    return GetRawData().IsExpandable();
+  }
+
+  // Let subclasses provide storage for various types.
+  virtual const BitVector& GetRawData() const = 0;
+  virtual BitVector& GetRawData() = 0;
+
+  size_t NumRows() const {
+    return num_rows_;
+  }
+
+  // NB This might be more than the requested size for alignment purposes.
+  size_t NumColumns() const {
+    return num_columns_;
+  }
+
+  void Clear() {
+    GetRawData().ClearAllBits();
+  }
+
+  // Ensure that we can set all bits in the given range. The actual number of
+  // columns might be larger than requested for alignment purposes.
+  void Resize(size_t rows, size_t cols, bool clear = true);
+
+  void SetBit(size_t row, size_t col) {
+    DCHECK_LT(col, num_columns_);
+    DCHECK_LT(row, num_rows_);
+    GetRawData().SetBit(row * num_columns_ + col);
+  }
+
+  void ClearBit(size_t row, size_t col) {
+    DCHECK_LT(col, num_columns_);
+    DCHECK_LT(row, num_rows_);
+    GetRawData().ClearBit(row * num_columns_ + col);
+  }
+
+  bool IsBitSet(size_t row, size_t col) const {
+    DCHECK_LT(col, num_columns_);
+    DCHECK_LT(row, num_rows_);
+    return GetRawData().IsBitSet(row * num_columns_ + col);
+  }
+
+  // Union the vector of 'other' into 'dest_row'.
+  void UnionRows(size_t dest_row, size_t other);
+
+  static size_t RequiredBitVectorSize(size_t rows, size_t cols) {
+    return rows * RoundUp(cols, BitVector::kWordBits);
+  }
+
+  static size_t MaxRowsFor(const BitVector& bv, size_t cols) {
+    return cols != 0 ? bv.GetBitSizeOf() / RoundUp(cols, BitVector::kWordBits) : 0;
+  }
+
+ private:
+  size_t num_columns_;
+  size_t num_rows_;
+};
+
+// A BitVectorArray with a standard owned BitVector providing the backing
+// storage. This should be used when the BitVectorArray is the owner of the
+// whole BitVector and should use standard allocators for cleanup/allocation.
+// Contrast this with ArenaBitVectorArray which uses arena allocators.
+class BitVectorArray final : public BaseBitVectorArray {
+ public:
+  BitVectorArray(const BitVectorArray& bv) = delete;
+  BitVectorArray& operator=(const BitVectorArray& other) = delete;
+
+  explicit BitVectorArray(BitVector&& bv) : BaseBitVectorArray(), data_(std::move(bv)) {}
+  explicit BitVectorArray(BitVector&& bv, size_t cols)
+      : BaseBitVectorArray(BaseBitVectorArray::MaxRowsFor(bv, cols), cols), data_(std::move(bv)) {}
+  explicit BitVectorArray(BitVector&& bv, size_t rows, size_t cols)
+      : BaseBitVectorArray(rows, cols), data_(std::move(bv)) {}
+
+  BitVectorArray(uint32_t start_rows, uint32_t start_cols, bool expandable, Allocator* allocator)
+      : BaseBitVectorArray(start_rows, start_cols),
+        data_(BaseBitVectorArray::RequiredBitVectorSize(start_rows, start_cols),
+              expandable,
+              allocator) {}
+
+  BitVectorArray(const BaseBitVectorArray& src, bool expandable, Allocator* allocator)
+      : BaseBitVectorArray(src.NumRows(), src.NumColumns()),
+        data_(src.GetRawData(), expandable, allocator) {}
+
+  ~BitVectorArray() override {}
+
+  const BitVector& GetRawData() const override {
+    return data_;
+  }
+
+  BitVector& GetRawData() override {
+    return data_;
+  }
+
+ private:
+  BitVector data_;
+};
+
+// A bit vector array that uses an unowned BitVector reference as it's backing
+// data.
+class BitVectorArrayWrapper final : public BaseBitVectorArray {
+ public:
+  BitVectorArrayWrapper& operator=(BitVectorArrayWrapper& other) = default;
+  BitVectorArrayWrapper(BitVectorArrayWrapper&) = default;
+  explicit BitVectorArrayWrapper(BitVector* bv) : BaseBitVectorArray(), data_(bv) {}
+  explicit BitVectorArrayWrapper(BitVector* bv, size_t cols)
+      : BaseBitVectorArray(BaseBitVectorArray::MaxRowsFor(*bv, cols), cols), data_(bv) {}
+  explicit BitVectorArrayWrapper(BitVector* bv, size_t rows, size_t cols)
+      : BaseBitVectorArray(rows, cols), data_(bv) {}
+
+  ~BitVectorArrayWrapper() override {}
+
+  const BitVector& GetRawData() const override {
+    return *data_;
+  }
+
+  BitVector& GetRawData() override {
+    return *data_;
+  }
+
+ private:
+  BitVector* data_;
+};
 
 }  // namespace art