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_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index b21bc09..5456b1e 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -73,10 +73,18 @@
}
/**
- * Returns narrowest data type.
+ * Returns result of implicit widening type conversion done in HIR.
*/
-static Primitive::Type Narrowest(Primitive::Type type1, Primitive::Type type2) {
- return Primitive::ComponentSize(type1) <= Primitive::ComponentSize(type2) ? type1 : type2;
+static Primitive::Type ImplicitConversion(Primitive::Type type) {
+ switch (type) {
+ case Primitive::kPrimShort:
+ case Primitive::kPrimChar:
+ case Primitive::kPrimByte:
+ case Primitive::kPrimBoolean:
+ return Primitive::kPrimInt;
+ default:
+ return type;
+ }
}
//
@@ -232,9 +240,9 @@
} else if (instruction->IsSelect()) {
info = TransferPhi(loop, instruction, /*input_index*/ 0, /*adjust_input_size*/ 1);
} else if (instruction->IsTypeConversion()) {
- info = TransferCnv(LookupInfo(loop, instruction->InputAt(0)),
- instruction->AsTypeConversion()->GetInputType(),
- instruction->AsTypeConversion()->GetResultType());
+ info = TransferConversion(LookupInfo(loop, instruction->InputAt(0)),
+ instruction->AsTypeConversion()->GetInputType(),
+ instruction->AsTypeConversion()->GetResultType());
} else if (instruction->IsBoundsCheck()) {
info = LookupInfo(loop, instruction->InputAt(0)); // Pass-through.
}
@@ -267,8 +275,12 @@
return;
}
- // Store interesting cycle.
- AssignCycle(phi->AsPhi());
+ // Store interesting cycle in each loop phi.
+ for (size_t i = 0; i < size; i++) {
+ if (scc_[i]->IsLoopHeaderPhi()) {
+ AssignCycle(scc_[i]->AsPhi());
+ }
+ }
// Singleton is wrap-around induction if all internal links have the same meaning.
if (size == 1) {
@@ -326,7 +338,7 @@
} else if (instruction->IsSelect()) {
update = SolvePhi(instruction, /*input_index*/ 0, /*adjust_input_size*/ 1); // acts like Phi
} else if (instruction->IsTypeConversion()) {
- update = SolveCnv(instruction->AsTypeConversion());
+ update = SolveConversion(loop, phi, instruction->AsTypeConversion());
}
if (update == nullptr) {
return;
@@ -416,8 +428,9 @@
// wrap-around, or periodic can be combined with an invariant to yield a similar result.
// Two linear or two polynomial inputs can be combined too. Other combinations fail.
if (a != nullptr && b != nullptr) {
- type_ = Narrowest(type_, Narrowest(a->type, b->type));
- if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
+ if (IsNarrowingLinear(a) || IsNarrowingLinear(b)) {
+ return nullptr; // no transfer
+ } else if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
return CreateInvariantOp(op, a, b);
} else if ((a->induction_class == kLinear && b->induction_class == kLinear) ||
(a->induction_class == kPolynomial && b->induction_class == kPolynomial)) {
@@ -452,8 +465,9 @@
// Transfer over a unary negation: an invariant, linear, polynomial, geometric (mul),
// wrap-around, or periodic input yields a similar but negated induction as result.
if (a != nullptr) {
- type_ = Narrowest(type_, a->type);
- if (a->induction_class == kInvariant) {
+ if (IsNarrowingLinear(a)) {
+ return nullptr; // no transfer
+ } else if (a->induction_class == kInvariant) {
return CreateInvariantOp(kNeg, nullptr, a);
} else if (a->induction_class != kGeometric || a->operation == kMul) {
return CreateInduction(a->induction_class,
@@ -473,8 +487,9 @@
// wrap-around, or periodic can be multiplied with an invariant to yield a similar
// but multiplied result. Two non-invariant inputs cannot be multiplied, however.
if (a != nullptr && b != nullptr) {
- type_ = Narrowest(type_, Narrowest(a->type, b->type));
- if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
+ if (IsNarrowingLinear(a) || IsNarrowingLinear(b)) {
+ return nullptr; // no transfer
+ } else if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
return CreateInvariantOp(kMul, a, b);
} else if (a->induction_class == kInvariant && (b->induction_class != kGeometric ||
b->operation == kMul)) {
@@ -497,17 +512,17 @@
return nullptr;
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferCnv(InductionInfo* a,
- Primitive::Type from,
- Primitive::Type to) {
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferConversion(
+ InductionInfo* a,
+ Primitive::Type from,
+ Primitive::Type to) {
if (a != nullptr) {
- // Allow narrowing conversion on linear induction in certain cases.
- if (IsNarrowingIntegralConversion(from, to)) {
- if (a->induction_class == kLinear) {
- if (a->type == to || (a->type == from && IsNarrowingIntegralConversion(from, to))) {
- return CreateInduction(kLinear, kNop, a->op_a, a->op_b, /*fetch*/ nullptr, to);
- }
- }
+ // Allow narrowing conversion on linear induction in certain cases:
+ // induction is already at narrow type, or can be made narrower.
+ if (IsNarrowingIntegralConversion(from, to) &&
+ a->induction_class == kLinear &&
+ (a->type == to || IsNarrowingIntegralConversion(a->type, to))) {
+ return CreateInduction(kLinear, kNop, a->op_a, a->op_b, /*fetch*/ nullptr, to);
}
}
return nullptr;
@@ -700,16 +715,29 @@
return nullptr;
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveCnv(HTypeConversion* conversion) {
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveConversion(
+ HLoopInformation* loop,
+ HInstruction* entry_phi,
+ HTypeConversion* conversion) {
Primitive::Type from = conversion->GetInputType();
Primitive::Type to = conversion->GetResultType();
- // A narrowing conversion is allowed within the cycle of a linear induction, provided that the
- // narrowest encountered type is recorded with the induction to account for the precision loss.
- if (IsNarrowingIntegralConversion(from, to)) {
- auto it = cycle_.find(conversion->GetInput());
- if (it != cycle_.end() && it->second->induction_class == kInvariant) {
- type_ = Narrowest(type_, to);
- return it->second;
+ // A narrowing conversion is allowed as *last* operation of the cycle of a linear induction
+ // with an initial value that fits the type, provided that the narrowest encountered type is
+ // recorded with the induction to account for the precision loss. The narrower induction does
+ // *not* transfer to any wider operations, however, since these may yield out-of-type values
+ if (entry_phi->InputCount() == 2 && conversion == entry_phi->InputAt(1)) {
+ int64_t min = Primitive::MinValueOfIntegralType(to);
+ int64_t max = Primitive::MaxValueOfIntegralType(to);
+ int64_t value = 0;
+ InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
+ if (IsNarrowingIntegralConversion(from, to) &&
+ IsAtLeast(initial, &value) && value >= min &&
+ IsAtMost(initial, &value) && value <= max) {
+ auto it = cycle_.find(conversion->GetInput());
+ if (it != cycle_.end() && it->second->induction_class == kInvariant) {
+ type_ = to;
+ return it->second;
+ }
}
}
return nullptr;
@@ -729,7 +757,7 @@
HCondition* condition = if_expr->AsCondition();
InductionInfo* a = LookupInfo(loop, condition->InputAt(0));
InductionInfo* b = LookupInfo(loop, condition->InputAt(1));
- Primitive::Type type = condition->InputAt(0)->GetType();
+ Primitive::Type type = ImplicitConversion(condition->InputAt(0)->GetType());
// Determine if the loop control uses a known sequence on an if-exit (X outside) or on
// an if-iterate (X inside), expressed as if-iterate when passed into VisitCondition().
if (a == nullptr || b == nullptr) {
@@ -901,8 +929,8 @@
int64_t stride_value,
Primitive::Type type,
IfCondition cmp) {
- const int64_t min = Primitive::MinValueOfIntegralType(type);
- const int64_t max = Primitive::MaxValueOfIntegralType(type);
+ int64_t min = Primitive::MinValueOfIntegralType(type);
+ int64_t max = Primitive::MaxValueOfIntegralType(type);
// Some rules under which it is certain at compile-time that the loop is finite.
int64_t value;
switch (cmp) {
@@ -938,8 +966,6 @@
min++;
}
// Do both bounds fit the range?
- // Note: The `value` is initialized to please valgrind - the compiler can reorder
- // the return value check with the `value` check, b/27651442 .
int64_t value = 0;
return IsAtLeast(lower_expr, &value) && value >= min &&
IsAtMost(lower_expr, &value) && value <= max &&
@@ -1046,7 +1072,8 @@
return CreateSimplifiedInvariant(kSub, b->op_b, b->op_a);
}
}
- return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr, b->type);
+ return new (graph_->GetArena()) InductionInfo(
+ kInvariant, op, a, b, nullptr, ImplicitConversion(b->type));
}
HInstruction* HInductionVarAnalysis::GetShiftConstant(HLoopInformation* loop,
@@ -1108,6 +1135,16 @@
return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtLeast, value);
}
+bool HInductionVarAnalysis::IsNarrowingLinear(InductionInfo* info) {
+ return info != nullptr &&
+ info->induction_class == kLinear &&
+ (info->type == Primitive::kPrimByte ||
+ info->type == Primitive::kPrimShort ||
+ info->type == Primitive::kPrimChar ||
+ (info->type == Primitive::kPrimInt && (info->op_a->type == Primitive::kPrimLong ||
+ info->op_b->type == Primitive::kPrimLong)));
+}
+
bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1,
InductionInfo* info2) {
// Test structural equality only, without accounting for simplifications.