From 7d275379bf490a87805852129e3fe2e8afe961e7 Mon Sep 17 00:00:00 2001
From: David Brazdil <dbrazdil@google.com>
Date: Tue, 21 Apr 2015 16:36:35 +0100
Subject: ART: Update loop info of all nested loops when inlining

When inlining into a nested loop, the inliner would only add the new
blocks into the innermost loop info object. This patch fixes that and
modifies SsaChecker to verify the property.

Change-Id: I21d343a6f7d972f5b7420701f816c65ab3f20566
---
 runtime/base/bit_vector.cc      | 26 ++++++++++++++++++++++++
 runtime/base/bit_vector.h       |  2 ++
 runtime/base/bit_vector_test.cc | 44 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 72 insertions(+)

(limited to 'runtime/base')

diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc
index c3e24a7..65cb028 100644
--- a/runtime/base/bit_vector.cc
+++ b/runtime/base/bit_vector.cc
@@ -79,6 +79,32 @@ bool BitVector::SameBitsSet(const BitVector *src) const {
   return (memcmp(storage_, src->GetRawStorage(), our_highest_index * kWordBytes) == 0);
 }
 
+bool BitVector::IsSubsetOf(const BitVector *other) const {
+  int this_highest = GetHighestBitSet();
+  int other_highest = other->GetHighestBitSet();
+
+  // If the highest bit set is -1, this is empty and a trivial subset.
+  if (this_highest < 0) {
+    return true;
+  }
+
+  // If the highest bit set is higher, this cannot be a subset.
+  if (this_highest > other_highest) {
+    return false;
+  }
+
+  // Compare each 32-bit word.
+  size_t this_highest_index = BitsToWords(this_highest + 1);
+  for (size_t i = 0; i < this_highest_index; ++i) {
+    uint32_t this_storage = storage_[i];
+    uint32_t other_storage = other->storage_[i];
+    if ((this_storage | other_storage) != other_storage) {
+      return false;
+    }
+  }
+  return true;
+}
+
 void BitVector::Intersect(const BitVector* src) {
   uint32_t src_storage_size = src->storage_size_;
 
diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h
index 557a2ec..be4d363 100644
--- a/runtime/base/bit_vector.h
+++ b/runtime/base/bit_vector.h
@@ -173,6 +173,8 @@ class BitVector {
    */
   bool SameBitsSet(const BitVector *src) const;
 
+  bool IsSubsetOf(const BitVector *other) const;
+
   // Count the number of bits that are set.
   uint32_t NumSetBits() const;
 
diff --git a/runtime/base/bit_vector_test.cc b/runtime/base/bit_vector_test.cc
index fe3313d..c51b9b0 100644
--- a/runtime/base/bit_vector_test.cc
+++ b/runtime/base/bit_vector_test.cc
@@ -167,4 +167,48 @@ TEST(BitVector, UnionIfNotIn) {
   }
 }
 
+TEST(BitVector, Subset) {
+  {
+    BitVector first(2, true, Allocator::GetMallocAllocator());
+    BitVector second(5, true, Allocator::GetMallocAllocator());
+
+    EXPECT_TRUE(first.IsSubsetOf(&second));
+    second.SetBit(4);
+    EXPECT_TRUE(first.IsSubsetOf(&second));
+  }
+
+  {
+    BitVector first(5, true, Allocator::GetMallocAllocator());
+    BitVector second(5, true, Allocator::GetMallocAllocator());
+
+    first.SetBit(5);
+    EXPECT_FALSE(first.IsSubsetOf(&second));
+    second.SetBit(4);
+    EXPECT_FALSE(first.IsSubsetOf(&second));
+  }
+
+  {
+    BitVector first(5, true, Allocator::GetMallocAllocator());
+    BitVector second(5, true, Allocator::GetMallocAllocator());
+
+    first.SetBit(16);
+    first.SetBit(32);
+    first.SetBit(48);
+    second.SetBit(16);
+    second.SetBit(32);
+    second.SetBit(48);
+
+    EXPECT_TRUE(first.IsSubsetOf(&second));
+    second.SetBit(8);
+    EXPECT_TRUE(first.IsSubsetOf(&second));
+    second.SetBit(40);
+    EXPECT_TRUE(first.IsSubsetOf(&second));
+    second.SetBit(52);
+    EXPECT_TRUE(first.IsSubsetOf(&second));
+
+    first.SetBit(9);
+    EXPECT_FALSE(first.IsSubsetOf(&second));
+  }
+}
+
 }  // namespace art
-- 
cgit v1.1