Merge "Optimizing: Tag more arena allocations."
diff --git a/benchmark/Android.mk b/benchmark/Android.mk
index 09aca98..a4a603a 100644
--- a/benchmark/Android.mk
+++ b/benchmark/Android.mk
@@ -19,6 +19,7 @@
include art/build/Android.common_build.mk
LIBARTBENCHMARK_COMMON_SRC_FILES := \
+ jobject-benchmark/jobject_benchmark.cc \
jni-perf/perf_jni.cc \
scoped-primitive-array/scoped_primitive_array.cc
diff --git a/benchmark/jobject-benchmark/info.txt b/benchmark/jobject-benchmark/info.txt
new file mode 100644
index 0000000..f2a256a
--- /dev/null
+++ b/benchmark/jobject-benchmark/info.txt
@@ -0,0 +1,7 @@
+Benchmark for jobject functions
+
+Measures performance of:
+Add/RemoveLocalRef
+Add/RemoveGlobalRef
+Add/RemoveWeakGlobalRef
+Decoding local, weak, global, handle scope jobjects.
diff --git a/benchmark/jobject-benchmark/jobject_benchmark.cc b/benchmark/jobject-benchmark/jobject_benchmark.cc
new file mode 100644
index 0000000..e7ca9eb
--- /dev/null
+++ b/benchmark/jobject-benchmark/jobject_benchmark.cc
@@ -0,0 +1,103 @@
+/*
+ * 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.
+ */
+
+#include "jni.h"
+
+#include "mirror/class-inl.h"
+#include "scoped_thread_state_change.h"
+
+namespace art {
+namespace {
+
+extern "C" JNIEXPORT void JNICALL Java_JObjectBenchmark_timeAddRemoveLocal(
+ JNIEnv* env, jobject jobj, jint reps) {
+ ScopedObjectAccess soa(env);
+ mirror::Object* obj = soa.Decode<mirror::Object*>(jobj);
+ CHECK(obj != nullptr);
+ for (jint i = 0; i < reps; ++i) {
+ jobject ref = soa.Env()->AddLocalReference<jobject>(obj);
+ soa.Env()->DeleteLocalRef(ref);
+ }
+}
+
+extern "C" JNIEXPORT void JNICALL Java_JObjectBenchmark_timeDecodeLocal(
+ JNIEnv* env, jobject jobj, jint reps) {
+ ScopedObjectAccess soa(env);
+ mirror::Object* obj = soa.Decode<mirror::Object*>(jobj);
+ CHECK(obj != nullptr);
+ jobject ref = soa.Env()->AddLocalReference<jobject>(obj);
+ for (jint i = 0; i < reps; ++i) {
+ CHECK_EQ(soa.Decode<mirror::Object*>(ref), obj);
+ }
+ soa.Env()->DeleteLocalRef(ref);
+}
+
+extern "C" JNIEXPORT void JNICALL Java_JObjectBenchmark_timeAddRemoveGlobal(
+ JNIEnv* env, jobject jobj, jint reps) {
+ ScopedObjectAccess soa(env);
+ mirror::Object* obj = soa.Decode<mirror::Object*>(jobj);
+ CHECK(obj != nullptr);
+ for (jint i = 0; i < reps; ++i) {
+ jobject ref = soa.Vm()->AddGlobalRef(soa.Self(), obj);
+ soa.Vm()->DeleteGlobalRef(soa.Self(), ref);
+ }
+}
+
+extern "C" JNIEXPORT void JNICALL Java_JObjectBenchmark_timeDecodeGlobal(
+ JNIEnv* env, jobject jobj, jint reps) {
+ ScopedObjectAccess soa(env);
+ mirror::Object* obj = soa.Decode<mirror::Object*>(jobj);
+ CHECK(obj != nullptr);
+ jobject ref = soa.Vm()->AddGlobalRef(soa.Self(), obj);
+ for (jint i = 0; i < reps; ++i) {
+ CHECK_EQ(soa.Decode<mirror::Object*>(ref), obj);
+ }
+ soa.Vm()->DeleteGlobalRef(soa.Self(), ref);
+}
+
+extern "C" JNIEXPORT void JNICALL Java_JObjectBenchmark_timeAddRemoveWeakGlobal(
+ JNIEnv* env, jobject jobj, jint reps) {
+ ScopedObjectAccess soa(env);
+ mirror::Object* obj = soa.Decode<mirror::Object*>(jobj);
+ CHECK(obj != nullptr);
+ for (jint i = 0; i < reps; ++i) {
+ jobject ref = soa.Vm()->AddWeakGlobalRef(soa.Self(), obj);
+ soa.Vm()->DeleteWeakGlobalRef(soa.Self(), ref);
+ }
+}
+
+extern "C" JNIEXPORT void JNICALL Java_JObjectBenchmark_timeDecodeWeakGlobal(
+ JNIEnv* env, jobject jobj, jint reps) {
+ ScopedObjectAccess soa(env);
+ mirror::Object* obj = soa.Decode<mirror::Object*>(jobj);
+ CHECK(obj != nullptr);
+ jobject ref = soa.Vm()->AddWeakGlobalRef(soa.Self(), obj);
+ for (jint i = 0; i < reps; ++i) {
+ CHECK_EQ(soa.Decode<mirror::Object*>(ref), obj);
+ }
+ soa.Vm()->DeleteWeakGlobalRef(soa.Self(), ref);
+}
+
+extern "C" JNIEXPORT void JNICALL Java_JObjectBenchmark_timeDecodeHandleScopeRef(
+ JNIEnv* env, jobject jobj, jint reps) {
+ ScopedObjectAccess soa(env);
+ for (jint i = 0; i < reps; ++i) {
+ soa.Decode<mirror::Object*>(jobj);
+ }
+}
+
+} // namespace
+} // namespace art
diff --git a/benchmark/jobject-benchmark/src/JObjectBenchmark.java b/benchmark/jobject-benchmark/src/JObjectBenchmark.java
new file mode 100644
index 0000000..f4c059c
--- /dev/null
+++ b/benchmark/jobject-benchmark/src/JObjectBenchmark.java
@@ -0,0 +1,39 @@
+/*
+ * 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.
+ */
+
+import com.google.caliper.SimpleBenchmark;
+
+public class JObjectBenchmark extends SimpleBenchmark {
+ public JObjectBenchmark() {
+ // Make sure to link methods before benchmark starts.
+ System.loadLibrary("artbenchmark");
+ timeAddRemoveLocal(1);
+ timeDecodeLocal(1);
+ timeAddRemoveGlobal(1);
+ timeDecodeGlobal(1);
+ timeAddRemoveWeakGlobal(1);
+ timeDecodeWeakGlobal(1);
+ timeDecodeHandleScopeRef(1);
+ }
+
+ public native void timeAddRemoveLocal(int reps);
+ public native void timeDecodeLocal(int reps);
+ public native void timeAddRemoveGlobal(int reps);
+ public native void timeDecodeGlobal(int reps);
+ public native void timeAddRemoveWeakGlobal(int reps);
+ public native void timeDecodeWeakGlobal(int reps);
+ public native void timeDecodeHandleScopeRef(int reps);
+}
diff --git a/build/Android.executable.mk b/build/Android.executable.mk
index 72cf978..3b2d1cc 100644
--- a/build/Android.executable.mk
+++ b/build/Android.executable.mk
@@ -101,7 +101,10 @@
# TODO: Having this is not ideal as it might obscure errors. Try to get rid of it.
LOCAL_LDFLAGS += -z muldefs
ifeq ($$(HOST_OS),linux)
- LOCAL_LDLIBS += -lrt
+ LOCAL_LDLIBS += -lrt -lncurses -ltinfo
+ endif
+ ifeq ($$(HOST_OS),darwin)
+ LOCAL_LDLIBS += -lncurses -ltinfo
endif
endif
diff --git a/compiler/image_writer.cc b/compiler/image_writer.cc
index 955c575..d9f8fcb 100644
--- a/compiler/image_writer.cc
+++ b/compiler/image_writer.cc
@@ -1362,6 +1362,10 @@
// If src is a ClassLoader, set the class table to null so that it gets recreated by the
// ClassLoader.
down_cast<mirror::ClassLoader*>(copy)->SetClassTable(nullptr);
+ // Also set allocator to null to be safe. The allocator is created when we create the class
+ // table. We also never expect to unload things in the image since they are held live as
+ // roots.
+ down_cast<mirror::ClassLoader*>(copy)->SetAllocator(nullptr);
}
}
FixupVisitor visitor(this, copy);
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 62f5b9a..42b3541 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -14,8 +14,11 @@
* limitations under the License.
*/
-#include "base/arena_containers.h"
#include "bounds_check_elimination.h"
+
+#include <limits>
+
+#include "base/arena_containers.h"
#include "induction_var_range.h"
#include "nodes.h"
@@ -48,11 +51,11 @@
if (right == 0) {
return false;
}
- if ((right > 0) && (left <= INT_MAX - right)) {
+ if ((right > 0) && (left <= (std::numeric_limits<int32_t>::max() - right))) {
// No overflow.
return false;
}
- if ((right < 0) && (left >= INT_MIN - right)) {
+ if ((right < 0) && (left >= (std::numeric_limits<int32_t>::min() - right))) {
// No underflow.
return false;
}
@@ -120,8 +123,8 @@
return instruction_ == nullptr;
}
- static ValueBound Min() { return ValueBound(nullptr, INT_MIN); }
- static ValueBound Max() { return ValueBound(nullptr, INT_MAX); }
+ static ValueBound Min() { return ValueBound(nullptr, std::numeric_limits<int32_t>::min()); }
+ static ValueBound Max() { return ValueBound(nullptr, std::numeric_limits<int32_t>::max()); }
bool Equals(ValueBound bound) const {
return instruction_ == bound.instruction_ && constant_ == bound.constant_;
@@ -213,7 +216,7 @@
int32_t new_constant;
if (c > 0) {
- if (constant_ > INT_MAX - c) {
+ if (constant_ > (std::numeric_limits<int32_t>::max() - c)) {
*overflow = true;
return Max();
}
@@ -227,7 +230,7 @@
*overflow = true;
return Max();
} else {
- if (constant_ < INT_MIN - c) {
+ if (constant_ < (std::numeric_limits<int32_t>::min() - c)) {
*underflow = true;
return Min();
}
@@ -256,8 +259,8 @@
explicit ArrayAccessInsideLoopFinder(HInstruction* induction_variable)
: induction_variable_(induction_variable),
found_array_length_(nullptr),
- offset_low_(INT_MAX),
- offset_high_(INT_MIN) {
+ offset_low_(std::numeric_limits<int32_t>::max()),
+ offset_high_(std::numeric_limits<int32_t>::min()) {
Run();
}
@@ -492,7 +495,7 @@
HInstruction* initial,
int32_t increment,
ValueBound bound)
- // To be conservative, give it full range [INT_MIN, INT_MAX] in case it's
+ // To be conservative, give it full range [Min(), Max()] in case it's
// used as a regular value range, due to possible overflow/underflow.
: ValueRange(allocator, ValueBound::Min(), ValueBound::Max()),
induction_variable_(induction_variable),
@@ -554,19 +557,19 @@
if (increment_ > 0) {
// Monotonically increasing.
ValueBound lower = ValueBound::NarrowLowerBound(bound_, range->GetLower());
- if (!lower.IsConstant() || lower.GetConstant() == INT_MIN) {
+ if (!lower.IsConstant() || lower.GetConstant() == std::numeric_limits<int32_t>::min()) {
// Lower bound isn't useful. Leave it to deoptimization.
return this;
}
- // We currently conservatively assume max array length is INT_MAX. If we can
- // make assumptions about the max array length, e.g. due to the max heap size,
+ // We currently conservatively assume max array length is Max().
+ // If we can make assumptions about the max array length, e.g. due to the max heap size,
// divided by the element size (such as 4 bytes for each integer array), we can
// lower this number and rule out some possible overflows.
- int32_t max_array_len = INT_MAX;
+ int32_t max_array_len = std::numeric_limits<int32_t>::max();
// max possible integer value of range's upper value.
- int32_t upper = INT_MAX;
+ int32_t upper = std::numeric_limits<int32_t>::max();
// Try to lower upper.
ValueBound upper_bound = range->GetUpper();
if (upper_bound.IsConstant()) {
@@ -593,7 +596,7 @@
((int64_t)upper - (int64_t)initial_constant) / increment_ * increment_;
}
}
- if (last_num_in_sequence <= INT_MAX - increment_) {
+ if (last_num_in_sequence <= (std::numeric_limits<int32_t>::max() - increment_)) {
// No overflow. The sequence will be stopped by the upper bound test as expected.
return new (GetAllocator()) ValueRange(GetAllocator(), lower, range->GetUpper());
}
@@ -604,7 +607,7 @@
DCHECK_NE(increment_, 0);
// Monotonically decreasing.
ValueBound upper = ValueBound::NarrowUpperBound(bound_, range->GetUpper());
- if ((!upper.IsConstant() || upper.GetConstant() == INT_MAX) &&
+ if ((!upper.IsConstant() || upper.GetConstant() == std::numeric_limits<int32_t>::max()) &&
!upper.IsRelatedToArrayLength()) {
// Upper bound isn't useful. Leave it to deoptimization.
return this;
@@ -614,7 +617,7 @@
// for common cases.
if (range->GetLower().IsConstant()) {
int32_t constant = range->GetLower().GetConstant();
- if (constant >= INT_MIN - increment_) {
+ if (constant >= (std::numeric_limits<int32_t>::min() - increment_)) {
return new (GetAllocator()) ValueRange(GetAllocator(), range->GetLower(), upper);
}
}
@@ -1099,7 +1102,8 @@
// Very large constant index is considered as an anomaly. This is a threshold
// beyond which we don't bother to apply the deoptimization technique since
// it's likely some AIOOBE will be thrown.
- static constexpr int32_t kMaxConstantForAddingDeoptimize = INT_MAX - 1024 * 1024;
+ static constexpr int32_t kMaxConstantForAddingDeoptimize =
+ std::numeric_limits<int32_t>::max() - 1024 * 1024;
// Added blocks for loop body entry test.
bool IsAddedBlock(HBasicBlock* block) const {
@@ -1165,8 +1169,8 @@
ValueRange* LookupInductionRange(HInstruction* context, HInstruction* instruction) {
InductionVarRange::Value v1 = induction_range_.GetMinInduction(context, instruction);
InductionVarRange::Value v2 = induction_range_.GetMaxInduction(context, instruction);
- if ((v1.a_constant == 0 || v1.a_constant == 1) && v1.b_constant != INT_MIN &&
- (v2.a_constant == 0 || v2.a_constant == 1) && v2.b_constant != INT_MAX) {
+ if (v1.is_known && (v1.a_constant == 0 || v1.a_constant == 1) &&
+ v2.is_known && (v2.a_constant == 0 || v2.a_constant == 1)) {
DCHECK(v1.a_constant == 1 || v1.instruction == nullptr);
DCHECK(v2.a_constant == 1 || v2.instruction == nullptr);
ValueBound low = ValueBound(v1.instruction, v1.b_constant);
@@ -1467,8 +1471,8 @@
// Once we have an array access like 'array[5] = 1', we record array.length >= 6.
// We currently don't do it for non-constant index since a valid array[i] can't prove
// a valid array[i-1] yet due to the lower bound side.
- if (constant == INT_MAX) {
- // INT_MAX as an index will definitely throw AIOOBE.
+ if (constant == std::numeric_limits<int32_t>::max()) {
+ // Max() as an index will definitely throw AIOOBE.
return;
}
ValueBound lower = ValueBound(nullptr, constant + 1);
@@ -1690,8 +1694,8 @@
// The value of left input of instruction equals (left + c).
// (array_length + 1) or smaller divided by two or more
- // always generate a value in [INT_MIN, array_length].
- // This is true even if array_length is INT_MAX.
+ // always generate a value in [Min(), array_length].
+ // This is true even if array_length is Max().
if (left->IsArrayLength() && c <= 1) {
if (instruction->IsUShr() && c < 0) {
// Make sure for unsigned shift, left side is not negative.
@@ -1701,7 +1705,7 @@
}
ValueRange* range = new (GetGraph()->GetArena()) ValueRange(
GetGraph()->GetArena(),
- ValueBound(nullptr, INT_MIN),
+ ValueBound(nullptr, std::numeric_limits<int32_t>::min()),
ValueBound(left, 0));
GetValueRangeMap(instruction->GetBlock())->Overwrite(instruction->GetId(), range);
}
@@ -1811,7 +1815,7 @@
continue;
}
HIntConstant* lower_bound_const_instr = nullptr;
- int32_t lower_bound_const = INT_MIN;
+ int32_t lower_bound_const = std::numeric_limits<int32_t>::min();
size_t counter = 0;
// Count the constant indexing for which bounds checks haven't
// been removed yet.
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index f2bde89..e19e74f 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -262,22 +262,6 @@
return false;
}
-static const DexFile::TryItem* GetTryItem(HBasicBlock* block,
- const DexFile::CodeItem& code_item,
- const ArenaBitVector& can_block_throw) {
- DCHECK(!block->IsSingleTryBoundary());
-
- // Block does not contain throwing instructions. Even if it is covered by
- // a TryItem, we will consider it not in a try block.
- if (!can_block_throw.IsBitSet(block->GetBlockId())) {
- return nullptr;
- }
-
- // Instructions in the block may throw. Find a TryItem covering this block.
- int32_t try_item_idx = DexFile::FindTryItem(code_item, block->GetDexPc());
- return (try_item_idx == -1) ? nullptr : DexFile::GetTryItems(code_item, try_item_idx);
-}
-
void HGraphBuilder::CreateBlocksForTryCatch(const DexFile::CodeItem& code_item) {
if (code_item.tries_size_ == 0) {
return;
@@ -316,18 +300,18 @@
}
}
-void HGraphBuilder::SplitTryBoundaryEdge(HBasicBlock* predecessor,
- HBasicBlock* successor,
- HTryBoundary::BoundaryKind kind,
- const DexFile::CodeItem& code_item,
- const DexFile::TryItem& try_item) {
- // Split the edge with a single TryBoundary instruction.
- HTryBoundary* try_boundary = new (arena_) HTryBoundary(kind, successor->GetDexPc());
- HBasicBlock* try_entry_block = graph_->SplitEdge(predecessor, successor);
- try_entry_block->AddInstruction(try_boundary);
+// Returns the TryItem stored for `block` or nullptr if there is no info for it.
+static const DexFile::TryItem* GetTryItem(
+ HBasicBlock* block,
+ const ArenaSafeMap<uint32_t, const DexFile::TryItem*>& try_block_info) {
+ auto iterator = try_block_info.find(block->GetBlockId());
+ return (iterator == try_block_info.end()) ? nullptr : iterator->second;
+}
- // Link the TryBoundary to the handlers of `try_item`.
- for (CatchHandlerIterator it(code_item, try_item); it.HasNext(); it.Next()) {
+void HGraphBuilder::LinkToCatchBlocks(HTryBoundary* try_boundary,
+ const DexFile::CodeItem& code_item,
+ const DexFile::TryItem* try_item) {
+ for (CatchHandlerIterator it(code_item, *try_item); it.HasNext(); it.Next()) {
try_boundary->AddExceptionHandler(FindBlockStartingAt(it.GetHandlerAddress()));
}
}
@@ -337,132 +321,103 @@
return;
}
- // Bit vector stores information on which blocks contain throwing instructions.
- // Must be expandable because catch blocks may be split into two.
- ArenaBitVector can_block_throw(arena_, graph_->GetBlocks().size(), /* expandable */ true);
+ // Keep a map of all try blocks and their respective TryItems. We do not use
+ // the block's pointer but rather its id to ensure deterministic iteration.
+ ArenaSafeMap<uint32_t, const DexFile::TryItem*> try_block_info(
+ std::less<uint32_t>(), arena_->Adapter());
- // Scan blocks and mark those which contain throwing instructions.
- // NOTE: We're appending new blocks inside the loop, so we need to use index because iterators
- // can be invalidated. We remember the initial size to avoid iterating over the new blocks.
- for (size_t block_id = 0u, end = graph_->GetBlocks().size(); block_id != end; ++block_id) {
- HBasicBlock* block = graph_->GetBlocks()[block_id];
- bool can_throw = false;
- for (HInstructionIterator insn(block->GetInstructions()); !insn.Done(); insn.Advance()) {
- if (insn.Current()->CanThrow()) {
- can_throw = true;
- break;
- }
- }
+ // Obtain TryItem information for blocks with throwing instructions, and split
+ // blocks which are both try & catch to simplify the graph.
+ // NOTE: We are appending new blocks inside the loop, so we need to use index
+ // because iterators can be invalidated. We remember the initial size to avoid
+ // iterating over the new blocks which cannot throw.
+ for (size_t i = 0, e = graph_->GetBlocks().size(); i < e; ++i) {
+ HBasicBlock* block = graph_->GetBlocks()[i];
- if (can_throw) {
- if (block->IsCatchBlock()) {
- // Catch blocks are always considered an entry point into the TryItem in
- // order to avoid splitting exceptional edges. We split the block after
- // the move-exception (if present) and mark the first part non-throwing.
- // Later on, a TryBoundary will be inserted between the two blocks.
- HInstruction* first_insn = block->GetFirstInstruction();
- if (first_insn->IsLoadException()) {
- // Catch block starts with a LoadException. Split the block after the
- // StoreLocal and ClearException which must come after the load.
- DCHECK(first_insn->GetNext()->IsStoreLocal());
- DCHECK(first_insn->GetNext()->GetNext()->IsClearException());
- block = block->SplitBefore(first_insn->GetNext()->GetNext()->GetNext());
- } else {
- // Catch block does not load the exception. Split at the beginning to
- // create an empty catch block.
- block = block->SplitBefore(first_insn);
+ // Do not bother creating exceptional edges for try blocks which have no
+ // throwing instructions. In that case we simply assume that the block is
+ // not covered by a TryItem. This prevents us from creating a throw-catch
+ // loop for synchronized blocks.
+ if (block->HasThrowingInstructions()) {
+ // Try to find a TryItem covering the block.
+ DCHECK_NE(block->GetDexPc(), kNoDexPc) << "Block must have a dec_pc to find its TryItem.";
+ const int32_t try_item_idx = DexFile::FindTryItem(code_item, block->GetDexPc());
+ if (try_item_idx != -1) {
+ // Block throwing and in a TryItem. Store the try block information.
+ HBasicBlock* throwing_block = block;
+ if (block->IsCatchBlock()) {
+ // Simplify blocks which are both try and catch, otherwise we would
+ // need a strategy for splitting exceptional edges. We split the block
+ // after the move-exception (if present) and mark the first part not
+ // throwing. The normal-flow edge between them will be split later.
+ HInstruction* first_insn = block->GetFirstInstruction();
+ if (first_insn->IsLoadException()) {
+ // Catch block starts with a LoadException. Split the block after
+ // the StoreLocal and ClearException which must come after the load.
+ DCHECK(first_insn->GetNext()->IsStoreLocal());
+ DCHECK(first_insn->GetNext()->GetNext()->IsClearException());
+ throwing_block = block->SplitBefore(first_insn->GetNext()->GetNext()->GetNext());
+ } else {
+ // Catch block does not load the exception. Split at the beginning
+ // to create an empty catch block.
+ throwing_block = block->SplitBefore(first_insn);
+ }
}
+
+ try_block_info.Put(throwing_block->GetBlockId(),
+ DexFile::GetTryItems(code_item, try_item_idx));
}
- can_block_throw.SetBit(block->GetBlockId());
}
}
- // Iterate over all blocks, find those covered by some TryItem and:
- // (a) split edges which enter/exit the try range,
- // (b) create TryBoundary instructions in the new blocks,
- // (c) link the new blocks to corresponding exception handlers.
- // We cannot iterate only over blocks in `branch_targets_` because switch-case
- // blocks share the same dex_pc.
- // NOTE: We're appending new blocks inside the loop, so we need to use index because iterators
- // can be invalidated. We remember the initial size to avoid iterating over the new blocks.
- for (size_t block_id = 0u, end = graph_->GetBlocks().size(); block_id != end; ++block_id) {
- HBasicBlock* try_block = graph_->GetBlocks()[block_id];
- // TryBoundary blocks are added at the end of the list and not iterated over.
- DCHECK(!try_block->IsSingleTryBoundary());
-
- // Find the TryItem for this block.
- const DexFile::TryItem* try_item = GetTryItem(try_block, code_item, can_block_throw);
- if (try_item == nullptr) {
- continue;
+ // Do a pass over the try blocks and insert entering TryBoundaries where at
+ // least one predecessor is not covered by the same TryItem as the try block.
+ // We do not split each edge separately, but rather create one boundary block
+ // that all predecessors are relinked to. This preserves loop headers (b/23895756).
+ for (auto entry : try_block_info) {
+ HBasicBlock* try_block = graph_->GetBlock(entry.first);
+ for (HBasicBlock* predecessor : try_block->GetPredecessors()) {
+ if (GetTryItem(predecessor, try_block_info) != entry.second) {
+ // Found a predecessor not covered by the same TryItem. Insert entering
+ // boundary block.
+ HTryBoundary* try_entry =
+ new (arena_) HTryBoundary(HTryBoundary::kEntry, try_block->GetDexPc());
+ try_block->CreateImmediateDominator()->AddInstruction(try_entry);
+ LinkToCatchBlocks(try_entry, code_item, entry.second);
+ break;
+ }
}
+ }
- // Catch blocks were split earlier and cannot throw.
- DCHECK(!try_block->IsCatchBlock());
+ // Do a second pass over the try blocks and insert exit TryBoundaries where
+ // the successor is not in the same TryItem.
+ for (auto entry : try_block_info) {
+ HBasicBlock* try_block = graph_->GetBlock(entry.first);
+ // NOTE: Do not use iterators because SplitEdge would invalidate them.
+ for (size_t i = 0, e = try_block->GetSuccessors().size(); i < e; ++i) {
+ HBasicBlock* successor = try_block->GetSuccessor(i);
- // Find predecessors which are not covered by the same TryItem range. Such
- // edges enter the try block and will have a TryBoundary inserted.
- for (size_t i = 0; i < try_block->GetPredecessors().size(); ++i) {
- HBasicBlock* predecessor = try_block->GetPredecessor(i);
- if (predecessor->IsSingleTryBoundary()) {
- // The edge was already split because of an exit from a neighbouring
- // TryItem. We split it again and insert an entry point.
- if (kIsDebugBuild) {
- HTryBoundary* last_insn = predecessor->GetLastInstruction()->AsTryBoundary();
- const DexFile::TryItem* predecessor_try_item =
- GetTryItem(predecessor->GetSinglePredecessor(), code_item, can_block_throw);
- DCHECK(!last_insn->IsEntry());
- DCHECK_EQ(last_insn->GetNormalFlowSuccessor(), try_block);
- DCHECK(try_block->IsFirstIndexOfPredecessor(predecessor, i));
- DCHECK_NE(try_item, predecessor_try_item);
- }
- } else if (GetTryItem(predecessor, code_item, can_block_throw) != try_item) {
- // This is an entry point into the TryItem and the edge has not been
- // split yet. That means that `predecessor` is not in a TryItem, or
- // it is in a different TryItem and we happened to iterate over this
- // block first. We split the edge and insert an entry point.
- } else {
- // Not an edge on the boundary of the try block.
+ // If the successor is a try block, all of its predecessors must be
+ // covered by the same TryItem. Otherwise the previous pass would have
+ // created a non-throwing boundary block.
+ if (GetTryItem(successor, try_block_info) != nullptr) {
+ DCHECK_EQ(entry.second, GetTryItem(successor, try_block_info));
continue;
}
- SplitTryBoundaryEdge(predecessor, try_block, HTryBoundary::kEntry, code_item, *try_item);
- }
- // Find successors which are not covered by the same TryItem range. Such
- // edges exit the try block and will have a TryBoundary inserted.
- for (HBasicBlock* successor : try_block->GetSuccessors()) {
- if (successor->IsCatchBlock()) {
- // A catch block is always considered an entry point into its TryItem.
- // We therefore assume this is an exit point, regardless of whether
- // the catch block is in a different TryItem or not.
- } else if (successor->IsSingleTryBoundary()) {
- // The edge was already split because of an entry into a neighbouring
- // TryItem. We split it again and insert an exit.
- if (kIsDebugBuild) {
- HTryBoundary* last_insn = successor->GetLastInstruction()->AsTryBoundary();
- const DexFile::TryItem* successor_try_item =
- GetTryItem(last_insn->GetNormalFlowSuccessor(), code_item, can_block_throw);
- DCHECK_EQ(try_block, successor->GetSinglePredecessor());
- DCHECK(last_insn->IsEntry());
- DCHECK_NE(try_item, successor_try_item);
- }
- } else if (GetTryItem(successor, code_item, can_block_throw) != try_item) {
- // This is an exit out of the TryItem and the edge has not been split
- // yet. That means that either `successor` is not in a TryItem, or it
- // is in a different TryItem and we happened to iterate over this
- // block first. We split the edge and insert an exit.
- HInstruction* last_instruction = try_block->GetLastInstruction();
- if (last_instruction->IsReturn() || last_instruction->IsReturnVoid()) {
- DCHECK_EQ(successor, exit_block_);
- // Control flow exits the try block with a Return(Void). Because
- // splitting the edge would invalidate the invariant that Return
- // always jumps to Exit, we move the Return outside the try block.
- successor = try_block->SplitBefore(last_instruction);
- }
- } else {
- // Not an edge on the boundary of the try block.
- continue;
+ // Preserve the invariant that Return(Void) always jumps to Exit by moving
+ // it outside the try block if necessary.
+ HInstruction* last_instruction = try_block->GetLastInstruction();
+ if (last_instruction->IsReturn() || last_instruction->IsReturnVoid()) {
+ DCHECK_EQ(successor, exit_block_);
+ successor = try_block->SplitBefore(last_instruction);
}
- SplitTryBoundaryEdge(try_block, successor, HTryBoundary::kExit, code_item, *try_item);
+
+ // Insert TryBoundary and link to catch blocks.
+ HTryBoundary* try_exit =
+ new (arena_) HTryBoundary(HTryBoundary::kExit, successor->GetDexPc());
+ graph_->SplitEdge(try_block, successor)->AddInstruction(try_exit);
+ LinkToCatchBlocks(try_exit, code_item, entry.second);
}
}
}
@@ -1685,6 +1640,34 @@
dex_compilation_unit_->GetDexMethodIndex(), *dex_file_, type_index);
}
+void HGraphBuilder::BuildSwitchJumpTable(const SwitchTable& table,
+ const Instruction& instruction,
+ HInstruction* value,
+ uint32_t dex_pc) {
+ // Add the successor blocks to the current block.
+ uint16_t num_entries = table.GetNumEntries();
+ for (size_t i = 1; i <= num_entries; i++) {
+ int32_t target_offset = table.GetEntryAt(i);
+ HBasicBlock* case_target = FindBlockStartingAt(dex_pc + target_offset);
+ DCHECK(case_target != nullptr);
+
+ // Add the target block as a successor.
+ current_block_->AddSuccessor(case_target);
+ }
+
+ // Add the default target block as the last successor.
+ HBasicBlock* default_target = FindBlockStartingAt(dex_pc + instruction.SizeInCodeUnits());
+ DCHECK(default_target != nullptr);
+ current_block_->AddSuccessor(default_target);
+
+ // Now add the Switch instruction.
+ int32_t starting_key = table.GetEntryAt(0);
+ current_block_->AddInstruction(
+ new (arena_) HPackedSwitch(starting_key, num_entries, value, dex_pc));
+ // This block ends with control flow.
+ current_block_ = nullptr;
+}
+
void HGraphBuilder::BuildPackedSwitch(const Instruction& instruction, uint32_t dex_pc) {
// Verifier guarantees that the payload for PackedSwitch contains:
// (a) number of entries (may be zero)
@@ -1695,18 +1678,24 @@
// Value to test against.
HInstruction* value = LoadLocal(instruction.VRegA(), Primitive::kPrimInt, dex_pc);
+ // Starting key value.
+ int32_t starting_key = table.GetEntryAt(0);
+
// Retrieve number of entries.
uint16_t num_entries = table.GetNumEntries();
if (num_entries == 0) {
return;
}
- // Chained cmp-and-branch, starting from starting_key.
- int32_t starting_key = table.GetEntryAt(0);
-
- for (size_t i = 1; i <= num_entries; i++) {
- BuildSwitchCaseHelper(instruction, i, i == num_entries, table, value, starting_key + i - 1,
- table.GetEntryAt(i), dex_pc);
+ // Don't use a packed switch if there are very few entries.
+ if (num_entries > kSmallSwitchThreshold) {
+ BuildSwitchJumpTable(table, instruction, value, dex_pc);
+ } else {
+ // Chained cmp-and-branch, starting from starting_key.
+ for (size_t i = 1; i <= num_entries; i++) {
+ BuildSwitchCaseHelper(instruction, i, i == num_entries, table, value,
+ starting_key + i - 1, table.GetEntryAt(i), dex_pc);
+ }
}
}
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h
index 8d40d69..4c8e3d0 100644
--- a/compiler/optimizing/builder.h
+++ b/compiler/optimizing/builder.h
@@ -90,6 +90,9 @@
static constexpr const char* kBuilderPassName = "builder";
+ // The number of entries in a packed switch before we use a jump table.
+ static constexpr uint16_t kSmallSwitchThreshold = 5;
+
private:
// Analyzes the dex instruction and adds HInstruction to the graph
// to execute that instruction. Returns whether the instruction can
@@ -118,13 +121,13 @@
// instructions and links them to the corresponding catch blocks.
void InsertTryBoundaryBlocks(const DexFile::CodeItem& code_item);
- // Splits a single edge, inserting a TryBoundary of given `kind` and linking
- // it to exception handlers of `try_item`.
- void SplitTryBoundaryEdge(HBasicBlock* predecessor,
- HBasicBlock* successor,
- HTryBoundary::BoundaryKind kind,
- const DexFile::CodeItem& code_item,
- const DexFile::TryItem& try_item);
+ // Iterates over the exception handlers of `try_item`, finds the corresponding
+ // catch blocks and makes them successors of `try_boundary`. The order of
+ // successors matches the order in which runtime exception delivery searches
+ // for a handler.
+ void LinkToCatchBlocks(HTryBoundary* try_boundary,
+ const DexFile::CodeItem& code_item,
+ const DexFile::TryItem* try_item);
bool CanDecodeQuickenedInfo() const;
uint16_t LookupQuickenedInfo(uint32_t dex_pc);
@@ -239,6 +242,12 @@
// Builds an instruction sequence for a packed switch statement.
void BuildPackedSwitch(const Instruction& instruction, uint32_t dex_pc);
+ // Build a switch instruction from a packed switch statement.
+ void BuildSwitchJumpTable(const SwitchTable& table,
+ const Instruction& instruction,
+ HInstruction* value,
+ uint32_t dex_pc);
+
// Builds an instruction sequence for a sparse switch statement.
void BuildSparseSwitch(const Instruction& instruction, uint32_t dex_pc);
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 411e05f..d7b1d24 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -4953,6 +4953,33 @@
// Will be generated at use site.
}
+// Simple implementation of packed switch - generate cascaded compare/jumps.
+void LocationsBuilderARM::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ LocationSummary* locations =
+ new (GetGraph()->GetArena()) LocationSummary(switch_instr, LocationSummary::kNoCall);
+ locations->SetInAt(0, Location::RequiresRegister());
+}
+
+void InstructionCodeGeneratorARM::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ int32_t lower_bound = switch_instr->GetStartValue();
+ int32_t num_entries = switch_instr->GetNumEntries();
+ LocationSummary* locations = switch_instr->GetLocations();
+ Register value_reg = locations->InAt(0).AsRegister<Register>();
+ HBasicBlock* default_block = switch_instr->GetDefaultBlock();
+
+ // Create a series of compare/jumps.
+ const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors();
+ for (int32_t i = 0; i < num_entries; i++) {
+ GenerateCompareWithImmediate(value_reg, lower_bound + i);
+ __ b(codegen_->GetLabelOf(successors.at(i)), EQ);
+ }
+
+ // And the default for any other value.
+ if (!codegen_->GoesToNextBlock(switch_instr->GetBlock(), default_block)) {
+ __ b(codegen_->GetLabelOf(default_block));
+ }
+}
+
void CodeGeneratorARM::MoveFromReturnRegister(Location trg, Primitive::Type type) {
if (!trg.IsValid()) {
DCHECK(type == Primitive::kPrimVoid);
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 8e1260e..d175532 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -3540,6 +3540,38 @@
// Will be generated at use site.
}
+// Simple implementation of packed switch - generate cascaded compare/jumps.
+void LocationsBuilderARM64::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ LocationSummary* locations =
+ new (GetGraph()->GetArena()) LocationSummary(switch_instr, LocationSummary::kNoCall);
+ locations->SetInAt(0, Location::RequiresRegister());
+}
+
+void InstructionCodeGeneratorARM64::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ int32_t lower_bound = switch_instr->GetStartValue();
+ int32_t num_entries = switch_instr->GetNumEntries();
+ Register value_reg = InputRegisterAt(switch_instr, 0);
+ HBasicBlock* default_block = switch_instr->GetDefaultBlock();
+
+ // Create a series of compare/jumps.
+ const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors();
+ for (int32_t i = 0; i < num_entries; i++) {
+ int32_t case_value = lower_bound + i;
+ vixl::Label* succ = codegen_->GetLabelOf(successors.at(i));
+ if (case_value == 0) {
+ __ Cbz(value_reg, succ);
+ } else {
+ __ Cmp(value_reg, vixl::Operand(case_value));
+ __ B(eq, succ);
+ }
+ }
+
+ // And the default for any other value.
+ if (!codegen_->GoesToNextBlock(switch_instr->GetBlock(), default_block)) {
+ __ B(codegen_->GetLabelOf(default_block));
+ }
+}
+
#undef __
#undef QUICK_ENTRY_POINT
diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc
index f4f53d5..8fdd56e 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -3364,5 +3364,38 @@
// Will be generated at use site.
}
+// Simple implementation of packed switch - generate cascaded compare/jumps.
+void LocationsBuilderMIPS64::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ LocationSummary* locations =
+ new (GetGraph()->GetArena()) LocationSummary(switch_instr, LocationSummary::kNoCall);
+ locations->SetInAt(0, Location::RequiresRegister());
+}
+
+void InstructionCodeGeneratorMIPS64::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ int32_t lower_bound = switch_instr->GetStartValue();
+ int32_t num_entries = switch_instr->GetNumEntries();
+ LocationSummary* locations = switch_instr->GetLocations();
+ GpuRegister value_reg = locations->InAt(0).AsRegister<GpuRegister>();
+ HBasicBlock* default_block = switch_instr->GetDefaultBlock();
+
+ // Create a series of compare/jumps.
+ const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors();
+ for (int32_t i = 0; i < num_entries; i++) {
+ int32_t case_value = lower_bound + i;
+ Label* succ = codegen_->GetLabelOf(successors.at(i));
+ if (case_value == 0) {
+ __ Beqzc(value_reg, succ);
+ } else {
+ __ LoadConst32(TMP, case_value);
+ __ Beqc(value_reg, TMP, succ);
+ }
+ }
+
+ // And the default for any other value.
+ if (!codegen_->GoesToNextBlock(switch_instr->GetBlock(), default_block)) {
+ __ B(codegen_->GetLabelOf(default_block));
+ }
+}
+
} // namespace mips64
} // namespace art
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 86cdbdd..ab3d1d1 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -5488,6 +5488,38 @@
// Will be generated at use site.
}
+// Simple implementation of packed switch - generate cascaded compare/jumps.
+void LocationsBuilderX86::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ LocationSummary* locations =
+ new (GetGraph()->GetArena()) LocationSummary(switch_instr, LocationSummary::kNoCall);
+ locations->SetInAt(0, Location::RequiresRegister());
+}
+
+void InstructionCodeGeneratorX86::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ int32_t lower_bound = switch_instr->GetStartValue();
+ int32_t num_entries = switch_instr->GetNumEntries();
+ LocationSummary* locations = switch_instr->GetLocations();
+ Register value_reg = locations->InAt(0).AsRegister<Register>();
+ HBasicBlock* default_block = switch_instr->GetDefaultBlock();
+
+ // Create a series of compare/jumps.
+ const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors();
+ for (int i = 0; i < num_entries; i++) {
+ int32_t case_value = lower_bound + i;
+ if (case_value == 0) {
+ __ testl(value_reg, value_reg);
+ } else {
+ __ cmpl(value_reg, Immediate(case_value));
+ }
+ __ j(kEqual, codegen_->GetLabelOf(successors.at(i)));
+ }
+
+ // And the default for any other value.
+ if (!codegen_->GoesToNextBlock(switch_instr->GetBlock(), default_block)) {
+ __ jmp(codegen_->GetLabelOf(default_block));
+ }
+}
+
void LocationsBuilderX86::VisitX86ComputeBaseMethodAddress(
HX86ComputeBaseMethodAddress* insn) {
LocationSummary* locations =
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index b78b017..cfce7a0 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -5203,6 +5203,38 @@
// Will be generated at use site.
}
+// Simple implementation of packed switch - generate cascaded compare/jumps.
+void LocationsBuilderX86_64::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ LocationSummary* locations =
+ new (GetGraph()->GetArena()) LocationSummary(switch_instr, LocationSummary::kNoCall);
+ locations->SetInAt(0, Location::RequiresRegister());
+}
+
+void InstructionCodeGeneratorX86_64::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ int32_t lower_bound = switch_instr->GetStartValue();
+ int32_t num_entries = switch_instr->GetNumEntries();
+ LocationSummary* locations = switch_instr->GetLocations();
+ CpuRegister value_reg = locations->InAt(0).AsRegister<CpuRegister>();
+ HBasicBlock* default_block = switch_instr->GetDefaultBlock();
+
+ // Create a series of compare/jumps.
+ const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors();
+ for (int i = 0; i < num_entries; i++) {
+ int32_t case_value = lower_bound + i;
+ if (case_value == 0) {
+ __ testl(value_reg, value_reg);
+ } else {
+ __ cmpl(value_reg, Immediate(case_value));
+ }
+ __ j(kEqual, codegen_->GetLabelOf(successors.at(i)));
+ }
+
+ // And the default for any other value.
+ if (!codegen_->GoesToNextBlock(switch_instr->GetBlock(), default_block)) {
+ __ jmp(codegen_->GetLabelOf(default_block));
+ }
+}
+
void CodeGeneratorX86_64::Load64BitValue(CpuRegister dest, int64_t value) {
if (value == 0) {
__ xorl(dest, dest);
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 7d509a2..b322759 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -16,34 +16,63 @@
#include "dead_code_elimination.h"
+#include "utils/array_ref.h"
#include "base/bit_vector-inl.h"
#include "ssa_phi_elimination.h"
namespace art {
-static void MarkReachableBlocks(HBasicBlock* block, ArenaBitVector* visited) {
- int block_id = block->GetBlockId();
- if (visited->IsBitSet(block_id)) {
- return;
- }
- visited->SetBit(block_id);
+static void MarkReachableBlocks(HGraph* graph, ArenaBitVector* visited) {
+ ArenaVector<HBasicBlock*> worklist(graph->GetArena()->Adapter());
+ constexpr size_t kDefaultWorlistSize = 8;
+ worklist.reserve(kDefaultWorlistSize);
+ visited->SetBit(graph->GetEntryBlock()->GetBlockId());
+ worklist.push_back(graph->GetEntryBlock());
- HInstruction* last_instruction = block->GetLastInstruction();
- if (last_instruction->IsIf()) {
- HIf* if_instruction = last_instruction->AsIf();
- HInstruction* condition = if_instruction->InputAt(0);
- if (!condition->IsIntConstant()) {
- MarkReachableBlocks(if_instruction->IfTrueSuccessor(), visited);
- MarkReachableBlocks(if_instruction->IfFalseSuccessor(), visited);
- } else if (condition->AsIntConstant()->IsOne()) {
- MarkReachableBlocks(if_instruction->IfTrueSuccessor(), visited);
- } else {
- DCHECK(condition->AsIntConstant()->IsZero());
- MarkReachableBlocks(if_instruction->IfFalseSuccessor(), visited);
+ while (!worklist.empty()) {
+ HBasicBlock* block = worklist.back();
+ worklist.pop_back();
+ int block_id = block->GetBlockId();
+ DCHECK(visited->IsBitSet(block_id));
+
+ ArrayRef<HBasicBlock* const> live_successors(block->GetSuccessors());
+ HInstruction* last_instruction = block->GetLastInstruction();
+ if (last_instruction->IsIf()) {
+ HIf* if_instruction = last_instruction->AsIf();
+ HInstruction* condition = if_instruction->InputAt(0);
+ if (condition->IsIntConstant()) {
+ if (condition->AsIntConstant()->IsOne()) {
+ live_successors = live_successors.SubArray(0u, 1u);
+ DCHECK_EQ(live_successors[0], if_instruction->IfTrueSuccessor());
+ } else {
+ DCHECK(condition->AsIntConstant()->IsZero());
+ live_successors = live_successors.SubArray(1u, 1u);
+ DCHECK_EQ(live_successors[0], if_instruction->IfFalseSuccessor());
+ }
+ }
+ } else if (last_instruction->IsPackedSwitch()) {
+ HPackedSwitch* switch_instruction = last_instruction->AsPackedSwitch();
+ HInstruction* switch_input = switch_instruction->InputAt(0);
+ if (switch_input->IsIntConstant()) {
+ int32_t switch_value = switch_input->AsIntConstant()->GetValue();
+ int32_t start_value = switch_instruction->GetStartValue();
+ uint32_t switch_index = static_cast<uint32_t>(switch_value - start_value);
+ if (switch_index < switch_instruction->GetNumEntries()) {
+ live_successors = live_successors.SubArray(switch_index, 1u);
+ DCHECK_EQ(live_successors[0], block->GetSuccessor(switch_index));
+ } else {
+ live_successors = live_successors.SubArray(switch_instruction->GetNumEntries(), 1u);
+ DCHECK_EQ(live_successors[0], switch_instruction->GetDefaultBlock());
+ }
+ }
}
- } else {
- for (HBasicBlock* successor : block->GetSuccessors()) {
- MarkReachableBlocks(successor, visited);
+
+ for (HBasicBlock* successor : live_successors) {
+ // Add only those successors that have not been visited yet.
+ if (!visited->IsBitSet(successor->GetBlockId())) {
+ visited->SetBit(successor->GetBlockId());
+ worklist.push_back(successor);
+ }
}
}
}
@@ -67,7 +96,7 @@
ArenaBitVector live_blocks(allocator, graph_->GetBlocks().size(), false);
ArenaBitVector affected_loops(allocator, graph_->GetBlocks().size(), false);
- MarkReachableBlocks(graph_->GetEntryBlock(), &live_blocks);
+ MarkReachableBlocks(graph_, &live_blocks);
bool removed_one_or_more_blocks = false;
// Remove all dead blocks. Iterate in post order because removal needs the
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 583da30..4e1cafe 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -743,6 +743,22 @@
}
}
+void SSAChecker::VisitPackedSwitch(HPackedSwitch* instruction) {
+ VisitInstruction(instruction);
+ // Check that the number of block successors matches the switch count plus
+ // one for the default block.
+ HBasicBlock* block = instruction->GetBlock();
+ if (instruction->GetNumEntries() + 1u != block->GetSuccessors().size()) {
+ AddError(StringPrintf(
+ "%s instruction %d in block %d expects %u successors to the block, but found: %zu.",
+ instruction->DebugName(),
+ instruction->GetId(),
+ block->GetBlockId(),
+ instruction->GetNumEntries() + 1u,
+ block->GetSuccessors().size()));
+ }
+}
+
void SSAChecker::VisitIf(HIf* instruction) {
VisitInstruction(instruction);
HandleBooleanInput(instruction, 0);
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index 0e270db..7ddffc1 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -125,6 +125,7 @@
void VisitBinaryOperation(HBinaryOperation* op) OVERRIDE;
void VisitCondition(HCondition* op) OVERRIDE;
void VisitIf(HIf* instruction) OVERRIDE;
+ void VisitPackedSwitch(HPackedSwitch* instruction) OVERRIDE;
void VisitBooleanNot(HBooleanNot* instruction) OVERRIDE;
void VisitConstant(HConstant* instruction) OVERRIDE;
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 92c732c..9fb4304 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -33,17 +33,6 @@
}
/**
- * Returns true if instruction is proper entry-phi-operation for given loop
- * (referred to as mu-operation in Gerlek's paper).
- */
-static bool IsEntryPhi(HLoopInformation* loop, HInstruction* instruction) {
- return
- instruction->IsPhi() &&
- instruction->InputCount() == 2 &&
- instruction->GetBlock() == loop->GetHeader();
-}
-
-/**
* Since graph traversal may enter a SCC at any position, an initial representation may be rotated,
* along dependences, viz. any of (a, b, c, d), (d, a, b, c) (c, d, a, b), (b, c, d, a) assuming
* a chain of dependences (mutual independent items may occur in arbitrary order). For proper
@@ -58,8 +47,9 @@
size_t phi_pos = -1;
const size_t size = scc->size();
for (size_t i = 0; i < size; i++) {
- if (IsEntryPhi(loop, scc->at(i)) && (phi == nullptr || phis.FoundBefore(scc->at(i), phi))) {
- phi = scc->at(i);
+ HInstruction* other = scc->at(i);
+ if (other->IsLoopHeaderPhi() && (phi == nullptr || phis.FoundBefore(other, phi))) {
+ phi = other;
phi_pos = i;
}
}
@@ -168,7 +158,7 @@
}
// Classify the SCC.
- if (scc_.size() == 1 && !IsEntryPhi(loop, scc_[0])) {
+ if (scc_.size() == 1 && !scc_[0]->IsLoopHeaderPhi()) {
ClassifyTrivial(loop, scc_[0]);
} else {
ClassifyNonTrivial(loop);
@@ -200,10 +190,7 @@
void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) {
InductionInfo* info = nullptr;
if (instruction->IsPhi()) {
- for (size_t i = 1, count = instruction->InputCount(); i < count; i++) {
- info = TransferPhi(LookupInfo(loop, instruction->InputAt(0)),
- LookupInfo(loop, instruction->InputAt(i)));
- }
+ info = TransferPhi(loop, instruction, /* input_index */ 0);
} else if (instruction->IsAdd()) {
info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
LookupInfo(loop, instruction->InputAt(1)), kAdd);
@@ -245,21 +232,21 @@
RotateEntryPhiFirst(loop, &scc_, &other);
}
- // Analyze from phi onwards.
+ // Analyze from entry-phi onwards.
HInstruction* phi = scc_[0];
- if (!IsEntryPhi(loop, phi)) {
+ if (!phi->IsLoopHeaderPhi()) {
return;
}
- HInstruction* external = phi->InputAt(0);
- HInstruction* internal = phi->InputAt(1);
- InductionInfo* initial = LookupInfo(loop, external);
+
+ // External link should be loop invariant.
+ InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
if (initial == nullptr || initial->induction_class != kInvariant) {
return;
}
- // Singleton entry-phi-operation may be a wrap-around induction.
+ // Singleton is wrap-around induction if all internal links have the same meaning.
if (size == 1) {
- InductionInfo* update = LookupInfo(loop, internal);
+ InductionInfo* update = TransferPhi(loop, phi, /* input_index */ 1);
if (update != nullptr) {
AssignInfo(loop, phi, CreateInduction(kWrapAround, initial, update));
}
@@ -272,7 +259,7 @@
HInstruction* instruction = scc_[i];
InductionInfo* update = nullptr;
if (instruction->IsPhi()) {
- update = SolvePhi(loop, phi, instruction);
+ update = SolvePhiAllInputs(loop, phi, instruction);
} else if (instruction->IsAdd()) {
update = SolveAddSub(
loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kAdd, true);
@@ -286,10 +273,9 @@
cycle_.Put(instruction, update);
}
- // Success if the internal link received a meaning.
- auto it = cycle_.find(internal);
- if (it != cycle_.end()) {
- InductionInfo* induction = it->second;
+ // Success if all internal links received the same temporary meaning.
+ InductionInfo* induction = SolvePhi(phi, /* input_index */ 1);
+ if (induction != nullptr) {
switch (induction->induction_class) {
case kInvariant:
// Classify first phi and then the rest of the cycle "on-demand".
@@ -329,13 +315,20 @@
return CreateInduction(kPeriodic, induction->op_a, RotatePeriodicInduction(induction->op_b, last));
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(InductionInfo* a,
- InductionInfo* b) {
- // Transfer over a phi: if both inputs are identical, result is input.
- if (InductionEqual(a, b)) {
- return a;
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(HLoopInformation* loop,
+ HInstruction* phi,
+ size_t input_index) {
+ // Match all phi inputs from input_index onwards exactly.
+ const size_t count = phi->InputCount();
+ DCHECK_LT(input_index, count);
+ InductionInfo* a = LookupInfo(loop, phi->InputAt(input_index));
+ for (size_t i = input_index + 1; i < count; i++) {
+ InductionInfo* b = LookupInfo(loop, phi->InputAt(i));
+ if (!InductionEqual(a, b)) {
+ return nullptr;
+ }
}
- return nullptr;
+ return a;
}
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(InductionInfo* a,
@@ -421,47 +414,56 @@
return nullptr;
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi(HLoopInformation* loop,
- HInstruction* phi,
- HInstruction* instruction) {
- // Solve within a cycle over a phi: identical inputs are combined into that input as result.
- const size_t count = instruction->InputCount();
- DCHECK_GT(count, 0u);
- auto ita = cycle_.find(instruction->InputAt(0));
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi(HInstruction* phi,
+ size_t input_index) {
+ // Match all phi inputs from input_index onwards exactly.
+ const size_t count = phi->InputCount();
+ DCHECK_LT(input_index, count);
+ auto ita = cycle_.find(phi->InputAt(input_index));
if (ita != cycle_.end()) {
- InductionInfo* a = ita->second;
- for (size_t i = 1; i < count; i++) {
- auto itb = cycle_.find(instruction->InputAt(i));
- if (itb == cycle_.end() || !HInductionVarAnalysis::InductionEqual(a, itb->second)) {
+ for (size_t i = input_index + 1; i < count; i++) {
+ auto itb = cycle_.find(phi->InputAt(i));
+ if (itb == cycle_.end() ||
+ !HInductionVarAnalysis::InductionEqual(ita->second, itb->second)) {
return nullptr;
}
}
- return a;
+ return ita->second;
+ }
+ return nullptr;
+}
+
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhiAllInputs(
+ HLoopInformation* loop,
+ HInstruction* entry_phi,
+ HInstruction* phi) {
+ // Match all phi inputs.
+ InductionInfo* match = SolvePhi(phi, /* input_index */ 0);
+ if (match != nullptr) {
+ return match;
}
- // Solve within a cycle over another entry-phi: add invariants into a periodic.
- if (IsEntryPhi(loop, instruction)) {
- InductionInfo* a = LookupInfo(loop, instruction->InputAt(0));
+ // Otherwise, try to solve for a periodic seeded from phi onward.
+ // Only tight multi-statement cycles are considered in order to
+ // simplify rotating the periodic during the final classification.
+ if (phi->IsLoopHeaderPhi() && phi->InputCount() == 2) {
+ InductionInfo* a = LookupInfo(loop, phi->InputAt(0));
if (a != nullptr && a->induction_class == kInvariant) {
- if (instruction->InputAt(1) == phi) {
- InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
+ if (phi->InputAt(1) == entry_phi) {
+ InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
return CreateInduction(kPeriodic, a, initial);
}
- auto it = cycle_.find(instruction->InputAt(1));
- if (it != cycle_.end()) {
- InductionInfo* b = it->second;
- if (b->induction_class == kPeriodic) {
- return CreateInduction(kPeriodic, a, b);
- }
+ InductionInfo* b = SolvePhi(phi, /* input_index */ 1);
+ if (b != nullptr && b->induction_class == kPeriodic) {
+ return CreateInduction(kPeriodic, a, b);
}
}
}
-
return nullptr;
}
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopInformation* loop,
- HInstruction* phi,
+ HInstruction* entry_phi,
HInstruction* instruction,
HInstruction* x,
HInstruction* y,
@@ -471,7 +473,7 @@
// invariant value, seeded from phi, keeps adding to the stride of the induction.
InductionInfo* b = LookupInfo(loop, y);
if (b != nullptr && b->induction_class == kInvariant) {
- if (x == phi) {
+ if (x == entry_phi) {
return (op == kAdd) ? b : CreateInvariantOp(kNeg, nullptr, b);
}
auto it = cycle_.find(x);
@@ -487,14 +489,15 @@
if (op == kAdd) {
// Try the other way around for an addition if considered for first time.
if (is_first_call) {
- return SolveAddSub(loop, phi, instruction, y, x, op, false);
+ return SolveAddSub(loop, entry_phi, instruction, y, x, op, false);
}
} else if (op == kSub) {
- // Solve within a tight cycle for a periodic idiom k = c - k;
- if (y == phi && instruction == phi->InputAt(1)) {
+ // Solve within a tight cycle that is formed by exactly two instructions,
+ // one phi and one update, for a periodic idiom of the form k = c - k;
+ if (y == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) {
InductionInfo* a = LookupInfo(loop, x);
if (a != nullptr && a->induction_class == kInvariant) {
- InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
+ InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
return CreateInduction(kPeriodic, CreateInvariantOp(kSub, a, initial), initial);
}
}
@@ -539,32 +542,47 @@
Primitive::Type type,
IfCondition cmp) {
if (a->induction_class == kInvariant && b->induction_class == kLinear) {
- // Swap conditions (e.g. U > i is same as i < U).
+ // Swap condition if induction is at right-hand-side (e.g. U > i is same as i < U).
switch (cmp) {
case kCondLT: VisitCondition(loop, b, a, type, kCondGT); break;
case kCondLE: VisitCondition(loop, b, a, type, kCondGE); break;
case kCondGT: VisitCondition(loop, b, a, type, kCondLT); break;
case kCondGE: VisitCondition(loop, b, a, type, kCondLE); break;
+ case kCondNE: VisitCondition(loop, b, a, type, kCondNE); break;
default: break;
}
} else if (a->induction_class == kLinear && b->induction_class == kInvariant) {
- // Normalize a linear loop control with a constant, nonzero stride:
- // stride > 0, either i < U or i <= U
- // stride < 0, either i > U or i >= U
+ // Analyze condition with induction at left-hand-side (e.g. i < U).
InductionInfo* stride = a->op_a;
InductionInfo* lo_val = a->op_b;
InductionInfo* hi_val = b;
- // Analyze the stride thoroughly, since its representation may be compound at this point.
- InductionVarRange::Value v1 = InductionVarRange::GetMin(stride, nullptr);
- InductionVarRange::Value v2 = InductionVarRange::GetMax(stride, nullptr);
- if (v1.a_constant == 0 && v2.a_constant == 0 && v1.b_constant == v2.b_constant) {
- const int32_t stride_value = v1.b_constant;
- if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) ||
- (stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) {
- bool is_strict = cmp == kCondLT || cmp == kCondGT;
- VisitTripCount(loop, lo_val, hi_val, stride, stride_value, type, is_strict);
+ // Analyze stride (may be compound).
+ InductionVarRange::Value v1 = InductionVarRange::GetVal(stride, nullptr, /* is_min */ true);
+ InductionVarRange::Value v2 = InductionVarRange::GetVal(stride, nullptr, /* is_min */ false);
+ if (v1.a_constant != 0 || v2.a_constant != 0 || v1.b_constant != v2.b_constant) {
+ return;
+ }
+ // Rewrite safe condition i != U with unit stride into i < U or i > U
+ // (unit stride guarantees that the end condition is always reached).
+ const int32_t stride_value = v1.b_constant;
+ int64_t lo_value = 0;
+ int64_t hi_value = 0;
+ if (cmp == kCondNE && IsIntAndGet(lo_val, &lo_value) && IsIntAndGet(hi_val, &hi_value)) {
+ if ((stride_value == +1 && lo_value < hi_value) ||
+ (stride_value == -1 && lo_value > hi_value)) {
+ cmp = stride_value > 0 ? kCondLT : kCondGT;
}
}
+ // Normalize a linear loop control with a nonzero stride:
+ // stride > 0, either i < U or i <= U
+ // stride < 0, either i > U or i >= U
+ //
+ // TODO: construct conditions for constant/symbolic safety of trip-count
+ //
+ if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) ||
+ (stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) {
+ VisitTripCount(loop, lo_val, hi_val, stride, stride_value, type, cmp);
+ }
}
}
@@ -574,7 +592,7 @@
InductionInfo* stride,
int32_t stride_value,
Primitive::Type type,
- bool is_strict) {
+ IfCondition cmp) {
// Any loop of the general form:
//
// for (i = L; i <= U; i += S) // S > 0
@@ -586,26 +604,27 @@
// for (n = 0; n < TC; n++) // where TC = (U + S - L) / S
// .. L + S * n ..
//
- // NOTE: The TC (trip-count) expression is only valid if the top-test path is taken at
- // least once. Otherwise TC is 0. Also, the expression assumes the loop does not
- // have any early-exits. Otherwise, TC is an upper bound.
+ // NOTE: The TC (trip-count) expression is only valid when safe. Otherwise TC is 0
+ // (or possibly infinite). Also, the expression assumes the loop does not have
+ // early-exits. Otherwise, TC is an upper bound.
//
- bool cancels = is_strict && std::abs(stride_value) == 1; // compensation cancels conversion?
+ bool cancels = (cmp == kCondLT || cmp == kCondGT) && std::abs(stride_value) == 1;
if (!cancels) {
// Convert exclusive integral inequality into inclusive integral inequality,
// viz. condition i < U is i <= U - 1 and condition i > U is i >= U + 1.
- if (is_strict) {
- const InductionOp op = stride_value > 0 ? kSub : kAdd;
- hi_val = CreateInvariantOp(op, hi_val, CreateConstant(1, type));
+ if (cmp == kCondLT) {
+ hi_val = CreateInvariantOp(kSub, hi_val, CreateConstant(1, type));
+ } else if (cmp == kCondGT) {
+ hi_val = CreateInvariantOp(kAdd, hi_val, CreateConstant(1, type));
}
// Compensate for stride.
hi_val = CreateInvariantOp(kAdd, hi_val, stride);
}
// Assign the trip-count expression to the loop control. Clients that use the information
- // should be aware that due to the top-test assumption, the expression is only valid in the
- // loop-body proper, and not yet in the loop-header. If the loop has any early exits, the
- // trip-count forms a conservative upper bound on the number of loop iterations.
+ // should be aware that the expression is only valid in the loop-body proper (when symbolically
+ // safe), and not yet in the loop-header (unless constant safe). If the loop has any early exits,
+ // the trip-count forms a conservative upper bound on the number of loop iterations.
InductionInfo* trip_count =
CreateInvariantOp(kDiv, CreateInvariantOp(kSub, hi_val, lo_val), stride);
AssignInfo(loop, loop->GetHeader()->GetLastInstruction(), trip_count);
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 8eccf92..190a0db 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -121,26 +121,27 @@
uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction);
void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction);
void ClassifyNonTrivial(HLoopInformation* loop);
+ InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
// Transfer operations.
- InductionInfo* TransferPhi(InductionInfo* a, InductionInfo* b);
+ InductionInfo* TransferPhi(HLoopInformation* loop, HInstruction* phi, size_t input_index);
InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type type);
InductionInfo* TransferNeg(InductionInfo* a);
// Solvers.
- InductionInfo* SolvePhi(HLoopInformation* loop,
- HInstruction* phi,
- HInstruction* instruction);
+ InductionInfo* SolvePhi(HInstruction* phi, size_t input_index);
+ InductionInfo* SolvePhiAllInputs(HLoopInformation* loop,
+ HInstruction* entry_phi,
+ HInstruction* phi);
InductionInfo* SolveAddSub(HLoopInformation* loop,
- HInstruction* phi,
+ HInstruction* entry_phi,
HInstruction* instruction,
HInstruction* x,
HInstruction* y,
InductionOp op,
bool is_first_call);
- InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
// Trip count information.
void VisitControl(HLoopInformation* loop);
@@ -155,7 +156,7 @@
InductionInfo* stride,
int32_t stride_value,
Primitive::Type type,
- bool is_strict);
+ IfCondition cmp);
// Assign and lookup.
void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index fca1ca5..e519e77 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -20,6 +20,7 @@
#include "builder.h"
#include "gtest/gtest.h"
#include "induction_var_analysis.h"
+#include "induction_var_range.h"
#include "nodes.h"
#include "optimizing_unit_test.h"
@@ -388,7 +389,7 @@
HInstruction* store = InsertArrayStore(induc_, 0);
InsertLocalStore(induc_, InsertLocalLoad(tmp_, 0), 0);
HInstruction *sub = InsertInstruction(
- new (&allocator_) HSub(Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
+ new (&allocator_) HSub(Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
InsertLocalStore(tmp_, sub, 0);
PerformInductionVarAnalysis();
@@ -412,16 +413,16 @@
new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
InsertLocalStore(tmp_, add, 0);
HInstruction *sub = InsertInstruction(
- new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+ new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
InsertLocalStore(tmp_, sub, 0);
HInstruction *mul = InsertInstruction(
- new (&allocator_) HMul(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+ new (&allocator_) HMul(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
InsertLocalStore(tmp_, mul, 0);
HInstruction *shl = InsertInstruction(
- new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
+ new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
InsertLocalStore(tmp_, shl, 0);
HInstruction *neg = InsertInstruction(
- new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
+ new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
InsertLocalStore(tmp_, neg, 0);
InsertLocalStore(
induc_,
@@ -471,7 +472,7 @@
BuildLoopNest(1);
HInstruction* store = InsertArrayStore(induc_, 0);
HInstruction *sub = InsertInstruction(
- new (&allocator_) HSub(Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 0)), 0);
+ new (&allocator_) HSub(Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 0)), 0);
InsertLocalStore(induc_, sub, 0);
PerformInductionVarAnalysis();
@@ -497,19 +498,19 @@
HSub(Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 0)), 0), 0);
// Derived expressions.
HInstruction *add = InsertInstruction(
- new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+ new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
InsertLocalStore(tmp_, add, 0);
HInstruction *sub = InsertInstruction(
- new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+ new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
InsertLocalStore(tmp_, sub, 0);
HInstruction *mul = InsertInstruction(
- new (&allocator_) HMul(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+ new (&allocator_) HMul(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
InsertLocalStore(tmp_, mul, 0);
HInstruction *shl = InsertInstruction(
- new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
+ new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
InsertLocalStore(tmp_, shl, 0);
HInstruction *neg = InsertInstruction(
- new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
+ new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
InsertLocalStore(tmp_, neg, 0);
PerformInductionVarAnalysis();
@@ -520,6 +521,34 @@
EXPECT_STREQ("periodic(( - (1)), (0))", GetInductionInfo(neg, 0).c_str());
}
+TEST_F(InductionVarAnalysisTest, FindRange) {
+ // Setup:
+ // for (int i = 0; i < 100; i++) {
+ // k = i << 1;
+ // k = k + 1;
+ // a[k] = 0;
+ // }
+ BuildLoopNest(1);
+ HInstruction *shl = InsertInstruction(
+ new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(basic_[0], 0), constant1_), 0);
+ InsertLocalStore(induc_, shl, 0);
+ HInstruction *add = InsertInstruction(
+ new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
+ InsertLocalStore(induc_, add, 0);
+ HInstruction* store = InsertArrayStore(induc_, 0);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("((2) * i + (1))", GetInductionInfo(store->InputAt(1), 0).c_str());
+
+ InductionVarRange range(iva_);
+ InductionVarRange::Value v_min = range.GetMinInduction(store, store->InputAt(1));
+ InductionVarRange::Value v_max = range.GetMaxInduction(store, store->InputAt(1));
+ EXPECT_EQ(0, v_min.a_constant);
+ EXPECT_EQ(1, v_min.b_constant);
+ EXPECT_EQ(0, v_max.a_constant);
+ EXPECT_EQ(199, v_max.b_constant);
+}
+
TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) {
// Setup:
// k = 0;
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 486e904..119a80b 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -14,94 +14,95 @@
* limitations under the License.
*/
-#include <limits.h>
-
#include "induction_var_range.h"
+#include <limits>
+
namespace art {
-static bool IsValidConstant32(int32_t c) {
- return INT_MIN < c && c < INT_MAX;
+/** Returns true if 64-bit constant fits in 32-bit constant. */
+static bool CanLongValueFitIntoInt(int64_t c) {
+ return std::numeric_limits<int32_t>::min() <= c && c <= std::numeric_limits<int32_t>::max();
}
-static bool IsValidConstant64(int64_t c) {
- return INT_MIN < c && c < INT_MAX;
-}
-
-/** Returns true if 32-bit addition can be done safely (and is not an unknown range). */
+/** Returns true if 32-bit addition can be done safely. */
static bool IsSafeAdd(int32_t c1, int32_t c2) {
- if (IsValidConstant32(c1) && IsValidConstant32(c2)) {
- return IsValidConstant64(static_cast<int64_t>(c1) + static_cast<int64_t>(c2));
- }
- return false;
+ return CanLongValueFitIntoInt(static_cast<int64_t>(c1) + static_cast<int64_t>(c2));
}
-/** Returns true if 32-bit subtraction can be done safely (and is not an unknown range). */
+/** Returns true if 32-bit subtraction can be done safely. */
static bool IsSafeSub(int32_t c1, int32_t c2) {
- if (IsValidConstant32(c1) && IsValidConstant32(c2)) {
- return IsValidConstant64(static_cast<int64_t>(c1) - static_cast<int64_t>(c2));
- }
- return false;
+ return CanLongValueFitIntoInt(static_cast<int64_t>(c1) - static_cast<int64_t>(c2));
}
-/** Returns true if 32-bit multiplication can be done safely (and is not an unknown range). */
+/** Returns true if 32-bit multiplication can be done safely. */
static bool IsSafeMul(int32_t c1, int32_t c2) {
- if (IsValidConstant32(c1) && IsValidConstant32(c2)) {
- return IsValidConstant64(static_cast<int64_t>(c1) * static_cast<int64_t>(c2));
- }
- return false;
+ return CanLongValueFitIntoInt(static_cast<int64_t>(c1) * static_cast<int64_t>(c2));
}
-/** Returns true if 32-bit division can be done safely (and is not an unknown range). */
+/** Returns true if 32-bit division can be done safely. */
static bool IsSafeDiv(int32_t c1, int32_t c2) {
- if (IsValidConstant32(c1) && IsValidConstant32(c2) && c2 != 0) {
- return IsValidConstant64(static_cast<int64_t>(c1) / static_cast<int64_t>(c2));
- }
- return false;
+ return c2 != 0 && CanLongValueFitIntoInt(static_cast<int64_t>(c1) / static_cast<int64_t>(c2));
}
-/** Returns true for 32/64-bit integral constant within known range. */
+/** Returns true for 32/64-bit integral constant. */
static bool IsIntAndGet(HInstruction* instruction, int32_t* value) {
if (instruction->IsIntConstant()) {
- const int32_t c = instruction->AsIntConstant()->GetValue();
- if (IsValidConstant32(c)) {
- *value = c;
- return true;
- }
+ *value = instruction->AsIntConstant()->GetValue();
+ return true;
} else if (instruction->IsLongConstant()) {
const int64_t c = instruction->AsLongConstant()->GetValue();
- if (IsValidConstant64(c)) {
- *value = c;
+ if (CanLongValueFitIntoInt(c)) {
+ *value = static_cast<int32_t>(c);
return true;
}
}
return false;
}
+/**
+ * An upper bound a * (length / a) + b, where a > 0, can be conservatively rewritten as length + b
+ * because length >= 0 is true. This makes it more likely the bound is useful to clients.
+ */
+static InductionVarRange::Value SimplifyMax(InductionVarRange::Value v) {
+ int32_t value;
+ if (v.a_constant > 1 &&
+ v.instruction->IsDiv() &&
+ v.instruction->InputAt(0)->IsArrayLength() &&
+ IsIntAndGet(v.instruction->InputAt(1), &value) && v.a_constant == value) {
+ return InductionVarRange::Value(v.instruction->InputAt(0), 1, v.b_constant);
+ }
+ return v;
+}
+
//
// Public class methods.
//
InductionVarRange::InductionVarRange(HInductionVarAnalysis* induction_analysis)
: induction_analysis_(induction_analysis) {
+ DCHECK(induction_analysis != nullptr);
}
InductionVarRange::Value InductionVarRange::GetMinInduction(HInstruction* context,
HInstruction* instruction) {
HLoopInformation* loop = context->GetBlock()->GetLoopInformation();
- if (loop != nullptr && induction_analysis_ != nullptr) {
- return GetMin(induction_analysis_->LookupInfo(loop, instruction), GetTripCount(loop, context));
+ if (loop != nullptr) {
+ return GetVal(induction_analysis_->LookupInfo(loop, instruction),
+ GetTripCount(loop, context), /* is_min */ true);
}
- return Value(INT_MIN);
+ return Value();
}
InductionVarRange::Value InductionVarRange::GetMaxInduction(HInstruction* context,
HInstruction* instruction) {
HLoopInformation* loop = context->GetBlock()->GetLoopInformation();
- if (loop != nullptr && induction_analysis_ != nullptr) {
- return GetMax(induction_analysis_->LookupInfo(loop, instruction), GetTripCount(loop, context));
+ if (loop != nullptr) {
+ return SimplifyMax(
+ GetVal(induction_analysis_->LookupInfo(loop, instruction),
+ GetTripCount(loop, context), /* is_min */ false));
}
- return Value(INT_MAX);
+ return Value();
}
//
@@ -113,6 +114,9 @@
// The trip-count expression is only valid when the top-test is taken at least once,
// that means, when the analyzed context appears outside the loop header itself.
// Early-exit loops are okay, since in those cases, the trip-count is conservative.
+ //
+ // TODO: deal with runtime safety issues on TCs
+ //
if (context->GetBlock() != loop->GetHeader()) {
HInductionVarAnalysis::InductionInfo* trip =
induction_analysis_->LookupInfo(loop, loop->GetHeader()->GetLastInstruction());
@@ -127,7 +131,7 @@
InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction,
HInductionVarAnalysis::InductionInfo* trip,
- int32_t fail_value) {
+ bool is_min) {
// Detect constants and chase the fetch a bit deeper into the HIR tree, so that it becomes
// more likely range analysis will compare the same instructions as terminal nodes.
int32_t value;
@@ -135,14 +139,12 @@
return Value(value);
} else if (instruction->IsAdd()) {
if (IsIntAndGet(instruction->InputAt(0), &value)) {
- return AddValue(Value(value),
- GetFetch(instruction->InputAt(1), trip, fail_value), fail_value);
+ return AddValue(Value(value), GetFetch(instruction->InputAt(1), trip, is_min));
} else if (IsIntAndGet(instruction->InputAt(1), &value)) {
- return AddValue(GetFetch(instruction->InputAt(0), trip, fail_value),
- Value(value), fail_value);
+ return AddValue(GetFetch(instruction->InputAt(0), trip, is_min), Value(value));
}
- } else if (fail_value < 0) {
- // Special case: within the loop-body, minimum of trip-count is 1.
+ } else if (is_min) {
+ // Special case for finding minimum: minimum of trip-count is 1.
if (trip != nullptr && instruction == trip->op_b->fetch) {
return Value(1);
}
@@ -150,142 +152,111 @@
return Value(instruction, 1, 0);
}
-InductionVarRange::Value InductionVarRange::GetMin(HInductionVarAnalysis::InductionInfo* info,
- HInductionVarAnalysis::InductionInfo* trip) {
+InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool is_min) {
if (info != nullptr) {
switch (info->induction_class) {
case HInductionVarAnalysis::kInvariant:
// Invariants.
switch (info->operation) {
- case HInductionVarAnalysis::kNop: // normalized: 0
+ case HInductionVarAnalysis::kNop: // normalized: 0 or TC-1
DCHECK_EQ(info->op_a, info->op_b);
- return Value(0);
+ return is_min ? Value(0)
+ : SubValue(GetVal(info->op_b, trip, is_min), Value(1));
case HInductionVarAnalysis::kAdd:
- return AddValue(GetMin(info->op_a, trip), GetMin(info->op_b, trip), INT_MIN);
- case HInductionVarAnalysis::kSub: // second max!
- return SubValue(GetMin(info->op_a, trip), GetMax(info->op_b, trip), INT_MIN);
- case HInductionVarAnalysis::kNeg: // second max!
- return SubValue(Value(0), GetMax(info->op_b, trip), INT_MIN);
+ return AddValue(GetVal(info->op_a, trip, is_min),
+ GetVal(info->op_b, trip, is_min));
+ case HInductionVarAnalysis::kSub: // second reversed!
+ return SubValue(GetVal(info->op_a, trip, is_min),
+ GetVal(info->op_b, trip, !is_min));
+ case HInductionVarAnalysis::kNeg: // second reversed!
+ return SubValue(Value(0),
+ GetVal(info->op_b, trip, !is_min));
case HInductionVarAnalysis::kMul:
- return GetMul(info->op_a, info->op_b, trip, INT_MIN);
+ return GetMul(info->op_a, info->op_b, trip, is_min);
case HInductionVarAnalysis::kDiv:
- return GetDiv(info->op_a, info->op_b, trip, INT_MIN);
+ return GetDiv(info->op_a, info->op_b, trip, is_min);
case HInductionVarAnalysis::kFetch:
- return GetFetch(info->fetch, trip, INT_MIN);
+ return GetFetch(info->fetch, trip, is_min);
}
break;
case HInductionVarAnalysis::kLinear:
- // Minimum over linear induction a * i + b, for normalized 0 <= i < TC.
- return AddValue(GetMul(info->op_a, trip, trip, INT_MIN),
- GetMin(info->op_b, trip), INT_MIN);
+ // Linear induction a * i + b, for normalized 0 <= i < TC.
+ return AddValue(GetMul(info->op_a, trip, trip, is_min),
+ GetVal(info->op_b, trip, is_min));
case HInductionVarAnalysis::kWrapAround:
case HInductionVarAnalysis::kPeriodic:
- // Minimum over all values in the wrap-around/periodic.
- return MinValue(GetMin(info->op_a, trip), GetMin(info->op_b, trip));
+ // Merge values in the wrap-around/periodic.
+ return MergeVal(GetVal(info->op_a, trip, is_min),
+ GetVal(info->op_b, trip, is_min), is_min);
}
}
- return Value(INT_MIN);
-}
-
-InductionVarRange::Value InductionVarRange::GetMax(HInductionVarAnalysis::InductionInfo* info,
- HInductionVarAnalysis::InductionInfo* trip) {
- if (info != nullptr) {
- switch (info->induction_class) {
- case HInductionVarAnalysis::kInvariant:
- // Invariants.
- switch (info->operation) {
- case HInductionVarAnalysis::kNop: // normalized: TC - 1
- DCHECK_EQ(info->op_a, info->op_b);
- return SubValue(GetMax(info->op_b, trip), Value(1), INT_MAX);
- case HInductionVarAnalysis::kAdd:
- return AddValue(GetMax(info->op_a, trip), GetMax(info->op_b, trip), INT_MAX);
- case HInductionVarAnalysis::kSub: // second min!
- return SubValue(GetMax(info->op_a, trip), GetMin(info->op_b, trip), INT_MAX);
- case HInductionVarAnalysis::kNeg: // second min!
- return SubValue(Value(0), GetMin(info->op_b, trip), INT_MAX);
- case HInductionVarAnalysis::kMul:
- return GetMul(info->op_a, info->op_b, trip, INT_MAX);
- case HInductionVarAnalysis::kDiv:
- return GetDiv(info->op_a, info->op_b, trip, INT_MAX);
- case HInductionVarAnalysis::kFetch:
- return GetFetch(info->fetch, trip, INT_MAX);
- }
- break;
- case HInductionVarAnalysis::kLinear:
- // Maximum over linear induction a * i + b, for normalized 0 <= i < TC.
- return AddValue(GetMul(info->op_a, trip, trip, INT_MAX),
- GetMax(info->op_b, trip), INT_MAX);
- case HInductionVarAnalysis::kWrapAround:
- case HInductionVarAnalysis::kPeriodic:
- // Maximum over all values in the wrap-around/periodic.
- return MaxValue(GetMax(info->op_a, trip), GetMax(info->op_b, trip));
- }
- }
- return Value(INT_MAX);
+ return Value();
}
InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
- int32_t fail_value) {
- Value v1_min = GetMin(info1, trip);
- Value v1_max = GetMax(info1, trip);
- Value v2_min = GetMin(info2, trip);
- Value v2_max = GetMax(info2, trip);
- if (v1_min.a_constant == 0 && v1_min.b_constant >= 0) {
+ bool is_min) {
+ Value v1_min = GetVal(info1, trip, /* is_min */ true);
+ Value v1_max = GetVal(info1, trip, /* is_min */ false);
+ Value v2_min = GetVal(info2, trip, /* is_min */ true);
+ Value v2_max = GetVal(info2, trip, /* is_min */ false);
+ if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant >= 0) {
// Positive range vs. positive or negative range.
- if (v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
- return (fail_value < 0) ? MulValue(v1_min, v2_min, fail_value)
- : MulValue(v1_max, v2_max, fail_value);
- } else if (v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
- return (fail_value < 0) ? MulValue(v1_max, v2_min, fail_value)
- : MulValue(v1_min, v2_max, fail_value);
+ if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
+ return is_min ? MulValue(v1_min, v2_min)
+ : MulValue(v1_max, v2_max);
+ } else if (v2_max.is_known && v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
+ return is_min ? MulValue(v1_max, v2_min)
+ : MulValue(v1_min, v2_max);
}
- } else if (v1_min.a_constant == 0 && v1_min.b_constant <= 0) {
+ } else if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant <= 0) {
// Negative range vs. positive or negative range.
- if (v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
- return (fail_value < 0) ? MulValue(v1_min, v2_max, fail_value)
- : MulValue(v1_max, v2_min, fail_value);
- } else if (v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
- return (fail_value < 0) ? MulValue(v1_max, v2_max, fail_value)
- : MulValue(v1_min, v2_min, fail_value);
+ if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
+ return is_min ? MulValue(v1_min, v2_max)
+ : MulValue(v1_max, v2_min);
+ } else if (v2_max.is_known && v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
+ return is_min ? MulValue(v1_max, v2_max)
+ : MulValue(v1_min, v2_min);
}
}
- return Value(fail_value);
+ return Value();
}
InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
- int32_t fail_value) {
- Value v1_min = GetMin(info1, trip);
- Value v1_max = GetMax(info1, trip);
- Value v2_min = GetMin(info2, trip);
- Value v2_max = GetMax(info2, trip);
- if (v1_min.a_constant == 0 && v1_min.b_constant >= 0) {
+ bool is_min) {
+ Value v1_min = GetVal(info1, trip, /* is_min */ true);
+ Value v1_max = GetVal(info1, trip, /* is_min */ false);
+ Value v2_min = GetVal(info2, trip, /* is_min */ true);
+ Value v2_max = GetVal(info2, trip, /* is_min */ false);
+ if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant >= 0) {
// Positive range vs. positive or negative range.
- if (v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
- return (fail_value < 0) ? DivValue(v1_min, v2_max, fail_value)
- : DivValue(v1_max, v2_min, fail_value);
- } else if (v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
- return (fail_value < 0) ? DivValue(v1_max, v2_max, fail_value)
- : DivValue(v1_min, v2_min, fail_value);
+ if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
+ return is_min ? DivValue(v1_min, v2_max)
+ : DivValue(v1_max, v2_min);
+ } else if (v2_max.is_known && v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
+ return is_min ? DivValue(v1_max, v2_max)
+ : DivValue(v1_min, v2_min);
}
- } else if (v1_min.a_constant == 0 && v1_min.b_constant <= 0) {
+ } else if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant <= 0) {
// Negative range vs. positive or negative range.
- if (v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
- return (fail_value < 0) ? DivValue(v1_min, v2_min, fail_value)
- : DivValue(v1_max, v2_max, fail_value);
- } else if (v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
- return (fail_value < 0) ? DivValue(v1_max, v2_min, fail_value)
- : DivValue(v1_min, v2_max, fail_value);
+ if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
+ return is_min ? DivValue(v1_min, v2_min)
+ : DivValue(v1_max, v2_max);
+ } else if (v2_max.is_known && v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
+ return is_min ? DivValue(v1_max, v2_min)
+ : DivValue(v1_min, v2_max);
}
}
- return Value(fail_value);
+ return Value();
}
-InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2, int32_t fail_value) {
- if (IsSafeAdd(v1.b_constant, v2.b_constant)) {
+InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) {
+ if (v1.is_known && v2.is_known && IsSafeAdd(v1.b_constant, v2.b_constant)) {
const int32_t b = v1.b_constant + v2.b_constant;
if (v1.a_constant == 0) {
return Value(v2.instruction, v2.a_constant, b);
@@ -295,11 +266,11 @@
return Value(v1.instruction, v1.a_constant + v2.a_constant, b);
}
}
- return Value(fail_value);
+ return Value();
}
-InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2, int32_t fail_value) {
- if (IsSafeSub(v1.b_constant, v2.b_constant)) {
+InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2) {
+ if (v1.is_known && v2.is_known && IsSafeSub(v1.b_constant, v2.b_constant)) {
const int32_t b = v1.b_constant - v2.b_constant;
if (v1.a_constant == 0 && IsSafeSub(0, v2.a_constant)) {
return Value(v2.instruction, -v2.a_constant, b);
@@ -309,43 +280,42 @@
return Value(v1.instruction, v1.a_constant - v2.a_constant, b);
}
}
- return Value(fail_value);
+ return Value();
}
-InductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2, int32_t fail_value) {
- if (v1.a_constant == 0) {
- if (IsSafeMul(v1.b_constant, v2.a_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) {
- return Value(v2.instruction, v1.b_constant * v2.a_constant, v1.b_constant * v2.b_constant);
- }
- } else if (v2.a_constant == 0) {
- if (IsSafeMul(v1.a_constant, v2.b_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) {
- return Value(v1.instruction, v1.a_constant * v2.b_constant, v1.b_constant * v2.b_constant);
+InductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2) {
+ if (v1.is_known && v2.is_known) {
+ if (v1.a_constant == 0) {
+ if (IsSafeMul(v1.b_constant, v2.a_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) {
+ return Value(v2.instruction, v1.b_constant * v2.a_constant, v1.b_constant * v2.b_constant);
+ }
+ } else if (v2.a_constant == 0) {
+ if (IsSafeMul(v1.a_constant, v2.b_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) {
+ return Value(v1.instruction, v1.a_constant * v2.b_constant, v1.b_constant * v2.b_constant);
+ }
}
}
- return Value(fail_value);
+ return Value();
}
-InductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2, int32_t fail_value) {
- if (v1.a_constant == 0 && v2.a_constant == 0) {
+InductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2) {
+ if (v1.is_known && v2.is_known && v1.a_constant == 0 && v2.a_constant == 0) {
if (IsSafeDiv(v1.b_constant, v2.b_constant)) {
return Value(v1.b_constant / v2.b_constant);
}
}
- return Value(fail_value);
+ return Value();
}
-InductionVarRange::Value InductionVarRange::MinValue(Value v1, Value v2) {
- if (v1.instruction == v2.instruction && v1.a_constant == v2.a_constant) {
- return Value(v1.instruction, v1.a_constant, std::min(v1.b_constant, v2.b_constant));
+InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is_min) {
+ if (v1.is_known && v2.is_known) {
+ if (v1.instruction == v2.instruction && v1.a_constant == v2.a_constant) {
+ return Value(v1.instruction, v1.a_constant,
+ is_min ? std::min(v1.b_constant, v2.b_constant)
+ : std::max(v1.b_constant, v2.b_constant));
+ }
}
- return Value(INT_MIN);
-}
-
-InductionVarRange::Value InductionVarRange::MaxValue(Value v1, Value v2) {
- if (v1.instruction == v2.instruction && v1.a_constant == v2.a_constant) {
- return Value(v1.instruction, v1.a_constant, std::max(v1.b_constant, v2.b_constant));
- }
- return Value(INT_MAX);
+ return Value();
}
} // namespace art
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index e002e5f..8280c8b 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -22,30 +22,36 @@
namespace art {
/**
- * This class implements induction variable based range analysis on expressions within loops.
- * It takes the results of induction variable analysis in the constructor and provides a public
- * API to obtain a conservative lower and upper bound value on each instruction in the HIR.
+ * This class implements range analysis on expressions within loops. It takes the results
+ * of induction variable analysis in the constructor and provides a public API to obtain
+ * a conservative lower and upper bound value on each instruction in the HIR.
*
- * For example, given a linear induction 2 * i + x where 0 <= i <= 10, range analysis yields lower
- * bound value x and upper bound value x + 20 for the expression, thus, the range [x, x + 20].
+ * The range analysis is done with a combination of symbolic and partial integral evaluation
+ * of expressions. The analysis avoids complications with wrap-around arithmetic on the integral
+ * parts but all clients should be aware that wrap-around may occur on any of the symbolic parts.
+ * For example, given a known range for [0,100] for i, the evaluation yields range [-100,100]
+ * for expression -2*i+100, which is exact, and range [x,x+100] for expression i+x, which may
+ * wrap-around anywhere in the range depending on the actual value of x.
*/
class InductionVarRange {
public:
/*
* A value that can be represented as "a * instruction + b" for 32-bit constants, where
- * Value(INT_MIN) and Value(INT_MAX) denote an unknown lower and upper bound, respectively.
- * Although range analysis could yield more complex values, the format is sufficiently powerful
- * to represent useful cases and feeds directly into optimizations like bounds check elimination.
+ * Value() denotes an unknown lower and upper bound. Although range analysis could yield
+ * more complex values, the format is sufficiently powerful to represent useful cases
+ * and feeds directly into optimizations like bounds check elimination.
*/
struct Value {
+ Value() : instruction(nullptr), a_constant(0), b_constant(0), is_known(false) {}
Value(HInstruction* i, int32_t a, int32_t b)
- : instruction(a != 0 ? i : nullptr),
- a_constant(a),
- b_constant(b) {}
+ : instruction(a != 0 ? i : nullptr), a_constant(a), b_constant(b), is_known(true) {}
explicit Value(int32_t b) : Value(nullptr, 0, b) {}
+ // Representation as: a_constant x instruction + b_constant.
HInstruction* instruction;
int32_t a_constant;
int32_t b_constant;
+ // If true, represented by prior fields. Otherwise unknown value.
+ bool is_known;
};
explicit InductionVarRange(HInductionVarAnalysis* induction);
@@ -67,32 +73,29 @@
// Private helper methods.
//
- HInductionVarAnalysis::InductionInfo* GetTripCount(HLoopInformation* loop,
- HInstruction* context);
+ HInductionVarAnalysis::InductionInfo* GetTripCount(HLoopInformation* loop, HInstruction* context);
static Value GetFetch(HInstruction* instruction,
HInductionVarAnalysis::InductionInfo* trip,
- int32_t fail_value);
+ bool is_min);
- static Value GetMin(HInductionVarAnalysis::InductionInfo* info,
- HInductionVarAnalysis::InductionInfo* trip);
- static Value GetMax(HInductionVarAnalysis::InductionInfo* info,
- HInductionVarAnalysis::InductionInfo* trip);
+ static Value GetVal(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool is_min);
static Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
- int32_t fail_value);
+ bool is_min);
static Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
- int32_t fail_value);
+ bool is_min);
- static Value AddValue(Value v1, Value v2, int32_t fail_value);
- static Value SubValue(Value v1, Value v2, int32_t fail_value);
- static Value MulValue(Value v1, Value v2, int32_t fail_value);
- static Value DivValue(Value v1, Value v2, int32_t fail_value);
- static Value MinValue(Value v1, Value v2);
- static Value MaxValue(Value v1, Value v2);
+ static Value AddValue(Value v1, Value v2);
+ static Value SubValue(Value v1, Value v2);
+ static Value MulValue(Value v1, Value v2);
+ static Value DivValue(Value v1, Value v2);
+ static Value MergeVal(Value v1, Value v2, bool is_min);
/** Results of prior induction variable analysis. */
HInductionVarAnalysis *induction_analysis_;
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index d3c3518..5d9a075 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -14,8 +14,6 @@
* limitations under the License.
*/
-#include <limits.h>
-
#include "base/arena_allocator.h"
#include "builder.h"
#include "gtest/gtest.h"
@@ -45,6 +43,7 @@
EXPECT_EQ(v1.instruction, v2.instruction);
EXPECT_EQ(v1.a_constant, v2.a_constant);
EXPECT_EQ(v1.b_constant, v2.b_constant);
+ EXPECT_EQ(v1.is_known, v2.is_known);
}
/** Constructs bare minimum graph. */
@@ -113,30 +112,32 @@
Value GetMin(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* induc) {
- return InductionVarRange::GetMin(info, induc);
+ return InductionVarRange::GetVal(info, induc, /* is_min */ true);
}
Value GetMax(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* induc) {
- return InductionVarRange::GetMax(info, induc);
+ return InductionVarRange::GetVal(info, induc, /* is_min */ false);
}
Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
- HInductionVarAnalysis::InductionInfo* info2, int32_t fail_value) {
- return InductionVarRange::GetMul(info1, info2, nullptr, fail_value);
+ HInductionVarAnalysis::InductionInfo* info2,
+ bool is_min) {
+ return InductionVarRange::GetMul(info1, info2, nullptr, is_min);
}
Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
- HInductionVarAnalysis::InductionInfo* info2, int32_t fail_value) {
- return InductionVarRange::GetDiv(info1, info2, nullptr, fail_value);
+ HInductionVarAnalysis::InductionInfo* info2,
+ bool is_min) {
+ return InductionVarRange::GetDiv(info1, info2, nullptr, is_min);
}
- Value AddValue(Value v1, Value v2) { return InductionVarRange::AddValue(v1, v2, INT_MIN); }
- Value SubValue(Value v1, Value v2) { return InductionVarRange::SubValue(v1, v2, INT_MIN); }
- Value MulValue(Value v1, Value v2) { return InductionVarRange::MulValue(v1, v2, INT_MIN); }
- Value DivValue(Value v1, Value v2) { return InductionVarRange::DivValue(v1, v2, INT_MIN); }
- Value MinValue(Value v1, Value v2) { return InductionVarRange::MinValue(v1, v2); }
- Value MaxValue(Value v1, Value v2) { return InductionVarRange::MaxValue(v1, v2); }
+ Value AddValue(Value v1, Value v2) { return InductionVarRange::AddValue(v1, v2); }
+ Value SubValue(Value v1, Value v2) { return InductionVarRange::SubValue(v1, v2); }
+ Value MulValue(Value v1, Value v2) { return InductionVarRange::MulValue(v1, v2); }
+ Value DivValue(Value v1, Value v2) { return InductionVarRange::DivValue(v1, v2); }
+ Value MinValue(Value v1, Value v2) { return InductionVarRange::MergeVal(v1, v2, true); }
+ Value MaxValue(Value v1, Value v2) { return InductionVarRange::MergeVal(v1, v2, false); }
// General building fields.
ArenaPool pool_;
@@ -154,8 +155,8 @@
//
TEST_F(InductionVarRangeTest, GetMinMaxNull) {
- ExpectEqual(Value(INT_MIN), GetMin(nullptr, nullptr));
- ExpectEqual(Value(INT_MAX), GetMax(nullptr, nullptr));
+ ExpectEqual(Value(), GetMin(nullptr, nullptr));
+ ExpectEqual(Value(), GetMax(nullptr, nullptr));
}
TEST_F(InductionVarRangeTest, GetMinMaxAdd) {
@@ -251,91 +252,91 @@
}
TEST_F(InductionVarRangeTest, GetMulMin) {
- ExpectEqual(Value(6), GetMul(CreateRange(2, 10), CreateRange(3, 5), INT_MIN));
- ExpectEqual(Value(-50), GetMul(CreateRange(2, 10), CreateRange(-5, -3), INT_MIN));
- ExpectEqual(Value(-50), GetMul(CreateRange(-10, -2), CreateRange(3, 5), INT_MIN));
- ExpectEqual(Value(6), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), INT_MIN));
+ ExpectEqual(Value(6), GetMul(CreateRange(2, 10), CreateRange(3, 5), true));
+ ExpectEqual(Value(-50), GetMul(CreateRange(2, 10), CreateRange(-5, -3), true));
+ ExpectEqual(Value(-50), GetMul(CreateRange(-10, -2), CreateRange(3, 5), true));
+ ExpectEqual(Value(6), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), true));
}
TEST_F(InductionVarRangeTest, GetMulMax) {
- ExpectEqual(Value(50), GetMul(CreateRange(2, 10), CreateRange(3, 5), INT_MAX));
- ExpectEqual(Value(-6), GetMul(CreateRange(2, 10), CreateRange(-5, -3), INT_MAX));
- ExpectEqual(Value(-6), GetMul(CreateRange(-10, -2), CreateRange(3, 5), INT_MAX));
- ExpectEqual(Value(50), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), INT_MAX));
+ ExpectEqual(Value(50), GetMul(CreateRange(2, 10), CreateRange(3, 5), false));
+ ExpectEqual(Value(-6), GetMul(CreateRange(2, 10), CreateRange(-5, -3), false));
+ ExpectEqual(Value(-6), GetMul(CreateRange(-10, -2), CreateRange(3, 5), false));
+ ExpectEqual(Value(50), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), false));
}
TEST_F(InductionVarRangeTest, GetDivMin) {
- ExpectEqual(Value(10), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), INT_MIN));
- ExpectEqual(Value(-500), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), INT_MIN));
- ExpectEqual(Value(-500), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), INT_MIN));
- ExpectEqual(Value(10), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), INT_MIN));
+ ExpectEqual(Value(10), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), true));
+ ExpectEqual(Value(-500), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), true));
+ ExpectEqual(Value(-500), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), true));
+ ExpectEqual(Value(10), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), true));
}
TEST_F(InductionVarRangeTest, GetDivMax) {
- ExpectEqual(Value(500), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), INT_MAX));
- ExpectEqual(Value(-10), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), INT_MAX));
- ExpectEqual(Value(-10), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), INT_MAX));
- ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), INT_MAX));
+ ExpectEqual(Value(500), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), false));
+ ExpectEqual(Value(-10), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), false));
+ ExpectEqual(Value(-10), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), false));
+ ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), false));
}
TEST_F(InductionVarRangeTest, AddValue) {
ExpectEqual(Value(110), AddValue(Value(10), Value(100)));
ExpectEqual(Value(-5), AddValue(Value(&x_, 1, -4), Value(&x_, -1, -1)));
ExpectEqual(Value(&x_, 3, -5), AddValue(Value(&x_, 2, -4), Value(&x_, 1, -1)));
- ExpectEqual(Value(INT_MIN), AddValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
+ ExpectEqual(Value(), AddValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
ExpectEqual(Value(&x_, 1, 23), AddValue(Value(&x_, 1, 20), Value(3)));
ExpectEqual(Value(&y_, 1, 5), AddValue(Value(55), Value(&y_, 1, -50)));
- // Unsafe.
- ExpectEqual(Value(INT_MIN), AddValue(Value(INT_MAX - 5), Value(6)));
+ const int32_t max_value = std::numeric_limits<int32_t>::max();
+ ExpectEqual(Value(max_value), AddValue(Value(max_value - 5), Value(5)));
+ ExpectEqual(Value(), AddValue(Value(max_value - 5), Value(6))); // unsafe
}
TEST_F(InductionVarRangeTest, SubValue) {
ExpectEqual(Value(-90), SubValue(Value(10), Value(100)));
ExpectEqual(Value(-3), SubValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
ExpectEqual(Value(&x_, 2, -3), SubValue(Value(&x_, 3, -4), Value(&x_, 1, -1)));
- ExpectEqual(Value(INT_MIN), SubValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
+ ExpectEqual(Value(), SubValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
ExpectEqual(Value(&x_, 1, 17), SubValue(Value(&x_, 1, 20), Value(3)));
ExpectEqual(Value(&y_, -4, 105), SubValue(Value(55), Value(&y_, 4, -50)));
- // Unsafe.
- ExpectEqual(Value(INT_MIN), SubValue(Value(INT_MIN + 5), Value(6)));
+ const int32_t min_value = std::numeric_limits<int32_t>::min();
+ ExpectEqual(Value(min_value), SubValue(Value(min_value + 5), Value(5)));
+ ExpectEqual(Value(), SubValue(Value(min_value + 5), Value(6))); // unsafe
}
TEST_F(InductionVarRangeTest, MulValue) {
ExpectEqual(Value(1000), MulValue(Value(10), Value(100)));
- ExpectEqual(Value(INT_MIN), MulValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
- ExpectEqual(Value(INT_MIN), MulValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
+ ExpectEqual(Value(), MulValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
+ ExpectEqual(Value(), MulValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
ExpectEqual(Value(&x_, 9, 60), MulValue(Value(&x_, 3, 20), Value(3)));
ExpectEqual(Value(&y_, 55, -110), MulValue(Value(55), Value(&y_, 1, -2)));
- // Unsafe.
- ExpectEqual(Value(INT_MIN), MulValue(Value(90000), Value(-90000)));
+ ExpectEqual(Value(), MulValue(Value(90000), Value(-90000))); // unsafe
}
TEST_F(InductionVarRangeTest, DivValue) {
ExpectEqual(Value(25), DivValue(Value(100), Value(4)));
- ExpectEqual(Value(INT_MIN), DivValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
- ExpectEqual(Value(INT_MIN), DivValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
- ExpectEqual(Value(INT_MIN), DivValue(Value(&x_, 12, 24), Value(3)));
- ExpectEqual(Value(INT_MIN), DivValue(Value(55), Value(&y_, 1, -50)));
- // Unsafe.
- ExpectEqual(Value(INT_MIN), DivValue(Value(1), Value(0)));
+ ExpectEqual(Value(), DivValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
+ ExpectEqual(Value(), DivValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
+ ExpectEqual(Value(), DivValue(Value(&x_, 12, 24), Value(3)));
+ ExpectEqual(Value(), DivValue(Value(55), Value(&y_, 1, -50)));
+ ExpectEqual(Value(), DivValue(Value(1), Value(0))); // unsafe
}
TEST_F(InductionVarRangeTest, MinValue) {
ExpectEqual(Value(10), MinValue(Value(10), Value(100)));
ExpectEqual(Value(&x_, 1, -4), MinValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
ExpectEqual(Value(&x_, 4, -4), MinValue(Value(&x_, 4, -4), Value(&x_, 4, -1)));
- ExpectEqual(Value(INT_MIN), MinValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
- ExpectEqual(Value(INT_MIN), MinValue(Value(&x_, 1, 20), Value(3)));
- ExpectEqual(Value(INT_MIN), MinValue(Value(55), Value(&y_, 1, -50)));
+ ExpectEqual(Value(), MinValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
+ ExpectEqual(Value(), MinValue(Value(&x_, 1, 20), Value(3)));
+ ExpectEqual(Value(), MinValue(Value(55), Value(&y_, 1, -50)));
}
TEST_F(InductionVarRangeTest, MaxValue) {
ExpectEqual(Value(100), MaxValue(Value(10), Value(100)));
ExpectEqual(Value(&x_, 1, -1), MaxValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
ExpectEqual(Value(&x_, 4, -1), MaxValue(Value(&x_, 4, -4), Value(&x_, 4, -1)));
- ExpectEqual(Value(INT_MAX), MaxValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
- ExpectEqual(Value(INT_MAX), MaxValue(Value(&x_, 1, 20), Value(3)));
- ExpectEqual(Value(INT_MAX), MaxValue(Value(55), Value(&y_, 1, -50)));
+ ExpectEqual(Value(), MaxValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
+ ExpectEqual(Value(), MaxValue(Value(&x_, 1, 20), Value(3)));
+ ExpectEqual(Value(), MaxValue(Value(55), Value(&y_, 1, -50)));
}
} // namespace art
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index b2407c5..ef89932 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -20,6 +20,7 @@
#include "ssa_builder.h"
#include "base/bit_vector-inl.h"
#include "base/bit_utils.h"
+#include "base/stl_util.h"
#include "mirror/class-inl.h"
#include "utils/growable_array.h"
#include "scoped_thread_state_change.h"
@@ -32,8 +33,41 @@
}
void HGraph::FindBackEdges(ArenaBitVector* visited) {
+ // "visited" must be empty on entry, it's an output argument for all visited (i.e. live) blocks.
+ DCHECK_EQ(visited->GetHighestBitSet(), -1);
+
+ // Nodes that we're currently visiting, indexed by block id.
ArenaBitVector visiting(arena_, blocks_.size(), false);
- VisitBlockForBackEdges(entry_block_, visited, &visiting);
+ // Number of successors visited from a given node, indexed by block id.
+ ArenaVector<size_t> successors_visited(blocks_.size(), 0u, arena_->Adapter());
+ // Stack of nodes that we're currently visiting (same as marked in "visiting" above).
+ ArenaVector<HBasicBlock*> worklist(arena_->Adapter());
+ constexpr size_t kDefaultWorklistSize = 8;
+ worklist.reserve(kDefaultWorklistSize);
+ visited->SetBit(entry_block_->GetBlockId());
+ visiting.SetBit(entry_block_->GetBlockId());
+ worklist.push_back(entry_block_);
+
+ while (!worklist.empty()) {
+ HBasicBlock* current = worklist.back();
+ uint32_t current_id = current->GetBlockId();
+ if (successors_visited[current_id] == current->GetSuccessors().size()) {
+ visiting.ClearBit(current_id);
+ worklist.pop_back();
+ } else {
+ DCHECK_LT(successors_visited[current_id], current->GetSuccessors().size());
+ HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++];
+ uint32_t successor_id = successor->GetBlockId();
+ if (visiting.IsBitSet(successor_id)) {
+ DCHECK(ContainsElement(worklist, successor));
+ successor->AddBackEdge(current);
+ } else if (!visited->IsBitSet(successor_id)) {
+ visited->SetBit(successor_id);
+ visiting.SetBit(successor_id);
+ worklist.push_back(successor);
+ }
+ }
+ }
}
static void RemoveAsUser(HInstruction* instruction) {
@@ -79,24 +113,6 @@
}
}
-void HGraph::VisitBlockForBackEdges(HBasicBlock* block,
- ArenaBitVector* visited,
- ArenaBitVector* visiting) {
- int id = block->GetBlockId();
- if (visited->IsBitSet(id)) return;
-
- visited->SetBit(id);
- visiting->SetBit(id);
- for (HBasicBlock* successor : block->GetSuccessors()) {
- if (visiting->IsBitSet(successor->GetBlockId())) {
- successor->AddBackEdge(block);
- } else {
- VisitBlockForBackEdges(successor, visited, visiting);
- }
- }
- visiting->ClearBit(id);
-}
-
void HGraph::BuildDominatorTree() {
// (1) Simplify the CFG so that catch blocks have only exceptional incoming
// edges. This invariant simplifies building SSA form because Phis cannot
@@ -141,10 +157,43 @@
void HGraph::ComputeDominanceInformation() {
DCHECK(reverse_post_order_.empty());
reverse_post_order_.reserve(blocks_.size());
- ArenaVector<size_t> visits(blocks_.size(), 0u, arena_->Adapter());
reverse_post_order_.push_back(entry_block_);
- for (HBasicBlock* successor : entry_block_->GetSuccessors()) {
- VisitBlockForDominatorTree(successor, entry_block_, &visits);
+
+ // Number of visits of a given node, indexed by block id.
+ ArenaVector<size_t> visits(blocks_.size(), 0u, arena_->Adapter());
+ // Number of successors visited from a given node, indexed by block id.
+ ArenaVector<size_t> successors_visited(blocks_.size(), 0u, arena_->Adapter());
+ // Nodes for which we need to visit successors.
+ ArenaVector<HBasicBlock*> worklist(arena_->Adapter());
+ constexpr size_t kDefaultWorklistSize = 8;
+ worklist.reserve(kDefaultWorklistSize);
+ worklist.push_back(entry_block_);
+
+ while (!worklist.empty()) {
+ HBasicBlock* current = worklist.back();
+ uint32_t current_id = current->GetBlockId();
+ if (successors_visited[current_id] == current->GetSuccessors().size()) {
+ worklist.pop_back();
+ } else {
+ DCHECK_LT(successors_visited[current_id], current->GetSuccessors().size());
+ HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++];
+
+ if (successor->GetDominator() == nullptr) {
+ successor->SetDominator(current);
+ } else {
+ successor->SetDominator(FindCommonDominator(successor->GetDominator(), current));
+ }
+
+ // Once all the forward edges have been visited, we know the immediate
+ // dominator of the block. We can then start visiting its successors.
+ DCHECK_LT(successor->GetBlockId(), visits.size());
+ if (++visits[successor->GetBlockId()] ==
+ successor->GetPredecessors().size() - successor->NumberOfBackEdges()) {
+ successor->GetDominator()->AddDominatedBlock(successor);
+ reverse_post_order_.push_back(successor);
+ worklist.push_back(successor);
+ }
+ }
}
}
@@ -166,28 +215,6 @@
return nullptr;
}
-void HGraph::VisitBlockForDominatorTree(HBasicBlock* block,
- HBasicBlock* predecessor,
- ArenaVector<size_t>* visits) {
- if (block->GetDominator() == nullptr) {
- block->SetDominator(predecessor);
- } else {
- block->SetDominator(FindCommonDominator(block->GetDominator(), predecessor));
- }
-
- // Once all the forward edges have been visited, we know the immediate
- // dominator of the block. We can then start visiting its successors.
- DCHECK_LT(block->GetBlockId(), visits->size());
- if (++(*visits)[block->GetBlockId()] ==
- block->GetPredecessors().size() - block->NumberOfBackEdges()) {
- block->GetDominator()->AddDominatedBlock(block);
- reverse_post_order_.push_back(block);
- for (HBasicBlock* successor : block->GetSuccessors()) {
- VisitBlockForDominatorTree(successor, block, visits);
- }
- }
-}
-
void HGraph::TransformToSsa() {
DCHECK(!reverse_post_order_.empty());
SsaBuilder ssa_builder(this);
@@ -1143,6 +1170,23 @@
return new_block;
}
+HBasicBlock* HBasicBlock::CreateImmediateDominator() {
+ DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented";
+ DCHECK(!IsCatchBlock()) << "Support for updating try/catch information not implemented.";
+
+ HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), GetDexPc());
+
+ for (HBasicBlock* predecessor : GetPredecessors()) {
+ new_block->predecessors_.push_back(predecessor);
+ predecessor->successors_[predecessor->GetSuccessorIndexOf(this)] = new_block;
+ }
+ predecessors_.clear();
+ AddPredecessor(new_block);
+
+ GetGraph()->AddBlock(new_block);
+ return new_block;
+}
+
HBasicBlock* HBasicBlock::SplitAfter(HInstruction* cursor) {
DCHECK(!cursor->IsControlFlow());
DCHECK_NE(instructions_.last_instruction_, cursor);
@@ -1188,6 +1232,15 @@
}
}
+bool HBasicBlock::HasThrowingInstructions() const {
+ for (HInstructionIterator it(GetInstructions()); !it.Done(); it.Advance()) {
+ if (it.Current()->CanThrow()) {
+ return true;
+ }
+ }
+ return false;
+}
+
static bool HasOnlyOneInstruction(const HBasicBlock& block) {
return block.GetPhis().IsEmpty()
&& !block.GetInstructions().IsEmpty()
@@ -1297,16 +1350,25 @@
// instructions.
for (HBasicBlock* predecessor : predecessors_) {
HInstruction* last_instruction = predecessor->GetLastInstruction();
- predecessor->RemoveInstruction(last_instruction);
predecessor->RemoveSuccessor(this);
- if (predecessor->GetSuccessors().size() == 1u) {
- DCHECK(last_instruction->IsIf());
+ uint32_t num_pred_successors = predecessor->GetSuccessors().size();
+ if (num_pred_successors == 1u) {
+ // If we have one successor after removing one, then we must have
+ // had an HIf or HPackedSwitch, as they have more than one successor.
+ // Replace those with a HGoto.
+ DCHECK(last_instruction->IsIf() || last_instruction->IsPackedSwitch());
+ predecessor->RemoveInstruction(last_instruction);
predecessor->AddInstruction(new (graph_->GetArena()) HGoto(last_instruction->GetDexPc()));
- } else {
+ } else if (num_pred_successors == 0u) {
// The predecessor has no remaining successors and therefore must be dead.
// We deliberately leave it without a control-flow instruction so that the
// SSAChecker fails unless it is not removed during the pass too.
- DCHECK_EQ(predecessor->GetSuccessors().size(), 0u);
+ predecessor->RemoveInstruction(last_instruction);
+ } else {
+ // There are multiple successors left. This must come from a HPackedSwitch
+ // and we are in the middle of removing the HPackedSwitch. Like above, leave
+ // this alone, and the SSAChecker will fail if it is not removed as well.
+ DCHECK(last_instruction->IsPackedSwitch());
}
}
predecessors_.clear();
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 8dd31be..6b0ccf8 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -370,13 +370,7 @@
void SetHasTryCatch(bool value) { has_try_catch_ = value; }
private:
- void VisitBlockForDominatorTree(HBasicBlock* block,
- HBasicBlock* predecessor,
- ArenaVector<size_t>* visits);
void FindBackEdges(ArenaBitVector* visited);
- void VisitBlockForBackEdges(HBasicBlock* block,
- ArenaBitVector* visited,
- ArenaBitVector* visiting);
void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const;
void RemoveDeadBlocks(const ArenaBitVector& visited);
@@ -825,11 +819,17 @@
return EndsWithTryBoundary() ? 1 : GetSuccessors().size();
}
+ // Create a new block between this block and its predecessors. The new block
+ // is added to the graph, all predecessor edges are relinked to it and an edge
+ // is created to `this`. Returns the new empty block. Reverse post order or
+ // loop and try/catch information are not updated.
+ HBasicBlock* CreateImmediateDominator();
+
// Split the block into two blocks just before `cursor`. Returns the newly
// created, latter block. Note that this method will add the block to the
// graph, create a Goto at the end of the former block and will create an edge
// between the blocks. It will not, however, update the reverse post order or
- // loop information.
+ // loop and try/catch information.
HBasicBlock* SplitBefore(HInstruction* cursor);
// Split the block into two blocks just after `cursor`. Returns the newly
@@ -940,6 +940,8 @@
// the appropriate try entry will be returned.
const HTryBoundary* ComputeTryEntryOfSuccessors() const;
+ bool HasThrowingInstructions() const;
+
// Returns whether this block dominates the blocked passed as parameter.
bool Dominates(HBasicBlock* block) const;
@@ -949,7 +951,6 @@
void SetLifetimeStart(size_t start) { lifetime_start_ = start; }
void SetLifetimeEnd(size_t end) { lifetime_end_ = end; }
-
bool EndsWithControlFlowInstruction() const;
bool EndsWithIf() const;
bool EndsWithTryBoundary() const;
@@ -1056,6 +1057,7 @@
M(NullConstant, Instruction) \
M(NullCheck, Instruction) \
M(Or, BinaryOperation) \
+ M(PackedSwitch, Instruction) \
M(ParallelMove, Instruction) \
M(ParameterValue, Instruction) \
M(Phi, Instruction) \
@@ -2402,6 +2404,38 @@
DISALLOW_COPY_AND_ASSIGN(HCurrentMethod);
};
+// PackedSwitch (jump table). A block ending with a PackedSwitch instruction will
+// have one successor for each entry in the switch table, and the final successor
+// will be the block containing the next Dex opcode.
+class HPackedSwitch : public HTemplateInstruction<1> {
+ public:
+ HPackedSwitch(int32_t start_value, uint32_t num_entries, HInstruction* input,
+ uint32_t dex_pc = kNoDexPc)
+ : HTemplateInstruction(SideEffects::None(), dex_pc),
+ start_value_(start_value),
+ num_entries_(num_entries) {
+ SetRawInputAt(0, input);
+ }
+
+ bool IsControlFlow() const OVERRIDE { return true; }
+
+ int32_t GetStartValue() const { return start_value_; }
+
+ uint32_t GetNumEntries() const { return num_entries_; }
+
+ HBasicBlock* GetDefaultBlock() const {
+ // Last entry is the default block.
+ return GetBlock()->GetSuccessor(num_entries_);
+ }
+ DECLARE_INSTRUCTION(PackedSwitch);
+
+ private:
+ int32_t start_value_;
+ uint32_t num_entries_;
+
+ DISALLOW_COPY_AND_ASSIGN(HPackedSwitch);
+};
+
class HUnaryOperation : public HExpression<1> {
public:
HUnaryOperation(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc = kNoDexPc)
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index e6b2a8b..c43e58f 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -1527,10 +1527,10 @@
DCHECK_EQ(block->NumberOfNormalSuccessors(), 1u);
HInstruction* last = block->GetLastInstruction();
// We insert moves at exit for phi predecessors and connecting blocks.
- // A block ending with an if cannot branch to a block with phis because
- // we do not allow critical edges. It can also not connect
+ // A block ending with an if or a packed switch cannot branch to a block
+ // with phis because we do not allow critical edges. It can also not connect
// a split interval between two blocks: the move has to happen in the successor.
- DCHECK(!last->IsIf());
+ DCHECK(!last->IsIf() && !last->IsPackedSwitch());
HInstruction* previous = last->GetPrevious();
HParallelMove* move;
// This is a parallel move for connecting blocks. We need to differentiate
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 0ef86d8..ad8c682 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -191,12 +191,6 @@
ProcessWorklist();
}
-static bool IsPhiEquivalentOf(HInstruction* instruction, HPhi* phi) {
- return instruction != nullptr
- && instruction->IsPhi()
- && instruction->AsPhi()->GetRegNumber() == phi->GetRegNumber();
-}
-
void SsaBuilder::FixNullConstantType() {
// The order doesn't matter here.
for (HReversePostOrderIterator itb(*GetGraph()); !itb.Done(); itb.Advance()) {
@@ -324,13 +318,13 @@
// If the phi is not dead, or has no environment uses, there is nothing to do.
if (!phi->IsDead() || !phi->HasEnvironmentUses()) continue;
HInstruction* next = phi->GetNext();
- if (!IsPhiEquivalentOf(next, phi)) continue;
+ if (!phi->IsVRegEquivalentOf(next)) continue;
if (next->AsPhi()->IsDead()) {
// If the phi equivalent is dead, check if there is another one.
next = next->GetNext();
- if (!IsPhiEquivalentOf(next, phi)) continue;
+ if (!phi->IsVRegEquivalentOf(next)) continue;
// There can be at most two phi equivalents.
- DCHECK(!IsPhiEquivalentOf(next->GetNext(), phi));
+ DCHECK(!phi->IsVRegEquivalentOf(next->GetNext()));
if (next->AsPhi()->IsDead()) continue;
}
// We found a live phi equivalent. Update the environment uses of `phi` with it.
@@ -403,6 +397,24 @@
if (block->IsCatchBlock()) {
// Catch phis were already created and inputs collected from throwing sites.
+ if (kIsDebugBuild) {
+ // Make sure there was at least one throwing instruction which initialized
+ // locals (guaranteed by HGraphBuilder) and that all try blocks have been
+ // visited already (from HTryBoundary scoping and reverse post order).
+ bool throwing_instruction_found = false;
+ bool catch_block_visited = false;
+ for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
+ HBasicBlock* current = it.Current();
+ if (current == block) {
+ catch_block_visited = true;
+ } else if (current->IsTryBlock() &&
+ current->GetTryCatchInformation()->GetTryEntry().HasExceptionHandler(*block)) {
+ DCHECK(!catch_block_visited) << "Catch block visited before its try block.";
+ throwing_instruction_found |= current->HasThrowingInstructions();
+ }
+ }
+ DCHECK(throwing_instruction_found) << "No instructions throwing into a live catch block.";
+ }
} else if (block->IsLoopHeader()) {
// If the block is a loop header, we know we only have visited the pre header
// because we are visiting in reverse post order. We create phis for all initialized
diff --git a/compiler/utils/array_ref.h b/compiler/utils/array_ref.h
index 303e0d5..48f0328 100644
--- a/compiler/utils/array_ref.h
+++ b/compiler/utils/array_ref.h
@@ -161,6 +161,15 @@
value_type* data() { return array_; }
const value_type* data() const { return array_; }
+ ArrayRef SubArray(size_type pos) const {
+ return SubArray(pos, size_ - pos);
+ }
+ ArrayRef SubArray(size_type pos, size_type length) const {
+ DCHECK_LE(pos, size());
+ DCHECK_LE(length, size() - pos);
+ return ArrayRef(array_ + pos, length);
+ }
+
private:
T* array_;
size_t size_;
diff --git a/dex2oat/Android.mk b/dex2oat/Android.mk
index 3cfdc4c..e252765 100644
--- a/dex2oat/Android.mk
+++ b/dex2oat/Android.mk
@@ -58,14 +58,16 @@
ifeq ($(ART_BUILD_HOST_NDEBUG),true)
$(eval $(call build-art-executable,dex2oat,$(DEX2OAT_SRC_FILES),libcutils libart-compiler libsigchain libziparchive-host,art/compiler,host,ndebug,$(dex2oat_host_arch)))
ifeq ($(ART_BUILD_HOST_STATIC),true)
- $(eval $(call build-art-executable,dex2oat,$(DEX2OAT_SRC_FILES),libart libart-compiler libart libziparchive-host libnativehelper libnativebridge libsigchain_dummy libvixl liblog libz libbacktrace libcutils libunwindbacktrace libutils libbase,art/compiler,host,ndebug,$(dex2oat_host_arch),static))
+ $(eval $(call build-art-executable,dex2oat,$(DEX2OAT_SRC_FILES),libart libart-compiler libart libziparchive-host libnativehelper libnativebridge libsigchain_dummy libvixl liblog libz \
+ libbacktrace libLLVMObject libLLVMBitReader libLLVMMC libLLVMMCParser libLLVMCore libLLVMSupport libcutils libunwindbacktrace libutils libbase,art/compiler,host,ndebug,$(dex2oat_host_arch),static))
endif
endif
ifeq ($(ART_BUILD_HOST_DEBUG),true)
$(eval $(call build-art-executable,dex2oat,$(DEX2OAT_SRC_FILES),libcutils libartd-compiler libsigchain libziparchive-host,art/compiler,host,debug,$(dex2oat_host_arch)))
ifeq ($(ART_BUILD_HOST_STATIC),true)
- $(eval $(call build-art-executable,dex2oat,$(DEX2OAT_SRC_FILES),libartd libartd-compiler libartd libziparchive-host libnativehelper libnativebridge libsigchain_dummy libvixld liblog libz libbacktrace libcutils libunwindbacktrace libutils libbase,art/compiler,host,debug,$(dex2oat_host_arch),static))
+ $(eval $(call build-art-executable,dex2oat,$(DEX2OAT_SRC_FILES),libartd libartd-compiler libartd libziparchive-host libnativehelper libnativebridge libsigchain_dummy libvixld liblog libz \
+ libbacktrace libLLVMObject libLLVMBitReader libLLVMMC libLLVMMCParser libLLVMCore libLLVMSupport libcutils libunwindbacktrace libutils libbase,art/compiler,host,debug,$(dex2oat_host_arch),static))
endif
endif
diff --git a/dexdump/Android.mk b/dexdump/Android.mk
index a208ccf..ec2529e 100755
--- a/dexdump/Android.mk
+++ b/dexdump/Android.mk
@@ -34,8 +34,6 @@
LOCAL_CFLAGS += -Wall
LOCAL_SHARED_LIBRARIES += $(dexdump_libraries)
LOCAL_MODULE := dexdump2
-LOCAL_MODULE_TAGS := optional
-LOCAL_MODULE_PATH := $(TARGET_OUT_OPTIONAL_EXECUTABLES)
include $(BUILD_EXECUTABLE)
endif # !SDK_ONLY
diff --git a/dexdump/dexdump_test.cc b/dexdump/dexdump_test.cc
index d9b210d..4230cb2 100644
--- a/dexdump/dexdump_test.cc
+++ b/dexdump/dexdump_test.cc
@@ -43,12 +43,7 @@
// Runs test with given arguments.
bool Exec(const std::vector<std::string>& args, std::string* error_msg) {
// TODO(ajcbik): dexdump2 -> dexdump
- std::string file_path = GetTestAndroidRoot();
- if (IsHost()) {
- file_path += "/bin/dexdump2";
- } else {
- file_path += "/xbin/dexdump2";
- }
+ std::string file_path = GetTestAndroidRoot() + "/bin/dexdump2";
EXPECT_TRUE(OS::FileExists(file_path.c_str())) << file_path << " should be a valid file path";
std::vector<std::string> exec_argv = { file_path };
exec_argv.insert(exec_argv.end(), args.begin(), args.end());
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index bc8a9f4..6b9c8aa 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -1318,9 +1318,8 @@
boot_class_table_.VisitRoots(buffered_visitor);
// TODO: Avoid marking these to enable class unloading.
JavaVMExt* const vm = Runtime::Current()->GetJavaVM();
- for (jweak weak_root : class_loaders_) {
- mirror::Object* class_loader =
- down_cast<mirror::ClassLoader*>(vm->DecodeWeakGlobal(self, weak_root));
+ for (const ClassLoaderData& data : class_loaders_) {
+ mirror::Object* class_loader = vm->DecodeWeakGlobal(self, data.weak_root);
// Don't need to update anything since the class loaders will be updated by SweepSystemWeaks.
visitor->VisitRootIfNonNull(&class_loader, RootInfo(kRootVMInternal));
}
@@ -1503,13 +1502,10 @@
STLDeleteElements(&oat_files_);
Thread* const self = Thread::Current();
JavaVMExt* const vm = Runtime::Current()->GetJavaVM();
- for (jweak weak_root : class_loaders_) {
- auto* const class_loader = down_cast<mirror::ClassLoader*>(
- vm->DecodeWeakGlobalDuringShutdown(self, weak_root));
- if (class_loader != nullptr) {
- delete class_loader->GetClassTable();
- }
- vm->DeleteWeakGlobalRef(self, weak_root);
+ for (const ClassLoaderData& data : class_loaders_) {
+ vm->DecodeWeakGlobalDuringShutdown(self, data.weak_root);
+ delete data.allocator;
+ delete data.class_table;
}
class_loaders_.clear();
}
@@ -2375,21 +2371,25 @@
}
}
-LengthPrefixedArray<ArtField>* ClassLinker::AllocArtFieldArray(Thread* self, size_t length) {
+LengthPrefixedArray<ArtField>* ClassLinker::AllocArtFieldArray(Thread* self,
+ LinearAlloc* allocator,
+ size_t length) {
if (length == 0) {
return nullptr;
}
// If the ArtField alignment changes, review all uses of LengthPrefixedArray<ArtField>.
static_assert(alignof(ArtField) == 4, "ArtField alignment is expected to be 4.");
size_t storage_size = LengthPrefixedArray<ArtField>::ComputeSize(length);
- void* array_storage = Runtime::Current()->GetLinearAlloc()->Alloc(self, storage_size);
+ void* array_storage = allocator->Alloc(self, storage_size);
auto* ret = new(array_storage) LengthPrefixedArray<ArtField>(length);
CHECK(ret != nullptr);
std::uninitialized_fill_n(&ret->At(0), length, ArtField());
return ret;
}
-LengthPrefixedArray<ArtMethod>* ClassLinker::AllocArtMethodArray(Thread* self, size_t length) {
+LengthPrefixedArray<ArtMethod>* ClassLinker::AllocArtMethodArray(Thread* self,
+ LinearAlloc* allocator,
+ size_t length) {
if (length == 0) {
return nullptr;
}
@@ -2397,7 +2397,7 @@
const size_t method_size = ArtMethod::Size(image_pointer_size_);
const size_t storage_size =
LengthPrefixedArray<ArtMethod>::ComputeSize(length, method_size, method_alignment);
- void* array_storage = Runtime::Current()->GetLinearAlloc()->Alloc(self, storage_size);
+ void* array_storage = allocator->Alloc(self, storage_size);
auto* ret = new (array_storage) LengthPrefixedArray<ArtMethod>(length);
CHECK(ret != nullptr);
for (size_t i = 0; i < length; ++i) {
@@ -2406,6 +2406,15 @@
return ret;
}
+LinearAlloc* ClassLinker::GetAllocatorForClassLoader(mirror::ClassLoader* class_loader) {
+ if (class_loader == nullptr) {
+ return Runtime::Current()->GetLinearAlloc();
+ }
+ LinearAlloc* allocator = class_loader->GetAllocator();
+ DCHECK(allocator != nullptr);
+ return allocator;
+}
+
void ClassLinker::LoadClassMembers(Thread* self,
const DexFile& dex_file,
const uint8_t* class_data,
@@ -2418,8 +2427,11 @@
// Load static fields.
// We allow duplicate definitions of the same field in a class_data_item
// but ignore the repeated indexes here, b/21868015.
+ LinearAlloc* const allocator = GetAllocatorForClassLoader(klass->GetClassLoader());
ClassDataItemIterator it(dex_file, class_data);
- LengthPrefixedArray<ArtField>* sfields = AllocArtFieldArray(self, it.NumStaticFields());
+ LengthPrefixedArray<ArtField>* sfields = AllocArtFieldArray(self,
+ allocator,
+ it.NumStaticFields());
size_t num_sfields = 0;
uint32_t last_field_idx = 0u;
for (; it.HasNextStaticField(); it.Next()) {
@@ -2435,7 +2447,9 @@
klass->SetSFieldsPtr(sfields);
DCHECK_EQ(klass->NumStaticFields(), num_sfields);
// Load instance fields.
- LengthPrefixedArray<ArtField>* ifields = AllocArtFieldArray(self, it.NumInstanceFields());
+ LengthPrefixedArray<ArtField>* ifields = AllocArtFieldArray(self,
+ allocator,
+ it.NumInstanceFields());
size_t num_ifields = 0u;
last_field_idx = 0u;
for (; it.HasNextInstanceField(); it.Next()) {
@@ -2458,8 +2472,8 @@
klass->SetIFieldsPtr(ifields);
DCHECK_EQ(klass->NumInstanceFields(), num_ifields);
// Load methods.
- klass->SetDirectMethodsPtr(AllocArtMethodArray(self, it.NumDirectMethods()));
- klass->SetVirtualMethodsPtr(AllocArtMethodArray(self, it.NumVirtualMethods()));
+ klass->SetDirectMethodsPtr(AllocArtMethodArray(self, allocator, it.NumDirectMethods()));
+ klass->SetVirtualMethodsPtr(AllocArtMethodArray(self, allocator, it.NumVirtualMethods()));
size_t class_def_method_index = 0;
uint32_t last_dex_method_index = DexFile::kDexNoIndex;
size_t last_class_def_method_index = 0;
@@ -3031,7 +3045,7 @@
WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
boot_class_table_.FreezeSnapshot();
MoveClassTableToPreZygoteVisitor visitor;
- VisitClassLoadersAndRemoveClearedLoaders(&visitor);
+ VisitClassLoaders(&visitor);
}
mirror::Class* ClassLinker::LookupClassFromImage(const char* descriptor) {
@@ -3414,9 +3428,12 @@
mirror::Class* existing = InsertClass(descriptor.c_str(), klass.Get(), hash);
CHECK(existing == nullptr);
+ // Needs to be after we insert the class so that the allocator field is set.
+ LinearAlloc* const allocator = GetAllocatorForClassLoader(klass->GetClassLoader());
+
// Instance fields are inherited, but we add a couple of static fields...
const size_t num_fields = 2;
- LengthPrefixedArray<ArtField>* sfields = AllocArtFieldArray(self, num_fields);
+ LengthPrefixedArray<ArtField>* sfields = AllocArtFieldArray(self, allocator, num_fields);
klass->SetSFieldsPtr(sfields);
// 1. Create a static field 'interfaces' that holds the _declared_ interfaces implemented by
@@ -3433,7 +3450,7 @@
throws_sfield.SetAccessFlags(kAccStatic | kAccPublic | kAccFinal);
// Proxies have 1 direct method, the constructor
- LengthPrefixedArray<ArtMethod>* directs = AllocArtMethodArray(self, 1);
+ LengthPrefixedArray<ArtMethod>* directs = AllocArtMethodArray(self, allocator, 1);
// Currently AllocArtMethodArray cannot return null, but the OOM logic is left there in case we
// want to throw OOM in the future.
if (UNLIKELY(directs == nullptr)) {
@@ -3448,7 +3465,7 @@
DCHECK_EQ(h_methods->GetClass(), mirror::Method::ArrayClass())
<< PrettyClass(h_methods->GetClass());
const size_t num_virtual_methods = h_methods->GetLength();
- auto* virtuals = AllocArtMethodArray(self, num_virtual_methods);
+ auto* virtuals = AllocArtMethodArray(self, allocator, num_virtual_methods);
// Currently AllocArtMethodArray cannot return null, but the OOM logic is left there in case we
// want to throw OOM in the future.
if (UNLIKELY(virtuals == nullptr)) {
@@ -4166,9 +4183,14 @@
if (class_table == nullptr) {
class_table = new ClassTable;
Thread* const self = Thread::Current();
- class_loaders_.push_back(self->GetJniEnv()->vm->AddWeakGlobalRef(self, class_loader));
+ ClassLoaderData data;
+ data.weak_root = self->GetJniEnv()->vm->AddWeakGlobalRef(self, class_loader);
+ data.class_table = class_table;
+ data.allocator = Runtime::Current()->CreateLinearAlloc();
+ class_loaders_.push_back(data);
// Don't already have a class table, add it to the class loader.
- class_loader->SetClassTable(class_table);
+ class_loader->SetClassTable(data.class_table);
+ class_loader->SetAllocator(data.allocator);
}
return class_table;
}
@@ -6158,7 +6180,10 @@
ArtMethod* ClassLinker::CreateRuntimeMethod() {
const size_t method_alignment = ArtMethod::Alignment(image_pointer_size_);
const size_t method_size = ArtMethod::Size(image_pointer_size_);
- LengthPrefixedArray<ArtMethod>* method_array = AllocArtMethodArray(Thread::Current(), 1);
+ LengthPrefixedArray<ArtMethod>* method_array = AllocArtMethodArray(
+ Thread::Current(),
+ Runtime::Current()->GetLinearAlloc(),
+ 1);
ArtMethod* method = &method_array->At(0, method_size, method_alignment);
CHECK(method != nullptr);
method->SetDexMethodIndex(DexFile::kDexNoIndex);
@@ -6171,33 +6196,34 @@
find_array_class_cache_next_victim_ = 0;
}
-void ClassLinker::VisitClassLoadersAndRemoveClearedLoaders(ClassLoaderVisitor* visitor) {
+void ClassLinker::VisitClassLoaders(ClassLoaderVisitor* visitor) const {
Thread* const self = Thread::Current();
- Locks::classlinker_classes_lock_->AssertExclusiveHeld(self);
JavaVMExt* const vm = self->GetJniEnv()->vm;
- for (auto it = class_loaders_.begin(); it != class_loaders_.end();) {
- const jweak weak_root = *it;
- mirror::ClassLoader* const class_loader = down_cast<mirror::ClassLoader*>(
- vm->DecodeWeakGlobal(self, weak_root));
+ for (const ClassLoaderData& data : class_loaders_) {
+ auto* const class_loader = down_cast<mirror::ClassLoader*>(
+ vm->DecodeWeakGlobal(self, data.weak_root));
if (class_loader != nullptr) {
visitor->Visit(class_loader);
- ++it;
- } else {
- // Remove the cleared weak reference from the array.
- vm->DeleteWeakGlobalRef(self, weak_root);
- it = class_loaders_.erase(it);
}
}
}
-void ClassLinker::VisitClassLoaders(ClassLoaderVisitor* visitor) const {
+void ClassLinker::CleanupClassLoaders() {
Thread* const self = Thread::Current();
- JavaVMExt* const vm = self->GetJniEnv()->vm;
- for (jweak weak_root : class_loaders_) {
- mirror::ClassLoader* const class_loader = down_cast<mirror::ClassLoader*>(
- vm->DecodeWeakGlobal(self, weak_root));
+ WriterMutexLock mu(self, *Locks::classlinker_classes_lock_);
+ JavaVMExt* const vm = Runtime::Current()->GetJavaVM();
+ for (auto it = class_loaders_.begin(); it != class_loaders_.end(); ) {
+ const ClassLoaderData& data = *it;
+ auto* const class_loader = down_cast<mirror::ClassLoader*>(
+ vm->DecodeWeakGlobal(self, data.weak_root));
if (class_loader != nullptr) {
- visitor->Visit(class_loader);
+ ++it;
+ } else {
+ // Weak reference was cleared, delete the data associated with this class loader.
+ delete data.class_table;
+ delete data.allocator;
+ vm->DeleteWeakGlobalRef(self, data.weak_root);
+ it = class_loaders_.erase(it);
}
}
}
diff --git a/runtime/class_linker.h b/runtime/class_linker.h
index fee7066..f705330 100644
--- a/runtime/class_linker.h
+++ b/runtime/class_linker.h
@@ -403,9 +403,13 @@
SHARED_REQUIRES(Locks::mutator_lock_)
REQUIRES(!Roles::uninterruptible_);
- LengthPrefixedArray<ArtField>* AllocArtFieldArray(Thread* self, size_t length);
+ LengthPrefixedArray<ArtField>* AllocArtFieldArray(Thread* self,
+ LinearAlloc* allocator,
+ size_t length);
- LengthPrefixedArray<ArtMethod>* AllocArtMethodArray(Thread* self, size_t length);
+ LengthPrefixedArray<ArtMethod>* AllocArtMethodArray(Thread* self,
+ LinearAlloc* allocator,
+ size_t length);
mirror::PointerArray* AllocPointerArray(Thread* self, size_t length)
SHARED_REQUIRES(Locks::mutator_lock_)
@@ -546,17 +550,24 @@
// entries are roots, but potentially not image classes.
void DropFindArrayClassCache() SHARED_REQUIRES(Locks::mutator_lock_);
- private:
- // The RemoveClearedLoaders version removes cleared weak global class loaders and frees their
- // class tables. This version can only be called with reader access to the
- // classlinker_classes_lock_ since it modifies the class_loaders_ list.
- void VisitClassLoadersAndRemoveClearedLoaders(ClassLoaderVisitor* visitor)
- REQUIRES(Locks::classlinker_classes_lock_)
+ // Clean up class loaders, this needs to happen after JNI weak globals are cleared.
+ void CleanupClassLoaders()
+ SHARED_REQUIRES(Locks::mutator_lock_)
+ REQUIRES(!Locks::classlinker_classes_lock_);
+
+ static LinearAlloc* GetAllocatorForClassLoader(mirror::ClassLoader* class_loader)
SHARED_REQUIRES(Locks::mutator_lock_);
+
+ private:
+ struct ClassLoaderData {
+ jobject weak_root; // Weak root to enable class unloading.
+ ClassTable* class_table;
+ LinearAlloc* allocator;
+ };
+
void VisitClassLoaders(ClassLoaderVisitor* visitor) const
SHARED_REQUIRES(Locks::classlinker_classes_lock_, Locks::mutator_lock_);
-
void VisitClassesInternal(ClassVisitor* visitor)
SHARED_REQUIRES(Locks::classlinker_classes_lock_, Locks::mutator_lock_);
@@ -826,8 +837,8 @@
std::vector<const OatFile*> oat_files_ GUARDED_BY(dex_lock_);
// This contains the class loaders which have class tables. It is populated by
- // InsertClassTableForClassLoader. Weak roots to enable class unloading.
- std::list<jweak> class_loaders_
+ // InsertClassTableForClassLoader.
+ std::list<ClassLoaderData> class_loaders_
GUARDED_BY(Locks::classlinker_classes_lock_);
// Boot class path table. Since the class loader for this is null.
diff --git a/runtime/class_linker_test.cc b/runtime/class_linker_test.cc
index b4ea3b3..0926ce3 100644
--- a/runtime/class_linker_test.cc
+++ b/runtime/class_linker_test.cc
@@ -550,6 +550,7 @@
struct ClassLoaderOffsets : public CheckOffsets<mirror::ClassLoader> {
ClassLoaderOffsets() : CheckOffsets<mirror::ClassLoader>(false, "Ljava/lang/ClassLoader;") {
+ addOffset(OFFSETOF_MEMBER(mirror::ClassLoader, allocator_), "allocator");
addOffset(OFFSETOF_MEMBER(mirror::ClassLoader, class_table_), "classTable");
addOffset(OFFSETOF_MEMBER(mirror::ClassLoader, packages_), "packages");
addOffset(OFFSETOF_MEMBER(mirror::ClassLoader, parent_), "parent");
diff --git a/runtime/gc/collector/concurrent_copying.cc b/runtime/gc/collector/concurrent_copying.cc
index 399591b..468179c 100644
--- a/runtime/gc/collector/concurrent_copying.cc
+++ b/runtime/gc/collector/concurrent_copying.cc
@@ -457,6 +457,8 @@
CheckEmptyMarkStack();
// Re-enable weak ref accesses.
ReenableWeakRefAccess(self);
+ // Free data for class loaders that we unloaded.
+ Runtime::Current()->GetClassLinker()->CleanupClassLoaders();
// Marking is done. Disable marking.
DisableMarking();
CheckEmptyMarkStack();
diff --git a/runtime/gc/collector/mark_compact.cc b/runtime/gc/collector/mark_compact.cc
index 60f833b..f561764 100644
--- a/runtime/gc/collector/mark_compact.cc
+++ b/runtime/gc/collector/mark_compact.cc
@@ -205,6 +205,7 @@
ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_);
SweepSystemWeaks();
}
+ Runtime::Current()->GetClassLinker()->CleanupClassLoaders();
// Revoke buffers before measuring how many objects were moved since the TLABs need to be revoked
// before they are properly counted.
RevokeAllThreadLocalBuffers();
diff --git a/runtime/gc/collector/mark_sweep-inl.h b/runtime/gc/collector/mark_sweep-inl.h
index 56edcc9..e72277f 100644
--- a/runtime/gc/collector/mark_sweep-inl.h
+++ b/runtime/gc/collector/mark_sweep-inl.h
@@ -29,7 +29,8 @@
namespace collector {
template<typename MarkVisitor, typename ReferenceVisitor>
-inline void MarkSweep::ScanObjectVisit(mirror::Object* obj, const MarkVisitor& visitor,
+inline void MarkSweep::ScanObjectVisit(mirror::Object* obj,
+ const MarkVisitor& visitor,
const ReferenceVisitor& ref_visitor) {
DCHECK(IsMarked(obj)) << "Scanning unmarked object " << obj << "\n" << heap_->DumpSpaces();
obj->VisitReferences(visitor, ref_visitor);
diff --git a/runtime/gc/collector/mark_sweep.cc b/runtime/gc/collector/mark_sweep.cc
index 089f453..77a288b 100644
--- a/runtime/gc/collector/mark_sweep.cc
+++ b/runtime/gc/collector/mark_sweep.cc
@@ -95,10 +95,13 @@
: GarbageCollector(heap,
name_prefix +
(is_concurrent ? "concurrent mark sweep": "mark sweep")),
- current_space_bitmap_(nullptr), mark_bitmap_(nullptr), mark_stack_(nullptr),
+ current_space_bitmap_(nullptr),
+ mark_bitmap_(nullptr),
+ mark_stack_(nullptr),
gc_barrier_(new Barrier(0)),
mark_stack_lock_("mark sweep mark stack lock", kMarkSweepMarkStackLock),
- is_concurrent_(is_concurrent), live_stack_freeze_size_(0) {
+ is_concurrent_(is_concurrent),
+ live_stack_freeze_size_(0) {
std::string error_msg;
MemMap* mem_map = MemMap::MapAnonymous(
"mark sweep sweep array free buffer", nullptr,
@@ -173,7 +176,10 @@
void MarkSweep::ProcessReferences(Thread* self) {
WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
GetHeap()->GetReferenceProcessor()->ProcessReferences(
- true, GetTimings(), GetCurrentIteration()->GetClearSoftReferences(), this);
+ true,
+ GetTimings(),
+ GetCurrentIteration()->GetClearSoftReferences(),
+ this);
}
void MarkSweep::PausePhase() {
@@ -265,8 +271,9 @@
void MarkSweep::UpdateAndMarkModUnion() {
for (const auto& space : heap_->GetContinuousSpaces()) {
if (immune_region_.ContainsSpace(space)) {
- const char* name = space->IsZygoteSpace() ? "UpdateAndMarkZygoteModUnionTable" :
- "UpdateAndMarkImageModUnionTable";
+ const char* name = space->IsZygoteSpace()
+ ? "UpdateAndMarkZygoteModUnionTable"
+ : "UpdateAndMarkImageModUnionTable";
TimingLogger::ScopedTiming t(name, GetTimings());
accounting::ModUnionTable* mod_union_table = heap_->FindModUnionTableFromSpace(space);
CHECK(mod_union_table != nullptr);
@@ -283,11 +290,15 @@
void MarkSweep::ReclaimPhase() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
- Thread* self = Thread::Current();
+ Thread* const self = Thread::Current();
// Process the references concurrently.
ProcessReferences(self);
SweepSystemWeaks(self);
- Runtime::Current()->AllowNewSystemWeaks();
+ Runtime* const runtime = Runtime::Current();
+ runtime->AllowNewSystemWeaks();
+ // Clean up class loaders after system weaks are swept since that is how we know if class
+ // unloading occurred.
+ runtime->GetClassLinker()->CleanupClassLoaders();
{
WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
GetHeap()->RecordFreeRevoke();
@@ -361,10 +372,10 @@
class MarkSweepMarkObjectSlowPath {
public:
- explicit MarkSweepMarkObjectSlowPath(MarkSweep* mark_sweep, mirror::Object* holder = nullptr,
+ explicit MarkSweepMarkObjectSlowPath(MarkSweep* mark_sweep,
+ mirror::Object* holder = nullptr,
MemberOffset offset = MemberOffset(0))
- : mark_sweep_(mark_sweep), holder_(holder), offset_(offset) {
- }
+ : mark_sweep_(mark_sweep), holder_(holder), offset_(offset) {}
void operator()(const mirror::Object* obj) const NO_THREAD_SAFETY_ANALYSIS {
if (kProfileLargeObjects) {
@@ -441,7 +452,8 @@
MemberOffset offset_;
};
-inline void MarkSweep::MarkObjectNonNull(mirror::Object* obj, mirror::Object* holder,
+inline void MarkSweep::MarkObjectNonNull(mirror::Object* obj,
+ mirror::Object* holder,
MemberOffset offset) {
DCHECK(obj != nullptr);
if (kUseBakerOrBrooksReadBarrier) {
@@ -508,7 +520,8 @@
}
// Used to mark objects when processing the mark stack. If an object is null, it is not marked.
-inline void MarkSweep::MarkObject(mirror::Object* obj, mirror::Object* holder,
+inline void MarkSweep::MarkObject(mirror::Object* obj,
+ mirror::Object* holder,
MemberOffset offset) {
if (obj != nullptr) {
MarkObjectNonNull(obj, holder, offset);
@@ -530,14 +543,16 @@
MarkSweep* const collector_;
};
-void MarkSweep::VisitRoots(mirror::Object*** roots, size_t count,
+void MarkSweep::VisitRoots(mirror::Object*** roots,
+ size_t count,
const RootInfo& info ATTRIBUTE_UNUSED) {
for (size_t i = 0; i < count; ++i) {
MarkObjectNonNull(*roots[i]);
}
}
-void MarkSweep::VisitRoots(mirror::CompressedReference<mirror::Object>** roots, size_t count,
+void MarkSweep::VisitRoots(mirror::CompressedReference<mirror::Object>** roots,
+ size_t count,
const RootInfo& info ATTRIBUTE_UNUSED) {
for (size_t i = 0; i < count; ++i) {
MarkObjectNonNull(roots[i]->AsMirrorPtr());
@@ -596,8 +611,10 @@
explicit ScanObjectVisitor(MarkSweep* const mark_sweep) ALWAYS_INLINE
: mark_sweep_(mark_sweep) {}
- void operator()(mirror::Object* obj) const ALWAYS_INLINE
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_) {
+ void operator()(mirror::Object* obj) const
+ ALWAYS_INLINE
+ REQUIRES(Locks::heap_bitmap_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_) {
if (kCheckLocks) {
Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
Locks::heap_bitmap_lock_->AssertExclusiveHeld(Thread::Current());
@@ -611,12 +628,11 @@
class DelayReferenceReferentVisitor {
public:
- explicit DelayReferenceReferentVisitor(MarkSweep* collector) : collector_(collector) {
- }
+ explicit DelayReferenceReferentVisitor(MarkSweep* collector) : collector_(collector) {}
void operator()(mirror::Class* klass, mirror::Reference* ref) const
- SHARED_REQUIRES(Locks::mutator_lock_)
- REQUIRES(Locks::heap_bitmap_lock_) {
+ REQUIRES(Locks::heap_bitmap_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_) {
collector_->DelayReferenceReferent(klass, ref);
}
@@ -627,7 +643,9 @@
template <bool kUseFinger = false>
class MarkStackTask : public Task {
public:
- MarkStackTask(ThreadPool* thread_pool, MarkSweep* mark_sweep, size_t mark_stack_size,
+ MarkStackTask(ThreadPool* thread_pool,
+ MarkSweep* mark_sweep,
+ size_t mark_stack_size,
StackReference<mirror::Object>* mark_stack)
: mark_sweep_(mark_sweep),
thread_pool_(thread_pool),
@@ -652,8 +670,10 @@
MarkSweep* mark_sweep)
: chunk_task_(chunk_task), mark_sweep_(mark_sweep) {}
- void operator()(mirror::Object* obj, MemberOffset offset, bool /* static */) const
- ALWAYS_INLINE SHARED_REQUIRES(Locks::mutator_lock_) {
+ ALWAYS_INLINE void operator()(mirror::Object* obj,
+ MemberOffset offset,
+ bool is_static ATTRIBUTE_UNUSED) const
+ SHARED_REQUIRES(Locks::mutator_lock_) {
Mark(obj->GetFieldObject<mirror::Object>(offset));
}
@@ -674,7 +694,7 @@
}
private:
- void Mark(mirror::Object* ref) const ALWAYS_INLINE SHARED_REQUIRES(Locks::mutator_lock_) {
+ ALWAYS_INLINE void Mark(mirror::Object* ref) const SHARED_REQUIRES(Locks::mutator_lock_) {
if (ref != nullptr && mark_sweep_->MarkObjectParallel(ref)) {
if (kUseFinger) {
std::atomic_thread_fence(std::memory_order_seq_cst);
@@ -693,12 +713,13 @@
class ScanObjectParallelVisitor {
public:
- explicit ScanObjectParallelVisitor(MarkStackTask<kUseFinger>* chunk_task) ALWAYS_INLINE
+ ALWAYS_INLINE explicit ScanObjectParallelVisitor(MarkStackTask<kUseFinger>* chunk_task)
: chunk_task_(chunk_task) {}
// No thread safety analysis since multiple threads will use this visitor.
- void operator()(mirror::Object* obj) const SHARED_REQUIRES(Locks::mutator_lock_)
- REQUIRES(Locks::heap_bitmap_lock_) {
+ void operator()(mirror::Object* obj) const
+ REQUIRES(Locks::heap_bitmap_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_) {
MarkSweep* const mark_sweep = chunk_task_->mark_sweep_;
MarkObjectParallelVisitor mark_visitor(chunk_task_, mark_sweep);
DelayReferenceReferentVisitor ref_visitor(mark_sweep);
@@ -729,7 +750,9 @@
if (UNLIKELY(mark_stack_pos_ == kMaxSize)) {
// Mark stack overflow, give 1/2 the stack to the thread pool as a new work task.
mark_stack_pos_ /= 2;
- auto* task = new MarkStackTask(thread_pool_, mark_sweep_, kMaxSize - mark_stack_pos_,
+ auto* task = new MarkStackTask(thread_pool_,
+ mark_sweep_,
+ kMaxSize - mark_stack_pos_,
mark_stack_ + mark_stack_pos_);
thread_pool_->AddTask(Thread::Current(), task);
}
@@ -743,9 +766,9 @@
}
// Scans all of the objects
- virtual void Run(Thread* self) SHARED_REQUIRES(Locks::mutator_lock_)
- REQUIRES(Locks::heap_bitmap_lock_) {
- UNUSED(self);
+ virtual void Run(Thread* self ATTRIBUTE_UNUSED)
+ REQUIRES(Locks::heap_bitmap_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_) {
ScanObjectParallelVisitor visitor(this);
// TODO: Tune this.
static const size_t kFifoSize = 4;
@@ -778,16 +801,21 @@
class CardScanTask : public MarkStackTask<false> {
public:
- CardScanTask(ThreadPool* thread_pool, MarkSweep* mark_sweep,
+ CardScanTask(ThreadPool* thread_pool,
+ MarkSweep* mark_sweep,
accounting::ContinuousSpaceBitmap* bitmap,
- uint8_t* begin, uint8_t* end, uint8_t minimum_age, size_t mark_stack_size,
- StackReference<mirror::Object>* mark_stack_obj, bool clear_card)
+ uint8_t* begin,
+ uint8_t* end,
+ uint8_t minimum_age,
+ size_t mark_stack_size,
+ StackReference<mirror::Object>* mark_stack_obj,
+ bool clear_card)
: MarkStackTask<false>(thread_pool, mark_sweep, mark_stack_size, mark_stack_obj),
bitmap_(bitmap),
begin_(begin),
end_(end),
- minimum_age_(minimum_age), clear_card_(clear_card) {
- }
+ minimum_age_(minimum_age),
+ clear_card_(clear_card) {}
protected:
accounting::ContinuousSpaceBitmap* const bitmap_;
@@ -803,9 +831,9 @@
virtual void Run(Thread* self) NO_THREAD_SAFETY_ANALYSIS {
ScanObjectParallelVisitor visitor(this);
accounting::CardTable* card_table = mark_sweep_->GetHeap()->GetCardTable();
- size_t cards_scanned = clear_card_ ?
- card_table->Scan<true>(bitmap_, begin_, end_, visitor, minimum_age_) :
- card_table->Scan<false>(bitmap_, begin_, end_, visitor, minimum_age_);
+ size_t cards_scanned = clear_card_
+ ? card_table->Scan<true>(bitmap_, begin_, end_, visitor, minimum_age_)
+ : card_table->Scan<false>(bitmap_, begin_, end_, visitor, minimum_age_);
VLOG(heap) << "Parallel scanning cards " << reinterpret_cast<void*>(begin_) << " - "
<< reinterpret_cast<void*>(end_) << " = " << cards_scanned;
// Finish by emptying our local mark stack.
@@ -873,9 +901,15 @@
mark_stack_->PopBackCount(static_cast<int32_t>(mark_stack_increment));
DCHECK_EQ(mark_stack_end, mark_stack_->End());
// Add the new task to the thread pool.
- auto* task = new CardScanTask(thread_pool, this, space->GetMarkBitmap(), card_begin,
- card_begin + card_increment, minimum_age,
- mark_stack_increment, mark_stack_end, clear_card);
+ auto* task = new CardScanTask(thread_pool,
+ this,
+ space->GetMarkBitmap(),
+ card_begin,
+ card_begin + card_increment,
+ minimum_age,
+ mark_stack_increment,
+ mark_stack_end,
+ clear_card);
thread_pool->AddTask(self, task);
card_begin += card_increment;
}
@@ -911,10 +945,16 @@
ScanObjectVisitor visitor(this);
bool clear_card = paused && !space->IsZygoteSpace() && !space->IsImageSpace();
if (clear_card) {
- card_table->Scan<true>(space->GetMarkBitmap(), space->Begin(), space->End(), visitor,
+ card_table->Scan<true>(space->GetMarkBitmap(),
+ space->Begin(),
+ space->End(),
+ visitor,
minimum_age);
} else {
- card_table->Scan<false>(space->GetMarkBitmap(), space->Begin(), space->End(), visitor,
+ card_table->Scan<false>(space->GetMarkBitmap(),
+ space->Begin(),
+ space->End(),
+ visitor,
minimum_age);
}
}
@@ -924,11 +964,15 @@
class RecursiveMarkTask : public MarkStackTask<false> {
public:
- RecursiveMarkTask(ThreadPool* thread_pool, MarkSweep* mark_sweep,
- accounting::ContinuousSpaceBitmap* bitmap, uintptr_t begin, uintptr_t end)
- : MarkStackTask<false>(thread_pool, mark_sweep, 0, nullptr), bitmap_(bitmap), begin_(begin),
- end_(end) {
- }
+ RecursiveMarkTask(ThreadPool* thread_pool,
+ MarkSweep* mark_sweep,
+ accounting::ContinuousSpaceBitmap* bitmap,
+ uintptr_t begin,
+ uintptr_t end)
+ : MarkStackTask<false>(thread_pool, mark_sweep, 0, nullptr),
+ bitmap_(bitmap),
+ begin_(begin),
+ end_(end) {}
protected:
accounting::ContinuousSpaceBitmap* const bitmap_;
@@ -985,7 +1029,10 @@
delta = RoundUp(delta, KB);
if (delta < 16 * KB) delta = end - begin;
begin += delta;
- auto* task = new RecursiveMarkTask(thread_pool, this, current_space_bitmap_, start,
+ auto* task = new RecursiveMarkTask(thread_pool,
+ this,
+ current_space_bitmap_,
+ start,
begin);
thread_pool->AddTask(self, task);
}
@@ -1032,7 +1079,8 @@
public:
explicit VerifySystemWeakVisitor(MarkSweep* mark_sweep) : mark_sweep_(mark_sweep) {}
- virtual mirror::Object* IsMarked(mirror::Object* obj) OVERRIDE
+ virtual mirror::Object* IsMarked(mirror::Object* obj)
+ OVERRIDE
SHARED_REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_) {
mark_sweep_->VerifyIsLive(obj);
return obj;
@@ -1073,7 +1121,8 @@
}
}
- void VisitRoots(mirror::CompressedReference<mirror::Object>** roots, size_t count,
+ void VisitRoots(mirror::CompressedReference<mirror::Object>** roots,
+ size_t count,
const RootInfo& info ATTRIBUTE_UNUSED)
OVERRIDE SHARED_REQUIRES(Locks::mutator_lock_)
REQUIRES(Locks::heap_bitmap_lock_) {
@@ -1247,7 +1296,8 @@
if (space->IsContinuousMemMapAllocSpace()) {
space::ContinuousMemMapAllocSpace* alloc_space = space->AsContinuousMemMapAllocSpace();
TimingLogger::ScopedTiming split(
- alloc_space->IsZygoteSpace() ? "SweepZygoteSpace" : "SweepMallocSpace", GetTimings());
+ alloc_space->IsZygoteSpace() ? "SweepZygoteSpace" : "SweepMallocSpace",
+ GetTimings());
RecordFree(alloc_space->Sweep(swap_bitmaps));
}
}
@@ -1270,12 +1320,13 @@
class MarkVisitor {
public:
- explicit MarkVisitor(MarkSweep* const mark_sweep) ALWAYS_INLINE : mark_sweep_(mark_sweep) {
- }
+ ALWAYS_INLINE explicit MarkVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) {}
- void operator()(mirror::Object* obj, MemberOffset offset, bool is_static ATTRIBUTE_UNUSED) const
- ALWAYS_INLINE SHARED_REQUIRES(Locks::mutator_lock_)
- REQUIRES(Locks::heap_bitmap_lock_) {
+ ALWAYS_INLINE void operator()(mirror::Object* obj,
+ MemberOffset offset,
+ bool is_static ATTRIBUTE_UNUSED) const
+ REQUIRES(Locks::heap_bitmap_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_) {
if (kCheckLocks) {
Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
Locks::heap_bitmap_lock_->AssertExclusiveHeld(Thread::Current());
@@ -1284,14 +1335,16 @@
}
void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_) {
+ REQUIRES(Locks::heap_bitmap_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_) {
if (!root->IsNull()) {
VisitRoot(root);
}
}
void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_) {
+ REQUIRES(Locks::heap_bitmap_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_) {
if (kCheckLocks) {
Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
Locks::heap_bitmap_lock_->AssertExclusiveHeld(Thread::Current());
diff --git a/runtime/gc/collector/mark_sweep.h b/runtime/gc/collector/mark_sweep.h
index 371bba5..8f7df78 100644
--- a/runtime/gc/collector/mark_sweep.h
+++ b/runtime/gc/collector/mark_sweep.h
@@ -33,9 +33,9 @@
namespace art {
namespace mirror {
- class Class;
- class Object;
- class Reference;
+class Class;
+class Object;
+class Reference;
} // namespace mirror
class Thread;
@@ -46,8 +46,8 @@
class Heap;
namespace accounting {
- template<typename T> class AtomicStack;
- typedef AtomicStack<mirror::Object> ObjectStack;
+template<typename T> class AtomicStack;
+typedef AtomicStack<mirror::Object> ObjectStack;
} // namespace accounting
namespace collector {
@@ -60,12 +60,14 @@
virtual void RunPhases() OVERRIDE REQUIRES(!mark_stack_lock_);
void InitializePhase();
- void MarkingPhase() SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(!mark_stack_lock_);
- void PausePhase() REQUIRES(Locks::mutator_lock_, !mark_stack_lock_);
- void ReclaimPhase() SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(!mark_stack_lock_);
+ void MarkingPhase() REQUIRES(!mark_stack_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
+ void PausePhase() REQUIRES(Locks::mutator_lock_) REQUIRES(!mark_stack_lock_);
+ void ReclaimPhase() REQUIRES(!mark_stack_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
void FinishPhase();
virtual void MarkReachableObjects()
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
bool IsConcurrent() const {
return is_concurrent_;
@@ -87,20 +89,30 @@
// Marks all objects in the root set at the start of a garbage collection.
void MarkRoots(Thread* self)
- REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
void MarkNonThreadRoots()
- REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
void MarkConcurrentRoots(VisitRootFlags flags)
- REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
void MarkRootsCheckpoint(Thread* self, bool revoke_ros_alloc_thread_local_buffers_at_checkpoint)
- REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
// Builds a mark stack and recursively mark until it empties.
void RecursiveMark()
- REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
// Bind the live bits to the mark bits of bitmaps for spaces that are never collected, ie
// the image. Mark that portion of the heap as immune.
@@ -108,26 +120,35 @@
// Builds a mark stack with objects on dirty cards and recursively mark until it empties.
void RecursiveMarkDirtyObjects(bool paused, uint8_t minimum_age)
- REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
// Remarks the root set after completing the concurrent mark.
void ReMarkRoots()
- REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
void ProcessReferences(Thread* self)
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(!mark_stack_lock_);
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
// Update and mark references from immune spaces.
void UpdateAndMarkModUnion()
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(!mark_stack_lock_);
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
// Pre clean cards to reduce how much work is needed in the pause.
void PreCleanCards()
- REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
// Sweeps unmarked objects to complete the garbage collection. Virtual as by default it sweeps
// all allocation spaces. Partial and sticky GCs want to just sweep a subset of the heap.
- virtual void Sweep(bool swap_bitmaps) REQUIRES(Locks::heap_bitmap_lock_)
+ virtual void Sweep(bool swap_bitmaps)
+ REQUIRES(Locks::heap_bitmap_lock_)
SHARED_REQUIRES(Locks::mutator_lock_);
// Sweeps unmarked objects to complete the garbage collection.
@@ -135,20 +156,27 @@
// Sweep only pointers within an array. WARNING: Trashes objects.
void SweepArray(accounting::ObjectStack* allocation_stack_, bool swap_bitmaps)
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
// Blackens an object.
void ScanObject(mirror::Object* obj)
- REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
// No thread safety analysis due to lambdas.
template<typename MarkVisitor, typename ReferenceVisitor>
- void ScanObjectVisit(mirror::Object* obj, const MarkVisitor& visitor,
+ void ScanObjectVisit(mirror::Object* obj,
+ const MarkVisitor& visitor,
const ReferenceVisitor& ref_visitor)
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
void SweepSystemWeaks(Thread* self)
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(!Locks::heap_bitmap_lock_);
+ REQUIRES(!Locks::heap_bitmap_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
static mirror::Object* VerifySystemWeakIsLiveCallback(mirror::Object* obj, void* arg)
SHARED_REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
@@ -161,22 +189,36 @@
SHARED_REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_);
virtual bool IsMarkedHeapReference(mirror::HeapReference<mirror::Object>* ref) OVERRIDE
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
virtual void VisitRoots(mirror::Object*** roots, size_t count, const RootInfo& info) OVERRIDE
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
- virtual void VisitRoots(mirror::CompressedReference<mirror::Object>** roots, size_t count,
+ virtual void VisitRoots(mirror::CompressedReference<mirror::Object>** roots,
+ size_t count,
const RootInfo& info) OVERRIDE
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
// Marks an object.
virtual mirror::Object* MarkObject(mirror::Object* obj) OVERRIDE
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
+
void MarkObject(mirror::Object* obj, mirror::Object* holder, MemberOffset offset)
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
+
virtual void MarkHeapReference(mirror::HeapReference<mirror::Object>* ref) OVERRIDE
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
Barrier& GetBarrier() {
return *gc_barrier_;
@@ -191,13 +233,17 @@
virtual mirror::Object* IsMarked(mirror::Object* object) OVERRIDE
SHARED_REQUIRES(Locks::heap_bitmap_lock_);
- void MarkObjectNonNull(mirror::Object* obj, mirror::Object* holder = nullptr,
+ void MarkObjectNonNull(mirror::Object* obj,
+ mirror::Object* holder = nullptr,
MemberOffset offset = MemberOffset(0))
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
// Marks an object atomically, safe to use from multiple threads.
void MarkObjectNonNullParallel(mirror::Object* obj)
- SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(!mark_stack_lock_);
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
// Returns true if we need to add obj to a mark stack.
bool MarkObjectParallel(mirror::Object* obj) NO_THREAD_SAFETY_ANALYSIS;
@@ -208,9 +254,12 @@
NO_THREAD_SAFETY_ANALYSIS;
// Expand mark stack to 2x its current size.
- void ExpandMarkStack() REQUIRES(mark_stack_lock_)
+ void ExpandMarkStack()
+ REQUIRES(mark_stack_lock_)
SHARED_REQUIRES(Locks::mutator_lock_);
- void ResizeMarkStack(size_t new_size) REQUIRES(mark_stack_lock_)
+
+ void ResizeMarkStack(size_t new_size)
+ REQUIRES(mark_stack_lock_)
SHARED_REQUIRES(Locks::mutator_lock_);
// Returns how many threads we should use for the current GC phase based on if we are paused,
@@ -218,24 +267,34 @@
size_t GetThreadCount(bool paused) const;
// Push a single reference on a mark stack.
- void PushOnMarkStack(mirror::Object* obj) SHARED_REQUIRES(Locks::mutator_lock_)
- REQUIRES(!mark_stack_lock_);
+ void PushOnMarkStack(mirror::Object* obj)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
// Blackens objects grayed during a garbage collection.
void ScanGrayObjects(bool paused, uint8_t minimum_age)
- REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
- virtual void ProcessMarkStack() OVERRIDE REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_)
+ virtual void ProcessMarkStack()
+ OVERRIDE
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
SHARED_REQUIRES(Locks::mutator_lock_) {
ProcessMarkStack(false);
}
// Recursively blackens objects on the mark stack.
void ProcessMarkStack(bool paused)
- REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
void ProcessMarkStackParallel(size_t thread_count)
- REQUIRES(Locks::heap_bitmap_lock_, !mark_stack_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
+ REQUIRES(Locks::heap_bitmap_lock_)
+ REQUIRES(!mark_stack_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
// Used to Get around thread safety annotations. The call is from MarkingPhase and is guarded by
// IsExclusiveHeld.
@@ -293,23 +352,15 @@
std::unique_ptr<MemMap> sweep_array_free_buffer_mem_map_;
private:
- friend class AddIfReachesAllocSpaceVisitor; // Used by mod-union table.
friend class CardScanTask;
friend class CheckBitmapVisitor;
friend class CheckReferenceVisitor;
friend class CheckpointMarkThreadRoots;
- friend class art::gc::Heap;
+ friend class Heap;
friend class FifoMarkStackChunk;
friend class MarkObjectVisitor;
template<bool kUseFinger> friend class MarkStackTask;
friend class MarkSweepMarkObjectSlowPath;
- friend class ModUnionCheckReferences;
- friend class ModUnionClearCardVisitor;
- friend class ModUnionReferenceVisitor;
- friend class ModUnionScanImageRootVisitor;
- friend class ModUnionTableBitmap;
- friend class ModUnionTableReferenceCache;
- friend class ModUnionVisitor;
friend class VerifyRootMarkedVisitor;
friend class VerifyRootVisitor;
diff --git a/runtime/gc/collector/semi_space.cc b/runtime/gc/collector/semi_space.cc
index ed63ed0..7f57f30 100644
--- a/runtime/gc/collector/semi_space.cc
+++ b/runtime/gc/collector/semi_space.cc
@@ -248,6 +248,7 @@
ReaderMutexLock mu(self_, *Locks::heap_bitmap_lock_);
SweepSystemWeaks();
}
+ Runtime::Current()->GetClassLinker()->CleanupClassLoaders();
// Revoke buffers before measuring how many objects were moved since the TLABs need to be revoked
// before they are properly counted.
RevokeAllThreadLocalBuffers();
diff --git a/runtime/gc/collector/sticky_mark_sweep.cc b/runtime/gc/collector/sticky_mark_sweep.cc
index 5be3db7..6c32658 100644
--- a/runtime/gc/collector/sticky_mark_sweep.cc
+++ b/runtime/gc/collector/sticky_mark_sweep.cc
@@ -25,8 +25,7 @@
namespace collector {
StickyMarkSweep::StickyMarkSweep(Heap* heap, bool is_concurrent, const std::string& name_prefix)
- : PartialMarkSweep(heap, is_concurrent,
- name_prefix.empty() ? "sticky " : name_prefix) {
+ : PartialMarkSweep(heap, is_concurrent, name_prefix.empty() ? "sticky " : name_prefix) {
cumulative_timings_.SetName(GetName());
}
diff --git a/runtime/gc/collector/sticky_mark_sweep.h b/runtime/gc/collector/sticky_mark_sweep.h
index e8f0672..abaf978 100644
--- a/runtime/gc/collector/sticky_mark_sweep.h
+++ b/runtime/gc/collector/sticky_mark_sweep.h
@@ -38,13 +38,15 @@
// alloc space will be marked as immune.
void BindBitmaps() OVERRIDE SHARED_REQUIRES(Locks::mutator_lock_);
- void MarkReachableObjects() OVERRIDE
- SHARED_REQUIRES(Locks::mutator_lock_)
- REQUIRES(Locks::heap_bitmap_lock_);
+ void MarkReachableObjects()
+ OVERRIDE
+ REQUIRES(Locks::heap_bitmap_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
- void Sweep(bool swap_bitmaps) OVERRIDE
- SHARED_REQUIRES(Locks::mutator_lock_)
- REQUIRES(Locks::heap_bitmap_lock_);
+ void Sweep(bool swap_bitmaps)
+ OVERRIDE
+ REQUIRES(Locks::heap_bitmap_lock_)
+ SHARED_REQUIRES(Locks::mutator_lock_);
private:
DISALLOW_IMPLICIT_CONSTRUCTORS(StickyMarkSweep);
diff --git a/runtime/jit/jit_code_cache_test.cc b/runtime/jit/jit_code_cache_test.cc
index a6cbb71..c76dc11 100644
--- a/runtime/jit/jit_code_cache_test.cc
+++ b/runtime/jit/jit_code_cache_test.cc
@@ -49,8 +49,11 @@
ASSERT_TRUE(reserved_code != nullptr);
ASSERT_TRUE(code_cache->ContainsCodePtr(reserved_code));
ASSERT_EQ(code_cache->NumMethods(), 1u);
- ClassLinker* const cl = Runtime::Current()->GetClassLinker();
- ArtMethod* method = &cl->AllocArtMethodArray(soa.Self(), 1)->At(0);
+ Runtime* const runtime = Runtime::Current();
+ ClassLinker* const class_linker = runtime->GetClassLinker();
+ ArtMethod* method = &class_linker->AllocArtMethodArray(soa.Self(),
+ runtime->GetLinearAlloc(),
+ 1)->At(0);
ASSERT_FALSE(code_cache->ContainsMethod(method));
method->SetEntryPointFromQuickCompiledCode(reserved_code);
ASSERT_TRUE(code_cache->ContainsMethod(method));
diff --git a/runtime/mirror/class_loader.h b/runtime/mirror/class_loader.h
index f27b615..c2a65d6 100644
--- a/runtime/mirror/class_loader.h
+++ b/runtime/mirror/class_loader.h
@@ -35,18 +35,31 @@
static constexpr uint32_t InstanceSize() {
return sizeof(ClassLoader);
}
+
ClassLoader* GetParent() SHARED_REQUIRES(Locks::mutator_lock_) {
return GetFieldObject<ClassLoader>(OFFSET_OF_OBJECT_MEMBER(ClassLoader, parent_));
}
+
ClassTable* GetClassTable() SHARED_REQUIRES(Locks::mutator_lock_) {
return reinterpret_cast<ClassTable*>(
GetField64(OFFSET_OF_OBJECT_MEMBER(ClassLoader, class_table_)));
}
+
void SetClassTable(ClassTable* class_table) SHARED_REQUIRES(Locks::mutator_lock_) {
SetField64<false>(OFFSET_OF_OBJECT_MEMBER(ClassLoader, class_table_),
reinterpret_cast<uint64_t>(class_table));
}
+ LinearAlloc* GetAllocator() SHARED_REQUIRES(Locks::mutator_lock_) {
+ return reinterpret_cast<LinearAlloc*>(
+ GetField64(OFFSET_OF_OBJECT_MEMBER(ClassLoader, allocator_)));
+ }
+
+ void SetAllocator(LinearAlloc* allocator) SHARED_REQUIRES(Locks::mutator_lock_) {
+ SetField64<false>(OFFSET_OF_OBJECT_MEMBER(ClassLoader, allocator_),
+ reinterpret_cast<uint64_t>(allocator));
+ }
+
private:
// Visit instance fields of the class loader as well as its associated classes.
// Null class loader is handled by ClassLinker::VisitClassRoots.
@@ -61,6 +74,7 @@
HeapReference<Object> proxyCache_;
// Native pointer to class table, need to zero this out when image writing.
uint32_t padding_ ATTRIBUTE_UNUSED;
+ uint64_t allocator_;
uint64_t class_table_;
friend struct art::ClassLoaderOffsets; // for verifying offset information
diff --git a/runtime/runtime.cc b/runtime/runtime.cc
index 6b144cf..8cba1a9 100644
--- a/runtime/runtime.cc
+++ b/runtime/runtime.cc
@@ -274,9 +274,6 @@
VLOG(jit) << "Deleting jit";
jit_.reset(nullptr);
}
- linear_alloc_.reset();
- arena_pool_.reset();
- low_4gb_arena_pool_.reset();
// Shutdown the fault manager if it was initialized.
fault_manager.Shutdown();
@@ -290,7 +287,13 @@
Thread::Shutdown();
QuasiAtomic::Shutdown();
verifier::MethodVerifier::Shutdown();
+
+ // Destroy allocators before shutting down the MemMap because they may use it.
+ linear_alloc_.reset();
+ low_4gb_arena_pool_.reset();
+ arena_pool_.reset();
MemMap::Shutdown();
+
// TODO: acquire a static mutex on Runtime to avoid racing.
CHECK(instance_ == nullptr || instance_ == this);
instance_ = nullptr;
@@ -941,13 +944,11 @@
// can't be trimmed as easily.
const bool use_malloc = IsAotCompiler();
arena_pool_.reset(new ArenaPool(use_malloc, false));
- if (IsCompiler() && Is64BitInstructionSet(kRuntimeISA)) {
+ if (IsAotCompiler() && Is64BitInstructionSet(kRuntimeISA)) {
// 4gb, no malloc. Explanation in header.
low_4gb_arena_pool_.reset(new ArenaPool(false, true));
- linear_alloc_.reset(new LinearAlloc(low_4gb_arena_pool_.get()));
- } else {
- linear_alloc_.reset(new LinearAlloc(arena_pool_.get()));
}
+ linear_alloc_.reset(CreateLinearAlloc());
BlockSignals();
InitPlatformSignalHandlers();
@@ -1788,4 +1789,10 @@
return verify_ == verifier::VerifyMode::kSoftFail;
}
+LinearAlloc* Runtime::CreateLinearAlloc() {
+ return (IsAotCompiler() && Is64BitInstructionSet(kRuntimeISA))
+ ? new LinearAlloc(low_4gb_arena_pool_.get())
+ : new LinearAlloc(arena_pool_.get());
+}
+
} // namespace art
diff --git a/runtime/runtime.h b/runtime/runtime.h
index a35eac1..6154c34 100644
--- a/runtime/runtime.h
+++ b/runtime/runtime.h
@@ -570,6 +570,9 @@
// Called from class linker.
void SetSentinel(mirror::Object* sentinel) SHARED_REQUIRES(Locks::mutator_lock_);
+ // Create a normal LinearAlloc or low 4gb version if we are 64 bit AOT compiler.
+ LinearAlloc* CreateLinearAlloc();
+
private:
static void InitPlatformSignalHandlers();
diff --git a/runtime/stack.cc b/runtime/stack.cc
index d739743..7f72f8a 100644
--- a/runtime/stack.cc
+++ b/runtime/stack.cc
@@ -840,23 +840,30 @@
} else {
CHECK(declaring_class == nullptr);
}
- auto* runtime = Runtime::Current();
- auto* la = runtime->GetLinearAlloc();
- if (!la->Contains(method)) {
- // Check image space.
- bool in_image = false;
- for (auto& space : runtime->GetHeap()->GetContinuousSpaces()) {
- if (space->IsImageSpace()) {
- auto* image_space = space->AsImageSpace();
- const auto& header = image_space->GetImageHeader();
- const auto* methods = &header.GetMethodsSection();
- if (methods->Contains(reinterpret_cast<const uint8_t*>(method) - image_space->Begin())) {
- in_image = true;
- break;
+ Runtime* const runtime = Runtime::Current();
+ LinearAlloc* const linear_alloc = runtime->GetLinearAlloc();
+ if (!linear_alloc->Contains(method)) {
+ // Check class linker linear allocs.
+ mirror::Class* klass = method->GetDeclaringClass();
+ LinearAlloc* const class_linear_alloc = (klass != nullptr)
+ ? ClassLinker::GetAllocatorForClassLoader(klass->GetClassLoader())
+ : linear_alloc;
+ if (!class_linear_alloc->Contains(method)) {
+ // Check image space.
+ bool in_image = false;
+ for (auto& space : runtime->GetHeap()->GetContinuousSpaces()) {
+ if (space->IsImageSpace()) {
+ auto* image_space = space->AsImageSpace();
+ const auto& header = image_space->GetImageHeader();
+ const auto* methods = &header.GetMethodsSection();
+ if (methods->Contains(reinterpret_cast<const uint8_t*>(method) - image_space->Begin())) {
+ in_image = true;
+ break;
+ }
}
}
+ CHECK(in_image) << PrettyMethod(method) << " not in linear alloc or image";
}
- CHECK(in_image) << PrettyMethod(method) << " not in linear alloc or image";
}
if (cur_quick_frame_ != nullptr) {
method->AssertPcIsWithinQuickCode(cur_quick_frame_pc_);
diff --git a/runtime/thread_pool.cc b/runtime/thread_pool.cc
index d8f80fa..0527d3a 100644
--- a/runtime/thread_pool.cc
+++ b/runtime/thread_pool.cc
@@ -16,7 +16,9 @@
#include "thread_pool.h"
+#include "base/bit_utils.h"
#include "base/casts.h"
+#include "base/logging.h"
#include "base/stl_util.h"
#include "base/time_utils.h"
#include "runtime.h"
@@ -30,10 +32,15 @@
size_t stack_size)
: thread_pool_(thread_pool),
name_(name) {
+ // Add an inaccessible page to catch stack overflow.
+ stack_size += kPageSize;
std::string error_msg;
stack_.reset(MemMap::MapAnonymous(name.c_str(), nullptr, stack_size, PROT_READ | PROT_WRITE,
false, false, &error_msg));
CHECK(stack_.get() != nullptr) << error_msg;
+ CHECK_ALIGNED(stack_->Begin(), kPageSize);
+ int mprotect_result = mprotect(stack_->Begin(), kPageSize, PROT_NONE);
+ CHECK_EQ(mprotect_result, 0) << "Failed to mprotect() bottom page of thread pool worker stack.";
const char* reason = "new thread pool worker thread";
pthread_attr_t attr;
CHECK_PTHREAD_CALL(pthread_attr_init, (&attr), reason);
@@ -92,7 +99,8 @@
while (GetThreadCount() < num_threads) {
const std::string worker_name = StringPrintf("%s worker thread %zu", name_.c_str(),
GetThreadCount());
- threads_.push_back(new ThreadPoolWorker(this, worker_name, ThreadPoolWorker::kDefaultStackSize));
+ threads_.push_back(
+ new ThreadPoolWorker(this, worker_name, ThreadPoolWorker::kDefaultStackSize));
}
// Wait for all of the threads to attach.
creation_barier_.Wait(self);
diff --git a/test/117-nopatchoat/nopatchoat.cc b/test/117-nopatchoat/nopatchoat.cc
index 7eac412..3e533ad 100644
--- a/test/117-nopatchoat/nopatchoat.cc
+++ b/test/117-nopatchoat/nopatchoat.cc
@@ -16,7 +16,10 @@
#include "class_linker.h"
#include "dex_file-inl.h"
+#include "gc/heap.h"
+#include "gc/space/image_space.h"
#include "mirror/class-inl.h"
+#include "runtime.h"
#include "scoped_thread_state_change.h"
#include "thread.h"
@@ -31,6 +34,11 @@
return dex_file.GetOatDexFile();
}
+ static bool isRelocationDeltaZero() {
+ gc::space::ImageSpace* space = Runtime::Current()->GetHeap()->GetImageSpace();
+ return space != nullptr && space->GetImageHeader().GetPatchDelta() == 0;
+ }
+
static bool hasExecutableOat(jclass cls) {
const OatFile::OatDexFile* oat_dex_file = getOatDexFile(cls);
@@ -49,6 +57,10 @@
}
};
+extern "C" JNIEXPORT jboolean JNICALL Java_Main_isRelocationDeltaZero(JNIEnv*, jclass) {
+ return NoPatchoatTest::isRelocationDeltaZero();
+}
+
extern "C" JNIEXPORT jboolean JNICALL Java_Main_hasExecutableOat(JNIEnv*, jclass cls) {
return NoPatchoatTest::hasExecutableOat(cls);
}
diff --git a/test/117-nopatchoat/run b/test/117-nopatchoat/run
index c749c74..c634900 100755
--- a/test/117-nopatchoat/run
+++ b/test/117-nopatchoat/run
@@ -36,8 +36,6 @@
# Make sure we can run without relocation
echo "Run without dex2oat/patchoat"
-# /bin/false is actually not even there for either, so the exec will fail.
-# Unfortunately there is no equivalent to /bin/false in android.
${RUN} ${flags} --runtime-option -Xnodex2oat
# Make sure we can run with the oat file.
diff --git a/test/117-nopatchoat/src/Main.java b/test/117-nopatchoat/src/Main.java
index 223e120..5cca309 100644
--- a/test/117-nopatchoat/src/Main.java
+++ b/test/117-nopatchoat/src/Main.java
@@ -18,9 +18,13 @@
public static void main(String[] args) {
System.loadLibrary(args[0]);
+ // With a relocationDelta of 0, the runtime has no way to determine if the oat file in
+ // ANDROID_DATA has been relocated, since a non-relocated oat file always has a 0 delta.
+ // Hitting this condition should be rare and ideally we would prevent it from happening but
+ // there is no way to do so without major changes to the run-test framework.
boolean executable_correct = (isPic() ?
- hasExecutableOat() == true :
- hasExecutableOat() == isDex2OatEnabled());
+ hasExecutableOat() == true :
+ hasExecutableOat() == (isDex2OatEnabled() || isRelocationDeltaZero()));
System.out.println(
"dex2oat & patchoat are " + ((isDex2OatEnabled()) ? "enabled" : "disabled") +
@@ -50,4 +54,6 @@
private native static boolean hasOat();
private native static boolean hasExecutableOat();
+
+ private native static boolean isRelocationDeltaZero();
}
diff --git a/test/142-classloader2/expected.txt b/test/142-classloader2/expected.txt
new file mode 100644
index 0000000..86f5e22
--- /dev/null
+++ b/test/142-classloader2/expected.txt
@@ -0,0 +1 @@
+Everything OK.
diff --git a/test/142-classloader2/info.txt b/test/142-classloader2/info.txt
new file mode 100644
index 0000000..eb821a8
--- /dev/null
+++ b/test/142-classloader2/info.txt
@@ -0,0 +1 @@
+Check sub-classing of PathClassLoader.
diff --git a/test/142-classloader2/smali/MyPathClassLoader.smali b/test/142-classloader2/smali/MyPathClassLoader.smali
new file mode 100644
index 0000000..553abd4
--- /dev/null
+++ b/test/142-classloader2/smali/MyPathClassLoader.smali
@@ -0,0 +1,13 @@
+# Simple subclass of PathClassLoader with methods overridden.
+# We need to use smali right now to subclass a libcore class, see b/24304298.
+
+.class public LMyPathClassLoader;
+
+.super Ldalvik/system/PathClassLoader;
+
+# Simple forwarding constructor.
+.method public constructor <init>(Ljava/lang/String;Ljava/lang/ClassLoader;)V
+ .registers 3
+ invoke-direct {p0, p1, p2}, Ldalvik/system/PathClassLoader;-><init>(Ljava/lang/String;Ljava/lang/ClassLoader;)V
+ return-void
+.end method
diff --git a/test/142-classloader2/src-ex/A.java b/test/142-classloader2/src-ex/A.java
new file mode 100644
index 0000000..d5fa1f9d
--- /dev/null
+++ b/test/142-classloader2/src-ex/A.java
@@ -0,0 +1,22 @@
+/*
+ * 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.
+ */
+
+/**
+ * Identical class to the main src, except with a different value, so we can distinguish them.
+ */
+public class A {
+ public static String value = "Ex-A";
+}
diff --git a/test/142-classloader2/src/A.java b/test/142-classloader2/src/A.java
new file mode 100644
index 0000000..532df51
--- /dev/null
+++ b/test/142-classloader2/src/A.java
@@ -0,0 +1,22 @@
+/*
+ * 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.
+ */
+
+/**
+ * Main class, with a simple value.
+ */
+public class A {
+ public static String value = "Src-A";
+}
diff --git a/test/142-classloader2/src/Main.java b/test/142-classloader2/src/Main.java
new file mode 100644
index 0000000..86c61eb
--- /dev/null
+++ b/test/142-classloader2/src/Main.java
@@ -0,0 +1,76 @@
+/*
+ * 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.
+ */
+
+import java.lang.reflect.Constructor;
+import java.lang.reflect.Field;
+
+/**
+ * PathClassLoader test.
+ */
+public class Main {
+
+ private static ClassLoader createClassLoader(String dexPath, ClassLoader parent) {
+ try {
+ Class<?> myClassLoaderClass = Class.forName("MyPathClassLoader");
+ Constructor constructor = myClassLoaderClass.getConstructor(String.class,
+ ClassLoader.class);
+ return (ClassLoader)constructor.newInstance(dexPath, parent);
+ } catch (Exception e) {
+ // Ups, not available?!?!
+ throw new RuntimeException(e);
+ }
+ }
+
+ /**
+ * Main entry point.
+ */
+ public static void main(String[] args) throws Exception {
+ // Check the class-path for the second file. We'll use that one as the source of the
+ // new classloader.
+ String cp = System.getProperty("java.class.path");
+ if (cp.split(System.getProperty("path.separator")).length != 1) {
+ throw new IllegalStateException("Didn't find exactly one classpath element in " + cp);
+ }
+ if (!cp.endsWith("classloader2.jar")) {
+ throw new IllegalStateException("Don't understand classpath " + cp);
+ }
+ cp = cp.replace("classloader2.jar", "classloader2-ex.jar");
+
+ ClassLoader myClassLoader = createClassLoader(
+ cp, ClassLoader.getSystemClassLoader().getParent());
+
+ // Now load our test class.
+ Class<?> srcClass = A.class;
+ Class<?> exClass = myClassLoader.loadClass("A");
+
+ // First check: classes should be different.
+ if (srcClass == exClass) {
+ throw new IllegalStateException("Loaded class instances are the same");
+ }
+
+ // Secondary checks: get the static field values and make sure they aren't the same.
+ String srcValue = (String)srcClass.getDeclaredField("value").get(null);
+ if (!"Src-A".equals(srcValue)) {
+ throw new IllegalStateException("Expected Src-A, found " + srcValue);
+ }
+ String exValue = (String)exClass.getDeclaredField("value").get(null);
+ if (!"Ex-A".equals(exValue)) {
+ throw new IllegalStateException("Expected Ex-A, found " + exValue);
+ }
+
+ System.out.println("Everything OK.");
+ }
+}
diff --git a/test/482-checker-loop-back-edge-use/src/Main.java b/test/482-checker-loop-back-edge-use/src/Main.java
index 2cfb04d..6b4da9d 100644
--- a/test/482-checker-loop-back-edge-use/src/Main.java
+++ b/test/482-checker-loop-back-edge-use/src/Main.java
@@ -18,16 +18,27 @@
public class Main {
/// CHECK-START: void Main.loop1(boolean) liveness (after)
- /// CHECK: ParameterValue liveness:2 ranges:{[2,22)} uses:[17,22]
- /// CHECK: Goto liveness:20
+ /// CHECK: <<Arg:z\d+>> ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse:\d+>>)} uses:[<<ArgUse:\d+>>,<<ArgLoopUse>>]
+ /// CHECK: If [<<Arg>>] liveness:<<IfLiv:\d+>>
+ /// CHECK: Goto liveness:<<GotoLiv:\d+>>
+ /// CHECK: Exit
+ /// CHECK-EVAL: <<IfLiv>> + 1 == <<ArgUse>>
+ /// CHECK-EVAL: <<GotoLiv>> + 2 == <<ArgLoopUse>>
+
public static void loop1(boolean incoming) {
while (incoming) {}
}
/// CHECK-START: void Main.loop2(boolean) liveness (after)
- /// CHECK: ParameterValue liveness:4 ranges:{[4,44)} uses:[35,40,44]
- /// CHECK: Goto liveness:38
- /// CHECK: Goto liveness:42
+ /// CHECK: <<Arg:z\d+>> ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse2:\d+>>)} uses:[<<ArgUse:\d+>>,<<ArgLoopUse1:\d+>>,<<ArgLoopUse2>>]
+ /// CHECK: If [<<Arg>>] liveness:<<IfLiv:\d+>>
+ /// CHECK: Goto liveness:<<GotoLiv1:\d+>>
+ /// CHECK: Goto liveness:<<GotoLiv2:\d+>>
+ /// CHECK-EVAL: <<IfLiv>> + 1 == <<ArgUse>>
+ /// CHECK-EVAL: <<GotoLiv1>> < <<GotoLiv2>>
+ /// CHECK-EVAL: <<GotoLiv1>> + 2 == <<ArgLoopUse1>>
+ /// CHECK-EVAL: <<GotoLiv2>> + 2 == <<ArgLoopUse2>>
+
public static void loop2(boolean incoming) {
while (true) {
System.out.println("foo");
@@ -36,11 +47,14 @@
}
/// CHECK-START: void Main.loop3(boolean) liveness (after)
- /// CHECK: ParameterValue liveness:4 ranges:{[4,60)} uses:[56,60]
- /// CHECK: Goto liveness:58
+ /// CHECK: <<Arg:z\d+>> ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse:\d+>>)} uses:[<<ArgUse:\d+>>,<<ArgLoopUse>>]
+ /// CHECK: Goto liveness:<<GotoLiv1:\d+>>
+ /// CHECK: InvokeVirtual [{{l\d+}},<<Arg>>] method_name:java.io.PrintStream.println liveness:<<InvokeLiv:\d+>>
+ /// CHECK: Goto liveness:<<GotoLiv2:\d+>>
+ /// CHECK-EVAL: <<InvokeLiv>> == <<ArgUse>>
+ /// CHECK-EVAL: <<GotoLiv1>> < <<GotoLiv2>>
+ /// CHECK-EVAL: <<GotoLiv2>> + 2 == <<ArgLoopUse>>
- // CHECK-START: void Main.loop3(boolean) liveness (after)
- // CHECK-NOT: Goto liveness:50
public static void loop3(boolean incoming) {
// 'incoming' only needs a use at the outer loop's back edge.
while (System.currentTimeMillis() != 42) {
@@ -49,11 +63,11 @@
}
}
- // CHECK-START: void Main.loop4(boolean) liveness (after)
- // CHECK: ParameterValue liveness:4 ranges:{[4,22)} uses:[22]
+ /// CHECK-START: void Main.loop4(boolean) liveness (after)
+ /// CHECK: <<Arg:z\d+>> ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgUse:\d+>>)} uses:[<<ArgUse>>]
+ /// CHECK: InvokeVirtual [{{l\d+}},<<Arg>>] method_name:java.io.PrintStream.println liveness:<<InvokeLiv:\d+>>
+ /// CHECK-EVAL: <<InvokeLiv>> == <<ArgUse>>
- // CHECK-START: void Main.loop4(boolean) liveness (after)
- // CHECK-NOT: Goto liveness:18
public static void loop4(boolean incoming) {
// 'incoming' has no loop use, so should not have back edge uses.
System.out.println(incoming);
@@ -63,59 +77,98 @@
}
/// CHECK-START: void Main.loop5(boolean) liveness (after)
- /// CHECK: ParameterValue liveness:4 ranges:{[4,54)} uses:[37,46,50,54]
- /// CHECK: Goto liveness:48
- /// CHECK: Goto liveness:52
+ /// CHECK: <<Arg:z\d+>> ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse2:\d+>>)} uses:[<<ArgUse:\d+>>,<<ArgLoopUse1:\d+>>,<<ArgLoopUse2>>]
+ /// CHECK: InvokeVirtual [{{l\d+}},<<Arg>>] method_name:java.io.PrintStream.println liveness:<<InvokeLiv:\d+>>
+ /// CHECK: Goto liveness:<<GotoLiv1:\d+>>
+ /// CHECK: Goto liveness:<<GotoLiv2:\d+>>
+ /// CHECK: Exit
+ /// CHECK-EVAL: <<InvokeLiv>> == <<ArgUse>>
+ /// CHECK-EVAL: <<GotoLiv1>> < <<GotoLiv2>>
+ /// CHECK-EVAL: <<GotoLiv1>> + 2 == <<ArgLoopUse1>>
+ /// CHECK-EVAL: <<GotoLiv2>> + 2 == <<ArgLoopUse2>>
+
public static void loop5(boolean incoming) {
// 'incoming' must have a use at both back edges.
- while (Runtime.getRuntime() != null) {
- while (incoming) {
+ for (long i = System.nanoTime(); i < 42; ++i) {
+ for (long j = System.currentTimeMillis(); j != 42; ++j) {
System.out.println(incoming);
}
}
}
/// CHECK-START: void Main.loop6(boolean) liveness (after)
- /// CHECK: ParameterValue liveness:4 ranges:{[4,50)} uses:[26,50]
- /// CHECK: Goto liveness:48
+ /// CHECK: <<Arg:z\d+>> ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse:\d+>>)} uses:[<<ArgUse:\d+>>,<<ArgLoopUse>>]
+ /// CHECK: InvokeVirtual [{{l\d+}},<<Arg>>] method_name:java.io.PrintStream.println liveness:<<InvokeLiv:\d+>>
+ /// CHECK: Add
+ /// CHECK: Goto liveness:<<GotoLiv1:\d+>>
+ /// CHECK: Add
+ /// CHECK: Goto liveness:<<GotoLiv2:\d+>>
+ /// CHECK: Exit
+ /// CHECK-EVAL: <<InvokeLiv>> == <<ArgUse>>
+ /// CHECK-EVAL: <<GotoLiv1>> < <<GotoLiv2>>
+ /// CHECK-EVAL: <<GotoLiv2>> + 2 == <<ArgLoopUse>>
- /// CHECK-START: void Main.loop6(boolean) liveness (after)
- /// CHECK-NOT: Goto liveness:24
public static void loop6(boolean incoming) {
// 'incoming' must have a use only at the first loop's back edge.
- while (true) {
+ for (long i = System.nanoTime(); i < 42; ++i) {
System.out.println(incoming);
- while (Runtime.getRuntime() != null) {}
+ for (long j = System.currentTimeMillis(); j != 42; ++j) {}
}
}
/// CHECK-START: void Main.loop7(boolean) liveness (after)
- /// CHECK: ParameterValue liveness:4 ranges:{[4,54)} uses:[36,45,50,54]
- /// CHECK: Goto liveness:48
- /// CHECK: Goto liveness:52
+ /// CHECK: <<Arg:z\d+>> ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse2:\d+>>)} uses:[<<ArgUse1:\d+>>,<<ArgUse2:\d+>>,<<ArgLoopUse1:\d+>>,<<ArgLoopUse2>>]
+ /// CHECK: InvokeVirtual [{{l\d+}},<<Arg>>] method_name:java.io.PrintStream.println liveness:<<InvokeLiv:\d+>>
+ /// CHECK: If [<<Arg>>] liveness:<<IfLiv:\d+>>
+ /// CHECK: Goto liveness:<<GotoLiv1:\d+>>
+ /// CHECK: Goto liveness:<<GotoLiv2:\d+>>
+ /// CHECK: Exit
+ /// CHECK-EVAL: <<InvokeLiv>> == <<ArgUse1>>
+ /// CHECK-EVAL: <<IfLiv>> + 1 == <<ArgUse2>>
+ /// CHECK-EVAL: <<GotoLiv1>> < <<GotoLiv2>>
+ /// CHECK-EVAL: <<GotoLiv1>> + 2 == <<ArgLoopUse1>>
+ /// CHECK-EVAL: <<GotoLiv2>> + 2 == <<ArgLoopUse2>>
+
public static void loop7(boolean incoming) {
// 'incoming' must have a use at both back edges.
while (Runtime.getRuntime() != null) {
System.out.println(incoming);
while (incoming) {}
+ System.nanoTime(); // beat back edge splitting
}
}
/// CHECK-START: void Main.loop8() liveness (after)
- /// CHECK: StaticFieldGet liveness:14 ranges:{[14,48)} uses:[39,44,48]
- /// CHECK: Goto liveness:42
- /// CHECK: Goto liveness:46
+ /// CHECK: <<Arg:z\d+>> StaticFieldGet liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse2:\d+>>)} uses:[<<ArgUse:\d+>>,<<ArgLoopUse1:\d+>>,<<ArgLoopUse2>>]
+ /// CHECK: If [<<Arg>>] liveness:<<IfLiv:\d+>>
+ /// CHECK: Goto liveness:<<GotoLiv1:\d+>>
+ /// CHECK: Goto liveness:<<GotoLiv2:\d+>>
+ /// CHECK: Exit
+ /// CHECK-EVAL: <<IfLiv>> + 1 == <<ArgUse>>
+ /// CHECK-EVAL: <<GotoLiv1>> < <<GotoLiv2>>
+ /// CHECK-EVAL: <<GotoLiv1>> + 2 == <<ArgLoopUse1>>
+ /// CHECK-EVAL: <<GotoLiv2>> + 2 == <<ArgLoopUse2>>
+
public static void loop8() {
// 'incoming' must have a use at both back edges.
boolean incoming = field;
while (Runtime.getRuntime() != null) {
+ System.nanoTime(); // beat pre-header creation
while (incoming) {}
+ System.nanoTime(); // beat back edge splitting
}
}
/// CHECK-START: void Main.loop9() liveness (after)
- /// CHECK: StaticFieldGet liveness:26 ranges:{[26,40)} uses:[35,40]
- /// CHECK: Goto liveness:42
+ /// CHECK: <<Arg:z\d+>> StaticFieldGet liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopUse:\d+>>)} uses:[<<ArgUse:\d+>>,<<ArgLoopUse>>]
+ /// CHECK: If [<<Arg>>] liveness:<<IfLiv:\d+>>
+ /// CHECK: Goto liveness:<<GotoLiv1:\d+>>
+ /// CHECK: Goto liveness:<<GotoLiv2:\d+>>
+ /// CHECK: Exit
+ /// CHECK-EVAL: <<IfLiv>> + 1 == <<ArgUse>>
+ /// CHECK-EVAL: <<GotoLiv1>> < <<GotoLiv2>>
+ /// CHECK-EVAL: <<GotoLiv1>> + 2 == <<ArgLoopUse>>
+
public static void loop9() {
while (Runtime.getRuntime() != null) {
// 'incoming' must only have a use in the inner loop.
diff --git a/test/510-checker-try-catch/smali/Builder.smali b/test/510-checker-try-catch/smali/Builder.smali
index 2274ba4..1fde5ed 100644
--- a/test/510-checker-try-catch/smali/Builder.smali
+++ b/test/510-checker-try-catch/smali/Builder.smali
@@ -59,7 +59,7 @@
## CHECK: StoreLocal [v0,<<Minus2>>]
## CHECK: name "<<BCatch3>>"
-## CHECK: predecessors "<<BEnterTry1>>" "<<BExitTry1>>" "<<BEnterTry2>>" "<<BExitTry2>>"
+## CHECK: predecessors "<<BEnterTry1>>" "<<BEnterTry2>>" "<<BExitTry1>>" "<<BExitTry2>>"
## CHECK: successors "<<BReturn>>"
## CHECK: flags "catch_block"
## CHECK: StoreLocal [v0,<<Minus3>>]
@@ -70,18 +70,18 @@
## CHECK: xhandlers "<<BCatch1>>" "<<BCatch3>>"
## CHECK: TryBoundary kind:entry
-## CHECK: name "<<BExitTry1>>"
-## CHECK: predecessors "<<BTry1>>"
-## CHECK: successors "<<BAdd>>"
-## CHECK: xhandlers "<<BCatch1>>" "<<BCatch3>>"
-## CHECK: TryBoundary kind:exit
-
## CHECK: name "<<BEnterTry2>>"
## CHECK: predecessors "<<BAdd>>"
## CHECK: successors "<<BTry2>>"
## CHECK: xhandlers "<<BCatch2>>" "<<BCatch3>>"
## CHECK: TryBoundary kind:entry
+## CHECK: name "<<BExitTry1>>"
+## CHECK: predecessors "<<BTry1>>"
+## CHECK: successors "<<BAdd>>"
+## CHECK: xhandlers "<<BCatch1>>" "<<BCatch3>>"
+## CHECK: TryBoundary kind:exit
+
## CHECK: name "<<BExitTry2>>"
## CHECK: predecessors "<<BTry2>>"
## CHECK: successors "<<BReturn>>"
@@ -121,8 +121,7 @@
goto :return
.end method
-# Test that multiple try-entry blocks are generated if there are multiple entry
-# points into the try block.
+# Tests try-entry block when there are multiple entry points into the try block.
## CHECK-START: int Builder.testMultipleEntries(int, int, int, int) builder (after)
@@ -142,20 +141,20 @@
## CHECK: name "<<BTry1:B\d+>>"
## CHECK: predecessors "<<BEnterTry1>>"
-## CHECK: successors "<<BTry2:B\d+>>"
+## CHECK: successors "<<BExitTry1:B\d+>>"
## CHECK: Div
-## CHECK: name "<<BTry2>>"
-## CHECK: predecessors "<<BEnterTry2>>" "<<BTry1>>"
-## CHECK: successors "<<BExitTry:B\d+>>"
+## CHECK: name "<<BTry2:B\d+>>"
+## CHECK: predecessors "<<BEnterTry2>>"
+## CHECK: successors "<<BExitTry2:B\d+>>"
## CHECK: Div
## CHECK: name "<<BReturn:B\d+>>"
-## CHECK: predecessors "<<BExitTry>>" "<<BCatch:B\d+>>"
+## CHECK: predecessors "<<BExitTry2>>" "<<BCatch:B\d+>>"
## CHECK: Return
## CHECK: name "<<BCatch>>"
-## CHECK: predecessors "<<BEnterTry1>>" "<<BEnterTry2>>" "<<BExitTry>>"
+## CHECK: predecessors "<<BEnterTry1>>" "<<BEnterTry2>>" "<<BExitTry1>>" "<<BExitTry2>>"
## CHECK: successors "<<BReturn>>"
## CHECK: flags "catch_block"
## CHECK: StoreLocal [v0,<<Minus1>>]
@@ -167,12 +166,18 @@
## CHECK: TryBoundary kind:entry
## CHECK: name "<<BEnterTry2>>"
-## CHECK: predecessors "<<BIf>>"
+## CHECK: predecessors "<<BIf>>" "<<BExitTry1>>"
## CHECK: successors "<<BTry2>>"
## CHECK: xhandlers "<<BCatch>>"
## CHECK: TryBoundary kind:entry
-## CHECK: name "<<BExitTry>>"
+## CHECK: name "<<BExitTry1>>"
+## CHECK: predecessors "<<BTry1>>"
+## CHECK: successors "<<BEnterTry2>>"
+## CHECK: xhandlers "<<BCatch>>"
+## CHECK: TryBoundary kind:exit
+
+## CHECK: name "<<BExitTry2>>"
## CHECK: predecessors "<<BTry2>>"
## CHECK: successors "<<BReturn>>"
## CHECK: xhandlers "<<BCatch>>"
@@ -314,18 +319,18 @@
## CHECK: xhandlers "<<BCatch1>>"
## CHECK: TryBoundary kind:entry
-## CHECK: name "<<BExit1>>"
-## CHECK: predecessors "<<BTry1>>"
-## CHECK: successors "<<BEnter2>>"
-## CHECK: xhandlers "<<BCatch1>>"
-## CHECK: TryBoundary kind:exit
-
## CHECK: name "<<BEnter2>>"
## CHECK: predecessors "<<BExit1>>"
## CHECK: successors "<<BTry2>>"
## CHECK: xhandlers "<<BCatch2>>"
## CHECK: TryBoundary kind:entry
+## CHECK: name "<<BExit1>>"
+## CHECK: predecessors "<<BTry1>>"
+## CHECK: successors "<<BEnter2>>"
+## CHECK: xhandlers "<<BCatch1>>"
+## CHECK: TryBoundary kind:exit
+
## CHECK: name "<<BExit2>>"
## CHECK: predecessors "<<BTry2>>"
## CHECK: successors "<<BReturn>>"
@@ -402,18 +407,18 @@
## CHECK: xhandlers "<<BCatch1>>"
## CHECK: TryBoundary kind:entry
-## CHECK: name "<<BExit1>>"
-## CHECK: predecessors "<<BTry1>>"
-## CHECK: successors "<<BReturn>>"
-## CHECK: xhandlers "<<BCatch1>>"
-## CHECK: TryBoundary kind:exit
-
## CHECK: name "<<BEnter2>>"
## CHECK: predecessors "<<BGoto>>"
## CHECK: successors "<<BTry2>>"
## CHECK: xhandlers "<<BCatch2>>"
## CHECK: TryBoundary kind:entry
+## CHECK: name "<<BExit1>>"
+## CHECK: predecessors "<<BTry1>>"
+## CHECK: successors "<<BReturn>>"
+## CHECK: xhandlers "<<BCatch1>>"
+## CHECK: TryBoundary kind:exit
+
## CHECK: name "<<BExit2>>"
## CHECK: predecessors "<<BTry2>>"
## CHECK: successors "<<BEnter1>>"
@@ -483,7 +488,7 @@
## CHECK: StoreLocal [v0,<<Minus1>>]
## CHECK: name "<<BCatchAll>>"
-## CHECK: predecessors "<<BEnter1>>" "<<BExit1>>" "<<BEnter2>>" "<<BExit2>>" "<<BEnter3>>" "<<BExit3>>"
+## CHECK: predecessors "<<BEnter1>>" "<<BEnter2>>" "<<BEnter3>>" "<<BExit1>>" "<<BExit2>>" "<<BExit3>>"
## CHECK: successors "<<BReturn>>"
## CHECK: flags "catch_block"
## CHECK: StoreLocal [v0,<<Minus2>>]
@@ -494,30 +499,30 @@
## CHECK: xhandlers "<<BCatchAll>>"
## CHECK: TryBoundary kind:entry
-## CHECK: name "<<BExit1>>"
-## CHECK: predecessors "<<BTry1>>"
-## CHECK: successors "<<BEnter2>>"
-## CHECK: xhandlers "<<BCatchAll>>"
-## CHECK: TryBoundary kind:exit
-
## CHECK: name "<<BEnter2>>"
## CHECK: predecessors "<<BExit1>>"
## CHECK: successors "<<BTry2>>"
## CHECK: xhandlers "<<BCatchArith>>" "<<BCatchAll>>"
## CHECK: TryBoundary kind:entry
-## CHECK: name "<<BExit2>>"
-## CHECK: predecessors "<<BTry2>>"
-## CHECK: successors "<<BEnter3>>"
-## CHECK: xhandlers "<<BCatchArith>>" "<<BCatchAll>>"
-## CHECK: TryBoundary kind:exit
-
## CHECK: name "<<BEnter3>>"
## CHECK: predecessors "<<BExit2>>"
## CHECK: successors "<<BTry3>>"
## CHECK: xhandlers "<<BCatchAll>>"
## CHECK: TryBoundary kind:entry
+## CHECK: name "<<BExit1>>"
+## CHECK: predecessors "<<BTry1>>"
+## CHECK: successors "<<BEnter2>>"
+## CHECK: xhandlers "<<BCatchAll>>"
+## CHECK: TryBoundary kind:exit
+
+## CHECK: name "<<BExit2>>"
+## CHECK: predecessors "<<BTry2>>"
+## CHECK: successors "<<BEnter3>>"
+## CHECK: xhandlers "<<BCatchArith>>" "<<BCatchAll>>"
+## CHECK: TryBoundary kind:exit
+
## CHECK: name "<<BExit3>>"
## CHECK: predecessors "<<BTry3>>"
## CHECK: successors "<<BReturn>>"
@@ -577,7 +582,7 @@
## CHECK: Div
## CHECK: name "<<BCatch>>"
-## CHECK: predecessors "<<BEnterTry1>>" "<<BExitTry1>>" "<<BEnterTry2>>" "<<BExitTry2>>"
+## CHECK: predecessors "<<BEnterTry1>>" "<<BEnterTry2>>" "<<BExitTry1>>" "<<BExitTry2>>"
## CHECK: successors "<<BReturn>>"
## CHECK: flags "catch_block"
## CHECK: StoreLocal [v0,<<Minus1>>]
@@ -588,18 +593,18 @@
## CHECK: xhandlers "<<BCatch>>"
## CHECK: TryBoundary kind:entry
-## CHECK: name "<<BExitTry1>>"
-## CHECK: predecessors "<<BTry1>>"
-## CHECK: successors "<<BOutside>>"
-## CHECK: xhandlers "<<BCatch>>"
-## CHECK: TryBoundary kind:exit
-
## CHECK: name "<<BEnterTry2>>"
## CHECK: predecessors "<<BOutside>>"
## CHECK: successors "<<BTry2>>"
## CHECK: xhandlers "<<BCatch>>"
## CHECK: TryBoundary kind:entry
+## CHECK: name "<<BExitTry1>>"
+## CHECK: predecessors "<<BTry1>>"
+## CHECK: successors "<<BOutside>>"
+## CHECK: xhandlers "<<BCatch>>"
+## CHECK: TryBoundary kind:exit
+
## CHECK: name "<<BExitTry2>>"
## CHECK: predecessors "<<BTry2>>"
## CHECK: successors "<<BReturn>>"
@@ -647,21 +652,21 @@
## CHECK: name "<<BTry1:B\d+>>"
## CHECK: predecessors "<<BEnterTry1>>"
-## CHECK: successors "<<BTry2:B\d+>>"
+## CHECK: successors "<<BExitTry1:B\d+>>"
## CHECK: Div
-## CHECK: name "<<BTry2>>"
-## CHECK: predecessors "<<BEnterTry2>>" "<<BTry1>>"
-## CHECK: successors "<<BExitTry:B\d+>>"
+## CHECK: name "<<BTry2:B\d+>>"
+## CHECK: predecessors "<<BEnterTry2>>"
+## CHECK: successors "<<BExitTry2:B\d+>>"
## CHECK: Div
## CHECK: name "<<BOutside>>"
-## CHECK: predecessors "<<BPSwitch1>>" "<<BExitTry>>"
+## CHECK: predecessors "<<BPSwitch1>>" "<<BExitTry2>>"
## CHECK: successors "<<BCatchReturn:B\d+>>"
## CHECK: Div
## CHECK: name "<<BCatchReturn>>"
-## CHECK: predecessors "<<BOutside>>" "<<BEnterTry1>>" "<<BEnterTry2>>" "<<BExitTry>>"
+## CHECK: predecessors "<<BOutside>>" "<<BEnterTry1>>" "<<BEnterTry2>>" "<<BExitTry1>>" "<<BExitTry2>>"
## CHECK: flags "catch_block"
## CHECK: Return
@@ -677,7 +682,13 @@
## CHECK: xhandlers "<<BCatchReturn>>"
## CHECK: TryBoundary kind:entry
-## CHECK: name "<<BExitTry>>"
+## CHECK: name "<<BExitTry1>>"
+## CHECK: predecessors "<<BTry1>>"
+## CHECK: successors "<<BEnterTry2>>"
+## CHECK: xhandlers "<<BCatchReturn>>"
+## CHECK: TryBoundary kind:exit
+
+## CHECK: name "<<BExitTry2>>"
## CHECK: predecessors "<<BTry2>>"
## CHECK: successors "<<BOutside>>"
## CHECK: xhandlers "<<BCatchReturn>>"
@@ -741,7 +752,7 @@
## CHECK: Div
## CHECK: name "<<BCatchReturn>>"
-## CHECK: predecessors "<<BOutside>>" "<<BEnterTry1>>" "<<BExitTry1>>" "<<BEnterTry2>>" "<<BExitTry2>>"
+## CHECK: predecessors "<<BOutside>>" "<<BEnterTry1>>" "<<BEnterTry2>>" "<<BExitTry1>>" "<<BExitTry2>>"
## CHECK: flags "catch_block"
## CHECK: Return
@@ -751,18 +762,18 @@
## CHECK: xhandlers "<<BCatchReturn>>"
## CHECK: TryBoundary kind:entry
-## CHECK: name "<<BExitTry1>>"
-## CHECK: predecessors "<<BPSwitch0>>"
-## CHECK: successors "<<BPSwitch1>>"
-## CHECK: xhandlers "<<BCatchReturn>>"
-## CHECK: TryBoundary kind:exit
-
## CHECK: name "<<BEnterTry2>>"
## CHECK: predecessors "<<BPSwitch1>>"
## CHECK: successors "<<BTry1>>"
## CHECK: xhandlers "<<BCatchReturn>>"
## CHECK: TryBoundary kind:entry
+## CHECK: name "<<BExitTry1>>"
+## CHECK: predecessors "<<BPSwitch0>>"
+## CHECK: successors "<<BPSwitch1>>"
+## CHECK: xhandlers "<<BCatchReturn>>"
+## CHECK: TryBoundary kind:exit
+
## CHECK: name "<<BExitTry2>>"
## CHECK: predecessors "<<BTry2>>"
## CHECK: successors "<<BOutside>>"
@@ -907,7 +918,7 @@
## CHECK: Div
## CHECK: name "<<BCatch:B\d+>>"
-## CHECK: predecessors "<<BExitTry1>>" "<<BEnterTry1>>" "<<BExitTry1>>" "<<BEnterTry2:B\d+>>" "<<BExitTry2:B\d+>>"
+## CHECK: predecessors "<<BExitTry1>>" "<<BEnterTry1>>" "<<BEnterTry2:B\d+>>" "<<BExitTry1>>" "<<BExitTry2:B\d+>>"
## CHECK: successors "<<BEnterTry2>>"
## CHECK: flags "catch_block"
@@ -928,18 +939,18 @@
## CHECK: xhandlers "<<BCatch>>"
## CHECK: TryBoundary kind:entry
-## CHECK: name "<<BExitTry1>>"
-## CHECK: predecessors "<<BTry1>>"
-## CHECK: successors "<<BCatch>>"
-## CHECK: xhandlers "<<BCatch>>"
-## CHECK: TryBoundary kind:exit
-
## CHECK: name "<<BEnterTry2>>"
## CHECK: predecessors "<<BCatch>>"
## CHECK: successors "<<BTry2>>"
## CHECK: xhandlers "<<BCatch>>"
## CHECK: TryBoundary kind:entry
+## CHECK: name "<<BExitTry1>>"
+## CHECK: predecessors "<<BTry1>>"
+## CHECK: successors "<<BCatch>>"
+## CHECK: xhandlers "<<BCatch>>"
+## CHECK: TryBoundary kind:exit
+
## CHECK: name "<<BExitTry2>>"
## CHECK: predecessors "<<BTry2>>"
## CHECK: successors "<<BReturn>>"
@@ -1001,18 +1012,18 @@
## CHECK: xhandlers "<<BCatch2>>"
## CHECK: TryBoundary kind:entry
-## CHECK: name "<<BExitTry1>>"
-## CHECK: predecessors "<<BTry1>>"
-## CHECK: successors "<<BCatch2>>"
-## CHECK: xhandlers "<<BCatch2>>"
-## CHECK: TryBoundary kind:exit
-
## CHECK: name "<<BEnterTry2>>"
## CHECK: predecessors "<<BCatch2>>"
## CHECK: successors "<<BTry2>>"
## CHECK: xhandlers "<<BCatch1>>"
## CHECK: TryBoundary kind:entry
+## CHECK: name "<<BExitTry1>>"
+## CHECK: predecessors "<<BTry1>>"
+## CHECK: successors "<<BCatch2>>"
+## CHECK: xhandlers "<<BCatch2>>"
+## CHECK: TryBoundary kind:exit
+
## CHECK: name "<<BExitTry2>>"
## CHECK: predecessors "<<BTry2>>"
## CHECK: successors "<<BReturn>>"
@@ -1037,6 +1048,52 @@
return p0
.end method
+# Test graph with try/catch inside a loop.
+
+## CHECK-START: int Builder.testTryInLoop(int, int) builder (after)
+
+## CHECK: name "B0"
+## CHECK: successors "<<BEnterTry:B\d+>>"
+
+## CHECK: name "<<BTry:B\d+>>"
+## CHECK: predecessors "<<BEnterTry>>"
+## CHECK: successors "<<BExitTry:B\d+>>"
+## CHECK: Div
+
+## CHECK: name "<<BCatch:B\d+>>"
+## CHECK: predecessors "<<BEnterTry>>" "<<BExitTry>>"
+## CHECK: successors "<<BEnterTry>>"
+## CHECK: flags "catch_block"
+
+## CHECK: name "<<BExit:B\d+>>"
+## CHECK-NOT: predecessors "{{B\d+}}"
+## CHECK: end_block
+
+## CHECK: name "<<BEnterTry>>"
+## CHECK: predecessors "B0"
+## CHECK: successors "<<BTry>>"
+## CHECK: xhandlers "<<BCatch>>"
+## CHECK: TryBoundary kind:entry
+
+## CHECK: name "<<BExitTry>>"
+## CHECK: predecessors "<<BTry>>"
+## CHECK: successors "<<BEnterTry>>"
+## CHECK: xhandlers "<<BCatch>>"
+## CHECK: TryBoundary kind:exit
+
+.method public static testTryInLoop(II)I
+ .registers 3
+
+ :try_start
+ div-int/2addr p0, p1
+ goto :try_start
+ :try_end
+ .catchall {:try_start .. :try_end} :catch_all
+
+ :catch_all
+ goto :try_start
+.end method
+
# Test that a MOVE_RESULT instruction is placed into the same block as the
# INVOKE it follows, even if there is a try boundary between them.
diff --git a/test/530-checker-loops/src/Main.java b/test/530-checker-loops/src/Main.java
index e518a61..1c5b5d6 100644
--- a/test/530-checker-loops/src/Main.java
+++ b/test/530-checker-loops/src/Main.java
@@ -62,6 +62,19 @@
return result;
}
+ /// CHECK-START: int Main.linearVeryObscure(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearVeryObscure(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearVeryObscure(int[] x) {
+ int result = 0;
+ for (int i = 0; i < x.length; i++) {
+ int k = (-i) + (i << 5) + i - (32 * i) + 5 + (int) i;
+ result += x[k - 5];
+ }
+ return result;
+ }
+
/// CHECK-START: int Main.linearWhile(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearWhile(int[]) BCE (after)
@@ -75,6 +88,42 @@
return result;
}
+ /// CHECK-START: int Main.linearThreeWayPhi(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearThreeWayPhi(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearThreeWayPhi(int[] x) {
+ int result = 0;
+ for (int i = 0; i < x.length; ) {
+ if (x[i] == 5) {
+ i++;
+ continue;
+ }
+ result += x[i++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearFourWayPhi(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearFourWayPhi(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearFourWayPhi(int[] x) {
+ int result = 0;
+ for (int i = 0; i < x.length; ) {
+ if (x[i] == 5) {
+ i++;
+ continue;
+ } else if (x[i] == 6) {
+ i++;
+ result += 7;
+ continue;
+ }
+ result += x[i++];
+ }
+ return result;
+ }
+
/// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (after)
@@ -90,6 +139,25 @@
return result;
}
+ /// CHECK-START: int Main.wrapAroundThenLinearThreeWayPhi(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.wrapAroundThenLinearThreeWayPhi(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int wrapAroundThenLinearThreeWayPhi(int[] x) {
+ // Loop with wrap around (length - 1, 0, 1, 2, ..).
+ int w = x.length - 1;
+ int result = 0;
+ for (int i = 0; i < x.length; ) {
+ if (x[w] == 1) {
+ w = i++;
+ continue;
+ }
+ result += x[w];
+ w = i++;
+ }
+ return result;
+ }
+
/// CHECK-START: int[] Main.linearWithParameter(int) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int[] Main.linearWithParameter(int) BCE (after)
@@ -102,6 +170,19 @@
return x;
}
+ /// CHECK-START: int[] Main.linearCopy(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int[] Main.linearCopy(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int[] linearCopy(int x[]) {
+ int n = x.length;
+ int y[] = new int[n];
+ for (int i = 0; i < n; i++) {
+ y[i] = x[i];
+ }
+ return y;
+ }
+
/// CHECK-START: int Main.linearWithCompoundStride() BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearWithCompoundStride() BCE (after)
@@ -126,7 +207,7 @@
int result = 0;
int k = 0;
// Range analysis has no problem with a trip-count defined by a
- // reasonably large positive stride.
+ // reasonably large positive stride far away from upper bound.
for (int i = 1; i <= 10 * 10000000 + 1; i += 10000000) {
result += x[k++];
}
@@ -143,7 +224,7 @@
int k = 0;
// Range analysis conservatively bails due to potential of wrap-around
// arithmetic while computing the trip-count for this very large stride.
- for (int i = 1; i < 2147483647; i += 195225786) {
+ for (int i = 1; i < Integer.MAX_VALUE; i += 195225786) {
result += x[k++];
}
return result;
@@ -158,7 +239,7 @@
int result = 0;
int k = 0;
// Range analysis has no problem with a trip-count defined by a
- // reasonably large negative stride.
+ // reasonably large negative stride far away from lower bound.
for (int i = -1; i >= -10 * 10000000 - 1; i -= 10000000) {
result += x[k++];
}
@@ -175,12 +256,54 @@
int k = 0;
// Range analysis conservatively bails due to potential of wrap-around
// arithmetic while computing the trip-count for this very large stride.
- for (int i = -2; i > -2147483648; i -= 195225786) {
+ for (int i = -2; i > Integer.MIN_VALUE; i -= 195225786) {
result += x[k++];
}
return result;
}
+ /// CHECK-START: int Main.linearForNE() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearForNE() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearForNE() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = 0; i != 10; i++) {
+ result += x[i];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearDoWhile() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearDoWhile() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static int linearDoWhile() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ int i = 0;
+ // TODO: make this work
+ do {
+ result += x[i++];
+ } while (i < 10);
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearShort() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearShort() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static int linearShort() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ // TODO: make this work
+ for (short i = 0; i < 10; i++) {
+ result += x[i];
+ }
+ return result;
+ }
+
/// CHECK-START: int Main.periodicIdiom(int) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.periodicIdiom(int) BCE (after)
@@ -242,6 +365,112 @@
return result;
}
+ /// CHECK-START: int Main.justRightUp1() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightUp1() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightUp1() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MAX_VALUE - 10, k = 0; i < Integer.MAX_VALUE; i++) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justRightUp2() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightUp2() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightUp2() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MAX_VALUE - 10; i < Integer.MAX_VALUE; i++) {
+ result += x[i - Integer.MAX_VALUE + 10];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justRightUp3() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightUp3() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightUp3() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MAX_VALUE - 10, k = 0; i <= Integer.MAX_VALUE - 1; i++) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justOOBUp() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justOOBUp() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static int justOOBUp() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ // Infinite loop!
+ for (int i = Integer.MAX_VALUE - 9, k = 0; i <= Integer.MAX_VALUE; i++) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justRightDown1() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightDown1() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightDown1() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MIN_VALUE + 10, k = 0; i > Integer.MIN_VALUE; i--) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justRightDown2() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightDown2() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightDown2() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MIN_VALUE + 10; i > Integer.MIN_VALUE; i--) {
+ result += x[Integer.MAX_VALUE + i];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justRightDown3() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightDown3() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightDown3() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MIN_VALUE + 10, k = 0; i >= Integer.MIN_VALUE + 1; i--) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justOOBDown() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justOOBDown() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static int justOOBDown() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ // Infinite loop!
+ for (int i = Integer.MIN_VALUE + 9, k = 0; i >= Integer.MIN_VALUE; i--) {
+ result += x[k++];
+ }
+ return result;
+ }
+
//
// Cases that actually go out of bounds. These test cases
// ensure the exceptions are thrown at the right places.
@@ -274,10 +503,18 @@
expectEquals(55, linearDown(x));
expectEquals(0, linearObscure(empty));
expectEquals(55, linearObscure(x));
+ expectEquals(0, linearVeryObscure(empty));
+ expectEquals(55, linearVeryObscure(x));
expectEquals(0, linearWhile(empty));
expectEquals(55, linearWhile(x));
+ expectEquals(0, linearThreeWayPhi(empty));
+ expectEquals(50, linearThreeWayPhi(x));
+ expectEquals(0, linearFourWayPhi(empty));
+ expectEquals(51, linearFourWayPhi(x));
expectEquals(0, wrapAroundThenLinear(empty));
expectEquals(55, wrapAroundThenLinear(x));
+ expectEquals(0, wrapAroundThenLinearThreeWayPhi(empty));
+ expectEquals(54, wrapAroundThenLinearThreeWayPhi(x));
// Linear with parameter.
sResult = 0;
@@ -295,6 +532,16 @@
}
}
+ // Linear copy.
+ expectEquals(0, linearCopy(empty).length);
+ {
+ int[] r = linearCopy(x);
+ expectEquals(x.length, r.length);
+ for (int i = 0; i < x.length; i++) {
+ expectEquals(x[i], r[i]);
+ }
+ }
+
// Linear with non-unit strides.
expectEquals(56, linearWithCompoundStride());
expectEquals(66, linearWithLargePositiveStride());
@@ -302,6 +549,11 @@
expectEquals(66, linearWithLargeNegativeStride());
expectEquals(66, linearWithVeryLargeNegativeStride());
+ // Special forms.
+ expectEquals(55, linearForNE());
+ expectEquals(55, linearDoWhile());
+ expectEquals(55, linearShort());
+
// Periodic adds (1, 3), one at the time.
expectEquals(0, periodicIdiom(-1));
for (int tc = 0; tc < 32; tc++) {
@@ -326,6 +578,28 @@
expectEquals(tc * 16, periodicSequence4(tc));
}
+ // Large bounds.
+ expectEquals(55, justRightUp1());
+ expectEquals(55, justRightUp2());
+ expectEquals(55, justRightUp3());
+ expectEquals(55, justRightDown1());
+ expectEquals(55, justRightDown2());
+ expectEquals(55, justRightDown3());
+ sResult = 0;
+ try {
+ justOOBUp();
+ } catch (ArrayIndexOutOfBoundsException e) {
+ sResult = 1;
+ }
+ expectEquals(1, sResult);
+ sResult = 0;
+ try {
+ justOOBDown();
+ } catch (ArrayIndexOutOfBoundsException e) {
+ sResult = 1;
+ }
+ expectEquals(1, sResult);
+
// Lower bound goes OOB.
sResult = 0;
try {
diff --git a/tools/buildbot-build.sh b/tools/buildbot-build.sh
index eb64994..a670fc7 100755
--- a/tools/buildbot-build.sh
+++ b/tools/buildbot-build.sh
@@ -76,6 +76,8 @@
if [[ $TARGET_PRODUCT == "mips32r2_fp" ]]; then
env="$env USE_CLANG_PLATFORM_BUILD=true"
fi
+ # Disable NINJA for building on target, it does not support the -e option to Makefile.
+ env="$env USE_NINJA=false"
# Use '-e' to force the override of TARGET_GLOBAL_LDFLAGS.
# Also, we build extra tools that will be used by tests, so that
# they are compiled with our own linker.