summaryrefslogtreecommitdiff
path: root/compiler/optimizing
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/optimizing')
-rw-r--r--compiler/optimizing/bounds_check_elimination.cc4
-rw-r--r--compiler/optimizing/code_generator_arm.cc17
-rw-r--r--compiler/optimizing/code_generator_arm64.cc17
-rw-r--r--compiler/optimizing/code_generator_mips64.cc11
-rw-r--r--compiler/optimizing/code_generator_x86.cc30
-rw-r--r--compiler/optimizing/code_generator_x86_64.cc41
-rw-r--r--compiler/optimizing/induction_var_range.cc246
-rw-r--r--compiler/optimizing/induction_var_range.h45
-rw-r--r--compiler/optimizing/induction_var_range_test.cc97
-rw-r--r--compiler/optimizing/ssa_builder.cc57
-rw-r--r--compiler/optimizing/ssa_builder.h25
11 files changed, 341 insertions, 249 deletions
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 62f5b9aa52..59f3749c8c 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -1165,8 +1165,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);
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 4cf4596791..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());
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 40dfedd3a2..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());
diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc
index f93449e6be..8fdd56e0bc 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -971,11 +971,11 @@ size_t CodeGeneratorMIPS64::RestoreFloatingPointRegister(size_t stack_index, uin
}
void CodeGeneratorMIPS64::DumpCoreRegister(std::ostream& stream, int reg) const {
- stream << Mips64ManagedRegister::FromGpuRegister(GpuRegister(reg));
+ stream << GpuRegister(reg);
}
void CodeGeneratorMIPS64::DumpFloatingPointRegister(std::ostream& stream, int reg) const {
- stream << Mips64ManagedRegister::FromFpuRegister(FpuRegister(reg));
+ stream << FpuRegister(reg);
}
void CodeGeneratorMIPS64::InvokeRuntime(QuickEntrypointEnum entrypoint,
@@ -1444,12 +1444,11 @@ void InstructionCodeGeneratorMIPS64::VisitArrayLength(HArrayLength* instruction)
}
void LocationsBuilderMIPS64::VisitArraySet(HArraySet* instruction) {
- Primitive::Type value_type = instruction->GetComponentType();
- bool is_object = value_type == Primitive::kPrimNot;
+ bool needs_runtime_call = instruction->NeedsTypeCheck();
LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(
instruction,
- is_object ? LocationSummary::kCall : LocationSummary::kNoCall);
- if (is_object) {
+ needs_runtime_call ? LocationSummary::kCall : LocationSummary::kNoCall);
+ if (needs_runtime_call) {
InvokeRuntimeCallingConvention calling_convention;
locations->SetInAt(0, Location::RegisterLocation(calling_convention.GetRegisterAt(0)));
locations->SetInAt(1, Location::RegisterLocation(calling_convention.GetRegisterAt(1)));
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 4b185f03ce..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);
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 7ee974fd11..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);
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 486e904bd1..311042756f 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -20,88 +20,87 @@
namespace art {
-static bool IsValidConstant32(int32_t c) {
- return INT_MIN < c && c < INT_MAX;
+/** Returns true if 64-bit constant fits in 32-bit constant. */
+static bool CanLongValueFitIntoInt(int64_t c) {
+ return INT_MIN <= c && c <= INT_MAX;
}
-static bool IsValidConstant64(int64_t c) {
- return INT_MIN < c && c < INT_MAX;
-}
-
-/** Returns true if 32-bit addition can be done safely (and is not an unknown range). */
+/** Returns true if 32-bit addition can be done safely. */
static bool IsSafeAdd(int32_t c1, int32_t c2) {
- if (IsValidConstant32(c1) && IsValidConstant32(c2)) {
- return IsValidConstant64(static_cast<int64_t>(c1) + static_cast<int64_t>(c2));
- }
- return false;
+ return CanLongValueFitIntoInt(static_cast<int64_t>(c1) + static_cast<int64_t>(c2));
}
-/** Returns true if 32-bit subtraction can be done safely (and is not an unknown range). */
+/** Returns true if 32-bit subtraction can be done safely. */
static bool IsSafeSub(int32_t c1, int32_t c2) {
- if (IsValidConstant32(c1) && IsValidConstant32(c2)) {
- return IsValidConstant64(static_cast<int64_t>(c1) - static_cast<int64_t>(c2));
- }
- return false;
+ return CanLongValueFitIntoInt(static_cast<int64_t>(c1) - static_cast<int64_t>(c2));
}
-/** Returns true if 32-bit multiplication can be done safely (and is not an unknown range). */
+/** Returns true if 32-bit multiplication can be done safely. */
static bool IsSafeMul(int32_t c1, int32_t c2) {
- if (IsValidConstant32(c1) && IsValidConstant32(c2)) {
- return IsValidConstant64(static_cast<int64_t>(c1) * static_cast<int64_t>(c2));
- }
- return false;
+ return CanLongValueFitIntoInt(static_cast<int64_t>(c1) * static_cast<int64_t>(c2));
}
-/** Returns true if 32-bit division can be done safely (and is not an unknown range). */
+/** Returns true if 32-bit division can be done safely. */
static bool IsSafeDiv(int32_t c1, int32_t c2) {
- if (IsValidConstant32(c1) && IsValidConstant32(c2) && c2 != 0) {
- return IsValidConstant64(static_cast<int64_t>(c1) / static_cast<int64_t>(c2));
- }
- return false;
+ return c2 != 0 && CanLongValueFitIntoInt(static_cast<int64_t>(c1) / static_cast<int64_t>(c2));
}
-/** Returns true for 32/64-bit integral constant within known range. */
+/** Returns true for 32/64-bit integral constant. */
static bool IsIntAndGet(HInstruction* instruction, int32_t* value) {
if (instruction->IsIntConstant()) {
- const int32_t c = instruction->AsIntConstant()->GetValue();
- if (IsValidConstant32(c)) {
- *value = c;
- return true;
- }
+ *value = instruction->AsIntConstant()->GetValue();
+ return true;
} else if (instruction->IsLongConstant()) {
const int64_t c = instruction->AsLongConstant()->GetValue();
- if (IsValidConstant64(c)) {
- *value = c;
+ if (CanLongValueFitIntoInt(c)) {
+ *value = static_cast<int32_t>(c);
return true;
}
}
return false;
}
+/**
+ * An upper bound a * (length / a) + b, where a > 0, can be conservatively rewritten as length + b
+ * because length >= 0 is true. This makes it more likely the bound is useful to clients.
+ */
+static InductionVarRange::Value SimplifyMax(InductionVarRange::Value v) {
+ int32_t value;
+ if (v.a_constant > 1 &&
+ v.instruction->IsDiv() &&
+ v.instruction->InputAt(0)->IsArrayLength() &&
+ IsIntAndGet(v.instruction->InputAt(1), &value) && v.a_constant == value) {
+ return InductionVarRange::Value(v.instruction->InputAt(0), 1, v.b_constant);
+ }
+ return v;
+}
+
//
// Public class methods.
//
InductionVarRange::InductionVarRange(HInductionVarAnalysis* induction_analysis)
: induction_analysis_(induction_analysis) {
+ DCHECK(induction_analysis != nullptr);
}
InductionVarRange::Value InductionVarRange::GetMinInduction(HInstruction* context,
HInstruction* instruction) {
HLoopInformation* loop = context->GetBlock()->GetLoopInformation();
- if (loop != nullptr && induction_analysis_ != nullptr) {
+ if (loop != nullptr) {
return GetMin(induction_analysis_->LookupInfo(loop, instruction), GetTripCount(loop, context));
}
- 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(
+ GetMax(induction_analysis_->LookupInfo(loop, instruction), GetTripCount(loop, context)));
}
- return Value(INT_MAX);
+ return Value();
}
//
@@ -113,6 +112,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 +129,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 +137,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);
}
@@ -161,30 +161,29 @@ InductionVarRange::Value InductionVarRange::GetMin(HInductionVarAnalysis::Induct
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);
+ return AddValue(GetMin(info->op_a, trip), GetMin(info->op_b, trip));
case HInductionVarAnalysis::kSub: // second max!
- return SubValue(GetMin(info->op_a, trip), GetMax(info->op_b, trip), INT_MIN);
+ return SubValue(GetMin(info->op_a, trip), GetMax(info->op_b, trip));
case HInductionVarAnalysis::kNeg: // second max!
- return SubValue(Value(0), GetMax(info->op_b, trip), INT_MIN);
+ return SubValue(Value(0), GetMax(info->op_b, trip));
case HInductionVarAnalysis::kMul:
- return GetMul(info->op_a, info->op_b, trip, INT_MIN);
+ return GetMul(info->op_a, info->op_b, trip, true);
case HInductionVarAnalysis::kDiv:
- return GetDiv(info->op_a, info->op_b, trip, INT_MIN);
+ return GetDiv(info->op_a, info->op_b, trip, true);
case HInductionVarAnalysis::kFetch:
- return GetFetch(info->fetch, trip, INT_MIN);
+ return GetFetch(info->fetch, trip, true);
}
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);
+ return AddValue(GetMul(info->op_a, trip, trip, true), GetMin(info->op_b, trip));
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);
+ return Value();
}
InductionVarRange::Value InductionVarRange::GetMax(HInductionVarAnalysis::InductionInfo* info,
@@ -196,96 +195,95 @@ InductionVarRange::Value InductionVarRange::GetMax(HInductionVarAnalysis::Induct
switch (info->operation) {
case HInductionVarAnalysis::kNop: // normalized: TC - 1
DCHECK_EQ(info->op_a, info->op_b);
- return SubValue(GetMax(info->op_b, trip), Value(1), INT_MAX);
+ return SubValue(GetMax(info->op_b, trip), Value(1));
case HInductionVarAnalysis::kAdd:
- return AddValue(GetMax(info->op_a, trip), GetMax(info->op_b, trip), INT_MAX);
+ return AddValue(GetMax(info->op_a, trip), GetMax(info->op_b, trip));
case HInductionVarAnalysis::kSub: // second min!
- return SubValue(GetMax(info->op_a, trip), GetMin(info->op_b, trip), INT_MAX);
+ return SubValue(GetMax(info->op_a, trip), GetMin(info->op_b, trip));
case HInductionVarAnalysis::kNeg: // second min!
- return SubValue(Value(0), GetMin(info->op_b, trip), INT_MAX);
+ return SubValue(Value(0), GetMin(info->op_b, trip));
case HInductionVarAnalysis::kMul:
- return GetMul(info->op_a, info->op_b, trip, INT_MAX);
+ return GetMul(info->op_a, info->op_b, trip, false);
case HInductionVarAnalysis::kDiv:
- return GetDiv(info->op_a, info->op_b, trip, INT_MAX);
+ return GetDiv(info->op_a, info->op_b, trip, false);
case HInductionVarAnalysis::kFetch:
- return GetFetch(info->fetch, trip, INT_MAX);
+ return GetFetch(info->fetch, trip, false);
}
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);
+ return AddValue(GetMul(info->op_a, trip, trip, false), GetMax(info->op_b, trip));
case HInductionVarAnalysis::kWrapAround:
case HInductionVarAnalysis::kPeriodic:
// Maximum over all values in the wrap-around/periodic.
return MaxValue(GetMax(info->op_a, trip), GetMax(info->op_b, trip));
}
}
- return Value(INT_MAX);
+ return Value();
}
InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
- int32_t fail_value) {
+ bool is_min) {
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) {
+ 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) {
+ bool is_min) {
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) {
+ 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 +293,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 +307,49 @@ 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));
+ 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, std::min(v1.b_constant, v2.b_constant));
+ }
}
- return Value(INT_MIN);
+ return Value();
}
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));
+ 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, 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..96cbd46279 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,12 +73,11 @@ 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);
@@ -81,16 +86,16 @@ class InductionVarRange {
static Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
- int32_t fail_value);
+ bool is_min);
static Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
- int32_t fail_value);
+ bool is_min);
- static Value AddValue(Value v1, Value v2, int32_t fail_value);
- static Value SubValue(Value v1, Value v2, int32_t fail_value);
- static Value MulValue(Value v1, Value v2, int32_t fail_value);
- static Value DivValue(Value v1, Value v2, int32_t fail_value);
+ static Value 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 MinValue(Value v1, Value v2);
static Value MaxValue(Value v1, Value v2);
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index d3c3518193..c8abe36119 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -45,6 +45,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. */
@@ -122,19 +123,21 @@ class InductionVarRangeTest : public testing::Test {
}
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 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::MinValue(v1, v2); }
Value MaxValue(Value v1, Value v2) { return InductionVarRange::MaxValue(v1, v2); }
@@ -154,8 +157,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 +254,89 @@ 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)));
+ ExpectEqual(Value(INT_MAX), AddValue(Value(INT_MAX - 5), Value(5)));
+ ExpectEqual(Value(), AddValue(Value(INT_MAX - 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)));
+ ExpectEqual(Value(INT_MIN), SubValue(Value(INT_MIN + 5), Value(5)));
+ ExpectEqual(Value(), SubValue(Value(INT_MIN + 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/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 6f71ea3d6b..0ef86d80ed 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -57,8 +57,13 @@ class DeadPhiHandling : public ValueObject {
};
bool DeadPhiHandling::UpdateType(HPhi* phi) {
+ if (phi->IsDead()) {
+ // Phi was rendered dead while waiting in the worklist because it was replaced
+ // with an equivalent.
+ return false;
+ }
+
Primitive::Type existing = phi->GetType();
- DCHECK(phi->IsLive());
bool conflict = false;
Primitive::Type new_type = existing;
@@ -112,11 +117,26 @@ bool DeadPhiHandling::UpdateType(HPhi* phi) {
phi->SetType(Primitive::kPrimVoid);
phi->SetDead();
return true;
- } else {
- DCHECK(phi->IsLive());
- phi->SetType(new_type);
- return existing != new_type;
+ } else if (existing == new_type) {
+ return false;
+ }
+
+ DCHECK(phi->IsLive());
+ phi->SetType(new_type);
+
+ // There might exist a `new_type` equivalent of `phi` already. In that case,
+ // we replace the equivalent with the, now live, `phi`.
+ HPhi* equivalent = phi->GetNextEquivalentPhiWithSameType();
+ if (equivalent != nullptr) {
+ // There cannot be more than two equivalents with the same type.
+ DCHECK(equivalent->GetNextEquivalentPhiWithSameType() == nullptr);
+ // If doing fix-point iteration, the equivalent might be in `worklist_`.
+ // Setting it dead will make UpdateType skip it.
+ equivalent->SetDead();
+ equivalent->ReplaceWith(phi);
}
+
+ return true;
}
void DeadPhiHandling::VisitBasicBlock(HBasicBlock* block) {
@@ -345,6 +365,33 @@ void SsaBuilder::BuildSsa() {
}
}
+ArenaVector<HInstruction*>* SsaBuilder::GetLocalsFor(HBasicBlock* block) {
+ DCHECK_LT(block->GetBlockId(), locals_for_.size());
+ ArenaVector<HInstruction*>* locals = &locals_for_[block->GetBlockId()];
+ const size_t vregs = GetGraph()->GetNumberOfVRegs();
+ if (locals->empty() && vregs != 0u) {
+ locals->resize(vregs, nullptr);
+
+ if (block->IsCatchBlock()) {
+ ArenaAllocator* arena = GetGraph()->GetArena();
+ // We record incoming inputs of catch phis at throwing instructions and
+ // must therefore eagerly create the phis. Phis for undefined vregs will
+ // be deleted when the first throwing instruction with the vreg undefined
+ // is encountered. Unused phis will be removed by dead phi analysis.
+ for (size_t i = 0; i < vregs; ++i) {
+ // No point in creating the catch phi if it is already undefined at
+ // the first throwing instruction.
+ if ((*current_locals_)[i] != nullptr) {
+ HPhi* phi = new (arena) HPhi(arena, i, 0, Primitive::kPrimVoid);
+ block->AddPhi(phi);
+ (*locals)[i] = phi;
+ }
+ }
+ }
+ }
+ return locals;
+}
+
HInstruction* SsaBuilder::ValueOfLocal(HBasicBlock* block, size_t local) {
ArenaVector<HInstruction*>* locals = GetLocalsFor(block);
DCHECK_LT(local, locals->size());
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index 804296f7ba..79f1a28ac8 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -61,28 +61,9 @@ class SsaBuilder : public HGraphVisitor {
void BuildSsa();
- ArenaVector<HInstruction*>* GetLocalsFor(HBasicBlock* block) {
- DCHECK_LT(block->GetBlockId(), locals_for_.size());
- ArenaVector<HInstruction*>* locals = &locals_for_[block->GetBlockId()];
- if (locals->empty() && GetGraph()->GetNumberOfVRegs() != 0u) {
- const size_t vregs = GetGraph()->GetNumberOfVRegs();
- locals->resize(vregs, nullptr);
-
- if (block->IsCatchBlock()) {
- // We record incoming inputs of catch phis at throwing instructions and
- // must therefore eagerly create the phis. Unused phis will be removed
- // in the dead phi analysis.
- ArenaAllocator* arena = GetGraph()->GetArena();
- for (size_t i = 0; i < vregs; ++i) {
- HPhi* phi = new (arena) HPhi(arena, i, 0, Primitive::kPrimVoid);
- block->AddPhi(phi);
- (*locals)[i] = phi;
- }
- }
- }
- return locals;
- }
-
+ // Returns locals vector for `block`. If it is a catch block, the vector will be
+ // prepopulated with catch phis for vregs which are defined in `current_locals_`.
+ ArenaVector<HInstruction*>* GetLocalsFor(HBasicBlock* block);
HInstruction* ValueOfLocal(HBasicBlock* block, size_t local);
void VisitBasicBlock(HBasicBlock* block);
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-11-01 07:09:47 +0000