Generalize induction and range analysis across type conversions.
Rationale:
This changelist implements allowing narrowing conversions within
inductions and loop control. More induction and loops recognized,
more bounds eliminated. We all win. The basic idea is pretty simple
(record type with detected induction) but one has to get all the
details right, as illustrated by the many new unit tests.
BUG=27151098
Change-Id: I254020bfa5fa623799b31bbbb5ccc97d4d5a0100
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index f9b6910..bc920d9 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -58,13 +58,13 @@
}
/**
- * An upper bound a * (length / a) + b, where a > 0, can be conservatively rewritten as length + b
+ * An upper bound a * (length / a) + b, where a >= 1, 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) {
int64_t value;
if (v.is_known &&
- v.a_constant > 1 &&
+ v.a_constant >= 1 &&
v.instruction->IsDiv() &&
v.instruction->InputAt(0)->IsArrayLength() &&
IsIntAndGet(v.instruction->InputAt(1), &value) && v.a_constant == value) {
@@ -73,6 +73,28 @@
return v;
}
+/**
+ * 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:
+ case Primitive::kPrimChar:
+ case Primitive::kPrimByte: {
+ // Constants within range only.
+ // 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)
+ ? 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;
@@ -114,6 +136,18 @@
if (info == nullptr) {
return false; // no induction information
}
+ // Type int or lower (this is not too restrictive since intended clients, like
+ // bounds check elimination, will have truncated higher precision induction
+ // at their use point already).
+ switch (info->type) {
+ case Primitive::kPrimInt:
+ case Primitive::kPrimShort:
+ case Primitive::kPrimChar:
+ case Primitive::kPrimByte:
+ break;
+ default:
+ return false;
+ }
// Set up loop information.
HBasicBlock* header = loop->GetHeader();
bool in_body = context->GetBlock() != header;
@@ -128,25 +162,27 @@
bool InductionVarRange::RefineOuter(/*in-out*/ Value* min_val,
/*in-out*/ Value* max_val) const {
- 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;
+ 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;
+ // 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;
}
@@ -277,7 +313,12 @@
if (HInductionVarAnalysis::InductionEqual(trip_expr->op_b, info->op_b)) {
// Analyze cancelled trip with just the positive operand (trip_expr->op_a).
HInductionVarAnalysis::InductionInfo cancelled_trip(
- trip->induction_class, trip->operation, trip_expr->op_a, trip->op_b, nullptr);
+ trip->induction_class,
+ trip->operation,
+ trip_expr->op_a,
+ trip->op_b,
+ nullptr,
+ trip->type);
return GetVal(&cancelled_trip, trip, in_body, is_min);
}
} else if (is_min && stride_value == -1) {
@@ -289,9 +330,10 @@
HInductionVarAnalysis::kNeg,
nullptr,
trip_expr->op_b,
- nullptr);
+ nullptr,
+ trip->type);
HInductionVarAnalysis::InductionInfo cancelled_trip(
- trip->induction_class, trip->operation, &neg, trip->op_b, nullptr);
+ trip->induction_class, trip->operation, &neg, trip->op_b, nullptr, trip->type);
return SubValue(Value(0), GetVal(&cancelled_trip, trip, in_body, !is_min));
}
}
@@ -322,6 +364,12 @@
}
} else if (instruction->IsArrayLength() && 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) {
@@ -374,7 +422,7 @@
}
break;
case HInductionVarAnalysis::kLinear: {
- return GetLinear(info, trip, in_body, is_min);
+ return CorrectForType(GetLinear(info, trip, in_body, is_min), info->type);
}
case HInductionVarAnalysis::kWrapAround:
case HInductionVarAnalysis::kPeriodic:
@@ -613,8 +661,12 @@
bool in_body,
bool is_min) const {
if (info != nullptr) {
- // Handle current operation.
+ // Verify type safety.
Primitive::Type type = Primitive::kPrimInt;
+ if (info->type != type) {
+ return false;
+ }
+ // Handle current operation.
HInstruction* opa = nullptr;
HInstruction* opb = nullptr;
switch (info->induction_class) {
@@ -667,13 +719,10 @@
}
break;
case HInductionVarAnalysis::kFetch:
- if (info->fetch->GetType() == type) {
- if (graph != nullptr) {
- *result = info->fetch; // already in HIR
- }
- return true;
+ if (graph != nullptr) {
+ *result = info->fetch; // already in HIR
}
- break;
+ return true;
case HInductionVarAnalysis::kTripCountInLoop:
case HInductionVarAnalysis::kTripCountInLoopUnsafe:
if (!in_body && !is_min) { // one extra!