Recognize XOR-based periodic induction.
Rationale:
This is a commonly used construct (e.g. x = !x for booleans
and x ^= 1 for integers). This CL prepares some upcoming
optimizations that exploit such inductions.
Change-Id: I46edffb9de1075a836995daf5c2dfff7891f3034
Test: 530-checker-loops2 and induction_var_analysis_test
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index 292bc4e..7c467f6 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -107,7 +107,7 @@
}
// Builds if-statement at depth d.
- HPhi* BuildIf(int d, HBasicBlock** ifT, HBasicBlock **ifF) {
+ HPhi* BuildIf(int d, HBasicBlock** ifT, HBasicBlock** ifF) {
HBasicBlock* cond = new (&allocator_) HBasicBlock(graph_);
HBasicBlock* ifTrue = new (&allocator_) HBasicBlock(graph_);
HBasicBlock* ifFalse = new (&allocator_) HBasicBlock(graph_);
@@ -259,15 +259,15 @@
// k = - i;
// }
BuildLoopNest(1);
- HInstruction *add = InsertInstruction(
+ HInstruction* add = InsertInstruction(
new (&allocator_) HAdd(Primitive::kPrimInt, constant100_, basic_[0]), 0);
- HInstruction *sub = InsertInstruction(
+ HInstruction* sub = InsertInstruction(
new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0]), 0);
- HInstruction *mul = InsertInstruction(
+ HInstruction* mul = InsertInstruction(
new (&allocator_) HMul(Primitive::kPrimInt, constant100_, basic_[0]), 0);
- HInstruction *shl = InsertInstruction(
+ HInstruction* shl = InsertInstruction(
new (&allocator_) HShl(Primitive::kPrimInt, basic_[0], constant1_), 0);
- HInstruction *neg = InsertInstruction(
+ HInstruction* neg = InsertInstruction(
new (&allocator_) HNeg(Primitive::kPrimInt, basic_[0]), 0);
PerformInductionVarAnalysis();
@@ -291,10 +291,10 @@
HPhi* k = InsertLoopPhi(0, 0);
k->AddInput(constant0_);
- HInstruction *add = InsertInstruction(
+ HInstruction* add = InsertInstruction(
new (&allocator_) HAdd(Primitive::kPrimInt, k, constant100_), 0);
HInstruction* store1 = InsertArrayStore(add, 0);
- HInstruction *sub = InsertInstruction(
+ HInstruction* sub = InsertInstruction(
new (&allocator_) HSub(Primitive::kPrimInt, add, constant1_), 0);
HInstruction* store2 = InsertArrayStore(sub, 0);
k->AddInput(sub);
@@ -381,7 +381,7 @@
k->AddInput(constant0_);
HInstruction* store = InsertArrayStore(k, 0);
- HInstruction *sub = InsertInstruction(
+ HInstruction* sub = InsertInstruction(
new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0]), 0);
k->AddInput(sub);
PerformInductionVarAnalysis();
@@ -407,7 +407,7 @@
HInstruction* store = InsertArrayStore(k, 0);
k->AddInput(t);
- HInstruction *sub = InsertInstruction(
+ HInstruction* sub = InsertInstruction(
new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0], 0), 0);
t->AddInput(sub);
PerformInductionVarAnalysis();
@@ -431,15 +431,15 @@
HPhi* k = InsertLoopPhi(0, 0);
k->AddInput(constant0_);
- HInstruction *add = InsertInstruction(
+ HInstruction* add = InsertInstruction(
new (&allocator_) HAdd(Primitive::kPrimInt, k, constant100_), 0);
- HInstruction *sub = InsertInstruction(
+ HInstruction* sub = InsertInstruction(
new (&allocator_) HSub(Primitive::kPrimInt, k, constant100_), 0);
- HInstruction *mul = InsertInstruction(
+ HInstruction* mul = InsertInstruction(
new (&allocator_) HMul(Primitive::kPrimInt, k, constant100_), 0);
- HInstruction *shl = InsertInstruction(
+ HInstruction* shl = InsertInstruction(
new (&allocator_) HShl(Primitive::kPrimInt, k, constant1_), 0);
- HInstruction *neg = InsertInstruction(
+ HInstruction* neg = InsertInstruction(
new (&allocator_) HNeg(Primitive::kPrimInt, k), 0);
k->AddInput(
InsertInstruction(new (&allocator_) HShl(Primitive::kPrimInt, basic_[0], constant1_), 0));
@@ -497,7 +497,7 @@
k->AddInput(constant0_);
HInstruction* store = InsertArrayStore(k, 0);
- HInstruction *sub = InsertInstruction(
+ HInstruction* sub = InsertInstruction(
new (&allocator_) HSub(Primitive::kPrimInt, constant1_, k), 0);
k->AddInput(sub);
PerformInductionVarAnalysis();
@@ -506,6 +506,45 @@
EXPECT_STREQ("periodic((1), (0)):PrimInt", GetInductionInfo(sub, 0).c_str());
}
+TEST_F(InductionVarAnalysisTest, FindXorPeriodicInduction) {
+ // Setup:
+ // k = 0;
+ // for (int i = 0; i < 100; i++) {
+ // a[k] = 0;
+ // k = k ^ 1;
+ // }
+ BuildLoopNest(1);
+ HPhi* k = InsertLoopPhi(0, 0);
+ k->AddInput(constant0_);
+
+ HInstruction* store = InsertArrayStore(k, 0);
+ HInstruction* x = InsertInstruction(
+ new (&allocator_) HXor(Primitive::kPrimInt, k, constant1_), 0);
+ k->AddInput(x);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("periodic((0), (1)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str());
+ EXPECT_STREQ("periodic((1), (0)):PrimInt", GetInductionInfo(x, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindXor100PeriodicInduction) {
+ // Setup:
+ // k = 100;
+ // for (int i = 0; i < 100; i++) {
+ // k = k ^ 100;
+ // }
+ BuildLoopNest(1);
+ HPhi* k = InsertLoopPhi(0, 0);
+ k->AddInput(constant100_);
+
+ HInstruction* x = InsertInstruction(
+ new (&allocator_) HXor(Primitive::kPrimInt, k, constant100_), 0);
+ k->AddInput(x);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("periodic(((100) ^ (100)), (100)):PrimInt", GetInductionInfo(x, 0).c_str());
+}
+
TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) {
// Setup:
// k = 0;
@@ -526,15 +565,15 @@
k_header->AddInput(k_body);
// Derived expressions.
- HInstruction *add = InsertInstruction(
+ HInstruction* add = InsertInstruction(
new (&allocator_) HAdd(Primitive::kPrimInt, k_body, constant100_), 0);
- HInstruction *sub = InsertInstruction(
+ HInstruction* sub = InsertInstruction(
new (&allocator_) HSub(Primitive::kPrimInt, k_body, constant100_), 0);
- HInstruction *mul = InsertInstruction(
+ HInstruction* mul = InsertInstruction(
new (&allocator_) HMul(Primitive::kPrimInt, k_body, constant100_), 0);
- HInstruction *shl = InsertInstruction(
+ HInstruction* shl = InsertInstruction(
new (&allocator_) HShl(Primitive::kPrimInt, k_body, constant1_), 0);
- HInstruction *neg = InsertInstruction(
+ HInstruction* neg = InsertInstruction(
new (&allocator_) HNeg(Primitive::kPrimInt, k_body), 0);
PerformInductionVarAnalysis();
@@ -563,7 +602,7 @@
k[d] = InsertLoopPhi(0, d);
}
- HInstruction *inc = InsertInstruction(
+ HInstruction* inc = InsertInstruction(
new (&allocator_) HAdd(Primitive::kPrimInt, constant1_, k[9]), 9);
HInstruction* store = InsertArrayStore(inc, 9);
@@ -597,7 +636,7 @@
// a[i] = 0;
// }
BuildLoopNest(1);
- HInstruction *conv = InsertInstruction(
+ HInstruction* conv = InsertInstruction(
new (&allocator_) HTypeConversion(Primitive::kPrimByte, basic_[0], -1), 0);
HInstruction* store1 = InsertArrayStore(conv, 0);
HInstruction* store2 = InsertArrayStore(basic_[0], 0);