Added polynomial induction variables analysis. With tests.
Rationale:
Information on polynomial sequences is nice to further enhance
BCE and last-value assignment. In this case, this CL enables more
loop optimizations for benchpress' Sum (80 x speedup). Also
changed rem-based geometric induction to wrap-around induction.
Test: test-art-host
Change-Id: Ie4d2659edefb814edda2c971c1f70ba400c31111
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 75619a3..e665551 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -460,6 +460,8 @@
if (info != nullptr) {
if (info->induction_class == HInductionVarAnalysis::kLinear) {
return IsConstant(info->op_a, kExact, stride_value);
+ } else if (info->induction_class == HInductionVarAnalysis::kPolynomial) {
+ return NeedsTripCount(info->op_a, stride_value);
} else if (info->induction_class == HInductionVarAnalysis::kWrapAround) {
return NeedsTripCount(info->op_b, stride_value);
}
@@ -492,7 +494,7 @@
bool in_body,
bool is_min) const {
DCHECK(info != nullptr);
- DCHECK(info->induction_class == HInductionVarAnalysis::kLinear);
+ DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kLinear);
// 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
@@ -539,25 +541,49 @@
GetVal(info->op_b, trip, in_body, is_min));
}
+InductionVarRange::Value InductionVarRange::GetPolynomial(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
+ bool is_min) const {
+ DCHECK(info != nullptr);
+ DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPolynomial);
+ int64_t a = 0;
+ 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
+ // 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) {
+ return c;
+ } else {
+ Value m = GetVal(trip, trip, in_body, is_min);
+ Value t = DivValue(MulValue(m, SubValue(m, Value(1))), Value(2));
+ Value x = MulValue(Value(a), t);
+ Value y = MulValue(Value(b), m);
+ return AddValue(AddValue(x, y), c);
+ }
+ }
+ return Value();
+}
+
InductionVarRange::Value InductionVarRange::GetGeometric(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
bool in_body,
bool is_min) const {
DCHECK(info != nullptr);
- DCHECK(info->induction_class == HInductionVarAnalysis::kGeometric);
+ DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kGeometric);
int64_t a = 0;
int64_t f = 0;
if (IsConstant(info->op_a, kExact, &a) &&
CanLongValueFitIntoInt(a) &&
- IsIntAndGet(info->fetch, &f) &&
- CanLongValueFitIntoInt(f) && f >= 1) {
- // Conservative bounds on a * f^-i + b with f >= 1 can be computed without trip count.
- // Same for mod. All other forms would require a much more elaborate evaluation.
+ IsIntAndGet(info->fetch, &f) && f >= 1) {
+ // Conservative bounds on a * f^-i + b with f >= 1 can be computed without
+ // trip count. Other forms would require a much more elaborate evaluation.
const bool is_min_a = a >= 0 ? is_min : !is_min;
if (info->operation == HInductionVarAnalysis::kDiv) {
- return AddValue(Value(is_min_a ? 0 : a), GetVal(info->op_b, trip, in_body, is_min));
- } else if (info->operation == HInductionVarAnalysis::kNop) {
- return AddValue(Value(is_min_a ? (a % f) : a), GetVal(info->op_b, trip, in_body, is_min));
+ Value b = GetVal(info->op_b, trip, in_body, is_min);
+ return is_min_a ? b : AddValue(Value(a), b);
}
}
return Value();
@@ -572,7 +598,7 @@
if (chase_hint_ == nullptr && in_body && trip != nullptr && instruction == trip->op_a->fetch) {
if (is_min) {
return Value(1);
- } else if (!IsUnsafeTripCount(trip)) {
+ } else if (!instruction->IsConstant() && !IsUnsafeTripCount(trip)) {
return Value(std::numeric_limits<int32_t>::max());
}
}
@@ -650,6 +676,8 @@
return GetMul(info->op_a, info->op_b, trip, in_body, is_min);
case HInductionVarAnalysis::kDiv:
return GetDiv(info->op_a, info->op_b, trip, in_body, is_min);
+ case HInductionVarAnalysis::kRem:
+ return GetRem(info->op_a, info->op_b);
case HInductionVarAnalysis::kXor:
return GetXor(info->op_a, info->op_b);
case HInductionVarAnalysis::kFetch:
@@ -675,7 +703,7 @@
case HInductionVarAnalysis::kLinear:
return CorrectForType(GetLinear(info, trip, in_body, is_min), info->type);
case HInductionVarAnalysis::kPolynomial:
- break;
+ return GetPolynomial(info, trip, in_body, is_min);
case HInductionVarAnalysis::kGeometric:
return GetGeometric(info, trip, in_body, is_min);
case HInductionVarAnalysis::kWrapAround:
@@ -757,6 +785,21 @@
return Value();
}
+InductionVarRange::Value InductionVarRange::GetRem(
+ HInductionVarAnalysis::InductionInfo* info1,
+ HInductionVarAnalysis::InductionInfo* info2) const {
+ int64_t v1 = 0;
+ int64_t v2 = 0;
+ // Only accept exact values.
+ if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2) && v2 != 0) {
+ int64_t value = v1 % v2;
+ if (CanLongValueFitIntoInt(value)) {
+ return Value(static_cast<int32_t>(value));
+ }
+ }
+ return Value();
+}
+
InductionVarRange::Value InductionVarRange::GetXor(
HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2) const {
@@ -898,8 +941,12 @@
upper = nullptr;
}
break;
+ case HInductionVarAnalysis::kPolynomial:
+ return GenerateLastValuePolynomial(info, trip, graph, block, lower);
case HInductionVarAnalysis::kGeometric:
return GenerateLastValueGeometric(info, trip, graph, block, lower);
+ case HInductionVarAnalysis::kWrapAround:
+ return GenerateLastValueWrapAround(info, trip, graph, block, lower);
case HInductionVarAnalysis::kPeriodic:
return GenerateLastValuePeriodic(info, trip, graph, block, lower, needs_taken_test);
default:
@@ -925,13 +972,43 @@
GenerateCode(info, trip, graph, block, upper, in_body, /* is_min */ false);
}
+bool InductionVarRange::GenerateLastValuePolynomial(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/HInstruction** result) const {
+ DCHECK(info != nullptr);
+ DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPolynomial);
+ // Detect known coefficients and trip count (always taken).
+ int64_t a = 0;
+ int64_t b = 0;
+ int64_t m = 0;
+ if (IsConstant(info->op_a->op_a, kExact, &a) && a >= 0 &&
+ IsConstant(info->op_a->op_b, kExact, &b) && b >= 0 &&
+ IsConstant(trip->op_a, kExact, &m) && m >= 1) {
+ // Evaluate bounds on sum_i=0^m-1(a * i + b) + c with a,b >= 0 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)) {
+ if (graph != nullptr) {
+ int64_t sum = a * ((m * (m - 1)) / 2) + b * m;
+ *result = Insert(block, new (graph->GetArena()) HAdd(info->type,
+ graph->GetIntConstant(sum), c_instr));
+ }
+ return true;
+ }
+ }
+ return false;
+}
+
bool InductionVarRange::GenerateLastValueGeometric(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
HGraph* graph,
HBasicBlock* block,
/*out*/HInstruction** result) const {
DCHECK(info != nullptr);
- DCHECK(info->induction_class == HInductionVarAnalysis::kGeometric);
+ DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kGeometric);
// Detect known base and trip count (always taken).
int64_t f = 0;
int64_t t = 0;
@@ -940,15 +1017,6 @@
HInstruction* opb = nullptr;
if (GenerateCode(info->op_a, nullptr, graph, block, &opa, false, false) &&
GenerateCode(info->op_b, nullptr, graph, block, &opb, false, false)) {
- // Generate a % f + b.
- if (info->operation == HInductionVarAnalysis::kNop) {
- if (graph != nullptr) {
- HInstruction* rem =
- Insert(block, new (graph->GetArena()) HRem(info->type, opa, info->fetch, kNoDexPc));
- *result = Insert(block, new (graph->GetArena()) HAdd(info->type, rem, opb));
- }
- return true;
- }
// Compute f ^ t.
int64_t fpowt = IntPow(f, t);
if (graph != nullptr) {
@@ -980,6 +1048,28 @@
return false;
}
+bool InductionVarRange::GenerateLastValueWrapAround(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/HInstruction** result) const {
+ DCHECK(info != nullptr);
+ DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kWrapAround);
+ // Count depth.
+ int32_t depth = 0;
+ 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;
+ if (info->induction_class == HInductionVarAnalysis::kInvariant &&
+ IsConstant(trip->op_a, kExact, &t) && t >= depth &&
+ GenerateCode(info, nullptr, graph, block, result, false, false)) {
+ return true;
+ }
+ return false;
+}
+
bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
HGraph* graph,
@@ -987,17 +1077,18 @@
/*out*/HInstruction** result,
/*out*/bool* needs_taken_test) const {
DCHECK(info != nullptr);
- DCHECK(info->induction_class == HInductionVarAnalysis::kPeriodic);
+ DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPeriodic);
// Count period.
int32_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; // TODO: easy to generalize
+ return false;
}
HInstruction* x_instr = nullptr;
HInstruction* y_instr = nullptr;
@@ -1058,6 +1149,7 @@
// invariants, some effort is made to keep this parameter consistent).
switch (info->operation) {
case HInductionVarAnalysis::kAdd:
+ case HInductionVarAnalysis::kRem: // no proper is_min for second arg
case HInductionVarAnalysis::kXor: // no proper is_min for second arg
case HInductionVarAnalysis::kLT:
case HInductionVarAnalysis::kLE:
@@ -1070,6 +1162,8 @@
switch (info->operation) {
case HInductionVarAnalysis::kAdd:
operation = new (graph->GetArena()) HAdd(type, opa, opb); break;
+ case HInductionVarAnalysis::kRem:
+ operation = new (graph->GetArena()) HRem(type, opa, opb, kNoDexPc); break;
case HInductionVarAnalysis::kXor:
operation = new (graph->GetArena()) HXor(type, opa, opb); break;
case HInductionVarAnalysis::kLT: