commit 639cc8c7bbb7d8c341173bcf24604ccb4328acb8
author Aart Bik <ajcbik@google.com> Tue Oct 18 13:03:31 2016 -0700
committer Aart Bik <ajcbik@google.com> Thu Oct 20 14:14:17 2016 -0700
tree ae8181b94ddd145edaff141a2b351478161f1559
parent 3941c882ea7b54772dec36a9a1b33e0b8a7474f7

Improve recognition of select-based period induction.

Rationale:
Similar to the previous CL, this helps to eliminate more dead induction.
Now, CaffeineLogic, when compiled with dx (rather than jack) improves
by a 1.5 speedup (9000us -> 6000us).

Note:
We need to run the simplifier before induction analysis to trigger
the select simplification first. Although a bit of a compile-time hit,
it seems a good idea to run a simplifier here again anyway.

Test: test-art-host
Change-Id: I93b91ca40a4d64385c64393028e8d213f0c904a8

compiler/optimizing/induction_var_analysis_test.cc

diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index 7c467f6..7599c8f 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -527,22 +527,108 @@
   EXPECT_STREQ("periodic((1), (0)):PrimInt", GetInductionInfo(x, 0).c_str());
 }
 
+TEST_F(InductionVarAnalysisTest, FindXorConstantLeftPeriodicInduction) {
+  // Setup:
+  // k = 1;
+  // for (int i = 0; i < 100; i++) {
+  //   k = 1 ^ k;
+  // }
+  BuildLoopNest(1);
+  HPhi* k = InsertLoopPhi(0, 0);
+  k->AddInput(constant1_);
+
+  HInstruction* x = InsertInstruction(
+      new (&allocator_) HXor(Primitive::kPrimInt, constant1_, k), 0);
+  k->AddInput(x);
+  PerformInductionVarAnalysis();
+
+  EXPECT_STREQ("periodic(((1) ^ (1)), (1)):PrimInt", GetInductionInfo(x, 0).c_str());
+}
+
 TEST_F(InductionVarAnalysisTest, FindXor100PeriodicInduction) {
   // Setup:
-  // k = 100;
+  // k = 1;
   // for (int i = 0; i < 100; i++) {
   //   k = k ^ 100;
   // }
   BuildLoopNest(1);
   HPhi* k = InsertLoopPhi(0, 0);
-  k->AddInput(constant100_);
+  k->AddInput(constant1_);
 
   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());
+  EXPECT_STREQ("periodic(((1) ^ (100)), (1)):PrimInt", GetInductionInfo(x, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindBooleanEqPeriodicInduction) {
+  // Setup:
+  // k = 0;
+  // for (int i = 0; i < 100; i++) {
+  //   k = (k == 0);
+  // }
+  BuildLoopNest(1);
+  HPhi* k = InsertLoopPhi(0, 0);
+  k->AddInput(constant0_);
+
+  HInstruction* x = InsertInstruction(new (&allocator_) HEqual(k, constant0_), 0);
+  k->AddInput(x);
+  PerformInductionVarAnalysis();
+
+  EXPECT_STREQ("periodic((1), (0)):PrimBoolean", GetInductionInfo(x, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindBooleanEqConstantLeftPeriodicInduction) {
+  // Setup:
+  // k = 0;
+  // for (int i = 0; i < 100; i++) {
+  //   k = (0 == k);
+  // }
+  BuildLoopNest(1);
+  HPhi* k = InsertLoopPhi(0, 0);
+  k->AddInput(constant0_);
+
+  HInstruction* x = InsertInstruction(new (&allocator_) HEqual(constant0_, k), 0);
+  k->AddInput(x);
+  PerformInductionVarAnalysis();
+
+  EXPECT_STREQ("periodic((1), (0)):PrimBoolean", GetInductionInfo(x, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindBooleanNePeriodicInduction) {
+  // Setup:
+  // k = 0;
+  // for (int i = 0; i < 100; i++) {
+  //   k = (k != 1);
+  // }
+  BuildLoopNest(1);
+  HPhi* k = InsertLoopPhi(0, 0);
+  k->AddInput(constant0_);
+
+  HInstruction* x = InsertInstruction(new (&allocator_) HNotEqual(k, constant1_), 0);
+  k->AddInput(x);
+  PerformInductionVarAnalysis();
+
+  EXPECT_STREQ("periodic((1), (0)):PrimBoolean", GetInductionInfo(x, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindBooleanNeConstantLeftPeriodicInduction) {
+  // Setup:
+  // k = 0;
+  // for (int i = 0; i < 100; i++) {
+  //   k = (1 != k);
+  // }
+  BuildLoopNest(1);
+  HPhi* k = InsertLoopPhi(0, 0);
+  k->AddInput(constant0_);
+
+  HInstruction* x = InsertInstruction(new (&allocator_) HNotEqual(constant1_, k), 0);
+  k->AddInput(x);
+  PerformInductionVarAnalysis();
+
+  EXPECT_STREQ("periodic((1), (0)):PrimBoolean", GetInductionInfo(x, 0).c_str());
 }
 
 TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) {