Added geometric induction variables analysis.
Rationale:
Information on geometric and polynomial (coming soon) sequences
are nice to have to further enhance BCE and last-value assignment.
Test: test-art-host
Change-Id: Ib5e2998c3eb1009def6fd00b82935da7c3ba7c6e
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index 3425b88..2199c8e 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -84,6 +84,7 @@
entry_->AddInstruction(parameter_);
constant0_ = graph_->GetIntConstant(0);
constant1_ = graph_->GetIntConstant(1);
+ constant2_ = graph_->GetIntConstant(2);
constant100_ = graph_->GetIntConstant(100);
float_constant0_ = graph_->GetFloatConstant(0.0f);
return_->AddInstruction(new (&allocator_) HReturnVoid());
@@ -191,6 +192,7 @@
HInstruction* parameter_; // "this"
HInstruction* constant0_;
HInstruction* constant1_;
+ HInstruction* constant2_;
HInstruction* constant100_;
HInstruction* float_constant0_;
@@ -252,11 +254,11 @@
TEST_F(InductionVarAnalysisTest, FindDerivedInduction) {
// Setup:
// for (int i = 0; i < 100; i++) {
- // k = 100 + i;
- // k = 100 - i;
- // k = 100 * i;
- // k = i << 1;
- // k = - i;
+ // t = 100 + i;
+ // t = 100 - i;
+ // t = 100 * i;
+ // t = i << 1;
+ // t = - i;
// }
BuildLoopNest(1);
HInstruction* add = InsertInstruction(
@@ -288,18 +290,20 @@
// a[k] = 0;
// }
BuildLoopNest(1);
- HPhi* k = InsertLoopPhi(0, 0);
- k->AddInput(constant0_);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant0_);
HInstruction* add = InsertInstruction(
- new (&allocator_) HAdd(Primitive::kPrimInt, k, constant100_), 0);
+ new (&allocator_) HAdd(Primitive::kPrimInt, k_header, constant100_), 0);
HInstruction* store1 = InsertArrayStore(add, 0);
HInstruction* sub = InsertInstruction(
new (&allocator_) HSub(Primitive::kPrimInt, add, constant1_), 0);
HInstruction* store2 = InsertArrayStore(sub, 0);
- k->AddInput(sub);
+ k_header->AddInput(sub);
PerformInductionVarAnalysis();
+ EXPECT_STREQ("(((100) - (1)) * i + (0)):PrimInt",
+ GetInductionInfo(k_header, 0).c_str());
EXPECT_STREQ("(((100) - (1)) * i + (100)):PrimInt",
GetInductionInfo(store1->InputAt(1), 0).c_str());
EXPECT_STREQ("(((100) - (1)) * i + ((100) - (1))):PrimInt",
@@ -335,6 +339,7 @@
k_header->AddInput(k_body);
PerformInductionVarAnalysis();
+ EXPECT_STREQ("((1) * i + (0)):PrimInt", GetInductionInfo(k_header, 0).c_str());
EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str());
// Both increments get same induction.
@@ -367,6 +372,153 @@
PerformInductionVarAnalysis();
EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str());
+
+ // Both increments get same induction.
+ EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc1));
+ EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc2));
+}
+
+TEST_F(InductionVarAnalysisTest, FindGeometricMulInduction) {
+ // Setup:
+ // k = 1;
+ // for (int i = 0; i < 100; i++) {
+ // k = k * 100; // geometric (x 100)
+ // }
+ BuildLoopNest(1);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant1_);
+
+ HInstruction* mul = InsertInstruction(
+ new (&allocator_) HMul(Primitive::kPrimInt, k_header, constant100_), 0);
+ k_header->AddInput(mul);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("geo((1) * 100 ^ i + (0)):PrimInt", GetInductionInfo(k_header, 0).c_str());
+ EXPECT_STREQ("geo((100) * 100 ^ i + (0)):PrimInt", GetInductionInfo(mul, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindGeometricShlInductionAndDerived) {
+ // Setup:
+ // k = 1;
+ // for (int i = 0; i < 100; i++) {
+ // t = k + 1;
+ // k = k << 1; // geometric (x 2)
+ // t = k + 100;
+ // t = k - 1;
+ // t = - t;
+ // t = k * 2;
+ // t = k << 2;
+ // }
+ BuildLoopNest(1);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant1_);
+
+ HInstruction* add1 = InsertInstruction(
+ new (&allocator_) HAdd(Primitive::kPrimInt, k_header, constant1_), 0);
+ HInstruction* shl1 = InsertInstruction(
+ new (&allocator_) HShl(Primitive::kPrimInt, k_header, constant1_), 0);
+ HInstruction* add2 = InsertInstruction(
+ new (&allocator_) HAdd(Primitive::kPrimInt, shl1, constant100_), 0);
+ HInstruction* sub = InsertInstruction(
+ new (&allocator_) HSub(Primitive::kPrimInt, shl1, constant1_), 0);
+ HInstruction* neg = InsertInstruction(
+ new (&allocator_) HNeg(Primitive::kPrimInt, sub), 0);
+ HInstruction* mul = InsertInstruction(
+ new (&allocator_) HMul(Primitive::kPrimInt, shl1, constant2_), 0);
+ HInstruction* shl2 = InsertInstruction(
+ new (&allocator_) HShl(Primitive::kPrimInt, shl1, constant2_), 0);
+ k_header->AddInput(shl1);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("geo((1) * 2 ^ i + (0)):PrimInt", GetInductionInfo(k_header, 0).c_str());
+ EXPECT_STREQ("geo((1) * 2 ^ i + (1)):PrimInt", GetInductionInfo(add1, 0).c_str());
+ EXPECT_STREQ("geo((2) * 2 ^ i + (0)):PrimInt", GetInductionInfo(shl1, 0).c_str());
+ EXPECT_STREQ("geo((2) * 2 ^ i + (100)):PrimInt", GetInductionInfo(add2, 0).c_str());
+ EXPECT_STREQ("geo((2) * 2 ^ i + ((0) - (1))):PrimInt", GetInductionInfo(sub, 0).c_str());
+ EXPECT_STREQ("geo(( - (2)) * 2 ^ i + ( - ((0) - (1)))):PrimInt",
+ GetInductionInfo(neg, 0).c_str());
+ EXPECT_STREQ("geo(((2) * (2)) * 2 ^ i + (0)):PrimInt", GetInductionInfo(mul, 0).c_str());
+ EXPECT_STREQ("geo(((2) * (4)) * 2 ^ i + (0)):PrimInt", GetInductionInfo(shl2, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindGeometricDivInductionAndDerived) {
+ // Setup:
+ // k = 1;
+ // for (int i = 0; i < 100; i++) {
+ // t = k + 100;
+ // t = k - 1;
+ // t = - t
+ // t = k * 2;
+ // t = k << 2;
+ // k = k / 100; // geometric (/ 100)
+ // }
+ BuildLoopNest(1);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant1_);
+
+ HInstruction* add = InsertInstruction(
+ new (&allocator_) HAdd(Primitive::kPrimInt, k_header, constant100_), 0);
+ HInstruction* sub = InsertInstruction(
+ new (&allocator_) HSub(Primitive::kPrimInt, k_header, constant1_), 0);
+ HInstruction* neg = InsertInstruction(
+ new (&allocator_) HNeg(Primitive::kPrimInt, sub), 0);
+ HInstruction* mul = InsertInstruction(
+ new (&allocator_) HMul(Primitive::kPrimInt, k_header, constant2_), 0);
+ HInstruction* shl = InsertInstruction(
+ new (&allocator_) HShl(Primitive::kPrimInt, k_header, constant2_), 0);
+ HInstruction* div = InsertInstruction(
+ new (&allocator_) HDiv(Primitive::kPrimInt, k_header, constant100_, kNoDexPc), 0);
+ k_header->AddInput(div);
+ PerformInductionVarAnalysis();
+
+ // Note, only the phi in the cycle and direct additive derived are classified.
+ EXPECT_STREQ("geo((1) * 100 ^ -i + (0)):PrimInt", GetInductionInfo(k_header, 0).c_str());
+ EXPECT_STREQ("geo((1) * 100 ^ -i + (100)):PrimInt", GetInductionInfo(add, 0).c_str());
+ EXPECT_STREQ("geo((1) * 100 ^ -i + ((0) - (1))):PrimInt", GetInductionInfo(sub, 0).c_str());
+ EXPECT_STREQ("", GetInductionInfo(neg, 0).c_str());
+ EXPECT_STREQ("", GetInductionInfo(mul, 0).c_str());
+ EXPECT_STREQ("", GetInductionInfo(shl, 0).c_str());
+ EXPECT_STREQ("", GetInductionInfo(div, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindGeometricRemInductionAndDerived) {
+ // Setup:
+ // k = 1;
+ // for (int i = 0; i < 100; i++) {
+ // t = k + 100;
+ // t = k - 1;
+ // t = -t
+ // t = k * 2;
+ // t = k << 2;
+ // k = k % 100; // geometric (% 100)
+ // }
+ BuildLoopNest(1);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant1_);
+
+ HInstruction* add = InsertInstruction(
+ new (&allocator_) HAdd(Primitive::kPrimInt, k_header, constant100_), 0);
+ HInstruction* sub = InsertInstruction(
+ new (&allocator_) HSub(Primitive::kPrimInt, k_header, constant1_), 0);
+ HInstruction* neg = InsertInstruction(
+ new (&allocator_) HNeg(Primitive::kPrimInt, sub), 0);
+ HInstruction* mul = InsertInstruction(
+ new (&allocator_) HMul(Primitive::kPrimInt, k_header, constant2_), 0);
+ HInstruction* shl = InsertInstruction(
+ new (&allocator_) HShl(Primitive::kPrimInt, k_header, constant2_), 0);
+ HInstruction* rem = InsertInstruction(
+ new (&allocator_) HRem(Primitive::kPrimInt, k_header, constant100_, kNoDexPc), 0);
+ k_header->AddInput(rem);
+ PerformInductionVarAnalysis();
+
+ // Note, only the phi in the cycle and direct additive derived are classified.
+ EXPECT_STREQ("geo((1) mod_i 100 + (0)):PrimInt", GetInductionInfo(k_header, 0).c_str());
+ EXPECT_STREQ("geo((1) mod_i 100 + (100)):PrimInt", GetInductionInfo(add, 0).c_str());
+ EXPECT_STREQ("geo((1) mod_i 100 + ((0) - (1))):PrimInt", GetInductionInfo(sub, 0).c_str());
+ EXPECT_STREQ("", GetInductionInfo(neg, 0).c_str());
+ EXPECT_STREQ("", GetInductionInfo(mul, 0).c_str());
+ EXPECT_STREQ("", GetInductionInfo(shl, 0).c_str());
+ EXPECT_STREQ("", GetInductionInfo(rem, 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindFirstOrderWrapAroundInduction) {
@@ -377,17 +529,20 @@
// k = 100 - i;
// }
BuildLoopNest(1);
- HPhi* k = InsertLoopPhi(0, 0);
- k->AddInput(constant0_);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant0_);
- HInstruction* store = InsertArrayStore(k, 0);
+ HInstruction* store = InsertArrayStore(k_header, 0);
HInstruction* sub = InsertInstruction(
new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0]), 0);
- k->AddInput(sub);
+ k_header->AddInput(sub);
PerformInductionVarAnalysis();
EXPECT_STREQ("wrap((0), (( - (1)) * i + (100)):PrimInt):PrimInt",
+ GetInductionInfo(k_header, 0).c_str());
+ EXPECT_STREQ("wrap((0), (( - (1)) * i + (100)):PrimInt):PrimInt",
GetInductionInfo(store->InputAt(1), 0).c_str());
+ EXPECT_STREQ("(( - (1)) * i + (100)):PrimInt", GetInductionInfo(sub, 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindSecondOrderWrapAroundInduction) {
@@ -400,13 +555,13 @@
// t = 100 - i;
// }
BuildLoopNest(1);
- HPhi* k = InsertLoopPhi(0, 0);
- k->AddInput(constant0_);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant0_);
HPhi* t = InsertLoopPhi(1, 0);
t->AddInput(constant100_);
- HInstruction* store = InsertArrayStore(k, 0);
- k->AddInput(t);
+ HInstruction* store = InsertArrayStore(k_header, 0);
+ k_header->AddInput(t);
HInstruction* sub = InsertInstruction(
new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0], 0), 0);
t->AddInput(sub);
@@ -426,23 +581,27 @@
// t = k << 1;
// t = - k;
// k = i << 1;
+ // t = - k;
// }
BuildLoopNest(1);
- HPhi* k = InsertLoopPhi(0, 0);
- k->AddInput(constant0_);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant0_);
HInstruction* add = InsertInstruction(
- new (&allocator_) HAdd(Primitive::kPrimInt, k, constant100_), 0);
+ new (&allocator_) HAdd(Primitive::kPrimInt, k_header, constant100_), 0);
HInstruction* sub = InsertInstruction(
- new (&allocator_) HSub(Primitive::kPrimInt, k, constant100_), 0);
+ new (&allocator_) HSub(Primitive::kPrimInt, k_header, constant100_), 0);
HInstruction* mul = InsertInstruction(
- new (&allocator_) HMul(Primitive::kPrimInt, k, constant100_), 0);
- HInstruction* shl = InsertInstruction(
- new (&allocator_) HShl(Primitive::kPrimInt, k, constant1_), 0);
- HInstruction* neg = InsertInstruction(
- new (&allocator_) HNeg(Primitive::kPrimInt, k), 0);
- k->AddInput(
- InsertInstruction(new (&allocator_) HShl(Primitive::kPrimInt, basic_[0], constant1_), 0));
+ new (&allocator_) HMul(Primitive::kPrimInt, k_header, constant100_), 0);
+ HInstruction* shl1 = InsertInstruction(
+ new (&allocator_) HShl(Primitive::kPrimInt, k_header, constant1_), 0);
+ HInstruction* neg1 = InsertInstruction(
+ new (&allocator_) HNeg(Primitive::kPrimInt, k_header), 0);
+ HInstruction* shl2 = InsertInstruction(
+ new (&allocator_) HShl(Primitive::kPrimInt, basic_[0], constant1_), 0);
+ HInstruction* neg2 = InsertInstruction(
+ new (&allocator_) HNeg(Primitive::kPrimInt, shl2), 0);
+ k_header->AddInput(shl2);
PerformInductionVarAnalysis();
EXPECT_STREQ("wrap((100), ((2) * i + (100)):PrimInt):PrimInt",
@@ -452,9 +611,11 @@
EXPECT_STREQ("wrap((0), (((2) * (100)) * i + (0)):PrimInt):PrimInt",
GetInductionInfo(mul, 0).c_str());
EXPECT_STREQ("wrap((0), (((2) * (2)) * i + (0)):PrimInt):PrimInt",
- GetInductionInfo(shl, 0).c_str());
+ GetInductionInfo(shl1, 0).c_str());
EXPECT_STREQ("wrap((0), (( - (2)) * i + (0)):PrimInt):PrimInt",
- GetInductionInfo(neg, 0).c_str());
+ GetInductionInfo(neg1, 0).c_str());
+ EXPECT_STREQ("((2) * i + (0)):PrimInt", GetInductionInfo(shl2, 0).c_str());
+ EXPECT_STREQ("(( - (2)) * i + (0)):PrimInt", GetInductionInfo(neg2, 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindPeriodicInduction) {
@@ -470,15 +631,15 @@
// k = d;
// }
BuildLoopNest(1);
- HPhi* k = InsertLoopPhi(0, 0);
- k->AddInput(constant0_);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant0_);
HPhi* t = InsertLoopPhi(1, 0);
t->AddInput(constant100_);
- HInstruction* store1 = InsertArrayStore(k, 0);
+ HInstruction* store1 = InsertArrayStore(k_header, 0);
HInstruction* store2 = InsertArrayStore(t, 0);
- k->AddInput(t);
- t->AddInput(k);
+ k_header->AddInput(t);
+ t->AddInput(k_header);
PerformInductionVarAnalysis();
EXPECT_STREQ("periodic((0), (100)):PrimInt", GetInductionInfo(store1->InputAt(1), 0).c_str());
@@ -493,13 +654,13 @@
// k = 1 - k;
// }
BuildLoopNest(1);
- HPhi* k = InsertLoopPhi(0, 0);
- k->AddInput(constant0_);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant0_);
- HInstruction* store = InsertArrayStore(k, 0);
+ HInstruction* store = InsertArrayStore(k_header, 0);
HInstruction* sub = InsertInstruction(
- new (&allocator_) HSub(Primitive::kPrimInt, constant1_, k), 0);
- k->AddInput(sub);
+ new (&allocator_) HSub(Primitive::kPrimInt, constant1_, k_header), 0);
+ k_header->AddInput(sub);
PerformInductionVarAnalysis();
EXPECT_STREQ("periodic((0), (1)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str());
@@ -514,13 +675,13 @@
// k = k ^ 1;
// }
BuildLoopNest(1);
- HPhi* k = InsertLoopPhi(0, 0);
- k->AddInput(constant0_);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant0_);
- HInstruction* store = InsertArrayStore(k, 0);
+ HInstruction* store = InsertArrayStore(k_header, 0);
HInstruction* x = InsertInstruction(
- new (&allocator_) HXor(Primitive::kPrimInt, k, constant1_), 0);
- k->AddInput(x);
+ new (&allocator_) HXor(Primitive::kPrimInt, k_header, constant1_), 0);
+ k_header->AddInput(x);
PerformInductionVarAnalysis();
EXPECT_STREQ("periodic((0), (1)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str());
@@ -534,14 +695,15 @@
// k = 1 ^ k;
// }
BuildLoopNest(1);
- HPhi* k = InsertLoopPhi(0, 0);
- k->AddInput(constant1_);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant1_);
HInstruction* x = InsertInstruction(
- new (&allocator_) HXor(Primitive::kPrimInt, constant1_, k), 0);
- k->AddInput(x);
+ new (&allocator_) HXor(Primitive::kPrimInt, constant1_, k_header), 0);
+ k_header->AddInput(x);
PerformInductionVarAnalysis();
+ EXPECT_STREQ("periodic((1), ((1) ^ (1))):PrimInt", GetInductionInfo(k_header, 0).c_str());
EXPECT_STREQ("periodic(((1) ^ (1)), (1)):PrimInt", GetInductionInfo(x, 0).c_str());
}
@@ -552,14 +714,15 @@
// k = k ^ 100;
// }
BuildLoopNest(1);
- HPhi* k = InsertLoopPhi(0, 0);
- k->AddInput(constant1_);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant1_);
HInstruction* x = InsertInstruction(
- new (&allocator_) HXor(Primitive::kPrimInt, k, constant100_), 0);
- k->AddInput(x);
+ new (&allocator_) HXor(Primitive::kPrimInt, k_header, constant100_), 0);
+ k_header->AddInput(x);
PerformInductionVarAnalysis();
+ EXPECT_STREQ("periodic((1), ((1) ^ (100))):PrimInt", GetInductionInfo(k_header, 0).c_str());
EXPECT_STREQ("periodic(((1) ^ (100)), (1)):PrimInt", GetInductionInfo(x, 0).c_str());
}
@@ -570,13 +733,14 @@
// k = (k == 0);
// }
BuildLoopNest(1);
- HPhi* k = InsertLoopPhi(0, 0);
- k->AddInput(constant0_);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant0_);
- HInstruction* x = InsertInstruction(new (&allocator_) HEqual(k, constant0_), 0);
- k->AddInput(x);
+ HInstruction* x = InsertInstruction(new (&allocator_) HEqual(k_header, constant0_), 0);
+ k_header->AddInput(x);
PerformInductionVarAnalysis();
+ EXPECT_STREQ("periodic((0), (1)):PrimBoolean", GetInductionInfo(k_header, 0).c_str());
EXPECT_STREQ("periodic((1), (0)):PrimBoolean", GetInductionInfo(x, 0).c_str());
}
@@ -587,13 +751,14 @@
// k = (0 == k);
// }
BuildLoopNest(1);
- HPhi* k = InsertLoopPhi(0, 0);
- k->AddInput(constant0_);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant0_);
- HInstruction* x = InsertInstruction(new (&allocator_) HEqual(constant0_, k), 0);
- k->AddInput(x);
+ HInstruction* x = InsertInstruction(new (&allocator_) HEqual(constant0_, k_header), 0);
+ k_header->AddInput(x);
PerformInductionVarAnalysis();
+ EXPECT_STREQ("periodic((0), (1)):PrimBoolean", GetInductionInfo(k_header, 0).c_str());
EXPECT_STREQ("periodic((1), (0)):PrimBoolean", GetInductionInfo(x, 0).c_str());
}
@@ -604,13 +769,14 @@
// k = (k != 1);
// }
BuildLoopNest(1);
- HPhi* k = InsertLoopPhi(0, 0);
- k->AddInput(constant0_);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant0_);
- HInstruction* x = InsertInstruction(new (&allocator_) HNotEqual(k, constant1_), 0);
- k->AddInput(x);
+ HInstruction* x = InsertInstruction(new (&allocator_) HNotEqual(k_header, constant1_), 0);
+ k_header->AddInput(x);
PerformInductionVarAnalysis();
+ EXPECT_STREQ("periodic((0), (1)):PrimBoolean", GetInductionInfo(k_header, 0).c_str());
EXPECT_STREQ("periodic((1), (0)):PrimBoolean", GetInductionInfo(x, 0).c_str());
}
@@ -621,13 +787,14 @@
// k = (1 != k);
// }
BuildLoopNest(1);
- HPhi* k = InsertLoopPhi(0, 0);
- k->AddInput(constant0_);
+ HPhi* k_header = InsertLoopPhi(0, 0);
+ k_header->AddInput(constant0_);
- HInstruction* x = InsertInstruction(new (&allocator_) HNotEqual(constant1_, k), 0);
- k->AddInput(x);
+ HInstruction* x = InsertInstruction(new (&allocator_) HNotEqual(constant1_, k_header), 0);
+ k_header->AddInput(x);
PerformInductionVarAnalysis();
+ EXPECT_STREQ("periodic((0), (1)):PrimBoolean", GetInductionInfo(k_header, 0).c_str());
EXPECT_STREQ("periodic((1), (0)):PrimBoolean", GetInductionInfo(x, 0).c_str());
}
@@ -635,6 +802,7 @@
// Setup:
// k = 0;
// for (int i = 0; i < 100; i++) {
+ // t = - k;
// k = 1 - k;
// t = k + 100;
// t = k - 100;
@@ -646,28 +814,31 @@
HPhi* k_header = InsertLoopPhi(0, 0);
k_header->AddInput(constant0_);
- HInstruction* k_body = InsertInstruction(
+ HInstruction* neg1 = InsertInstruction(
+ new (&allocator_) HNeg(Primitive::kPrimInt, k_header), 0);
+ HInstruction* idiom = InsertInstruction(
new (&allocator_) HSub(Primitive::kPrimInt, constant1_, k_header), 0);
- k_header->AddInput(k_body);
-
- // Derived expressions.
HInstruction* add = InsertInstruction(
- new (&allocator_) HAdd(Primitive::kPrimInt, k_body, constant100_), 0);
+ new (&allocator_) HAdd(Primitive::kPrimInt, idiom, constant100_), 0);
HInstruction* sub = InsertInstruction(
- new (&allocator_) HSub(Primitive::kPrimInt, k_body, constant100_), 0);
+ new (&allocator_) HSub(Primitive::kPrimInt, idiom, constant100_), 0);
HInstruction* mul = InsertInstruction(
- new (&allocator_) HMul(Primitive::kPrimInt, k_body, constant100_), 0);
+ new (&allocator_) HMul(Primitive::kPrimInt, idiom, constant100_), 0);
HInstruction* shl = InsertInstruction(
- new (&allocator_) HShl(Primitive::kPrimInt, k_body, constant1_), 0);
- HInstruction* neg = InsertInstruction(
- new (&allocator_) HNeg(Primitive::kPrimInt, k_body), 0);
+ new (&allocator_) HShl(Primitive::kPrimInt, idiom, constant1_), 0);
+ HInstruction* neg2 = InsertInstruction(
+ new (&allocator_) HNeg(Primitive::kPrimInt, idiom), 0);
+ k_header->AddInput(idiom);
PerformInductionVarAnalysis();
+ EXPECT_STREQ("periodic((0), (1)):PrimInt", GetInductionInfo(k_header, 0).c_str());
+ EXPECT_STREQ("periodic((0), ( - (1))):PrimInt", GetInductionInfo(neg1, 0).c_str());
+ EXPECT_STREQ("periodic((1), (0)):PrimInt", GetInductionInfo(idiom, 0).c_str());
EXPECT_STREQ("periodic(((1) + (100)), (100)):PrimInt", GetInductionInfo(add, 0).c_str());
EXPECT_STREQ("periodic(((1) - (100)), ((0) - (100))):PrimInt", GetInductionInfo(sub, 0).c_str());
EXPECT_STREQ("periodic((100), (0)):PrimInt", GetInductionInfo(mul, 0).c_str());
EXPECT_STREQ("periodic((2), (0)):PrimInt", GetInductionInfo(shl, 0).c_str());
- EXPECT_STREQ("periodic(( - (1)), (0)):PrimInt", GetInductionInfo(neg, 0).c_str());
+ EXPECT_STREQ("periodic(( - (1)), (0)):PrimInt", GetInductionInfo(neg2, 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) {
@@ -683,18 +854,18 @@
// }
BuildLoopNest(10);
- HPhi* k[10];
+ HPhi* k_header[10];
for (int d = 0; d < 10; d++) {
- k[d] = InsertLoopPhi(0, d);
+ k_header[d] = InsertLoopPhi(0, d);
}
HInstruction* inc = InsertInstruction(
- new (&allocator_) HAdd(Primitive::kPrimInt, constant1_, k[9]), 9);
+ new (&allocator_) HAdd(Primitive::kPrimInt, constant1_, k_header[9]), 9);
HInstruction* store = InsertArrayStore(inc, 9);
for (int d = 0; d < 10; d++) {
- k[d]->AddInput((d != 0) ? k[d - 1] : constant0_);
- k[d]->AddInput((d != 9) ? k[d + 1] : inc);
+ k_header[d]->AddInput((d != 0) ? k_header[d - 1] : constant0_);
+ k_header[d]->AddInput((d != 9) ? k_header[d + 1] : inc);
}
PerformInductionVarAnalysis();