diff options
61 files changed, 2190 insertions, 967 deletions
diff --git a/benchmark/Android.mk b/benchmark/Android.mk index 09aca98337..a4a603ad04 100644 --- a/benchmark/Android.mk +++ b/benchmark/Android.mk @@ -19,6 +19,7 @@ LOCAL_PATH := $(call my-dir) 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 0000000000..f2a256a3e6 --- /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 0000000000..e7ca9ebc1e --- /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 0000000000..f4c059c58b --- /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 72cf978339..3b2d1cc93d 100644 --- a/build/Android.executable.mk +++ b/build/Android.executable.mk @@ -101,7 +101,10 @@ define build-art-executable # 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 955c575198..d9f8fcb43a 100644 --- a/compiler/image_writer.cc +++ b/compiler/image_writer.cc @@ -1362,6 +1362,10 @@ void ImageWriter::FixupObject(Object* orig, Object* copy) { // 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 62f5b9aa52..42b3541912 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 @@ class ValueBound : public ValueObject { 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 @@ class ValueBound : public ValueObject { 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 @@ class ValueBound : public ValueObject { 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 @@ class ValueBound : public ValueObject { *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 @@ class ArrayAccessInsideLoopFinder : public ValueObject { 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 @@ class MonotonicValueRange : public ValueRange { 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 @@ class MonotonicValueRange : public ValueRange { 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 @@ class MonotonicValueRange : public ValueRange { ((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 @@ class MonotonicValueRange : public ValueRange { 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 @@ class MonotonicValueRange : public ValueRange { // 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 @@ class BCEVisitor : public HGraphVisitor { // 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 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { // 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 @@ class BCEVisitor : public HGraphVisitor { // 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 @@ class BCEVisitor : public HGraphVisitor { } 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 @@ class BCEVisitor : public HGraphVisitor { 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 f2bde899d2..e19e74f37a 100644 --- a/compiler/optimizing/builder.cc +++ b/compiler/optimizing/builder.cc @@ -262,22 +262,6 @@ bool HGraphBuilder::SkipCompilation(const DexFile::CodeItem& code_item, 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::CreateBlocksForTryCatch(const DexFile::CodeItem& code_item) } } -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); - - // Link the TryBoundary to the handlers of `try_item`. - for (CatchHandlerIterator it(code_item, try_item); it.HasNext(); it.Next()) { +// 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; +} + +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 @@ void HGraphBuilder::InsertTryBoundaryBlocks(const DexFile::CodeItem& code_item) 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()); + + // 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]; + + // 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); + } + } - // 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; + try_block_info.Put(throwing_block->GetBlockId(), + DexFile::GetTryItems(code_item, try_item_idx)); } } + } - 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 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; } - 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; - } - - // Catch blocks were split earlier and cannot throw. - DCHECK(!try_block->IsCatchBlock()); - - // 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. + } + } + + // 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); + + // 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 @@ bool HGraphBuilder::NeedsAccessCheck(uint32_t type_index) const { 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 @@ void HGraphBuilder::BuildPackedSwitch(const Instruction& instruction, uint32_t d // 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 8d40d69a32..4c8e3d0442 100644 --- a/compiler/optimizing/builder.h +++ b/compiler/optimizing/builder.h @@ -90,6 +90,9 @@ class HGraphBuilder : public ValueObject { 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 @@ class HGraphBuilder : public ValueObject { // 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 @@ class HGraphBuilder : public ValueObject { // 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 411e05f443..d7b1d24887 100644 --- a/compiler/optimizing/code_generator_arm.cc +++ b/compiler/optimizing/code_generator_arm.cc @@ -4953,6 +4953,33 @@ void InstructionCodeGeneratorARM::VisitFakeString(HFakeString* instruction ATTRI // 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 8e1260e821..d175532f4c 100644 --- a/compiler/optimizing/code_generator_arm64.cc +++ b/compiler/optimizing/code_generator_arm64.cc @@ -3540,6 +3540,38 @@ void InstructionCodeGeneratorARM64::VisitFakeString(HFakeString* instruction ATT // 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 f4f53d5f32..8fdd56e0bc 100644 --- a/compiler/optimizing/code_generator_mips64.cc +++ b/compiler/optimizing/code_generator_mips64.cc @@ -3364,5 +3364,38 @@ void InstructionCodeGeneratorMIPS64::VisitFakeString(HFakeString* instruction AT // 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 86cdbdde8c..ab3d1d1924 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -5488,6 +5488,38 @@ void InstructionCodeGeneratorX86::VisitFakeString(HFakeString* instruction ATTRI // 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 b78b017e23..cfce7a0faa 100644 --- a/compiler/optimizing/code_generator_x86_64.cc +++ b/compiler/optimizing/code_generator_x86_64.cc @@ -5203,6 +5203,38 @@ void InstructionCodeGeneratorX86_64::VisitFakeString(HFakeString* instruction AT // 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 7d509a22a6..b322759a6c 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); - - 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); +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()); + + 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 @@ void HDeadCodeElimination::RemoveDeadBlocks() { 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 583da30438..4e1cafee66 100644 --- a/compiler/optimizing/graph_checker.cc +++ b/compiler/optimizing/graph_checker.cc @@ -743,6 +743,22 @@ void SSAChecker::HandleBooleanInput(HInstruction* instruction, size_t input_inde } } +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 0e270dbe18..7ddffc136a 100644 --- a/compiler/optimizing/graph_checker.h +++ b/compiler/optimizing/graph_checker.h @@ -125,6 +125,7 @@ class SSAChecker : public GraphChecker { 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 92c732c0c3..9fb4304450 100644 --- a/compiler/optimizing/induction_var_analysis.cc +++ b/compiler/optimizing/induction_var_analysis.cc @@ -33,17 +33,6 @@ static bool IsLoopInvariant(HLoopInformation* loop, HInstruction* instruction) { } /** - * 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 @@ static void RotateEntryPhiFirst(HLoopInformation* loop, 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 @@ void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* inst } // 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 @@ uint32_t HInductionVarAnalysis::VisitDescendant(HLoopInformation* loop, HInstruc 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 @@ void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) { 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 @@ void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) { 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 @@ void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) { 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::RotatePeriodicInduc 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; - } - return nullptr; +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 a; } HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(InductionInfo* a, @@ -421,47 +414,56 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(Inducti 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; +} - // Solve within a cycle over another entry-phi: add invariants into a periodic. - if (IsEntryPhi(loop, instruction)) { - InductionInfo* a = LookupInfo(loop, instruction->InputAt(0)); +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; + } + + // 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopIn // 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopIn 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 @@ void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, 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 @@ void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop, 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 @@ void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop, // 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 8eccf925c1..190a0db65c 100644 --- a/compiler/optimizing/induction_var_analysis.h +++ b/compiler/optimizing/induction_var_analysis.h @@ -121,26 +121,27 @@ class HInductionVarAnalysis : public HOptimization { 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 @@ class HInductionVarAnalysis : public HOptimization { 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 fca1ca55e5..e519e77f60 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 @@ TEST_F(InductionVarAnalysisTest, FindSecondOrderWrapAroundInduction) { 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 @@ TEST_F(InductionVarAnalysisTest, FindWrapAroundDerivedInduction) { 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 @@ TEST_F(InductionVarAnalysisTest, FindIdiomaticPeriodicInduction) { 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 @@ TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) { 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 @@ TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) { 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 486e904bd1..119a80b6f4 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" -namespace art { +#include <limits> -static bool IsValidConstant32(int32_t c) { - return INT_MIN < c && c < INT_MAX; -} +namespace art { -static bool IsValidConstant64(int64_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(); } -/** 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 @@ HInductionVarAnalysis::InductionInfo* InductionVarRange::GetTripCount(HLoopInfor // 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 @@ HInductionVarAnalysis::InductionInfo* InductionVarRange::GetTripCount(HLoopInfor 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 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, 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 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, return Value(instruction, 1, 0); } -InductionVarRange::Value InductionVarRange::GetMin(HInductionVarAnalysis::InductionInfo* info, - HInductionVarAnalysis::InductionInfo* trip) { - if (info != nullptr) { - switch (info->induction_class) { - case HInductionVarAnalysis::kInvariant: - // Invariants. - switch (info->operation) { - case HInductionVarAnalysis::kNop: // normalized: 0 - DCHECK_EQ(info->op_a, info->op_b); - return Value(0); - 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); - case HInductionVarAnalysis::kMul: - return GetMul(info->op_a, info->op_b, trip, INT_MIN); - case HInductionVarAnalysis::kDiv: - return GetDiv(info->op_a, info->op_b, trip, INT_MIN); - case HInductionVarAnalysis::kFetch: - return GetFetch(info->fetch, trip, INT_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); - 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)); - } - } - return Value(INT_MIN); -} - -InductionVarRange::Value InductionVarRange::GetMax(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: TC - 1 + case HInductionVarAnalysis::kNop: // normalized: 0 or TC-1 DCHECK_EQ(info->op_a, info->op_b); - return SubValue(GetMax(info->op_b, trip), Value(1), INT_MAX); + return is_min ? Value(0) + : SubValue(GetVal(info->op_b, trip, is_min), Value(1)); 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); + 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_MAX); + return GetMul(info->op_a, info->op_b, trip, is_min); case HInductionVarAnalysis::kDiv: - return GetDiv(info->op_a, info->op_b, trip, INT_MAX); + return GetDiv(info->op_a, info->op_b, trip, is_min); case HInductionVarAnalysis::kFetch: - return GetFetch(info->fetch, trip, INT_MAX); + return GetFetch(info->fetch, trip, is_min); } 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); + // 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: - // Maximum over all values in the wrap-around/periodic. - return MaxValue(GetMax(info->op_a, trip), GetMax(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_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 @@ InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2, int32_t 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 @@ InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2, int32_t 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)); - } - 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)); +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_MAX); + return Value(); } } // namespace art diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h index e002e5ff6c..8280c8bedc 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 @@ class InductionVarRange { // 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); - - 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); + bool is_min); + + 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 d3c3518193..5d9a075aef 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 @@ class InductionVarRangeTest : public testing::Test { 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 @@ class InductionVarRangeTest : public testing::Test { 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 @@ class InductionVarRangeTest : public testing::Test { // 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, GetMinMaxPeriodic) { } 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 b2407c520c..ef89932e3b 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::AddBlock(HBasicBlock* block) { } 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::RemoveDeadBlocks(const ArenaBitVector& visited) { } } -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 HBasicBlock::ClearDominanceInformation() { 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 @@ HBasicBlock* HGraph::FindCommonDominator(HBasicBlock* first, HBasicBlock* second 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 @@ HBasicBlock* HBasicBlock::SplitBefore(HInstruction* cursor) { 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 @@ const HTryBoundary* HBasicBlock::ComputeTryEntryOfSuccessors() const { } } +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 @@ void HBasicBlock::DisconnectAndDelete() { // 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 8dd31bef86..6b0ccf8690 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -370,13 +370,7 @@ class HGraph : public ArenaObject<kArenaAllocGraph> { 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 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> { 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 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> { // 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 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> { 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 @@ class HLoopInformationOutwardIterator : public ValueObject { 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 @@ class HCurrentMethod : public HExpression<0> { 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 e6b2a8bb3e..c43e58ffc4 100644 --- a/compiler/optimizing/register_allocator.cc +++ b/compiler/optimizing/register_allocator.cc @@ -1527,10 +1527,10 @@ void RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block, 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 0ef86d80ed..ad8c682b3a 100644 --- a/compiler/optimizing/ssa_builder.cc +++ b/compiler/optimizing/ssa_builder.cc @@ -191,12 +191,6 @@ void DeadPhiHandling::Run() { 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 @@ void SsaBuilder::BuildSsa() { // 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 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) { 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 303e0d5ad4..48f0328dce 100644 --- a/compiler/utils/array_ref.h +++ b/compiler/utils/array_ref.h @@ -161,6 +161,15 @@ class ArrayRef { 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 3cfdc4c80e..e252765eaa 100644 --- a/dex2oat/Android.mk +++ b/dex2oat/Android.mk @@ -58,14 +58,16 @@ endif 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 a208ccf89b..ec2529e18f 100755 --- a/dexdump/Android.mk +++ b/dexdump/Android.mk @@ -34,8 +34,6 @@ LOCAL_C_INCLUDES := $(dexdump_c_includes) 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 d9b210d767..4230cb26b7 100644 --- a/dexdump/dexdump_test.cc +++ b/dexdump/dexdump_test.cc @@ -43,12 +43,7 @@ class DexDumpTest : public CommonRuntimeTest { // 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 bc8a9f4936..6b9c8aa353 100644 --- a/runtime/class_linker.cc +++ b/runtime/class_linker.cc @@ -1318,9 +1318,8 @@ void ClassLinker::VisitClassRoots(RootVisitor* visitor, VisitRootFlags flags) { 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 @@ ClassLinker::~ClassLinker() { 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 @@ void ClassLinker::LoadClass(Thread* self, } } -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 @@ LengthPrefixedArray<ArtMethod>* ClassLinker::AllocArtMethodArray(Thread* self, s 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 @@ LengthPrefixedArray<ArtMethod>* ClassLinker::AllocArtMethodArray(Thread* self, s 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 @@ void ClassLinker::LoadClassMembers(Thread* self, // 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 @@ void ClassLinker::LoadClassMembers(Thread* self, 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 @@ void ClassLinker::LoadClassMembers(Thread* self, 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 @@ void ClassLinker::MoveClassTableToPreZygote() { 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* ClassLinker::CreateProxyClass(ScopedObjectAccessAlreadyRunnable& 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 @@ mirror::Class* ClassLinker::CreateProxyClass(ScopedObjectAccessAlreadyRunnable& 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 @@ mirror::Class* ClassLinker::CreateProxyClass(ScopedObjectAccessAlreadyRunnable& 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 @@ ClassTable* ClassLinker::InsertClassTableForClassLoader(mirror::ClassLoader* cla 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 @@ jobject ClassLinker::CreatePathClassLoader(Thread* self, std::vector<const DexFi 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 @@ void ClassLinker::DropFindArrayClassCache() { 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 fee706625b..f705330b14 100644 --- a/runtime/class_linker.h +++ b/runtime/class_linker.h @@ -403,9 +403,13 @@ class ClassLinker { 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 @@ class ClassLinker { // 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 @@ class ClassLinker { 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 b4ea3b3460..0926ce3f6a 100644 --- a/runtime/class_linker_test.cc +++ b/runtime/class_linker_test.cc @@ -550,6 +550,7 @@ struct StackTraceElementOffsets : public CheckOffsets<mirror::StackTraceElement> 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 399591b93d..468179c9d5 100644 --- a/runtime/gc/collector/concurrent_copying.cc +++ b/runtime/gc/collector/concurrent_copying.cc @@ -457,6 +457,8 @@ void ConcurrentCopying::MarkingPhase() { 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 60f833b349..f561764ce4 100644 --- a/runtime/gc/collector/mark_compact.cc +++ b/runtime/gc/collector/mark_compact.cc @@ -205,6 +205,7 @@ void MarkCompact::MarkingPhase() { 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 56edcc9d09..e72277ffb2 100644 --- a/runtime/gc/collector/mark_sweep-inl.h +++ b/runtime/gc/collector/mark_sweep-inl.h @@ -29,7 +29,8 @@ namespace gc { 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 089f453888..77a288ba68 100644 --- a/runtime/gc/collector/mark_sweep.cc +++ b/runtime/gc/collector/mark_sweep.cc @@ -95,10 +95,13 @@ MarkSweep::MarkSweep(Heap* heap, bool is_concurrent, const std::string& name_pre : 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::RunPhases() { 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::MarkingPhase() { 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::MarkReachableObjects() { 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 @@ bool MarkSweep::IsMarkedHeapReference(mirror::HeapReference<mirror::Object>* ref 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 @@ class MarkSweepMarkObjectSlowPath { 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 @@ void MarkSweep::MarkHeapReference(mirror::HeapReference<mirror::Object>* ref) { } // 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 @@ class VerifyRootMarkedVisitor : public SingleRootVisitor { 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 @@ class ScanObjectVisitor { 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 ScanObjectVisitor { 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 @@ class DelayReferenceReferentVisitor { 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 @@ class MarkStackTask : public Task { 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 @@ class MarkStackTask : public Task { } 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 MarkStackTask : public Task { 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 @@ class MarkStackTask : public Task { 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 @@ class MarkStackTask : public Task { } // 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 MarkStackTask : public Task { 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 @@ class CardScanTask : public MarkStackTask<false> { 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 @@ void MarkSweep::ScanGrayObjects(bool paused, uint8_t minimum_age) { 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 @@ void MarkSweep::ScanGrayObjects(bool paused, uint8_t minimum_age) { 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 @@ void MarkSweep::ScanGrayObjects(bool paused, uint8_t minimum_age) { 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 @@ void MarkSweep::RecursiveMark() { 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 @@ class VerifySystemWeakVisitor : public IsMarkedVisitor { 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 @@ class CheckpointMarkThreadRoots : public Closure, public RootVisitor { } } - 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 @@ void MarkSweep::Sweep(bool swap_bitmaps) { 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 @@ void MarkSweep::DelayReferenceReferent(mirror::Class* klass, mirror::Reference* 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 @@ class MarkVisitor { } 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 371bba531d..8f7df78d53 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 @@ namespace gc { 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 @@ class MarkSweep : public GarbageCollector { 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 @@ class MarkSweep : public GarbageCollector { // 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 @@ class MarkSweep : public GarbageCollector { // 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 @@ class MarkSweep : public GarbageCollector { // 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 @@ class MarkSweep : public GarbageCollector { 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 @@ class MarkSweep : public GarbageCollector { 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 @@ class MarkSweep : public GarbageCollector { 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 @@ class MarkSweep : public GarbageCollector { 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 @@ class MarkSweep : public GarbageCollector { 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 ed63ed049f..7f57f30b27 100644 --- a/runtime/gc/collector/semi_space.cc +++ b/runtime/gc/collector/semi_space.cc @@ -248,6 +248,7 @@ void SemiSpace::MarkingPhase() { 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 5be3db712b..6c32658e43 100644 --- a/runtime/gc/collector/sticky_mark_sweep.cc +++ b/runtime/gc/collector/sticky_mark_sweep.cc @@ -25,8 +25,7 @@ namespace gc { 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 e8f0672426..abaf97845d 100644 --- a/runtime/gc/collector/sticky_mark_sweep.h +++ b/runtime/gc/collector/sticky_mark_sweep.h @@ -38,13 +38,15 @@ class StickyMarkSweep FINAL : public PartialMarkSweep { // 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 Sweep(bool swap_bitmaps) 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 + 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 a6cbb710af..c76dc1110a 100644 --- a/runtime/jit/jit_code_cache_test.cc +++ b/runtime/jit/jit_code_cache_test.cc @@ -49,8 +49,11 @@ TEST_F(JitCodeCacheTest, TestCoverage) { 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 f27b6155ce..c2a65d62e2 100644 --- a/runtime/mirror/class_loader.h +++ b/runtime/mirror/class_loader.h @@ -35,18 +35,31 @@ class MANAGED ClassLoader : public Object { 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 @@ class MANAGED ClassLoader : public Object { 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 6b144cf48b..8cba1a91d7 100644 --- a/runtime/runtime.cc +++ b/runtime/runtime.cc @@ -274,9 +274,6 @@ Runtime::~Runtime() { 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 @@ Runtime::~Runtime() { 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 @@ bool Runtime::Init(const RuntimeOptions& raw_options, bool ignore_unrecognized) // 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 @@ bool Runtime::IsVerificationSoftFail() const { 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 a35eac1af8..6154c34ec5 100644 --- a/runtime/runtime.h +++ b/runtime/runtime.h @@ -570,6 +570,9 @@ class Runtime { // 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 d739743151..7f72f8ab61 100644 --- a/runtime/stack.cc +++ b/runtime/stack.cc @@ -840,23 +840,30 @@ void StackVisitor::SanityCheckFrame() const { } 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 d8f80fa690..0527d3ae14 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 @@ ThreadPoolWorker::ThreadPoolWorker(ThreadPool* thread_pool, const std::string& n 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 @@ ThreadPool::ThreadPool(const char* name, size_t num_threads) 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 7eac412681..3e533ad62e 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 @@ class NoPatchoatTest { 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 @@ class NoPatchoatTest { } }; +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 c749c74345..c634900218 100755 --- a/test/117-nopatchoat/run +++ b/test/117-nopatchoat/run @@ -36,8 +36,6 @@ fi # 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 223e12084d..5cca309847 100644 --- a/test/117-nopatchoat/src/Main.java +++ b/test/117-nopatchoat/src/Main.java @@ -18,9 +18,13 @@ public class Main { 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 @@ public class Main { 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 0000000000..86f5e220e2 --- /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 0000000000..eb821a8ddb --- /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 0000000000..553abd46c9 --- /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 0000000000..d5fa1f9df7 --- /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 0000000000..532df51878 --- /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 0000000000..86c61ebc3a --- /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 2cfb04d652..6b4da9de27 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 @@ public class Main { } /// 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 @@ public class Main { } } - // 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 @@ public class Main { } /// 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 2274ba4d43..1fde5edc23 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 e518a61f88..1c5b5d65b9 100644 --- a/test/530-checker-loops/src/Main.java +++ b/test/530-checker-loops/src/Main.java @@ -62,6 +62,19 @@ public class Main { 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 @@ public class Main { 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 @@ public class Main { 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 @@ public class Main { 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 @@ public class Main { 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 @@ public class Main { 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 @@ public class Main { 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 @@ public class Main { 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 @@ public class Main { 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 @@ public class Main { 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 @@ public class Main { } } + // 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 @@ public class Main { 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 @@ public class Main { 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 eb64994212..a670fc7738 100755 --- a/tools/buildbot-build.sh +++ b/tools/buildbot-build.sh @@ -76,6 +76,8 @@ elif [[ $mode == "target" ]]; then 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. |