summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--compiler/optimizing/bounds_check_elimination.cc4
-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
4 files changed, 201 insertions, 191 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/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
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-11-02 02:15:11 +0000