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));
+ }
+}