diff options
Diffstat (limited to 'compiler/optimizing')
21 files changed, 976 insertions, 641 deletions
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 |