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;
diff --git a/test/530-checker-loops4/src/Main.java b/test/530-checker-loops4/src/Main.java
index 7d3d7d9..91af1f4 100644
--- a/test/530-checker-loops4/src/Main.java
+++ b/test/530-checker-loops4/src/Main.java
@@ -96,7 +96,29 @@
/// CHECK-NOT: Phi
public static int geo4(int a) {
for (int i = 0; i < 10; i++) {
- a %= 7;
+ a %= 7; // a wrap-around induction
+ }
+ return a;
+ }
+
+ /// CHECK-START: int Main.geo5() loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
+ /// CHECK-DAG: Shr loop:<<Loop>>
+ //
+ /// CHECK-START: int Main.geo5() loop_optimization (after)
+ /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Int1:i\d+>> IntConstant 2147483647 loop:none
+ /// CHECK-DAG: <<Int2:i\d+>> IntConstant 1024 loop:none
+ /// CHECK-DAG: <<Div:i\d+>> Div [<<Int1>>,<<Int2>>] loop:none
+ /// CHECK-DAG: <<Add:i\d+>> Add [<<Div>>,<<Zero>>] loop:none
+ /// CHECK-DAG: Return [<<Add>>] loop:none
+ //
+ /// CHECK-START: int Main.geo5() loop_optimization (after)
+ /// CHECK-NOT: Phi
+ public static int geo5() {
+ int a = 0x7fffffff;
+ for (int i = 0; i < 10; i++) {
+ a >>= 1;
}
return a;
}
@@ -186,7 +208,7 @@
int r = 0;
for (int i = 0; i < 100; i++) { // a converges to 0
r += x[a];
- a %= 5;
+ a %= 5; // a wrap-around induction
}
return r;
}
@@ -305,6 +327,8 @@
expectEquals(i % 7, geo4(i));
}
+ expectEquals(0x1fffff, geo5());
+
expectEquals(34, geo1BCE());
expectEquals(36, geo2BCE());
expectEquals(131, geo3BCE());
diff --git a/test/618-checker-induction/src/Main.java b/test/618-checker-induction/src/Main.java
index 87a69b2..ecc129a 100644
--- a/test/618-checker-induction/src/Main.java
+++ b/test/618-checker-induction/src/Main.java
@@ -248,6 +248,33 @@
return closed; // only needs last value
}
+ /// CHECK-START: int Main.closedFormInductionTrivialIf() loop_optimization (before)
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Select loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Return [<<Phi1>>] loop:none
+ //
+ /// CHECK-START: int Main.closedFormInductionTrivialIf() loop_optimization (after)
+ /// CHECK-NOT: Phi
+ /// CHECK-NOT: Select
+ //
+ /// CHECK-START: int Main.closedFormInductionTrivialIf() instruction_simplifier$after_bce (after)
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 81 loop:none
+ /// CHECK-DAG: Return [<<Int>>] loop:none
+ static int closedFormInductionTrivialIf() {
+ int closed = 11;
+ for (int i = 0; i < 10; i++) {
+ // Trivial if becomes trivial select at HIR level.
+ // Make sure this is still recognized as induction.
+ if (i < 5) {
+ closed += 7;
+ } else {
+ closed += 7;
+ }
+ }
+ return closed; // only needs last value
+ }
+
/// CHECK-START: int Main.closedFormNested() loop_optimization (before)
/// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none
/// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop1>> outer_loop:none
@@ -732,6 +759,7 @@
expectEquals(12395, closedFormInductionUp());
expectEquals(12295, closedFormInductionInAndDown(12345));
+ expectEquals(81, closedFormInductionTrivialIf());
expectEquals(10 * 10, closedFormNested());
expectEquals(12345 + 17 * 23 * 7, closedFormNestedAlt());
for (int n = -4; n < 10; n++) {
