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

1 files changed, 256 insertions, 85 deletions

diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index 3425b88260..2199c8e105 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -84,6 +84,7 @@ class InductionVarAnalysisTest : public CommonCompilerTest {
     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 @@ class InductionVarAnalysisTest : public CommonCompilerTest {
   HInstruction* parameter_;  // "this"
   HInstruction* constant0_;
   HInstruction* constant1_;
+  HInstruction* constant2_;
   HInstruction* constant100_;
   HInstruction* float_constant0_;
 
@@ -252,11 +254,11 @@ TEST_F(InductionVarAnalysisTest, FindBasicInduction) {
 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 @@ TEST_F(InductionVarAnalysisTest, FindChainInduction) {
   //   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 @@ TEST_F(InductionVarAnalysisTest, FindTwoWayBasicInduction) {
   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 @@ TEST_F(InductionVarAnalysisTest, FindTwoWayDerivedInduction) {
   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 @@ TEST_F(InductionVarAnalysisTest, FindFirstOrderWrapAroundInduction) {
   //   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 @@ TEST_F(InductionVarAnalysisTest, FindSecondOrderWrapAroundInduction) {
   //   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 @@ TEST_F(InductionVarAnalysisTest, FindWrapAroundDerivedInduction) {
   //   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 @@ TEST_F(InductionVarAnalysisTest, FindWrapAroundDerivedInduction) {
   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 @@ TEST_F(InductionVarAnalysisTest, FindPeriodicInduction) {
   //   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 @@ TEST_F(InductionVarAnalysisTest, FindIdiomaticPeriodicInduction) {
   //   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 @@ TEST_F(InductionVarAnalysisTest, FindXorPeriodicInduction) {
   //   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 @@ TEST_F(InductionVarAnalysisTest, FindXorConstantLeftPeriodicInduction) {
   //   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 @@ TEST_F(InductionVarAnalysisTest, FindXor100PeriodicInduction) {
   //   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 @@ TEST_F(InductionVarAnalysisTest, FindBooleanEqPeriodicInduction) {
   //   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 @@ TEST_F(InductionVarAnalysisTest, FindBooleanEqConstantLeftPeriodicInduction) {
   //   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 @@ TEST_F(InductionVarAnalysisTest, FindBooleanNePeriodicInduction) {
   //   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 @@ TEST_F(InductionVarAnalysisTest, FindBooleanNeConstantLeftPeriodicInduction) {
   //   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 @@ TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) {
   // 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 @@ TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) {
   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 @@ TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) {
   // }
   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();