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
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 2216cec..e743d8e 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -276,6 +276,17 @@
                             id));
     }
   }
+
+  // If this is a nested loop, ensure the outer loops contain a superset of the blocks.
+  for (HLoopInformationOutwardIterator it(*loop_header); !it.Done(); it.Advance()) {
+    HLoopInformation* outer_info = it.Current();
+    if (!loop_blocks.IsSubsetOf(&outer_info->GetBlocks())) {
+      AddError(StringPrintf("Blocks of loop defined by header %d are not a subset of blocks of "
+                            "an outer loop defined by header %d.",
+                            loop_header->GetBlockId(),
+                            outer_info->GetHeader()->GetBlockId()));
+    }
+  }
 }
 
 void SSAChecker::VisitInstruction(HInstruction* instruction) {
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 5fca4fa..4b9d4fc 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1064,8 +1064,10 @@
         outer_graph->AddBlock(current);
         outer_graph->reverse_post_order_.Put(++index_of_at, current);
         if (info != nullptr) {
-          info->Add(current);
           current->SetLoopInformation(info);
+          for (HLoopInformationOutwardIterator loop_it(*at); !loop_it.Done(); loop_it.Advance()) {
+            loop_it.Current()->Add(current);
+          }
         }
       }
     }
@@ -1075,8 +1077,10 @@
     outer_graph->AddBlock(to);
     outer_graph->reverse_post_order_.Put(++index_of_at, to);
     if (info != nullptr) {
-      info->Add(to);
       to->SetLoopInformation(info);
+      for (HLoopInformationOutwardIterator loop_it(*at); !loop_it.Done(); loop_it.Advance()) {
+        loop_it.Current()->Add(to);
+      }
       if (info->IsBackEdge(*at)) {
         // Only `at` can become a back edge, as the inlined blocks
         // are predecessors of `at`.
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 @@
   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 @@
    */
   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 fe3313d1..c51b9b0 100644
--- a/runtime/base/bit_vector_test.cc
+++ b/runtime/base/bit_vector_test.cc
@@ -167,4 +167,48 @@
   }
 }
 
+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
diff --git a/test/478-checker-inliner-nested-loop/expected.txt b/test/478-checker-inliner-nested-loop/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/478-checker-inliner-nested-loop/expected.txt
diff --git a/test/478-checker-inliner-nested-loop/info.txt b/test/478-checker-inliner-nested-loop/info.txt
new file mode 100644
index 0000000..c221e37
--- /dev/null
+++ b/test/478-checker-inliner-nested-loop/info.txt
@@ -0,0 +1,2 @@
+Tests inlining into a nested loop. SSAChecker should verify that
+loop information was updated correctly.
diff --git a/test/478-checker-inliner-nested-loop/src/Main.java b/test/478-checker-inliner-nested-loop/src/Main.java
new file mode 100644
index 0000000..df583d9
--- /dev/null
+++ b/test/478-checker-inliner-nested-loop/src/Main.java
@@ -0,0 +1,57 @@
+/*
+* Copyright (C) 2015 The Android Open Source Project
+*
+* Licensed under the Apache License, Version 2.0 (the "License");
+* you may not use this file except in compliance with the License.
+* You may obtain a copy of the License at
+*
+*      http://www.apache.org/licenses/LICENSE-2.0
+*
+* Unless required by applicable law or agreed to in writing, software
+* distributed under the License is distributed on an "AS IS" BASIS,
+* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+* See the License for the specific language governing permissions and
+* limitations under the License.
+*/
+
+
+public class Main {
+
+  public static void assertIntEquals(int expected, int result) {
+    if (expected != result) {
+      throw new Error("Expected: " + expected + ", found: " + result);
+    }
+  }
+
+  public static int Inline(int x, int y) {
+    int result;
+    if (x <= y) {
+      result = x * y;
+    } else {
+      result = 0;
+    }
+    return result;
+  }
+
+  // CHECK-START: int Main.NestedLoop(int, int) inliner (before)
+  // CHECK-NOT:     Mul
+
+  // CHECK-START: int Main.NestedLoop(int, int) inliner (after)
+  // CHECK:         Mul
+  // CHECK-NOT:     Mul
+
+  public static int NestedLoop(int max_x, int max_y) {
+    int total = 0;
+    for (int x = 0; x < max_x; ++x) {
+      for (int y = 0; y < max_y; ++y) {
+        total += Inline(x, y);
+      }
+    }
+    return total;
+  }
+
+  public static void main(String[] args) {
+    assertIntEquals(0, NestedLoop(1, 1));
+    assertIntEquals(3, NestedLoop(2, 3));
+  }
+}