From b3365e0c4cda4f8f19284d2d418db158ab78d810 Mon Sep 17 00:00:00 2001 From: Aart Bik Date: Mon, 21 Sep 2015 14:45:05 -0700 Subject: Various improvements in range analysis. Rationale: Using min/max values for "unknowns" is a bit wasteful, since it eliminates two useful values. Replaced this with additional boolean to make cases more accurate. Added few cases to handle examples found in real-life. Change-Id: I211f8d9a28b1ae79abdb55fb4569716f21d8043b --- compiler/optimizing/induction_var_range.cc | 246 +++++++++++++++-------------- 1 file changed, 125 insertions(+), 121 deletions(-) (limited to 'compiler/optimizing/induction_var_range.cc') 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(c1) + static_cast(c2)); - } - return false; + return CanLongValueFitIntoInt(static_cast(c1) + static_cast(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(c1) - static_cast(c2)); - } - return false; + return CanLongValueFitIntoInt(static_cast(c1) - static_cast(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(c1) * static_cast(c2)); - } - return false; + return CanLongValueFitIntoInt(static_cast(c1) * static_cast(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(c1) / static_cast(c2)); - } - return false; + return c2 != 0 && CanLongValueFitIntoInt(static_cast(c1) / static_cast(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(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 -- cgit v1.2.3-59-g8ed1b