diff options
Diffstat (limited to 'compiler/optimizing')
20 files changed, 784 insertions, 429 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 274a2a699f..9d70124a4c 100644 --- a/compiler/optimizing/builder.cc +++ b/compiler/optimizing/builder.cc @@ -1685,6 +1685,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 +1723,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 ae452f2589..7f87df6df2 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 @@ -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 d431acfb53..d7b1d24887 100644 --- a/compiler/optimizing/code_generator_arm.cc +++ b/compiler/optimizing/code_generator_arm.cc @@ -4477,7 +4477,11 @@ void InstructionCodeGeneratorARM::VisitInstanceOf(HInstanceOf* instruction) { break; } case TypeCheckKind::kArrayObjectCheck: { - // Just need to check that the object's class is a non primitive array. + // Do an exact check. + Label exact_check; + __ cmp(out, ShifterOperand(cls)); + __ b(&exact_check, EQ); + // Otherwise, we need to check that the object's class is a non primitive array. __ LoadFromOffset(kLoadWord, out, out, component_offset); __ MaybeUnpoisonHeapReference(out); // If `out` is null, we use it for the result, and jump to `done`. @@ -4485,6 +4489,7 @@ void InstructionCodeGeneratorARM::VisitInstanceOf(HInstanceOf* instruction) { __ LoadFromOffset(kLoadUnsignedHalfword, out, out, primitive_offset); static_assert(Primitive::kPrimNot == 0, "Expected 0 for kPrimNot"); __ CompareAndBranchIfNonZero(out, &zero); + __ Bind(&exact_check); __ LoadImmediate(out, 1); __ b(&done); break; @@ -4623,20 +4628,22 @@ void InstructionCodeGeneratorARM::VisitCheckCast(HCheckCast* instruction) { } case TypeCheckKind::kClassHierarchyCheck: { // Walk over the class hierarchy to find a match. - Label loop, success; + Label loop; __ Bind(&loop); __ cmp(temp, ShifterOperand(cls)); - __ b(&success, EQ); + __ b(&done, EQ); __ LoadFromOffset(kLoadWord, temp, temp, super_offset); __ MaybeUnpoisonHeapReference(temp); __ CompareAndBranchIfNonZero(temp, &loop); // Jump to the slow path to throw the exception. __ b(slow_path->GetEntryLabel()); - __ Bind(&success); break; } case TypeCheckKind::kArrayObjectCheck: { - // Just need to check that the object's class is a non primitive array. + // Do an exact check. + __ cmp(temp, ShifterOperand(cls)); + __ b(&done, EQ); + // Otherwise, we need to check that the object's class is a non primitive array. __ LoadFromOffset(kLoadWord, temp, temp, component_offset); __ MaybeUnpoisonHeapReference(temp); __ CompareAndBranchIfZero(temp, slow_path->GetEntryLabel()); @@ -4946,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 580e93e9c4..d175532f4c 100644 --- a/compiler/optimizing/code_generator_arm64.cc +++ b/compiler/optimizing/code_generator_arm64.cc @@ -2342,7 +2342,11 @@ void InstructionCodeGeneratorARM64::VisitInstanceOf(HInstanceOf* instruction) { break; } case TypeCheckKind::kArrayObjectCheck: { - // Just need to check that the object's class is a non primitive array. + // Do an exact check. + vixl::Label exact_check; + __ Cmp(out, cls); + __ B(eq, &exact_check); + // Otherwise, we need to check that the object's class is a non primitive array. __ Ldr(out, HeapOperand(out, component_offset)); GetAssembler()->MaybeUnpoisonHeapReference(out); // If `out` is null, we use it for the result, and jump to `done`. @@ -2350,6 +2354,7 @@ void InstructionCodeGeneratorARM64::VisitInstanceOf(HInstanceOf* instruction) { __ Ldrh(out, HeapOperand(out, primitive_offset)); static_assert(Primitive::kPrimNot == 0, "Expected 0 for kPrimNot"); __ Cbnz(out, &zero); + __ Bind(&exact_check); __ Mov(out, 1); __ B(&done); break; @@ -2489,20 +2494,22 @@ void InstructionCodeGeneratorARM64::VisitCheckCast(HCheckCast* instruction) { } case TypeCheckKind::kClassHierarchyCheck: { // Walk over the class hierarchy to find a match. - vixl::Label loop, success; + vixl::Label loop; __ Bind(&loop); __ Cmp(temp, cls); - __ B(eq, &success); + __ B(eq, &done); __ Ldr(temp, HeapOperand(temp, super_offset)); GetAssembler()->MaybeUnpoisonHeapReference(temp); __ Cbnz(temp, &loop); // Jump to the slow path to throw the exception. __ B(slow_path->GetEntryLabel()); - __ Bind(&success); break; } case TypeCheckKind::kArrayObjectCheck: { - // Just need to check that the object's class is a non primitive array. + // Do an exact check. + __ Cmp(temp, cls); + __ B(eq, &done); + // Otherwise, we need to check that the object's class is a non primitive array. __ Ldr(temp, HeapOperand(temp, component_offset)); GetAssembler()->MaybeUnpoisonHeapReference(temp); __ Cbz(temp, slow_path->GetEntryLabel()); @@ -3533,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 3d03dd8146..ab3d1d1924 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -1314,7 +1314,7 @@ void InstructionCodeGeneratorX86::VisitCondition(HCondition* cond) { default: { // Integer case. - // Clear output register: setcc only sets the low byte. + // Clear output register: setb only sets the low byte. __ xorl(reg, reg); if (rhs.IsRegister()) { @@ -5038,6 +5038,7 @@ void InstructionCodeGeneratorX86::VisitInstanceOf(HInstanceOf* instruction) { DCHECK(cls.IsStackSlot()) << cls; __ cmpl(out, Address(ESP, cls.GetStackIndex())); } + // Classes must be equal for the instanceof to succeed. __ j(kNotEqual, &zero); __ movl(out, Immediate(1)); @@ -5092,7 +5093,16 @@ void InstructionCodeGeneratorX86::VisitInstanceOf(HInstanceOf* instruction) { break; } case TypeCheckKind::kArrayObjectCheck: { - // Just need to check that the object's class is a non primitive array. + // Do an exact check. + NearLabel exact_check; + if (cls.IsRegister()) { + __ cmpl(out, cls.AsRegister<Register>()); + } else { + DCHECK(cls.IsStackSlot()) << cls; + __ cmpl(out, Address(ESP, cls.GetStackIndex())); + } + __ j(kEqual, &exact_check); + // Otherwise, we need to check that the object's class is a non primitive array. __ movl(out, Address(out, component_offset)); __ MaybeUnpoisonHeapReference(out); __ testl(out, out); @@ -5100,6 +5110,7 @@ void InstructionCodeGeneratorX86::VisitInstanceOf(HInstanceOf* instruction) { __ j(kEqual, &done); __ cmpw(Address(out, primitive_offset), Immediate(Primitive::kPrimNot)); __ j(kNotEqual, &zero); + __ Bind(&exact_check); __ movl(out, Immediate(1)); __ jmp(&done); break; @@ -5255,7 +5266,7 @@ void InstructionCodeGeneratorX86::VisitCheckCast(HCheckCast* instruction) { } case TypeCheckKind::kClassHierarchyCheck: { // Walk over the class hierarchy to find a match. - NearLabel loop, success; + NearLabel loop; __ Bind(&loop); if (cls.IsRegister()) { __ cmpl(temp, cls.AsRegister<Register>()); @@ -5263,18 +5274,25 @@ void InstructionCodeGeneratorX86::VisitCheckCast(HCheckCast* instruction) { DCHECK(cls.IsStackSlot()) << cls; __ cmpl(temp, Address(ESP, cls.GetStackIndex())); } - __ j(kEqual, &success); + __ j(kEqual, &done); __ movl(temp, Address(temp, super_offset)); __ MaybeUnpoisonHeapReference(temp); __ testl(temp, temp); __ j(kNotEqual, &loop); // Jump to the slow path to throw the exception. __ jmp(slow_path->GetEntryLabel()); - __ Bind(&success); break; } case TypeCheckKind::kArrayObjectCheck: { - // Just need to check that the object's class is a non primitive array. + // Do an exact check. + if (cls.IsRegister()) { + __ cmpl(temp, cls.AsRegister<Register>()); + } else { + DCHECK(cls.IsStackSlot()) << cls; + __ cmpl(temp, Address(ESP, cls.GetStackIndex())); + } + __ j(kEqual, &done); + // Otherwise, we need to check that the object's class is a non primitive array. __ movl(temp, Address(temp, component_offset)); __ MaybeUnpoisonHeapReference(temp); __ testl(temp, temp); @@ -5470,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 32a1db5475..cfce7a0faa 100644 --- a/compiler/optimizing/code_generator_x86_64.cc +++ b/compiler/optimizing/code_generator_x86_64.cc @@ -4766,10 +4766,16 @@ void InstructionCodeGeneratorX86_64::VisitInstanceOf(HInstanceOf* instruction) { DCHECK(cls.IsStackSlot()) << cls; __ cmpl(out, Address(CpuRegister(RSP), cls.GetStackIndex())); } - // Classes must be equal for the instanceof to succeed. - __ j(kNotEqual, &zero); - __ movl(out, Immediate(1)); - __ jmp(&done); + if (zero.IsLinked()) { + // Classes must be equal for the instanceof to succeed. + __ j(kNotEqual, &zero); + __ movl(out, Immediate(1)); + __ jmp(&done); + } else { + __ setcc(kEqual, out); + // setcc only sets the low byte. + __ andl(out, Immediate(1)); + } break; } case TypeCheckKind::kAbstractClassCheck: { @@ -4820,7 +4826,16 @@ void InstructionCodeGeneratorX86_64::VisitInstanceOf(HInstanceOf* instruction) { break; } case TypeCheckKind::kArrayObjectCheck: { - // Just need to check that the object's class is a non primitive array. + // Do an exact check. + NearLabel exact_check; + if (cls.IsRegister()) { + __ cmpl(out, cls.AsRegister<CpuRegister>()); + } else { + DCHECK(cls.IsStackSlot()) << cls; + __ cmpl(out, Address(CpuRegister(RSP), cls.GetStackIndex())); + } + __ j(kEqual, &exact_check); + // Otherwise, we need to check that the object's class is a non primitive array. __ movl(out, Address(out, component_offset)); __ MaybeUnpoisonHeapReference(out); __ testl(out, out); @@ -4828,6 +4843,7 @@ void InstructionCodeGeneratorX86_64::VisitInstanceOf(HInstanceOf* instruction) { __ j(kEqual, &done); __ cmpw(Address(out, primitive_offset), Immediate(Primitive::kPrimNot)); __ j(kNotEqual, &zero); + __ Bind(&exact_check); __ movl(out, Immediate(1)); __ jmp(&done); break; @@ -4983,7 +4999,7 @@ void InstructionCodeGeneratorX86_64::VisitCheckCast(HCheckCast* instruction) { } case TypeCheckKind::kClassHierarchyCheck: { // Walk over the class hierarchy to find a match. - NearLabel loop, success; + NearLabel loop; __ Bind(&loop); if (cls.IsRegister()) { __ cmpl(temp, cls.AsRegister<CpuRegister>()); @@ -4991,18 +5007,25 @@ void InstructionCodeGeneratorX86_64::VisitCheckCast(HCheckCast* instruction) { DCHECK(cls.IsStackSlot()) << cls; __ cmpl(temp, Address(CpuRegister(RSP), cls.GetStackIndex())); } - __ j(kEqual, &success); + __ j(kEqual, &done); __ movl(temp, Address(temp, super_offset)); __ MaybeUnpoisonHeapReference(temp); __ testl(temp, temp); __ j(kNotEqual, &loop); // Jump to the slow path to throw the exception. __ jmp(slow_path->GetEntryLabel()); - __ Bind(&success); break; } case TypeCheckKind::kArrayObjectCheck: { - // Just need to check that the object's class is a non primitive array. + // Do an exact check. + if (cls.IsRegister()) { + __ cmpl(temp, cls.AsRegister<CpuRegister>()); + } else { + DCHECK(cls.IsStackSlot()) << cls; + __ cmpl(temp, Address(CpuRegister(RSP), cls.GetStackIndex())); + } + __ j(kEqual, &done); + // Otherwise, we need to check that the object's class is a non primitive array. __ movl(temp, Address(temp, component_offset)); __ MaybeUnpoisonHeapReference(temp); __ testl(temp, temp); @@ -5180,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..345ff72148 100644 --- a/compiler/optimizing/dead_code_elimination.cc +++ b/compiler/optimizing/dead_code_elimination.cc @@ -41,6 +41,21 @@ static void MarkReachableBlocks(HBasicBlock* block, ArenaBitVector* visited) { DCHECK(condition->AsIntConstant()->IsZero()); MarkReachableBlocks(if_instruction->IfFalseSuccessor(), visited); } + } else if (last_instruction->IsPackedSwitch() && + last_instruction->AsPackedSwitch()->InputAt(0)->IsIntConstant()) { + HPackedSwitch* switch_instruction = last_instruction->AsPackedSwitch(); + int32_t switch_value = switch_instruction->InputAt(0)->AsIntConstant()->GetValue(); + int32_t start_value = switch_instruction->GetStartValue(); + int32_t last_value = start_value + switch_instruction->GetNumEntries(); + for (int32_t case_value = start_value; case_value <= last_value; case_value++) { + if (case_value == last_value) { + MarkReachableBlocks(switch_instruction->GetDefaultBlock(), visited); + } + if (case_value == switch_value) { + MarkReachableBlocks(block->GetSuccessor(case_value - start_value), visited); + break; + } + } } else { for (HBasicBlock* successor : block->GetSuccessors()) { MarkReachableBlocks(successor, visited); 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..012858920f 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -1297,16 +1297,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..52f6e232ea 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -1056,6 +1056,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 +2403,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, int32_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_; } + + int32_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_; + int32_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 a4f1f458fd..9594e3b8e1 100644 --- a/compiler/optimizing/register_allocator.cc +++ b/compiler/optimizing/register_allocator.cc @@ -1528,10 +1528,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 |