Improved induction var and range analysis around types.
Rationale:
Lots of code should not depend on int only. This CL generalizes
the kinds of types that can be optimized after analysis. As part
of the CL, however, a minor cleanup regarding type safety of the
stored induction var analysis results is required. This further
improved our int benchmark, and brings the long benchmark up-to-par.
Test: m test-art-host-run-test
Change-Id: I5dfb623dabf9113de90c2f6da99328dda8f8b60b
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 7bcc384..d5c4c2f 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -169,8 +169,8 @@
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);
+ int32_t min = Primitive::MinValueOfIntegralType(type);
+ int32_t max = Primitive::MaxValueOfIntegralType(type);
return (IsConstantValue(v) && min <= v.b_constant && v.b_constant <= max)
? v
: InductionVarRange::Value();
@@ -551,7 +551,7 @@
int64_t b = 0;
if (IsConstant(info->op_a->op_a, kExact, &a) && CanLongValueFitIntoInt(a) && a >= 0 &&
IsConstant(info->op_a->op_b, kExact, &b) && CanLongValueFitIntoInt(b) && b >= 0) {
- // Evaluate bounds on sum_i=0^m-1(a * i + b) + c with a,b >= 0 for known
+ // Evaluate bounds on sum_i=0^m-1(a * i + b) + c with a,b >= 0 for
// maximum index value m as a * (m * (m-1)) / 2 + b * m + c.
Value c = GetVal(info->op_b, trip, in_body, is_min);
if (is_min) {
@@ -629,6 +629,7 @@
}
} else if (instruction->IsTypeConversion()) {
// Since analysis is 32-bit (or narrower), chase beyond widening along the path.
+ // For example, this discovers the length in: for (long i = 0; i < a.length; i++);
if (instruction->AsTypeConversion()->GetInputType() == Primitive::kPrimInt &&
instruction->AsTypeConversion()->GetResultType() == Primitive::kPrimLong) {
return GetFetch(instruction->InputAt(0), trip, in_body, is_min);
@@ -843,7 +844,7 @@
InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) const {
if (v1.is_known && v2.is_known && IsSafeAdd(v1.b_constant, v2.b_constant)) {
- const int32_t b = v1.b_constant + v2.b_constant;
+ int32_t b = v1.b_constant + v2.b_constant;
if (v1.a_constant == 0) {
return Value(v2.instruction, v2.a_constant, b);
} else if (v2.a_constant == 0) {
@@ -857,7 +858,7 @@
InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2) const {
if (v1.is_known && v2.is_known && IsSafeSub(v1.b_constant, v2.b_constant)) {
- const int32_t b = v1.b_constant - v2.b_constant;
+ 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);
} else if (v2.a_constant == 0) {
@@ -988,13 +989,16 @@
IsConstant(trip->op_a, kExact, &m) && m >= 1) {
// Evaluate bounds on sum_i=0^m-1(a * i + b) + c for known
// maximum index value m as a * (m * (m-1)) / 2 + b * m + c.
- // TODO: generalize
- HInstruction* c_instr = nullptr;
- if (GenerateCode(info->op_b, nullptr, graph, block, graph ? &c_instr : nullptr, false, false)) {
+ HInstruction* c = nullptr;
+ if (GenerateCode(info->op_b, nullptr, graph, block, graph ? &c : nullptr, false, false)) {
if (graph != nullptr) {
+ Primitive::Type type = info->type;
int64_t sum = a * ((m * (m - 1)) / 2) + b * m;
- *result = Insert(block, new (graph->GetArena()) HAdd(info->type,
- graph->GetIntConstant(sum), c_instr));
+ if (type != Primitive::kPrimLong) {
+ sum = static_cast<int32_t>(sum); // okay to truncate
+ }
+ *result =
+ Insert(block, new (graph->GetArena()) HAdd(type, graph->GetConstant(type, sum), c));
}
return true;
}
@@ -1011,35 +1015,33 @@
DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kGeometric);
// Detect known base and trip count (always taken).
int64_t f = 0;
- int64_t t = 0;
- if (IsIntAndGet(info->fetch, &f) && f >= 1 && IsConstant(trip->op_a, kExact, &t) && t >= 1) {
+ int64_t m = 0;
+ if (IsIntAndGet(info->fetch, &f) && f >= 1 && IsConstant(trip->op_a, kExact, &m) && m >= 1) {
HInstruction* opa = nullptr;
HInstruction* opb = nullptr;
if (GenerateCode(info->op_a, nullptr, graph, block, &opa, false, false) &&
GenerateCode(info->op_b, nullptr, graph, block, &opb, false, false)) {
- // Compute f ^ t.
- int64_t fpowt = IntPow(f, t);
+ // Compute f ^ m for known maximum index value m.
+ int64_t fpow = IntPow(f, m);
if (graph != nullptr) {
- DCHECK(info->type == Primitive::kPrimInt); // due to codegen, generalize?
- if (fpowt == 0) {
+ DCHECK(info->operation == HInductionVarAnalysis::kMul ||
+ info->operation == HInductionVarAnalysis::kDiv);
+ Primitive::Type type = info->type;
+ if (fpow == 0) {
// Special case: repeated mul/div always yields zero.
- *result = graph->GetIntConstant(0);
- } else if (info->operation == HInductionVarAnalysis::kMul) {
- // Last value multiplication: a * f ^ t + b.
- HInstruction* mul = Insert(block,
- new (graph->GetArena()) HMul(info->type,
- opa,
- graph->GetIntConstant(fpowt)));
- *result = Insert(block, new (graph->GetArena()) HAdd(info->type, mul, opb));
+ *result = graph->GetConstant(type, 0);
} else {
- // Last value multiplication: a * f ^ -t + b.
- DCHECK_EQ(info->operation, HInductionVarAnalysis::kDiv);
- HInstruction* div = Insert(block,
- new (graph->GetArena()) HDiv(info->type,
- opa,
- graph->GetIntConstant(fpowt),
- kNoDexPc));
- *result = Insert(block, new (graph->GetArena()) HAdd(info->type, div, opb));
+ // Last value: a * f ^ m + b or a * f ^ -m + b.
+ if (type != Primitive::kPrimLong) {
+ fpow = static_cast<int32_t>(fpow); // okay to truncate
+ }
+ HInstruction* e = nullptr;
+ if (info->operation == HInductionVarAnalysis::kMul) {
+ e = new (graph->GetArena()) HMul(type, opa, graph->GetConstant(type, fpow));
+ } else {
+ e = new (graph->GetArena()) HDiv(type, opa, graph->GetConstant(type, fpow), kNoDexPc);
+ }
+ *result = Insert(block, new (graph->GetArena()) HAdd(type, Insert(block, e), opb));
}
}
return true;
@@ -1060,12 +1062,11 @@
for (; info->induction_class == HInductionVarAnalysis::kWrapAround;
info = info->op_b, ++depth) {}
// Handle wrap(x, wrap(.., y)) if trip count reaches an invariant at end.
- // TODO: generalize
- int64_t t = 0;
+ // TODO: generalize, but be careful to adjust the terminal.
+ int64_t m = 0;
if (info->induction_class == HInductionVarAnalysis::kInvariant &&
- IsConstant(trip->op_a, kExact, &t) && t >= depth &&
- GenerateCode(info, nullptr, graph, block, result, false, false)) {
- return true;
+ IsConstant(trip->op_a, kExact, &m) && m >= depth) {
+ return GenerateCode(info, nullptr, graph, block, result, false, false);
}
return false;
}
@@ -1079,43 +1080,49 @@
DCHECK(info != nullptr);
DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPeriodic);
// Count period.
- int32_t period = 1;
+ int64_t period = 1;
for (HInductionVarAnalysis::InductionInfo* p = info;
p->induction_class == HInductionVarAnalysis::kPeriodic;
p = p->op_b, ++period) {}
- // Handle periodic(x, y) case for restricted types.
- // TODO: generalize
- if (period != 2 ||
- trip->op_a->type != Primitive::kPrimInt ||
- (info->type != Primitive::kPrimInt && info->type != Primitive::kPrimBoolean)) {
- return false;
+ // Handle any periodic(x, periodic(.., y)) for known maximum index value m.
+ int64_t m = 0;
+ if (IsConstant(trip->op_a, kExact, &m) && m >= 1) {
+ int64_t li = m % period;
+ for (int64_t i = 0; i < li; info = info->op_b, i++) {}
+ if (info->induction_class == HInductionVarAnalysis::kPeriodic) {
+ info = info->op_a;
+ }
+ return GenerateCode(info, nullptr, graph, block, result, false, false);
}
- HInstruction* x_instr = nullptr;
- HInstruction* y_instr = nullptr;
- HInstruction* trip_expr = nullptr;
- if (GenerateCode(info->op_a, nullptr, graph, block, graph ? &x_instr : nullptr, false, false) &&
- GenerateCode(info->op_b, nullptr, graph, block, graph ? &y_instr : nullptr, false, false) &&
- GenerateCode(trip->op_a, nullptr, graph, block, graph ? &trip_expr : nullptr, false, false)) {
- // During actual code generation (graph != nullptr),
- // generate is_even ? x : y select instruction.
+ // Handle periodic(x, y) using even/odd-select on trip count. Enter trip count expression
+ // directly to obtain the maximum index value t even if taken test is needed.
+ HInstruction* x = nullptr;
+ HInstruction* y = nullptr;
+ HInstruction* t = nullptr;
+ if (period == 2 &&
+ GenerateCode(info->op_a, nullptr, graph, block, graph ? &x : nullptr, false, false) &&
+ GenerateCode(info->op_b, nullptr, graph, block, graph ? &y : nullptr, false, false) &&
+ GenerateCode(trip->op_a, nullptr, graph, block, graph ? &t : nullptr, false, false)) {
+ // During actual code generation (graph != nullptr), generate is_even ? x : y.
if (graph != nullptr) {
- HInstruction* is_even = Insert(block, new (graph->GetArena()) HEqual(
- Insert(block, new (graph->GetArena()) HAnd(
- Primitive::kPrimInt, trip_expr, graph->GetIntConstant(1))),
- graph->GetIntConstant(0), kNoDexPc));
- *result = Insert(block, new (graph->GetArena()) HSelect(is_even, x_instr, y_instr, kNoDexPc));
+ Primitive::Type type = trip->type;
+ HInstruction* msk =
+ Insert(block, new (graph->GetArena()) HAnd(type, t, graph->GetConstant(type, 1)));
+ HInstruction* is_even =
+ Insert(block, new (graph->GetArena()) HEqual(msk, graph->GetConstant(type, 0), kNoDexPc));
+ *result = Insert(block, new (graph->GetArena()) HSelect(is_even, x, y, kNoDexPc));
}
// Guard select with taken test if needed.
if (*needs_taken_test) {
- HInstruction* taken_test = nullptr;
- if (!GenerateCode(
- trip->op_b, nullptr, graph, block, graph ? &taken_test : nullptr, false, false)) {
+ HInstruction* is_taken = nullptr;
+ if (GenerateCode(trip->op_b, nullptr, graph, block, graph ? &is_taken : nullptr, false, false)) {
+ if (graph != nullptr) {
+ *result = Insert(block, new (graph->GetArena()) HSelect(is_taken, *result, x, kNoDexPc));
+ }
+ *needs_taken_test = false; // taken care of
+ } else {
return false;
- } else if (graph != nullptr) {
- *result = Insert(block,
- new (graph->GetArena()) HSelect(taken_test, *result, x_instr, kNoDexPc));
}
- *needs_taken_test = false; // taken care of
}
return true;
}
@@ -1134,13 +1141,8 @@
if (graph != nullptr && result == nullptr) {
return true;
}
- // Verify type safety.
- // TODO: generalize
- Primitive::Type type = Primitive::kPrimInt;
- if (info->type != Primitive::kPrimInt && info->type != Primitive::kPrimBoolean) {
- return false;
- }
// Handle current operation.
+ Primitive::Type type = info->type;
HInstruction* opa = nullptr;
HInstruction* opb = nullptr;
switch (info->induction_class) {
@@ -1214,15 +1216,15 @@
case HInductionVarAnalysis::kTripCountInBodyUnsafe:
if (is_min) {
if (graph != nullptr) {
- *result = graph->GetIntConstant(0);
+ *result = graph->GetConstant(type, 0);
}
return true;
} else if (in_body) {
if (GenerateCode(info->op_a, trip, graph, block, &opb, in_body, is_min)) {
if (graph != nullptr) {
- *result = Insert(block,
- new (graph->GetArena())
- HSub(type, opb, graph->GetIntConstant(1)));
+ *result =
+ Insert(block,
+ new (graph->GetArena()) HSub(type, opb, graph->GetConstant(type, 1)));
}
return true;
}
@@ -1236,26 +1238,31 @@
// Linear induction a * i + b, for normalized 0 <= i < TC. For ranges, this should
// be restricted to a unit stride to avoid arithmetic wrap-around situations that
// are harder to guard against. For a last value, requesting min/max based on any
- // stride yields right value.
- int64_t stride_value = 0;
- if (IsConstant(info->op_a, kExact, &stride_value)) {
- const bool is_min_a = stride_value >= 0 ? is_min : !is_min;
- if (GenerateCode(trip, trip, graph, block, &opa, in_body, is_min_a) &&
- GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) {
- if (graph != nullptr) {
- HInstruction* oper;
- if (stride_value == 1) {
- oper = new (graph->GetArena()) HAdd(type, opa, opb);
- } else if (stride_value == -1) {
- oper = new (graph->GetArena()) HSub(type, opb, opa);
- } else {
- HInstruction* mul = new (graph->GetArena()) HMul(
- type, graph->GetIntConstant(stride_value), opa);
- oper = new (graph->GetArena()) HAdd(type, Insert(block, mul), opb);
+ // known stride yields right value. Always avoid any narrowing linear induction or
+ // any type mismatch between the linear induction and the trip count expression.
+ // TODO: careful runtime type conversions could generalize this latter restriction.
+ if (!HInductionVarAnalysis::IsNarrowingLinear(info) && trip->type == type) {
+ int64_t stride_value = 0;
+ if (IsConstant(info->op_a, kExact, &stride_value) &&
+ CanLongValueFitIntoInt(stride_value)) {
+ const bool is_min_a = stride_value >= 0 ? is_min : !is_min;
+ if (GenerateCode(trip, trip, graph, block, &opa, in_body, is_min_a) &&
+ GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) {
+ if (graph != nullptr) {
+ HInstruction* oper;
+ if (stride_value == 1) {
+ oper = new (graph->GetArena()) HAdd(type, opa, opb);
+ } else if (stride_value == -1) {
+ oper = new (graph->GetArena()) HSub(type, opb, opa);
+ } else {
+ HInstruction* mul =
+ new (graph->GetArena()) HMul(type, graph->GetConstant(type, stride_value), opa);
+ oper = new (graph->GetArena()) HAdd(type, Insert(block, mul), opb);
+ }
+ *result = Insert(block, oper);
}
- *result = Insert(block, oper);
+ return true;
}
- return true;
}
}
break;
@@ -1270,7 +1277,7 @@
Value extreme = GetVal(info, trip, in_body, is_min);
if (IsConstantValue(extreme)) {
if (graph != nullptr) {
- *result = graph->GetIntConstant(extreme.b_constant);
+ *result = graph->GetConstant(type, extreme.b_constant);
}
return true;
}