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
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 486e904..3110427 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 @@
// 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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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