Fine tuning the induction analysis.
Rationale:
Based on some self-imposed "blind" testing, improved
the induction variable analysis for typical cases
that provide a bit more elaborate HIR.
Test: test-art-host
Change-Id: I6e6bbf99928c29973178fa48f3942b14bf069944
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index c240c67..b21bc09 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -211,7 +211,7 @@
void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) {
InductionInfo* info = nullptr;
if (instruction->IsPhi()) {
- info = TransferPhi(loop, instruction, /* input_index */ 0);
+ info = TransferPhi(loop, instruction, /*input_index*/ 0, /*adjust_input_size*/ 0);
} else if (instruction->IsAdd()) {
info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
LookupInfo(loop, instruction->InputAt(1)), kAdd);
@@ -224,11 +224,13 @@
info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
LookupInfo(loop, instruction->InputAt(1)));
} else if (instruction->IsShl()) {
- HInstruction* mulc = GetMultConstantForShift(loop, instruction);
+ HInstruction* mulc = GetShiftConstant(loop, instruction, /*initial*/ nullptr);
if (mulc != nullptr) {
info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
LookupInfo(loop, mulc));
}
+ } 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(),
@@ -270,7 +272,7 @@
// Singleton is wrap-around induction if all internal links have the same meaning.
if (size == 1) {
- InductionInfo* update = TransferPhi(loop, phi, /* input_index */ 1);
+ InductionInfo* update = TransferPhi(loop, phi, /*input_index*/ 1, /*adjust_input_size*/ 0);
if (update != nullptr) {
AssignInfo(loop, phi, CreateInduction(kWrapAround,
kNop,
@@ -305,10 +307,15 @@
update = SolveOp(
loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kRem);
} else if (instruction->IsShl()) {
- HInstruction* mulc = GetMultConstantForShift(loop, instruction);
+ HInstruction* mulc = GetShiftConstant(loop, instruction, /*initial*/ nullptr);
if (mulc != nullptr) {
update = SolveOp(loop, phi, instruction, instruction->InputAt(0), mulc, kMul);
}
+ } else if (instruction->IsShr() || instruction->IsUShr()) {
+ HInstruction* divc = GetShiftConstant(loop, instruction, initial);
+ if (divc != nullptr) {
+ update = SolveOp(loop, phi, instruction, instruction->InputAt(0), divc, kDiv);
+ }
} else if (instruction->IsXor()) {
update = SolveOp(
loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kXor);
@@ -316,6 +323,8 @@
update = SolveTest(loop, phi, instruction, 0);
} else if (instruction->IsNotEqual()) {
update = SolveTest(loop, phi, instruction, 1);
+ } 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());
}
@@ -326,7 +335,7 @@
}
// Success if all internal links received the same temporary meaning.
- InductionInfo* induction = SolvePhi(phi, /* input_index */ 1);
+ InductionInfo* induction = SolvePhi(phi, /*input_index*/ 1, /*adjust_input_size*/ 0);
if (induction != nullptr) {
switch (induction->induction_class) {
case kInvariant:
@@ -385,12 +394,13 @@
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(HLoopInformation* loop,
HInstruction* phi,
- size_t input_index) {
+ size_t input_index,
+ size_t adjust_input_size) {
// Match all phi inputs from input_index onwards exactly.
HInputsRef inputs = phi->GetInputs();
DCHECK_LT(input_index, inputs.size());
InductionInfo* a = LookupInfo(loop, inputs[input_index]);
- for (size_t i = input_index + 1; i < inputs.size(); i++) {
+ for (size_t i = input_index + 1, n = inputs.size() - adjust_input_size; i < n; i++) {
InductionInfo* b = LookupInfo(loop, inputs[i]);
if (!InductionEqual(a, b)) {
return nullptr;
@@ -504,13 +514,14 @@
}
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi(HInstruction* phi,
- size_t input_index) {
+ size_t input_index,
+ size_t adjust_input_size) {
// Match all phi inputs from input_index onwards exactly.
HInputsRef inputs = phi->GetInputs();
DCHECK_LT(input_index, inputs.size());
auto ita = cycle_.find(inputs[input_index]);
if (ita != cycle_.end()) {
- for (size_t i = input_index + 1; i < inputs.size(); i++) {
+ for (size_t i = input_index + 1, n = inputs.size() - adjust_input_size; i < n; i++) {
auto itb = cycle_.find(inputs[i]);
if (itb == cycle_.end() ||
!HInductionVarAnalysis::InductionEqual(ita->second, itb->second)) {
@@ -527,7 +538,7 @@
HInstruction* entry_phi,
HInstruction* phi) {
// Match all phi inputs.
- InductionInfo* match = SolvePhi(phi, /* input_index */ 0);
+ InductionInfo* match = SolvePhi(phi, /*input_index*/ 0, /*adjust_input_size*/ 0);
if (match != nullptr) {
return match;
}
@@ -542,7 +553,7 @@
InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
return CreateInduction(kPeriodic, kNop, a, initial, /*fetch*/ nullptr, type_);
}
- InductionInfo* b = SolvePhi(phi, /* input_index */ 1);
+ InductionInfo* b = SolvePhi(phi, /*input_index*/ 1, /*adjust_input_size*/ 0);
if (b != nullptr && b->induction_class == kPeriodic) {
return CreateInduction(kPeriodic, kNop, a, b, /*fetch*/ nullptr, type_);
}
@@ -574,14 +585,14 @@
return CreateInvariantOp(op, a, b);
}
}
- } else if (op == kAdd && b->induction_class == kLinear) {
+ } else if (b->induction_class == kLinear) {
// Solve within a tight cycle that adds a term that is already classified as a linear
// induction for a polynomial induction k = k + i (represented as sum over linear terms).
if (x == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) {
InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
return CreateInduction(kPolynomial,
kNop,
- b,
+ op == kAdd ? b : TransferNeg(b),
initial,
/*fetch*/ nullptr,
type_);
@@ -1038,13 +1049,23 @@
return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr, b->type);
}
-HInstruction* HInductionVarAnalysis::GetMultConstantForShift(HLoopInformation* loop,
- HInstruction* instruction) {
- // Obtain the constant needed to treat shift as equivalent multiplication. This yields an
- // existing instruction if the constant is already there. Otherwise, this has a side effect
- // on the HIR. The restriction on the shift factor avoids generating a negative constant
- // (viz. 1 << 31 and 1L << 63 set the sign bit). The code assumes that generalization for
- // shift factors outside [0,32) and [0,64) ranges is done by earlier simplification.
+HInstruction* HInductionVarAnalysis::GetShiftConstant(HLoopInformation* loop,
+ HInstruction* instruction,
+ InductionInfo* initial) {
+ DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr());
+ // Shift-rights are only the same as division for non-negative initial inputs.
+ // Otherwise we would round incorrectly.
+ if (initial != nullptr) {
+ int64_t value = -1;
+ if (!IsAtLeast(initial, &value) || value < 0) {
+ return nullptr;
+ }
+ }
+ // Obtain the constant needed to treat shift as equivalent multiplication or division.
+ // This yields an existing instruction if the constant is already there. Otherwise, this
+ // has a side effect on the HIR. The restriction on the shift factor avoids generating a
+ // negative constant (viz. 1 << 31 and 1L << 63 set the sign bit). The code assumes that
+ // generalization for shift factors outside [0,32) and [0,64) ranges is done earlier.
InductionInfo* b = LookupInfo(loop, instruction->InputAt(1));
int64_t value = -1;
if (IsExact(b, &value)) {
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 4720f2d..293aa70 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -115,7 +115,7 @@
InductionInfo* op_a;
InductionInfo* op_b;
HInstruction* fetch;
- Primitive::Type type; // precision of induction
+ Primitive::Type type; // precision of operation
};
bool IsVisitedNode(HInstruction* instruction) const {
@@ -160,14 +160,17 @@
InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
// Transfer operations.
- InductionInfo* TransferPhi(HLoopInformation* loop, HInstruction* phi, size_t input_index);
+ InductionInfo* TransferPhi(HLoopInformation* loop,
+ HInstruction* phi,
+ size_t input_index,
+ size_t adjust_input_size);
InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
InductionInfo* TransferNeg(InductionInfo* a);
InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
InductionInfo* TransferCnv(InductionInfo* a, Primitive::Type from, Primitive::Type to);
// Solvers.
- InductionInfo* SolvePhi(HInstruction* phi, size_t input_index);
+ InductionInfo* SolvePhi(HInstruction* phi, size_t input_index, size_t adjust_input_size);
InductionInfo* SolvePhiAllInputs(HLoopInformation* loop,
HInstruction* entry_phi,
HInstruction* phi);
@@ -220,7 +223,9 @@
InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
InductionInfo* CreateConstant(int64_t value, Primitive::Type type);
InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);
- HInstruction* GetMultConstantForShift(HLoopInformation* loop, HInstruction* instruction);
+ HInstruction* GetShiftConstant(HLoopInformation* loop,
+ HInstruction* instruction,
+ InductionInfo* initial);
void AssignCycle(HPhi* phi);
ArenaSet<HInstruction*>* LookupCycle(HPhi* phi);
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index 2d182f6..f52a1aa 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -87,6 +87,7 @@
constant2_ = graph_->GetIntConstant(2);
constant7_ = graph_->GetIntConstant(7);
constant100_ = graph_->GetIntConstant(100);
+ constantm1_ = graph_->GetIntConstant(-1);
float_constant0_ = graph_->GetFloatConstant(0.0f);
return_->AddInstruction(new (&allocator_) HReturnVoid());
exit_->AddInstruction(new (&allocator_) HExit());
@@ -196,6 +197,7 @@
HInstruction* constant2_;
HInstruction* constant7_;
HInstruction* constant100_;
+ HInstruction* constantm1_;
HInstruction* float_constant0_;
// Loop specifics.
@@ -612,6 +614,45 @@
EXPECT_STREQ("", GetInductionInfo(div, 0).c_str());
}
+TEST_F(InductionVarAnalysisTest, FindGeometricShrInduction) {
+ // Setup:
+ // k = 100;
+ // for (int i = 0; i < 100; i++) {
+ // k = k >> 1; // geometric (/ 2)
+ // }
+ BuildLoopNest(1);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant100_);
+
+ HInstruction* shr = InsertInstruction(
+ new (&allocator_) HShr(Primitive::kPrimInt, k_header, constant1_), 0);
+ k_header->AddInput(shr);
+ PerformInductionVarAnalysis();
+
+ // Note, only the phi in the cycle is classified.
+ EXPECT_STREQ("geo((100) * 2 ^ -i + (0)):PrimInt", GetInductionInfo(k_header, 0).c_str());
+ EXPECT_STREQ("", GetInductionInfo(shr, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindNotGeometricShrInduction) {
+ // Setup:
+ // k = -1;
+ // for (int i = 0; i < 100; i++) {
+ // k = k >> 1; // initial value is negative
+ // }
+ BuildLoopNest(1);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constantm1_);
+
+ HInstruction* shr = InsertInstruction(
+ new (&allocator_) HShr(Primitive::kPrimInt, k_header, constant1_), 0);
+ k_header->AddInput(shr);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("", GetInductionInfo(k_header, 0).c_str());
+ EXPECT_STREQ("", GetInductionInfo(shr, 0).c_str());
+}
+
TEST_F(InductionVarAnalysisTest, FindRemWrapAroundInductionAndDerived) {
// Setup:
// k = 100;
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index e665551..7bcc384 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -983,10 +983,10 @@
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 &&
+ if (IsConstant(info->op_a->op_a, kExact, &a) &&
+ IsConstant(info->op_a->op_b, kExact, &b) &&
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
+ // 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;
