Improvements in induction range analysis.
Rationale:
Uses range analysis while determining whether trip-counts
are "safe", which improves analysis of triangular loops.
Also implements more effective triangular loop analysis
by evaluating induction information only once and using
a top level hint (instead of the "iterative refinement"
that was used earlier). Also fixes analysis of triangular
trip counts that may wrap-around. All with tests.
Test: see induction_var_range_test/530-checker-loops*
BUG=27151190
Change-Id: I1877c8ce0c9a52005900eb9dfdbb1918df100278
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index e9fcfe2..d786e82 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -847,7 +847,7 @@
}
// Try index range obtained by induction variable analysis.
// Disables dynamic bce if OOB is certain.
- if (InductionRangeFitsIn(&array_range, bounds_check, index, &try_dynamic_bce)) {
+ if (InductionRangeFitsIn(&array_range, bounds_check, &try_dynamic_bce)) {
ReplaceInstruction(bounds_check, index);
return;
}
@@ -1299,33 +1299,30 @@
* parameter try_dynamic_bce is set to false if OOB is certain.
*/
bool InductionRangeFitsIn(ValueRange* array_range,
- HInstruction* context,
- HInstruction* index,
+ HBoundsCheck* context,
bool* try_dynamic_bce) {
InductionVarRange::Value v1;
InductionVarRange::Value v2;
bool needs_finite_test = false;
- if (induction_range_.GetInductionRange(context, index, &v1, &v2, &needs_finite_test)) {
- do {
- 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);
- ValueRange index_range(GetGraph()->GetArena(),
- ValueBound(v1.instruction, v1.b_constant),
- ValueBound(v2.instruction, v2.b_constant));
- // If analysis reveals a certain OOB, disable dynamic BCE.
- if (index_range.GetLower().LessThan(array_range->GetLower()) ||
- index_range.GetUpper().GreaterThan(array_range->GetUpper())) {
- *try_dynamic_bce = false;
- return false;
- }
- // Use analysis for static bce only if loop is finite.
- if (!needs_finite_test && index_range.FitsIn(array_range)) {
- return true;
- }
+ HInstruction* index = context->InputAt(0);
+ HInstruction* hint = ValueBound::HuntForDeclaration(context->InputAt(1));
+ if (induction_range_.GetInductionRange(context, index, hint, &v1, &v2, &needs_finite_test)) {
+ 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);
+ ValueRange index_range(GetGraph()->GetArena(),
+ ValueBound(v1.instruction, v1.b_constant),
+ ValueBound(v2.instruction, v2.b_constant));
+ // If analysis reveals a certain OOB, disable dynamic BCE. Otherwise,
+ // use analysis for static bce only if loop is finite.
+ if (index_range.GetLower().LessThan(array_range->GetLower()) ||
+ index_range.GetUpper().GreaterThan(array_range->GetUpper())) {
+ *try_dynamic_bce = false;
+ } else if (!needs_finite_test && index_range.FitsIn(array_range)) {
+ return true;
}
- } while (induction_range_.RefineOuter(&v1, &v2));
+ }
}
return false;
}
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index f1965f0..7c74816 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -132,7 +132,7 @@
InductionInfo* a,
InductionInfo* b,
Primitive::Type type) {
- DCHECK(a != nullptr);
+ DCHECK(a != nullptr && b != nullptr);
return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr, type);
}
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index bc920d9..5e587e0 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -73,9 +73,12 @@
return v;
}
-/**
- * Corrects a value for type to account for arithmetic wrap-around in lower precision.
- */
+/** Helper method to test for a constant value. */
+static bool IsConstantValue(InductionVarRange::Value v) {
+ return v.is_known && v.a_constant == 0;
+}
+
+/** Corrects a value for type to account for arithmetic wrap-around in lower precision. */
static InductionVarRange::Value CorrectForType(InductionVarRange::Value v, Primitive::Type type) {
switch (type) {
case Primitive::kPrimShort:
@@ -85,26 +88,15 @@
// TODO: maybe some room for improvement, like allowing widening conversions
const int32_t min = Primitive::MinValueOfIntegralType(type);
const int32_t max = Primitive::MaxValueOfIntegralType(type);
- return (v.is_known && v.a_constant == 0 && min <= v.b_constant && v.b_constant <= max)
+ return (IsConstantValue(v) && min <= v.b_constant && v.b_constant <= max)
? v
: InductionVarRange::Value();
}
default:
- // At int or higher.
return v;
}
}
-/** Helper method to test for a constant value. */
-static bool IsConstantValue(InductionVarRange::Value v) {
- return v.is_known && v.a_constant == 0;
-}
-
-/** Helper method to test for same constant value. */
-static bool IsSameConstantValue(InductionVarRange::Value v1, InductionVarRange::Value v2) {
- return IsConstantValue(v1) && IsConstantValue(v2) && v1.b_constant == v2.b_constant;
-}
-
/** Helper method to insert an instruction. */
static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) {
DCHECK(block != nullptr);
@@ -119,22 +111,22 @@
//
InductionVarRange::InductionVarRange(HInductionVarAnalysis* induction_analysis)
- : induction_analysis_(induction_analysis) {
+ : induction_analysis_(induction_analysis),
+ chase_hint_(nullptr) {
DCHECK(induction_analysis != nullptr);
}
bool InductionVarRange::GetInductionRange(HInstruction* context,
HInstruction* instruction,
+ HInstruction* chase_hint,
/*out*/Value* min_val,
/*out*/Value* max_val,
/*out*/bool* needs_finite_test) {
- HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop
- if (loop == nullptr) {
- return false; // no loop
- }
- HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, instruction);
- if (info == nullptr) {
- return false; // no induction information
+ HLoopInformation* loop = nullptr;
+ HInductionVarAnalysis::InductionInfo* info = nullptr;
+ HInductionVarAnalysis::InductionInfo* trip = nullptr;
+ if (!HasInductionInfo(context, instruction, &loop, &info, &trip)) {
+ return false;
}
// Type int or lower (this is not too restrictive since intended clients, like
// bounds check elimination, will have truncated higher precision induction
@@ -148,45 +140,15 @@
default:
return false;
}
- // Set up loop information.
- HBasicBlock* header = loop->GetHeader();
- bool in_body = context->GetBlock() != header;
- HInductionVarAnalysis::InductionInfo* trip =
- induction_analysis_->LookupInfo(loop, header->GetLastInstruction());
// Find range.
+ chase_hint_ = chase_hint;
+ bool in_body = context->GetBlock() != loop->GetHeader();
*min_val = GetVal(info, trip, in_body, /* is_min */ true);
*max_val = SimplifyMax(GetVal(info, trip, in_body, /* is_min */ false));
*needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip);
return true;
}
-bool InductionVarRange::RefineOuter(/*in-out*/ Value* min_val,
- /*in-out*/ Value* max_val) const {
- if (min_val->instruction != nullptr || max_val->instruction != nullptr) {
- Value v1_min = RefineOuter(*min_val, /* is_min */ true);
- Value v2_max = RefineOuter(*max_val, /* is_min */ false);
- // The refined range is safe if both sides refine the same instruction. Otherwise, since two
- // different ranges are combined, the new refined range is safe to pass back to the client if
- // the extremes of the computed ranges ensure no arithmetic wrap-around anomalies occur.
- if (min_val->instruction != max_val->instruction) {
- Value v1_max = RefineOuter(*min_val, /* is_min */ false);
- Value v2_min = RefineOuter(*max_val, /* is_min */ true);
- if (!IsConstantValue(v1_max) ||
- !IsConstantValue(v2_min) ||
- v1_max.b_constant > v2_min.b_constant) {
- return false;
- }
- }
- // Did something change?
- if (v1_min.instruction != min_val->instruction || v2_max.instruction != max_val->instruction) {
- *min_val = v1_min;
- *max_val = v2_max;
- return true;
- }
- }
- return false;
-}
-
bool InductionVarRange::CanGenerateCode(HInstruction* context,
HInstruction* instruction,
/*out*/bool* needs_finite_test,
@@ -226,7 +188,7 @@
bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info,
ConstantRequest request,
- /*out*/ int64_t *value) const {
+ /*out*/ int64_t* value) const {
if (info != nullptr) {
// A direct 32-bit or 64-bit constant fetch. This immediately satisfies
// any of the three requests (kExact, kAtMost, and KAtLeast).
@@ -236,27 +198,16 @@
return true;
}
}
- // Try range analysis while traversing outward on loops.
- bool in_body = true; // no known trip count
- Value v_min = GetVal(info, nullptr, in_body, /* is_min */ true);
- Value v_max = GetVal(info, nullptr, in_body, /* is_min */ false);
- do {
- // Make sure *both* extremes are known to avoid arithmetic wrap-around anomalies.
- if (IsConstantValue(v_min) && IsConstantValue(v_max) && v_min.b_constant <= v_max.b_constant) {
- if ((request == kExact && v_min.b_constant == v_max.b_constant) || request == kAtMost) {
- *value = v_max.b_constant;
- return true;
- } else if (request == kAtLeast) {
- *value = v_min.b_constant;
- return true;
- }
- }
- } while (RefineOuter(&v_min, &v_max));
- // Exploit array length + c >= c, with c <= 0 to avoid arithmetic wrap-around anomalies
- // (e.g. array length == maxint and c == 1 would yield minint).
- if (request == kAtLeast) {
- if (v_min.a_constant == 1 && v_min.b_constant <= 0 && v_min.instruction->IsArrayLength()) {
- *value = v_min.b_constant;
+ // Try range analysis on the invariant, but only on proper range to avoid wrap-around anomalies.
+ Value min_val = GetVal(info, nullptr, /* in_body */ true, /* is_min */ true);
+ Value max_val = GetVal(info, nullptr, /* in_body */ true, /* is_min */ false);
+ if (IsConstantValue(min_val) &&
+ IsConstantValue(max_val) && min_val.b_constant <= max_val.b_constant) {
+ if ((request == kExact && min_val.b_constant == max_val.b_constant) || request == kAtMost) {
+ *value = max_val.b_constant;
+ return true;
+ } else if (request == kAtLeast) {
+ *value = min_val.b_constant;
return true;
}
}
@@ -264,6 +215,51 @@
return false;
}
+bool InductionVarRange::HasInductionInfo(
+ HInstruction* context,
+ HInstruction* instruction,
+ /*out*/ HLoopInformation** loop,
+ /*out*/ HInductionVarAnalysis::InductionInfo** info,
+ /*out*/ HInductionVarAnalysis::InductionInfo** trip) const {
+ HLoopInformation* l = context->GetBlock()->GetLoopInformation(); // closest enveloping loop
+ if (l != nullptr) {
+ HInductionVarAnalysis::InductionInfo* i = induction_analysis_->LookupInfo(l, instruction);
+ if (i != nullptr) {
+ *loop = l;
+ *info = i;
+ *trip = induction_analysis_->LookupInfo(l, l->GetHeader()->GetLastInstruction());
+ return true;
+ }
+ }
+ return false;
+}
+
+bool InductionVarRange::IsWellBehavedTripCount(HInductionVarAnalysis::InductionInfo* trip) const {
+ if (trip != nullptr) {
+ // Both bounds that define a trip-count are well-behaved if they either are not defined
+ // in any loop, or are contained in a proper interval. This allows finding the min/max
+ // of an expression by chasing outward.
+ InductionVarRange range(induction_analysis_);
+ HInductionVarAnalysis::InductionInfo* lower = trip->op_b->op_a;
+ HInductionVarAnalysis::InductionInfo* upper = trip->op_b->op_b;
+ int64_t not_used = 0;
+ return (!HasFetchInLoop(lower) || range.IsConstant(lower, kAtLeast, ¬_used)) &&
+ (!HasFetchInLoop(upper) || range.IsConstant(upper, kAtLeast, ¬_used));
+ }
+ return true;
+}
+
+bool InductionVarRange::HasFetchInLoop(HInductionVarAnalysis::InductionInfo* info) const {
+ if (info != nullptr) {
+ if (info->induction_class == HInductionVarAnalysis::kInvariant &&
+ info->operation == HInductionVarAnalysis::kFetch) {
+ return info->fetch->GetBlock()->GetLoopInformation() != nullptr;
+ }
+ return HasFetchInLoop(info->op_a) || HasFetchInLoop(info->op_b);
+ }
+ return false;
+}
+
bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const {
if (info != nullptr) {
if (info->induction_class == HInductionVarAnalysis::kLinear) {
@@ -299,13 +295,13 @@
HInductionVarAnalysis::InductionInfo* trip,
bool in_body,
bool is_min) const {
- // Detect common situation where an offset inside the trip count cancels out during range
+ // Detect common situation where an offset inside the trip-count cancels out during range
// analysis (finding max a * (TC - 1) + OFFSET for a == 1 and TC = UPPER - OFFSET or finding
// min a * (TC - 1) + OFFSET for a == -1 and TC = OFFSET - UPPER) to avoid losing information
// with intermediate results that only incorporate single instructions.
if (trip != nullptr) {
HInductionVarAnalysis::InductionInfo* trip_expr = trip->op_a;
- if (trip_expr->operation == HInductionVarAnalysis::kSub) {
+ if (trip_expr->type == info->type && trip_expr->operation == HInductionVarAnalysis::kSub) {
int64_t stride_value = 0;
if (IsConstant(info->op_a, kExact, &stride_value)) {
if (!is_min && stride_value == 1) {
@@ -349,12 +345,25 @@
HInductionVarAnalysis::InductionInfo* trip,
bool in_body,
bool is_min) const {
- // 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.
+ // Stop chasing the instruction at constant or hint.
int64_t value;
- if (IsIntAndGet(instruction, &value) && CanLongValueFitIntoInt(value)) {
+ if (IsIntAndGet(instruction, &value) && CanLongValueFitIntoInt(value)) {
return Value(static_cast<int32_t>(value));
- } else if (instruction->IsAdd()) {
+ } else if (instruction == chase_hint_) {
+ return Value(instruction, 1, 0);
+ }
+ // Special cases when encountering a single instruction that denotes trip count in the
+ // loop-body: min is 1 and, when chasing constants, max of safe trip-count is max int
+ if (in_body && trip != nullptr && instruction == trip->op_a->fetch) {
+ if (is_min) {
+ return Value(1);
+ } else if (chase_hint_ == nullptr && !IsUnsafeTripCount(trip)) {
+ return Value(std::numeric_limits<int32_t>::max());
+ }
+ }
+ // Chase the instruction a bit deeper into the HIR tree, so that it becomes more likely
+ // range analysis will compare the same instructions as terminal nodes.
+ if (instruction->IsAdd()) {
if (IsIntAndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) {
return AddValue(Value(static_cast<int32_t>(value)),
GetFetch(instruction->InputAt(1), trip, in_body, is_min));
@@ -362,19 +371,35 @@
return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min),
Value(static_cast<int32_t>(value)));
}
- } else if (instruction->IsArrayLength() && instruction->InputAt(0)->IsNewArray()) {
- return GetFetch(instruction->InputAt(0)->InputAt(0), trip, in_body, is_min);
+ } else if (instruction->IsArrayLength()) {
+ // Return extreme values when chasing constants. Otherwise, chase deeper.
+ if (chase_hint_ == nullptr) {
+ return is_min ? Value(0) : Value(std::numeric_limits<int32_t>::max());
+ } else if (instruction->InputAt(0)->IsNewArray()) {
+ return GetFetch(instruction->InputAt(0)->InputAt(0), trip, in_body, is_min);
+ }
} else if (instruction->IsTypeConversion()) {
// Since analysis is 32-bit (or narrower) we allow a widening along the path.
if (instruction->AsTypeConversion()->GetInputType() == Primitive::kPrimInt &&
instruction->AsTypeConversion()->GetResultType() == Primitive::kPrimLong) {
return GetFetch(instruction->InputAt(0), trip, in_body, is_min);
}
- } else if (is_min) {
- // Special case for finding minimum: minimum of trip-count in loop-body is 1.
- if (trip != nullptr && in_body && instruction == trip->op_a->fetch) {
- return Value(1);
- }
+ }
+ // Chase an invariant fetch that is defined by an outer loop if the trip-count used
+ // so far is well-behaved in both bounds and the next trip-count is safe.
+ // Example:
+ // for (int i = 0; i <= 100; i++) // safe
+ // for (int j = 0; j <= i; j++) // well-behaved
+ // j is in range [0, i ] (if i is chase hint)
+ // or in range [0, 100] (otherwise)
+ HLoopInformation* next_loop = nullptr;
+ HInductionVarAnalysis::InductionInfo* next_info = nullptr;
+ HInductionVarAnalysis::InductionInfo* next_trip = nullptr;
+ bool next_in_body = true; // inner loop is always in body of outer loop
+ if (HasInductionInfo(instruction, instruction, &next_loop, &next_info, &next_trip) &&
+ IsWellBehavedTripCount(trip) &&
+ !IsUnsafeTripCount(next_trip)) {
+ return GetVal(next_info, next_trip, next_in_body, is_min);
}
return Value(instruction, 1, 0);
}
@@ -421,9 +446,8 @@
break;
}
break;
- case HInductionVarAnalysis::kLinear: {
+ case HInductionVarAnalysis::kLinear:
return CorrectForType(GetLinear(info, trip, in_body, is_min), info->type);
- }
case HInductionVarAnalysis::kWrapAround:
case HInductionVarAnalysis::kPeriodic:
return MergeVal(GetVal(info->op_a, trip, in_body, is_min),
@@ -438,20 +462,18 @@
HInductionVarAnalysis::InductionInfo* trip,
bool in_body,
bool is_min) const {
+ // Constant times range.
+ int64_t value = 0;
+ if (IsConstant(info1, kExact, &value)) {
+ return MulRangeAndConstant(value, info2, trip, in_body, is_min);
+ } else if (IsConstant(info2, kExact, &value)) {
+ return MulRangeAndConstant(value, info1, trip, in_body, is_min);
+ }
+ // Interval ranges.
Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true);
Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false);
Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true);
Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false);
- // Try to refine first operand.
- if (!IsConstantValue(v1_min) && !IsConstantValue(v1_max)) {
- RefineOuter(&v1_min, &v1_max);
- }
- // Constant times range.
- if (IsSameConstantValue(v1_min, v1_max)) {
- return MulRangeAndConstant(v2_min, v2_max, v1_min, is_min);
- } else if (IsSameConstantValue(v2_min, v2_max)) {
- return MulRangeAndConstant(v1_min, v1_max, v2_min, is_min);
- }
// Positive range vs. positive or negative range.
if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) {
if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
@@ -476,14 +498,16 @@
HInductionVarAnalysis::InductionInfo* trip,
bool in_body,
bool is_min) const {
+ // Range divided by constant.
+ int64_t value = 0;
+ if (IsConstant(info2, kExact, &value)) {
+ return DivRangeAndConstant(value, info1, trip, in_body, is_min);
+ }
+ // Interval ranges.
Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true);
Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false);
Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true);
Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false);
- // Range divided by constant.
- if (IsSameConstantValue(v2_min, v2_max)) {
- return DivRangeAndConstant(v1_min, v1_max, v2_min, is_min);
- }
// Positive range vs. positive or negative range.
if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) {
if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
@@ -503,18 +527,30 @@
return Value();
}
-InductionVarRange::Value InductionVarRange::MulRangeAndConstant(Value v_min,
- Value v_max,
- Value c,
- bool is_min) const {
- return is_min == (c.b_constant >= 0) ? MulValue(v_min, c) : MulValue(v_max, c);
+InductionVarRange::Value InductionVarRange::MulRangeAndConstant(
+ int64_t value,
+ HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
+ bool is_min) const {
+ if (CanLongValueFitIntoInt(value)) {
+ Value c(static_cast<int32_t>(value));
+ return MulValue(GetVal(info, trip, in_body, is_min == value >= 0), c);
+ }
+ return Value();
}
-InductionVarRange::Value InductionVarRange::DivRangeAndConstant(Value v_min,
- Value v_max,
- Value c,
- bool is_min) const {
- return is_min == (c.b_constant >= 0) ? DivValue(v_min, c) : DivValue(v_max, c);
+InductionVarRange::Value InductionVarRange::DivRangeAndConstant(
+ int64_t value,
+ HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
+ bool is_min) const {
+ if (CanLongValueFitIntoInt(value)) {
+ Value c(static_cast<int32_t>(value));
+ return DivValue(GetVal(info, trip, in_body, is_min == value >= 0), c);
+ }
+ return Value();
}
InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) const {
@@ -580,28 +616,6 @@
return Value();
}
-InductionVarRange::Value InductionVarRange::RefineOuter(Value v, bool is_min) const {
- if (v.instruction == nullptr) {
- return v; // nothing to refine
- }
- HLoopInformation* loop =
- v.instruction->GetBlock()->GetLoopInformation(); // closest enveloping loop
- if (loop == nullptr) {
- return v; // no loop
- }
- HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, v.instruction);
- if (info == nullptr) {
- return v; // no induction information
- }
- // Set up loop information.
- HBasicBlock* header = loop->GetHeader();
- bool in_body = true; // inner always in more outer
- HInductionVarAnalysis::InductionInfo* trip =
- induction_analysis_->LookupInfo(loop, header->GetLastInstruction());
- // Try to refine "a x instruction + b" with outer loop range information on instruction.
- return AddValue(MulValue(Value(v.a_constant), GetVal(info, trip, in_body, is_min)), Value(v.b_constant));
-}
-
bool InductionVarRange::GenerateCode(HInstruction* context,
HInstruction* instruction,
HGraph* graph,
@@ -611,27 +625,18 @@
/*out*/HInstruction** taken_test,
/*out*/bool* needs_finite_test,
/*out*/bool* needs_taken_test) const {
- HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop
- if (loop == nullptr) {
- return false; // no loop
- }
- HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, instruction);
- if (info == nullptr) {
- return false; // no induction information
- }
- // Set up loop information.
- HBasicBlock* header = loop->GetHeader();
- bool in_body = context->GetBlock() != header;
- HInductionVarAnalysis::InductionInfo* trip =
- induction_analysis_->LookupInfo(loop, header->GetLastInstruction());
- if (trip == nullptr) {
- return false; // codegen relies on trip count
+ HLoopInformation* loop = nullptr;
+ HInductionVarAnalysis::InductionInfo* info = nullptr;
+ HInductionVarAnalysis::InductionInfo* trip = nullptr;
+ if (!HasInductionInfo(context, instruction, &loop, &info, &trip) || trip == nullptr) {
+ return false; // codegen needs all information, including tripcount
}
// Determine what tests are needed. A finite test is needed if the evaluation code uses the
// trip-count and the loop maybe unsafe (because in such cases, the index could "overshoot"
// the computed range). A taken test is needed for any unknown trip-count, even if evaluation
// code does not use the trip-count explicitly (since there could be an implicit relation
// between e.g. an invariant subscript and a not-taken condition).
+ bool in_body = context->GetBlock() != loop->GetHeader();
*needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip);
*needs_taken_test = IsBodyTripCount(trip);
// Code generation for taken test: generate the code when requested or otherwise analyze
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index 0af4156..00aaa16 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -57,21 +57,19 @@
explicit InductionVarRange(HInductionVarAnalysis* induction);
/**
- * Given a context denoted by the first instruction, returns a possibly conservative
- * lower and upper bound on the instruction's value in the output parameters min_val
- * and max_val, respectively. The need_finite_test flag denotes if an additional finite-test
- * is needed to protect the range evaluation inside its loop. Returns false on failure.
+ * Given a context denoted by the first instruction, returns a possibly conservative lower
+ * and upper bound on the instruction's value in the output parameters min_val and max_val,
+ * respectively. The need_finite_test flag denotes if an additional finite-test is needed
+ * to protect the range evaluation inside its loop. The parameter chase_hint defines an
+ * instruction at which chasing may stop. Returns false on failure.
*/
bool GetInductionRange(HInstruction* context,
HInstruction* instruction,
+ HInstruction* chase_hint,
/*out*/ Value* min_val,
/*out*/ Value* max_val,
/*out*/ bool* needs_finite_test);
- /** Refines the values with induction of next outer loop. Returns true on change. */
- bool RefineOuter(/*in-out*/ Value* min_val,
- /*in-out*/ Value* max_val) const;
-
/**
* Returns true if range analysis is able to generate code for the lower and upper
* bound expressions on the instruction in the given context. The need_finite_test
@@ -132,11 +130,20 @@
*/
bool IsConstant(HInductionVarAnalysis::InductionInfo* info,
ConstantRequest request,
- /*out*/ int64_t *value) const;
+ /*out*/ int64_t* value) const;
+ /** Returns whether induction information can be obtained. */
+ bool HasInductionInfo(HInstruction* context,
+ HInstruction* instruction,
+ /*out*/ HLoopInformation** loop,
+ /*out*/ HInductionVarAnalysis::InductionInfo** info,
+ /*out*/ HInductionVarAnalysis::InductionInfo** trip) const;
+
+ bool HasFetchInLoop(HInductionVarAnalysis::InductionInfo* info) const;
bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const;
bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const;
bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const;
+ bool IsWellBehavedTripCount(HInductionVarAnalysis::InductionInfo* trip) const;
Value GetLinear(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
@@ -161,8 +168,16 @@
bool in_body,
bool is_min) const;
- Value MulRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const;
- Value DivRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const;
+ Value MulRangeAndConstant(int64_t value,
+ HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
+ bool is_min) const;
+ Value DivRangeAndConstant(int64_t value,
+ HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
+ bool is_min) const;
Value AddValue(Value v1, Value v2) const;
Value SubValue(Value v1, Value v2) const;
@@ -171,12 +186,6 @@
Value MergeVal(Value v1, Value v2, bool is_min) const;
/**
- * Returns refined value using induction of next outer loop or the input value if no
- * further refinement is possible.
- */
- Value RefineOuter(Value val, bool is_min) const;
-
- /**
* Generates code for lower/upper/taken-test in the HIR. Returns true on success.
* With values nullptr, the method can be used to determine if code generation
* would be successful without generating actual code yet.
@@ -200,7 +209,10 @@
bool is_min) const;
/** Results of prior induction variable analysis. */
- HInductionVarAnalysis *induction_analysis_;
+ HInductionVarAnalysis* induction_analysis_;
+
+ /** Instruction at which chasing may stop. */
+ HInstruction* chase_hint_;
friend class HInductionVarAnalysis;
friend class InductionVarRangeTest;
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index dc04dc2..4ea170f 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -66,6 +66,8 @@
entry_block_->AddInstruction(x_);
y_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt);
entry_block_->AddInstruction(y_);
+ // Set arbitrary range analysis hint while testing private methods.
+ SetHint(x_);
}
/** Constructs loop with given upper bound. */
@@ -111,6 +113,11 @@
iva_->Run();
}
+ /** Sets hint. */
+ void SetHint(HInstruction* hint) {
+ range_.chase_hint_ = hint;
+ }
+
/** Constructs an invariant. */
HInductionVarAnalysis::InductionInfo* CreateInvariant(char opc,
HInductionVarAnalysis::InductionInfo* a,
@@ -122,6 +129,7 @@
case 'n': op = HInductionVarAnalysis::kNeg; break;
case '*': op = HInductionVarAnalysis::kMul; break;
case '/': op = HInductionVarAnalysis::kDiv; break;
+ case '<': op = HInductionVarAnalysis::kLT; break;
default: op = HInductionVarAnalysis::kNop; break;
}
return iva_->CreateInvariantOp(op, a, b);
@@ -137,22 +145,21 @@
return CreateFetch(graph_->GetIntConstant(c));
}
- /** Constructs a trip-count. */
+ /** Constructs a constant trip-count. */
HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc, bool in_loop, bool safe) {
- Primitive::Type type = Primitive::kPrimInt;
+ HInductionVarAnalysis::InductionOp op = HInductionVarAnalysis::kTripCountInBodyUnsafe;
if (in_loop && safe) {
- return iva_->CreateTripCount(
- HInductionVarAnalysis::kTripCountInLoop, CreateConst(tc), nullptr, type);
+ op = HInductionVarAnalysis::kTripCountInLoop;
} else if (in_loop) {
- return iva_->CreateTripCount(
- HInductionVarAnalysis::kTripCountInLoopUnsafe, CreateConst(tc), nullptr, type);
+ op = HInductionVarAnalysis::kTripCountInLoopUnsafe;
} else if (safe) {
- return iva_->CreateTripCount(
- HInductionVarAnalysis::kTripCountInBody, CreateConst(tc), nullptr, type);
- } else {
- return iva_->CreateTripCount(
- HInductionVarAnalysis::kTripCountInBodyUnsafe, CreateConst(tc), nullptr, type);
+ op = HInductionVarAnalysis::kTripCountInBody;
}
+ // Return TC with taken-test 0 < TC.
+ return iva_->CreateTripCount(op,
+ CreateConst(tc),
+ CreateInvariant('<', CreateConst(0), CreateConst(tc)),
+ Primitive::kPrimInt);
}
/** Constructs a linear a * i + b induction. */
@@ -197,13 +204,13 @@
}
Value GetMin(HInductionVarAnalysis::InductionInfo* info,
- HInductionVarAnalysis::InductionInfo* induc) {
- return range_.GetVal(info, induc, /* in_body */ true, /* is_min */ true);
+ HInductionVarAnalysis::InductionInfo* trip) {
+ return range_.GetVal(info, trip, /* in_body */ true, /* is_min */ true);
}
Value GetMax(HInductionVarAnalysis::InductionInfo* info,
- HInductionVarAnalysis::InductionInfo* induc) {
- return range_.GetVal(info, induc, /* in_body */ true, /* is_min */ false);
+ HInductionVarAnalysis::InductionInfo* trip) {
+ return range_.GetVal(info, trip, /* in_body */ true, /* is_min */ false);
}
Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
@@ -558,6 +565,31 @@
ExpectEqual(Value(), MaxValue(Value(55), Value(y_, 1, -50)));
}
+TEST_F(InductionVarRangeTest, ArrayLengthAndHints) {
+ HInstruction* new_array = new (&allocator_)
+ HNewArray(x_,
+ graph_->GetCurrentMethod(),
+ 0, Primitive::kPrimInt,
+ graph_->GetDexFile(),
+ kQuickAllocArray);
+ entry_block_->AddInstruction(new_array);
+ HInstruction* array_length = new (&allocator_) HArrayLength(new_array, 0);
+ entry_block_->AddInstruction(array_length);
+ // With null hint: yields extreme constants.
+ const int32_t max_value = std::numeric_limits<int32_t>::max();
+ SetHint(nullptr);
+ ExpectEqual(Value(0), GetMin(CreateFetch(array_length), nullptr));
+ ExpectEqual(Value(max_value), GetMax(CreateFetch(array_length), nullptr));
+ // With explicit hint: yields the length instruction.
+ SetHint(array_length);
+ ExpectEqual(Value(array_length, 1, 0), GetMin(CreateFetch(array_length), nullptr));
+ ExpectEqual(Value(array_length, 1, 0), GetMax(CreateFetch(array_length), nullptr));
+ // With any non-null hint: chases beyond the length instruction.
+ SetHint(x_);
+ ExpectEqual(Value(x_, 1, 0), GetMin(CreateFetch(array_length), nullptr));
+ ExpectEqual(Value(x_, 1, 0), GetMax(CreateFetch(array_length), nullptr));
+}
+
//
// Tests on public methods.
//
@@ -570,23 +602,20 @@
bool needs_finite_test = true;
// In context of header: known.
- range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(condition_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(1000), v2);
- EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
// In context of loop-body: known.
- range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(999), v2);
- EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
- range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(1), v1);
ExpectEqual(Value(1000), v2);
- EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
}
TEST_F(InductionVarRangeTest, ConstantTripCountDown) {
@@ -597,23 +626,20 @@
bool needs_finite_test = true;
// In context of header: known.
- range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(condition_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(1000), v2);
- EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
// In context of loop-body: known.
- range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(1), v1);
ExpectEqual(Value(1000), v2);
- EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
- range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(999), v2);
- EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
}
TEST_F(InductionVarRangeTest, SymbolicTripCountUp) {
@@ -625,23 +651,20 @@
bool needs_taken_test = true;
// In context of header: upper unknown.
- range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(condition_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(), v2);
- EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
// In context of loop-body: known.
- range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(x_, 1, -1), v2);
- EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
- range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(1), v1);
ExpectEqual(Value(x_, 1, 0), v2);
- EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
HInstruction* lower = nullptr;
HInstruction* upper = nullptr;
@@ -695,23 +718,20 @@
bool needs_taken_test = true;
// In context of header: lower unknown.
- range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(condition_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(), v1);
ExpectEqual(Value(1000), v2);
- EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
// In context of loop-body: known.
- range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(x_, 1, 1), v1);
ExpectEqual(Value(1000), v2);
- EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
- range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(x_, 1, 0), v1);
ExpectEqual(Value(999), v2);
- EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
HInstruction* lower = nullptr;
HInstruction* upper = nullptr;