diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 1561502..c240c67 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -296,21 +296,22 @@
       update = SolveAddSub(
           loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true);
     } else if (instruction->IsMul()) {
-      update = SolveGeo(
+      update = SolveOp(
           loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kMul);
     } else if (instruction->IsDiv()) {
-      update = SolveGeo(
+      update = SolveOp(
           loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kDiv);
     } else if (instruction->IsRem()) {
-      update = SolveGeo(
-          loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kNop);
+      update = SolveOp(
+          loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kRem);
     } else if (instruction->IsShl()) {
       HInstruction* mulc = GetMultConstantForShift(loop, instruction);
       if (mulc != nullptr) {
-        update = SolveGeo(loop, phi, instruction, instruction->InputAt(0), mulc, kMul);
+        update = SolveOp(loop, phi, instruction, instruction->InputAt(0), mulc, kMul);
       }
     } else if (instruction->IsXor()) {
-      update = SolveXor(loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1));
+      update = SolveOp(
+          loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kXor);
     } else if (instruction->IsEqual()) {
       update = SolveTest(loop, phi, instruction, 0);
     } else if (instruction->IsNotEqual()) {
@@ -334,6 +335,7 @@
         FALLTHROUGH_INTENDED;
       case kPolynomial:
       case kGeometric:
+      case kWrapAround:
         // Classify first phi and then the rest of the cycle "on-demand".
         // Statements are scanned in order.
         AssignInfo(loop, phi, induction);
@@ -402,14 +404,15 @@
                                                                             InductionOp op) {
   // Transfer over an addition or subtraction: any invariant, linear, polynomial, geometric,
   // wrap-around, or periodic can be combined with an invariant to yield a similar result.
-  // Even two linear inputs can be combined. Other combinations fail.
+  // Two linear or two polynomial inputs can be combined too. Other combinations fail.
   if (a != nullptr && b != nullptr) {
     type_ = Narrowest(type_, Narrowest(a->type, b->type));
     if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
       return CreateInvariantOp(op, a, b);
-    } else if (a->induction_class == kLinear && b->induction_class == kLinear) {
-      return CreateInduction(kLinear,
-                             kNop,
+    } else if ((a->induction_class == kLinear && b->induction_class == kLinear) ||
+               (a->induction_class == kPolynomial && b->induction_class == kPolynomial)) {
+      return CreateInduction(a->induction_class,
+                             a->operation,
                              TransferAddSub(a->op_a, b->op_a, op),
                              TransferAddSub(a->op_b, b->op_b, op),
                              /*fetch*/ nullptr,
@@ -555,18 +558,33 @@
                                                                          HInstruction* y,
                                                                          InductionOp op,
                                                                          bool is_first_call) {
-  // Solve within a cycle over an addition or subtraction: adding or subtracting an
-  // invariant value, seeded from phi, keeps adding to the stride of the linear induction.
+  // Solve within a cycle over an addition or subtraction.
   InductionInfo* b = LookupInfo(loop, y);
-  if (b != nullptr && b->induction_class == kInvariant) {
-    if (x == entry_phi) {
-      return (op == kAdd) ? b : CreateInvariantOp(kNeg, nullptr, b);
-    }
-    auto it = cycle_.find(x);
-    if (it != cycle_.end()) {
-      InductionInfo* a = it->second;
-      if (a->induction_class == kInvariant) {
-        return CreateInvariantOp(op, a, b);
+  if (b != nullptr) {
+    if (b->induction_class == kInvariant) {
+      // Adding or subtracting an invariant value, seeded from phi,
+      // keeps adding to the stride of the linear induction.
+      if (x == entry_phi) {
+        return (op == kAdd) ? b : CreateInvariantOp(kNeg, nullptr, b);
+      }
+      auto it = cycle_.find(x);
+      if (it != cycle_.end()) {
+        InductionInfo* a = it->second;
+        if (a->induction_class == kInvariant) {
+          return CreateInvariantOp(op, a, b);
+        }
+      }
+    } else if (op == kAdd && 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,
+                               initial,
+                               /*fetch*/ nullptr,
+                               type_);
       }
     }
   }
@@ -593,58 +611,63 @@
       }
     }
   }
-
   return nullptr;
 }
 
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveGeo(HLoopInformation* loop,
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveOp(HLoopInformation* loop,
                                                                       HInstruction* entry_phi,
                                                                       HInstruction* instruction,
                                                                       HInstruction* x,
                                                                       HInstruction* y,
                                                                       InductionOp op) {
-  // Solve within a tight cycle that is formed by exactly two instructions, one phi and
-  // one update, for a geometric induction of the form k = k * c.
-  if (x == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) {
-    InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
-    InductionInfo* b = LookupInfo(loop, y);
-    if (b != nullptr && b->induction_class == kInvariant && b->operation == kFetch) {
-      return CreateInduction(kGeometric,
-                             op,
-                             initial,
-                             CreateConstant(0, type_),
-                             b->fetch,
-                             type_);
-    }
-  }
-  return nullptr;
-}
-
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveXor(HLoopInformation* loop,
-                                                                      HInstruction* entry_phi,
-                                                                      HInstruction* instruction,
-                                                                      HInstruction* x,
-                                                                      HInstruction* y) {
-  // Solve within a tight cycle on periodic idiom of the form x = c ^ x or x = x ^ c.
+  // Solve within a tight cycle for a binary operation k = k op c or, for some op, k = c op k.
   if (entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) {
-    InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
-    InductionInfo* a = LookupInfo(loop, x);
-    if (a != nullptr && a->induction_class == kInvariant && entry_phi == y) {
-      return CreateInduction(kPeriodic,
-                             kNop,
-                             CreateInvariantOp(kXor, a, initial),
-                             initial,
-                             /*fetch*/ nullptr,
-                             type_);
-    }
+    InductionInfo* c = nullptr;
     InductionInfo* b = LookupInfo(loop, y);
     if (b != nullptr && b->induction_class == kInvariant && entry_phi == x) {
-      return CreateInduction(kPeriodic,
-                             kNop,
-                             CreateInvariantOp(kXor, initial, b),
-                             initial,
-                             /*fetch*/ nullptr,
-                             type_);
+      c = b;
+    } else if (op != kDiv && op != kRem) {
+      InductionInfo* a = LookupInfo(loop, x);
+      if (a != nullptr && a->induction_class == kInvariant && entry_phi == y) {
+        c = a;
+      }
+    }
+    // Found suitable operand left or right?
+    if (c != nullptr) {
+      InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
+      switch (op) {
+        case kMul:
+        case kDiv:
+          // Restrict base of geometric induction to direct fetch.
+          if (c->operation == kFetch) {
+            return CreateInduction(kGeometric,
+                                   op,
+                                   initial,
+                                   CreateConstant(0, type_),
+                                   c->fetch,
+                                   type_);
+          };
+          break;
+        case kRem:
+          // Idiomatic MOD wrap-around induction.
+          return CreateInduction(kWrapAround,
+                                 kNop,
+                                 initial,
+                                 CreateInvariantOp(kRem, initial, c),
+                                 /*fetch*/ nullptr,
+                                 type_);
+        case kXor:
+          // Idiomatic XOR periodic induction.
+          return CreateInduction(kPeriodic,
+                                 kNop,
+                                 CreateInvariantOp(kXor, initial, c),
+                                 initial,
+                                 /*fetch*/ nullptr,
+                                 type_);
+        default:
+          CHECK(false) << op;
+          break;
+      }
     }
   }
   return nullptr;
@@ -659,9 +682,9 @@
   HInstruction* x = instruction->InputAt(0);
   HInstruction* y = instruction->InputAt(1);
   if (IsExact(LookupInfo(loop, x), &value) && value == opposite_value) {
-    return SolveXor(loop, entry_phi, instruction, graph_->GetIntConstant(1), y);
+    return SolveOp(loop, entry_phi, instruction, graph_->GetIntConstant(1), y, kXor);
   } else if (IsExact(LookupInfo(loop, y), &value) && value == opposite_value) {
-    return SolveXor(loop, entry_phi, instruction, x, graph_->GetIntConstant(1));
+    return SolveOp(loop, entry_phi, instruction, x, graph_->GetIntConstant(1), kXor);
   }
   return nullptr;
 }
@@ -1018,7 +1041,7 @@
 HInstruction* HInductionVarAnalysis::GetMultConstantForShift(HLoopInformation* loop,
                                                              HInstruction* instruction) {
   // Obtain the constant needed to treat shift as equivalent multiplication. This yields an
-  // existing instruction if the constants is already there. Otherwise, this has a side effect
+  // 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.
@@ -1102,6 +1125,7 @@
         case kNeg:   inv += " - ";  break;
         case kMul:   inv += " * ";  break;
         case kDiv:   inv += " / ";  break;
+        case kRem:   inv += " % ";  break;
         case kXor:   inv += " ^ ";  break;
         case kLT:    inv += " < ";  break;
         case kLE:    inv += " <= "; break;
@@ -1118,32 +1142,30 @@
       return inv;
     } else {
       if (info->induction_class == kLinear) {
+        DCHECK(info->operation == kNop);
         return "(" + InductionToString(info->op_a) + " * i + " +
                      InductionToString(info->op_b) + "):" +
                      Primitive::PrettyDescriptor(info->type);
       } else if (info->induction_class == kPolynomial) {
-        return "poly( sum_i(" + InductionToString(info->op_a) + ") + " +
+        DCHECK(info->operation == kNop);
+        return "poly(sum_lt(" + InductionToString(info->op_a) + ") + " +
                                 InductionToString(info->op_b) + "):" +
                                 Primitive::PrettyDescriptor(info->type);
       } else if (info->induction_class == kGeometric) {
+        DCHECK(info->operation == kMul || info->operation == kDiv);
         DCHECK(info->fetch != nullptr);
-        if (info->operation == kNop) {
-         return "geo(" + InductionToString(info->op_a) + " mod_i " +
-                         FetchToString(info->fetch) + " + " +
-                         InductionToString(info->op_b) + "):" +
-                         Primitive::PrettyDescriptor(info->type);
-        } else {
-         return "geo(" + InductionToString(info->op_a) + " * " +
-                         FetchToString(info->fetch) +
-                         (info->operation == kMul ? " ^ i + " : " ^ -i + ") +
-                         InductionToString(info->op_b) + "):" +
-                         Primitive::PrettyDescriptor(info->type);
-        }
+        return "geo(" + InductionToString(info->op_a) + " * " +
+                        FetchToString(info->fetch) +
+                        (info->operation == kMul ? " ^ i + " : " ^ -i + ") +
+                        InductionToString(info->op_b) + "):" +
+                        Primitive::PrettyDescriptor(info->type);
       } else if (info->induction_class == kWrapAround) {
+        DCHECK(info->operation == kNop);
         return "wrap(" + InductionToString(info->op_a) + ", " +
                          InductionToString(info->op_b) + "):" +
                          Primitive::PrettyDescriptor(info->type);
       } else if (info->induction_class == kPeriodic) {
+        DCHECK(info->operation == kNop);
         return "periodic(" + InductionToString(info->op_a) + ", " +
                              InductionToString(info->op_b) + "):" +
                              Primitive::PrettyDescriptor(info->type);
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 94afc71..4720f2d 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -65,6 +65,7 @@
     kNeg,
     kMul,
     kDiv,
+    kRem,
     kXor,
     kFetch,
     // Trip-counts.
@@ -85,10 +86,10 @@
    *         op: a + b, a - b, -b, a * b, a / b, a % b, a ^ b, fetch
    *   (2) linear:
    *         nop: a * i + b
-   *   (3) polynomial:                        // TODO: coming soon
-   *         nop: sum_i(a) + b, for linear a
+   *   (3) polynomial:
+   *         nop: sum_lt(a) + b, for linear a
    *   (4) geometric:
-   *         op: a * fetch^i + b, a * fetch^-i + b, a mod_i fetch + b
+   *         op: a * fetch^i + b, a * fetch^-i + b
    *   (5) wrap-around
    *         nop: a, then defined by b
    *   (6) periodic
@@ -177,17 +178,12 @@
                              HInstruction* y,
                              InductionOp op,
                              bool is_first_call);  // possibly swaps x and y to try again
-  InductionInfo* SolveGeo(HLoopInformation* loop,
-                          HInstruction* entry_phi,
-                          HInstruction* instruction,
-                          HInstruction* x,
-                          HInstruction* y,
-                          InductionOp op);
-  InductionInfo* SolveXor(HLoopInformation* loop,
-                          HInstruction* entry_phi,
-                          HInstruction* instruction,
-                          HInstruction* x,
-                          HInstruction* y);
+  InductionInfo* SolveOp(HLoopInformation* loop,
+                         HInstruction* entry_phi,
+                         HInstruction* instruction,
+                         HInstruction* x,
+                         HInstruction* y,
+                         InductionOp op);
   InductionInfo* SolveTest(HLoopInformation* loop,
                            HInstruction* entry_phi,
                            HInstruction* instruction,
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index 2199c8e..2d182f6 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -85,6 +85,7 @@
     constant0_ = graph_->GetIntConstant(0);
     constant1_ = graph_->GetIntConstant(1);
     constant2_ = graph_->GetIntConstant(2);
+    constant7_ = graph_->GetIntConstant(7);
     constant100_ = graph_->GetIntConstant(100);
     float_constant0_ = graph_->GetFloatConstant(0.0f);
     return_->AddInstruction(new (&allocator_) HReturnVoid());
@@ -193,6 +194,7 @@
   HInstruction* constant0_;
   HInstruction* constant1_;
   HInstruction* constant2_;
+  HInstruction* constant7_;
   HInstruction* constant100_;
   HInstruction* float_constant0_;
 
@@ -378,6 +380,135 @@
   EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc2));
 }
 
+TEST_F(InductionVarAnalysisTest, AddLinear) {
+  // Setup:
+  // for (int i = 0; i < 100; i++) {
+  //   t1 = i + i;
+  //   t2 = 7 + i;
+  //   t3 = t1 + t2;
+  // }
+  BuildLoopNest(1);
+
+  HInstruction* add1 = InsertInstruction(
+      new (&allocator_) HAdd(Primitive::kPrimInt, basic_[0], basic_[0]), 0);
+  HInstruction* add2 = InsertInstruction(
+      new (&allocator_) HAdd(Primitive::kPrimInt, constant7_, basic_[0]), 0);
+  HInstruction* add3 = InsertInstruction(
+      new (&allocator_) HAdd(Primitive::kPrimInt, add1, add2), 0);
+  PerformInductionVarAnalysis();
+
+  EXPECT_STREQ("((1) * i + (0)):PrimInt", GetInductionInfo(basic_[0], 0).c_str());
+  EXPECT_STREQ("(((1) + (1)) * i + (0)):PrimInt", GetInductionInfo(add1, 0).c_str());
+  EXPECT_STREQ("((1) * i + (7)):PrimInt", GetInductionInfo(add2, 0).c_str());
+  EXPECT_STREQ("((((1) + (1)) + (1)) * i + (7)):PrimInt", GetInductionInfo(add3, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindPolynomialInduction) {
+  // Setup:
+  // k = 1;
+  // for (int i = 0; i < 100; i++) {
+  //   t = i * 2;
+  //   t = 100 + t
+  //   k = t + k;  // polynomial
+  // }
+  BuildLoopNest(1);
+  HPhi* k_header = InsertLoopPhi(0, 0);
+  k_header->AddInput(constant1_);
+
+  HInstruction* mul = InsertInstruction(
+      new (&allocator_) HMul(Primitive::kPrimInt, basic_[0], constant2_), 0);
+  HInstruction* add = InsertInstruction(
+      new (&allocator_) HAdd(Primitive::kPrimInt, constant100_, mul), 0);
+  HInstruction* pol = InsertInstruction(
+      new (&allocator_) HAdd(Primitive::kPrimInt, add, k_header), 0);
+  k_header->AddInput(pol);
+  PerformInductionVarAnalysis();
+
+  // Note, only the phi in the cycle and the base linear induction are classified.
+  EXPECT_STREQ("poly(sum_lt(((2) * i + (100)):PrimInt) + (1)):PrimInt",
+               GetInductionInfo(k_header, 0).c_str());
+  EXPECT_STREQ("((2) * i + (100)):PrimInt", GetInductionInfo(add, 0).c_str());
+  EXPECT_STREQ("", GetInductionInfo(pol, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindPolynomialInductionAndDerived) {
+  // 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 + i;  // polynomial
+  // }
+  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* pol = InsertInstruction(
+      new (&allocator_) HAdd(Primitive::kPrimInt, k_header, basic_[0]), 0);
+  k_header->AddInput(pol);
+  PerformInductionVarAnalysis();
+
+  // Note, only the phi in the cycle and derived are classified.
+  EXPECT_STREQ("poly(sum_lt(((1) * i + (0)):PrimInt) + (1)):PrimInt",
+               GetInductionInfo(k_header, 0).c_str());
+  EXPECT_STREQ("poly(sum_lt(((1) * i + (0)):PrimInt) + ((1) + (100))):PrimInt",
+               GetInductionInfo(add, 0).c_str());
+  EXPECT_STREQ("poly(sum_lt(((1) * i + (0)):PrimInt) + ((1) - (1))):PrimInt",
+               GetInductionInfo(sub, 0).c_str());
+  EXPECT_STREQ("poly(sum_lt((( - (1)) * i + (0)):PrimInt) + ((1) - (1))):PrimInt",
+               GetInductionInfo(neg, 0).c_str());
+  EXPECT_STREQ("poly(sum_lt(((2) * i + (0)):PrimInt) + (2)):PrimInt",
+               GetInductionInfo(mul, 0).c_str());
+  EXPECT_STREQ("poly(sum_lt(((4) * i + (0)):PrimInt) + (4)):PrimInt",
+               GetInductionInfo(shl, 0).c_str());
+  EXPECT_STREQ("", GetInductionInfo(pol, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, AddPolynomial) {
+  // Setup:
+  // k = 7;
+  // for (int i = 0; i < 100; i++) {
+  //   t = k + k;
+  //   t = t + k;
+  //   k = k + i
+  // }
+  BuildLoopNest(1);
+  HPhi* k_header = InsertLoopPhi(0, 0);
+  k_header->AddInput(constant7_);
+
+  HInstruction* add1 = InsertInstruction(
+      new (&allocator_) HAdd(Primitive::kPrimInt, k_header, k_header), 0);
+  HInstruction* add2 = InsertInstruction(
+      new (&allocator_) HAdd(Primitive::kPrimInt, add1, k_header), 0);
+  HInstruction* add3 = InsertInstruction(
+      new (&allocator_) HAdd(Primitive::kPrimInt, k_header, basic_[0]), 0);
+  k_header->AddInput(add3);
+  PerformInductionVarAnalysis();
+
+  // Note, only the phi in the cycle and added-derived are classified.
+  EXPECT_STREQ("poly(sum_lt(((1) * i + (0)):PrimInt) + (7)):PrimInt",
+               GetInductionInfo(k_header, 0).c_str());
+  EXPECT_STREQ("poly(sum_lt((((1) + (1)) * i + (0)):PrimInt) + ((7) + (7))):PrimInt",
+               GetInductionInfo(add1, 0).c_str());
+  EXPECT_STREQ(
+      "poly(sum_lt(((((1) + (1)) + (1)) * i + (0)):PrimInt) + (((7) + (7)) + (7))):PrimInt",
+      GetInductionInfo(add2, 0).c_str());
+  EXPECT_STREQ("", GetInductionInfo(add3, 0).c_str());
+}
+
 TEST_F(InductionVarAnalysisTest, FindGeometricMulInduction) {
   // Setup:
   // k = 1;
@@ -481,20 +612,20 @@
   EXPECT_STREQ("", GetInductionInfo(div, 0).c_str());
 }
 
-TEST_F(InductionVarAnalysisTest, FindGeometricRemInductionAndDerived) {
+TEST_F(InductionVarAnalysisTest, FindRemWrapAroundInductionAndDerived) {
   // Setup:
-  // k = 1;
+  // k = 100;
   // 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)
+  //   k = k % 7;
   // }
   BuildLoopNest(1);
   HPhi* k_header = InsertLoopPhi(0, 0);
-  k_header->AddInput(constant1_);
+  k_header->AddInput(constant100_);
 
   HInstruction* add = InsertInstruction(
       new (&allocator_) HAdd(Primitive::kPrimInt, k_header, constant100_), 0);
@@ -507,17 +638,17 @@
   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);
+      new (&allocator_) HRem(Primitive::kPrimInt, k_header, constant7_, 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());
+  // Note, only the phi in the cycle and derived are classified.
+  EXPECT_STREQ("wrap((100), ((100) % (7))):PrimInt", GetInductionInfo(k_header, 0).c_str());
+  EXPECT_STREQ("wrap(((100) + (100)), (((100) % (7)) + (100))):PrimInt", GetInductionInfo(add, 0).c_str());
+  EXPECT_STREQ("wrap(((100) - (1)), (((100) % (7)) - (1))):PrimInt", GetInductionInfo(sub, 0).c_str());
+  EXPECT_STREQ("wrap(( - ((100) - (1))), ( - (((100) % (7)) - (1)))):PrimInt", GetInductionInfo(neg, 0).c_str());
+  EXPECT_STREQ("wrap(((100) * (2)), (((100) % (7)) * (2))):PrimInt", GetInductionInfo(mul, 0).c_str());
+  EXPECT_STREQ("wrap(((100) * (4)), (((100) % (7)) * (4))):PrimInt", GetInductionInfo(shl, 0).c_str());
   EXPECT_STREQ("", GetInductionInfo(rem, 0).c_str());
 }
 
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 75619a3..e665551 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -460,6 +460,8 @@
   if (info != nullptr) {
     if (info->induction_class == HInductionVarAnalysis::kLinear) {
       return IsConstant(info->op_a, kExact, stride_value);
+    } else if (info->induction_class == HInductionVarAnalysis::kPolynomial) {
+      return NeedsTripCount(info->op_a, stride_value);
     } else if (info->induction_class == HInductionVarAnalysis::kWrapAround) {
       return NeedsTripCount(info->op_b, stride_value);
     }
@@ -492,7 +494,7 @@
                                                       bool in_body,
                                                       bool is_min) const {
   DCHECK(info != nullptr);
-  DCHECK(info->induction_class == HInductionVarAnalysis::kLinear);
+  DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kLinear);
   // Detect common situation where an offset inside the trip-count cancels out during range
   // analysis (finding max a * (TC - 1) + OFFSET for a == 1 and TC = UPPER - OFFSET or finding
   // min a * (TC - 1) + OFFSET for a == -1 and TC = OFFSET - UPPER) to avoid losing information
@@ -539,25 +541,49 @@
                   GetVal(info->op_b, trip, in_body, is_min));
 }
 
+InductionVarRange::Value InductionVarRange::GetPolynomial(HInductionVarAnalysis::InductionInfo* info,
+                                                          HInductionVarAnalysis::InductionInfo* trip,
+                                                          bool in_body,
+                                                          bool is_min) const {
+  DCHECK(info != nullptr);
+  DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPolynomial);
+  int64_t a = 0;
+  int64_t b = 0;
+  if (IsConstant(info->op_a->op_a, kExact, &a) && CanLongValueFitIntoInt(a) && a >= 0 &&
+      IsConstant(info->op_a->op_b, kExact, &b) && CanLongValueFitIntoInt(b) && b >= 0) {
+    // Evaluate bounds on sum_i=0^m-1(a * i + b) + c with a,b >= 0 for known
+    // maximum index value m as a * (m * (m-1)) / 2 + b * m + c.
+    Value c = GetVal(info->op_b, trip, in_body, is_min);
+    if (is_min) {
+      return c;
+    } else {
+      Value m = GetVal(trip, trip, in_body, is_min);
+      Value t = DivValue(MulValue(m, SubValue(m, Value(1))), Value(2));
+      Value x = MulValue(Value(a), t);
+      Value y = MulValue(Value(b), m);
+      return AddValue(AddValue(x, y), c);
+    }
+  }
+  return Value();
+}
+
 InductionVarRange::Value InductionVarRange::GetGeometric(HInductionVarAnalysis::InductionInfo* info,
                                                          HInductionVarAnalysis::InductionInfo* trip,
                                                          bool in_body,
                                                          bool is_min) const {
   DCHECK(info != nullptr);
-  DCHECK(info->induction_class == HInductionVarAnalysis::kGeometric);
+  DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kGeometric);
   int64_t a = 0;
   int64_t f = 0;
   if (IsConstant(info->op_a, kExact, &a) &&
       CanLongValueFitIntoInt(a) &&
-      IsIntAndGet(info->fetch, &f) &&
-      CanLongValueFitIntoInt(f) && f >= 1) {
-    // Conservative bounds on a * f^-i + b with f >= 1 can be computed without trip count.
-    // Same for mod. All other forms would require a much more elaborate evaluation.
+      IsIntAndGet(info->fetch, &f) && f >= 1) {
+    // Conservative bounds on a * f^-i + b with f >= 1 can be computed without
+    // trip count. Other forms would require a much more elaborate evaluation.
     const bool is_min_a = a >= 0 ? is_min : !is_min;
     if (info->operation == HInductionVarAnalysis::kDiv) {
-      return AddValue(Value(is_min_a ? 0 : a), GetVal(info->op_b, trip, in_body, is_min));
-    } else if (info->operation == HInductionVarAnalysis::kNop) {
-      return AddValue(Value(is_min_a ? (a % f) : a), GetVal(info->op_b, trip, in_body, is_min));
+      Value b = GetVal(info->op_b, trip, in_body, is_min);
+      return is_min_a ? b : AddValue(Value(a), b);
     }
   }
   return Value();
@@ -572,7 +598,7 @@
   if (chase_hint_ == nullptr && in_body && trip != nullptr && instruction == trip->op_a->fetch) {
     if (is_min) {
       return Value(1);
-    } else if (!IsUnsafeTripCount(trip)) {
+    } else if (!instruction->IsConstant() && !IsUnsafeTripCount(trip)) {
       return Value(std::numeric_limits<int32_t>::max());
     }
   }
@@ -650,6 +676,8 @@
             return GetMul(info->op_a, info->op_b, trip, in_body, is_min);
           case HInductionVarAnalysis::kDiv:
             return GetDiv(info->op_a, info->op_b, trip, in_body, is_min);
+          case HInductionVarAnalysis::kRem:
+            return GetRem(info->op_a, info->op_b);
           case HInductionVarAnalysis::kXor:
             return GetXor(info->op_a, info->op_b);
           case HInductionVarAnalysis::kFetch:
@@ -675,7 +703,7 @@
       case HInductionVarAnalysis::kLinear:
         return CorrectForType(GetLinear(info, trip, in_body, is_min), info->type);
       case HInductionVarAnalysis::kPolynomial:
-        break;
+        return GetPolynomial(info, trip, in_body, is_min);
       case HInductionVarAnalysis::kGeometric:
         return GetGeometric(info, trip, in_body, is_min);
       case HInductionVarAnalysis::kWrapAround:
@@ -757,6 +785,21 @@
   return Value();
 }
 
+InductionVarRange::Value InductionVarRange::GetRem(
+    HInductionVarAnalysis::InductionInfo* info1,
+    HInductionVarAnalysis::InductionInfo* info2) const {
+  int64_t v1 = 0;
+  int64_t v2 = 0;
+  // Only accept exact values.
+  if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2) && v2 != 0) {
+    int64_t value = v1 % v2;
+    if (CanLongValueFitIntoInt(value)) {
+      return Value(static_cast<int32_t>(value));
+    }
+  }
+  return Value();
+}
+
 InductionVarRange::Value InductionVarRange::GetXor(
     HInductionVarAnalysis::InductionInfo* info1,
     HInductionVarAnalysis::InductionInfo* info2) const {
@@ -898,8 +941,12 @@
           upper = nullptr;
         }
         break;
+      case HInductionVarAnalysis::kPolynomial:
+        return GenerateLastValuePolynomial(info, trip, graph, block, lower);
       case HInductionVarAnalysis::kGeometric:
         return GenerateLastValueGeometric(info, trip, graph, block, lower);
+      case HInductionVarAnalysis::kWrapAround:
+        return GenerateLastValueWrapAround(info, trip, graph, block, lower);
       case HInductionVarAnalysis::kPeriodic:
         return GenerateLastValuePeriodic(info, trip, graph, block, lower, needs_taken_test);
       default:
@@ -925,13 +972,43 @@
       GenerateCode(info, trip, graph, block, upper, in_body, /* is_min */ false);
 }
 
+bool InductionVarRange::GenerateLastValuePolynomial(HInductionVarAnalysis::InductionInfo* info,
+                                                    HInductionVarAnalysis::InductionInfo* trip,
+                                                    HGraph* graph,
+                                                    HBasicBlock* block,
+                                                    /*out*/HInstruction** result) const {
+  DCHECK(info != nullptr);
+  DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPolynomial);
+  // Detect known coefficients and trip count (always taken).
+  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 &&
+      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
+    // maximum index value m as a * (m * (m-1)) / 2 + b * m + c.
+    // TODO: generalize
+    HInstruction* c_instr = nullptr;
+    if (GenerateCode(info->op_b, nullptr, graph, block, graph ? &c_instr : nullptr, false, false)) {
+      if (graph != nullptr) {
+        int64_t sum = a * ((m * (m - 1)) / 2) + b * m;
+        *result = Insert(block, new (graph->GetArena()) HAdd(info->type,
+                                                             graph->GetIntConstant(sum), c_instr));
+      }
+      return true;
+    }
+  }
+  return false;
+}
+
 bool InductionVarRange::GenerateLastValueGeometric(HInductionVarAnalysis::InductionInfo* info,
                                                    HInductionVarAnalysis::InductionInfo* trip,
                                                    HGraph* graph,
                                                    HBasicBlock* block,
                                                    /*out*/HInstruction** result) const {
   DCHECK(info != nullptr);
-  DCHECK(info->induction_class == HInductionVarAnalysis::kGeometric);
+  DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kGeometric);
   // Detect known base and trip count (always taken).
   int64_t f = 0;
   int64_t t = 0;
@@ -940,15 +1017,6 @@
     HInstruction* opb = nullptr;
     if (GenerateCode(info->op_a, nullptr, graph, block, &opa, false, false) &&
         GenerateCode(info->op_b, nullptr, graph, block, &opb, false, false)) {
-      // Generate a % f + b.
-      if (info->operation == HInductionVarAnalysis::kNop) {
-        if (graph != nullptr) {
-          HInstruction* rem =
-              Insert(block, new (graph->GetArena()) HRem(info->type, opa, info->fetch, kNoDexPc));
-          *result = Insert(block, new (graph->GetArena()) HAdd(info->type, rem, opb));
-        }
-        return true;
-      }
       // Compute f ^ t.
       int64_t fpowt = IntPow(f, t);
       if (graph != nullptr) {
@@ -980,6 +1048,28 @@
   return false;
 }
 
+bool InductionVarRange::GenerateLastValueWrapAround(HInductionVarAnalysis::InductionInfo* info,
+                                                    HInductionVarAnalysis::InductionInfo* trip,
+                                                    HGraph* graph,
+                                                    HBasicBlock* block,
+                                                    /*out*/HInstruction** result) const {
+  DCHECK(info != nullptr);
+  DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kWrapAround);
+  // Count depth.
+  int32_t depth = 0;
+  for (; info->induction_class == HInductionVarAnalysis::kWrapAround;
+       info = info->op_b, ++depth) {}
+  // Handle wrap(x, wrap(.., y)) if trip count reaches an invariant at end.
+  // TODO: generalize
+  int64_t t = 0;
+  if (info->induction_class == HInductionVarAnalysis::kInvariant &&
+      IsConstant(trip->op_a, kExact, &t) && t >= depth &&
+      GenerateCode(info, nullptr, graph, block, result, false, false)) {
+    return true;
+  }
+  return false;
+}
+
 bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::InductionInfo* info,
                                                   HInductionVarAnalysis::InductionInfo* trip,
                                                   HGraph* graph,
@@ -987,17 +1077,18 @@
                                                   /*out*/HInstruction** result,
                                                   /*out*/bool* needs_taken_test) const {
   DCHECK(info != nullptr);
-  DCHECK(info->induction_class == HInductionVarAnalysis::kPeriodic);
+  DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPeriodic);
   // Count period.
   int32_t period = 1;
   for (HInductionVarAnalysis::InductionInfo* p = info;
        p->induction_class == HInductionVarAnalysis::kPeriodic;
        p = p->op_b, ++period) {}
   // Handle periodic(x, y) case for restricted types.
+  // TODO: generalize
   if (period != 2 ||
       trip->op_a->type != Primitive::kPrimInt ||
       (info->type != Primitive::kPrimInt && info->type != Primitive::kPrimBoolean)) {
-    return false;  // TODO: easy to generalize
+    return false;
   }
   HInstruction* x_instr = nullptr;
   HInstruction* y_instr = nullptr;
@@ -1058,6 +1149,7 @@
         // invariants, some effort is made to keep this parameter consistent).
         switch (info->operation) {
           case HInductionVarAnalysis::kAdd:
+          case HInductionVarAnalysis::kRem:  // no proper is_min for second arg
           case HInductionVarAnalysis::kXor:  // no proper is_min for second arg
           case HInductionVarAnalysis::kLT:
           case HInductionVarAnalysis::kLE:
@@ -1070,6 +1162,8 @@
                 switch (info->operation) {
                   case HInductionVarAnalysis::kAdd:
                     operation = new (graph->GetArena()) HAdd(type, opa, opb); break;
+                  case HInductionVarAnalysis::kRem:
+                    operation = new (graph->GetArena()) HRem(type, opa, opb, kNoDexPc); break;
                   case HInductionVarAnalysis::kXor:
                     operation = new (graph->GetArena()) HXor(type, opa, opb); break;
                   case HInductionVarAnalysis::kLT:
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index f7360e8..ba14847 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -190,6 +190,10 @@
                   HInductionVarAnalysis::InductionInfo* trip,
                   bool in_body,
                   bool is_min) const;
+  Value GetPolynomial(HInductionVarAnalysis::InductionInfo* info,
+                      HInductionVarAnalysis::InductionInfo* trip,
+                      bool in_body,
+                      bool is_min) const;
   Value GetGeometric(HInductionVarAnalysis::InductionInfo* info,
                      HInductionVarAnalysis::InductionInfo* trip,
                      bool in_body,
@@ -212,6 +216,8 @@
                HInductionVarAnalysis::InductionInfo* trip,
                bool in_body,
                bool is_min) const;
+  Value GetRem(HInductionVarAnalysis::InductionInfo* info1,
+               HInductionVarAnalysis::InductionInfo* info2) const;
   Value GetXor(HInductionVarAnalysis::InductionInfo* info1,
                HInductionVarAnalysis::InductionInfo* info2) const;
 
@@ -249,12 +255,24 @@
                                 /*out*/ bool* needs_finite_test,
                                 /*out*/ bool* needs_taken_test) const;
 
+  bool GenerateLastValuePolynomial(HInductionVarAnalysis::InductionInfo* info,
+                                   HInductionVarAnalysis::InductionInfo* trip,
+                                   HGraph* graph,
+                                   HBasicBlock* block,
+                                   /*out*/HInstruction** result) const;
+
   bool GenerateLastValueGeometric(HInductionVarAnalysis::InductionInfo* info,
                                   HInductionVarAnalysis::InductionInfo* trip,
                                   HGraph* graph,
                                   HBasicBlock* block,
                                   /*out*/HInstruction** result) const;
 
+  bool GenerateLastValueWrapAround(HInductionVarAnalysis::InductionInfo* info,
+                                   HInductionVarAnalysis::InductionInfo* trip,
+                                   HGraph* graph,
+                                   HBasicBlock* block,
+                                   /*out*/HInstruction** result) const;
+
   bool GenerateLastValuePeriodic(HInductionVarAnalysis::InductionInfo* info,
                                  HInductionVarAnalysis::InductionInfo* trip,
                                  HGraph* graph,
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index 510841e..aa3e1aa 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -135,6 +135,8 @@
       case 'n': op = HInductionVarAnalysis::kNeg; break;
       case '*': op = HInductionVarAnalysis::kMul; break;
       case '/': op = HInductionVarAnalysis::kDiv; break;
+      case '%': op = HInductionVarAnalysis::kRem; break;
+      case '^': op = HInductionVarAnalysis::kXor; break;
       case '<': op = HInductionVarAnalysis::kLT;  break;
       default:  op = HInductionVarAnalysis::kNop; break;
     }
@@ -178,12 +180,21 @@
                                  Primitive::kPrimInt);
   }
 
+  /** Constructs a polynomial sum(a * i + b) + c induction. */
+  HInductionVarAnalysis::InductionInfo* CreatePolynomial(int32_t a, int32_t b, int32_t c) {
+    return iva_->CreateInduction(HInductionVarAnalysis::kPolynomial,
+                                 HInductionVarAnalysis::kNop,
+                                 CreateLinear(a, b),
+                                 CreateConst(c),
+                                 nullptr,
+                                 Primitive::kPrimInt);
+  }
+
   /** Constructs a geometric a * f^i + b induction. */
   HInductionVarAnalysis::InductionInfo* CreateGeometric(int32_t a, int32_t b, int32_t f, char op) {
     return iva_->CreateInduction(HInductionVarAnalysis::kGeometric,
-                                 op == '*' ? HInductionVarAnalysis::kMul :
-                                 op == '/' ? HInductionVarAnalysis::kDiv :
-                                             HInductionVarAnalysis::kNop,
+                                 op == '*' ? HInductionVarAnalysis::kMul
+                                           : HInductionVarAnalysis::kDiv,
                                  CreateConst(a),
                                  CreateConst(b),
                                  graph_->GetIntConstant(f),
@@ -200,7 +211,7 @@
                                  Primitive::kPrimInt);
   }
 
-  /** Constructs a wrap-around induction consisting of a constant, followed info */
+  /** Constructs a wrap-around induction consisting of a constant, followed by info. */
   HInductionVarAnalysis::InductionInfo* CreateWrapAround(
       int32_t initial,
       HInductionVarAnalysis::InductionInfo* info) {
@@ -256,6 +267,16 @@
     return range_.GetDiv(info1, info2, nullptr, /* in_body */ true, is_min);
   }
 
+  Value GetRem(HInductionVarAnalysis::InductionInfo* info1,
+               HInductionVarAnalysis::InductionInfo* info2) {
+    return range_.GetRem(info1, info2);
+  }
+
+  Value GetXor(HInductionVarAnalysis::InductionInfo* info1,
+               HInductionVarAnalysis::InductionInfo* info2) {
+    return range_.GetXor(info1, info2);
+  }
+
   bool IsExact(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
     return range_.IsConstant(info, InductionVarRange::kExact, value);
   }
@@ -438,6 +459,27 @@
   ExpectEqual(Value(20), GetMax(CreateWrapAround(20, -1, 10), nullptr));
 }
 
+TEST_F(InductionVarRangeTest, GetMinMaxPolynomial) {
+  ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), nullptr));
+  ExpectEqual(Value(), GetMax(CreatePolynomial(3, 5, 7), nullptr));
+  ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
+  ExpectEqual(Value(45), GetMax(CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
+  ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
+  ExpectEqual(Value(160), GetMax(CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
+  ExpectEqual(Value(-7), GetMin(CreatePolynomial(11, 13, -7),
+                               CreateTripCount(5, true, true)));
+  ExpectEqual(Value(111), GetMax(CreatePolynomial(11, 13, -7),
+                                 CreateTripCount(5, true, true)));
+  ExpectEqual(Value(-7), GetMin(CreatePolynomial(11, 13, -7),
+                               CreateTripCount(10, true, true)));
+  ExpectEqual(Value(506), GetMax(CreatePolynomial(11, 13, -7),
+                                 CreateTripCount(10, true, true)));
+  ExpectEqual(Value(), GetMin(CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
+  ExpectEqual(Value(), GetMax(CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
+  ExpectEqual(Value(), GetMin(CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
+  ExpectEqual(Value(), GetMax(CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
+}
+
 TEST_F(InductionVarRangeTest, GetMinMaxGeometricMul) {
   ExpectEqual(Value(), GetMin(CreateGeometric(1, 1, 1, '*'), nullptr));
   ExpectEqual(Value(), GetMax(CreateGeometric(1, 1, 1, '*'), nullptr));
@@ -454,17 +496,6 @@
   ExpectEqual(Value(-5), GetMax(CreateGeometric(-11, -5, 3, '/'), nullptr));
 }
 
-TEST_F(InductionVarRangeTest, GetMinMaxGeometricRem) {
-  ExpectEqual(Value(7), GetMin(CreateGeometric(11, 5, 3, '%'), nullptr));
-  ExpectEqual(Value(16), GetMax(CreateGeometric(11, 5, 3, '%'), nullptr));
-  ExpectEqual(Value(-3), GetMin(CreateGeometric(11, -5, 3, '%'), nullptr));
-  ExpectEqual(Value(6), GetMax(CreateGeometric(11, -5, 3, '%'), nullptr));
-  ExpectEqual(Value(-6), GetMin(CreateGeometric(-11, 5, 3, '%'), nullptr));
-  ExpectEqual(Value(3), GetMax(CreateGeometric(-11, 5, 3, '%'), nullptr));
-  ExpectEqual(Value(-16), GetMin(CreateGeometric(-11, -5, 3, '%'), nullptr));
-  ExpectEqual(Value(-7), GetMax(CreateGeometric(-11, -5, 3, '%'), nullptr));
-}
-
 TEST_F(InductionVarRangeTest, GetMinMaxPeriodic) {
   ExpectEqual(Value(-2), GetMin(CreateRange(-2, 99), nullptr));
   ExpectEqual(Value(99), GetMax(CreateRange(-2, 99), nullptr));
@@ -530,6 +561,46 @@
   ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), false));
 }
 
+TEST_F(InductionVarRangeTest, GetMinMaxRem) {
+  ExpectEqual(Value(), GetMin(CreateInvariant('%', CreateConst(2), CreateRange(10, 20)), nullptr));
+  ExpectEqual(Value(), GetMax(CreateInvariant('%', CreateConst(2), CreateRange(10, 20)), nullptr));
+  ExpectEqual(Value(), GetMin(CreateInvariant('%', CreateRange(10, 20), CreateConst(2)), nullptr));
+  ExpectEqual(Value(), GetMax(CreateInvariant('%', CreateRange(10, 20), CreateConst(2)), nullptr));
+  ExpectEqual(Value(2), GetMin(CreateInvariant('%', CreateConst(2), CreateConst(5)), nullptr));
+  ExpectEqual(Value(2), GetMax(CreateInvariant('%', CreateConst(2), CreateConst(5)), nullptr));
+  ExpectEqual(Value(1), GetMin(CreateInvariant('%', CreateConst(11), CreateConst(5)), nullptr));
+  ExpectEqual(Value(1), GetMax(CreateInvariant('%', CreateConst(11), CreateConst(5)), nullptr));
+}
+
+TEST_F(InductionVarRangeTest, GetRem) {
+  ExpectEqual(Value(0), GetRem(CreateConst(1), CreateConst(1)));
+  ExpectEqual(Value(2), GetRem(CreateConst(2), CreateConst(5)));
+  ExpectEqual(Value(1), GetRem(CreateConst(11), CreateConst(5)));
+  ExpectEqual(Value(-2), GetRem(CreateConst(-2), CreateConst(5)));
+  ExpectEqual(Value(-1), GetRem(CreateConst(-11), CreateConst(5)));
+  ExpectEqual(Value(2), GetRem(CreateConst(2), CreateConst(-5)));
+  ExpectEqual(Value(1), GetRem(CreateConst(11), CreateConst(-5)));
+  ExpectEqual(Value(-2), GetRem(CreateConst(-2), CreateConst(-5)));
+  ExpectEqual(Value(-1), GetRem(CreateConst(-11), CreateConst(-5)));
+  ExpectEqual(Value(), GetRem(CreateConst(1), CreateConst(0)));
+}
+
+TEST_F(InductionVarRangeTest, GetMinMaxXor) {
+  ExpectEqual(Value(), GetMin(CreateInvariant('^', CreateConst(2), CreateRange(10, 20)), nullptr));
+  ExpectEqual(Value(), GetMax(CreateInvariant('^', CreateConst(2), CreateRange(10, 20)), nullptr));
+  ExpectEqual(Value(), GetMin(CreateInvariant('^', CreateRange(10, 20), CreateConst(2)), nullptr));
+  ExpectEqual(Value(), GetMax(CreateInvariant('^', CreateRange(10, 20), CreateConst(2)), nullptr));
+  ExpectEqual(Value(3), GetMin(CreateInvariant('^', CreateConst(1), CreateConst(2)), nullptr));
+  ExpectEqual(Value(3), GetMax(CreateInvariant('^', CreateConst(1), CreateConst(2)), nullptr));
+}
+
+TEST_F(InductionVarRangeTest, GetXor) {
+  ExpectEqual(Value(0), GetXor(CreateConst(1), CreateConst(1)));
+  ExpectEqual(Value(3), GetXor(CreateConst(1), CreateConst(2)));
+  ExpectEqual(Value(-2), GetXor(CreateConst(1), CreateConst(-1)));
+  ExpectEqual(Value(0), GetXor(CreateConst(-1), CreateConst(-1)));
+}
+
 TEST_F(InductionVarRangeTest, AddValue) {
   ExpectEqual(Value(110), AddValue(Value(10), Value(100)));
   ExpectEqual(Value(-5), AddValue(Value(x_, 1, -4), Value(x_, -1, -1)));
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index f4616e3..9d73e29 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -64,7 +64,8 @@
       top_loop_(nullptr),
       last_loop_(nullptr),
       iset_(nullptr),
-      induction_simplication_count_(0) {
+      induction_simplication_count_(0),
+      simplified_(false) {
 }
 
 void HLoopOptimization::Run() {
@@ -169,9 +170,15 @@
     if (current_induction_simplification_count != induction_simplication_count_) {
       induction_range_.ReVisit(node->loop_info);
     }
-    SimplifyBlocks(node);
-    SimplifyInduction(node);
-    SimplifyBlocks(node);
+    // Repeat simplifications until no more changes occur. Note that since
+    // each simplification consists of eliminating code (without introducing
+    // new code), this process is always finite.
+    do {
+      simplified_ = false;
+      SimplifyBlocks(node);
+      SimplifyInduction(node);
+    } while (simplified_);
+    // Remove inner loops when empty.
     if (node->inner == nullptr) {
       RemoveIfEmptyInnerLoop(node);
     }
@@ -198,63 +205,57 @@
       for (HInstruction* i : *iset_) {
         RemoveFromCycle(i);
       }
+      simplified_ = true;
       induction_simplication_count_++;
     }
   }
 }
 
 void HLoopOptimization::SimplifyBlocks(LoopNode* node) {
-  // Repeat the block simplifications until no more changes occur. Note that since
-  // each simplification consists of eliminating code (without introducing new code),
-  // this process is always finite.
-  bool changed;
-  do {
-    changed = false;
-    // Iterate over all basic blocks in the loop-body.
-    for (HBlocksInLoopIterator it(*node->loop_info); !it.Done(); it.Advance()) {
-      HBasicBlock* block = it.Current();
-      // Remove dead instructions from the loop-body.
-      for (HBackwardInstructionIterator i(block->GetInstructions()); !i.Done(); i.Advance()) {
-        HInstruction* instruction = i.Current();
-        if (instruction->IsDeadAndRemovable()) {
-          changed = true;
-          block->RemoveInstruction(instruction);
-        }
+  // Iterate over all basic blocks in the loop-body.
+  for (HBlocksInLoopIterator it(*node->loop_info); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
+    // Remove dead instructions from the loop-body.
+    for (HBackwardInstructionIterator i(block->GetInstructions()); !i.Done(); i.Advance()) {
+      HInstruction* instruction = i.Current();
+      if (instruction->IsDeadAndRemovable()) {
+        simplified_ = true;
+        block->RemoveInstruction(instruction);
       }
-      // Remove trivial control flow blocks from the loop-body.
-      HBasicBlock* succ = nullptr;
-      if (IsGotoBlock(block, &succ) && succ->GetPredecessors().size() == 1) {
-        // Trivial goto block can be removed.
-        HBasicBlock* pred = block->GetSinglePredecessor();
-        changed = true;
-        pred->ReplaceSuccessor(block, succ);
-        block->RemoveDominatedBlock(succ);
-        block->DisconnectAndDelete();
-        pred->AddDominatedBlock(succ);
-        succ->SetDominator(pred);
-      } else if (block->GetSuccessors().size() == 2) {
-        // Trivial if block can be bypassed to either branch.
-        HBasicBlock* succ0 = block->GetSuccessors()[0];
-        HBasicBlock* succ1 = block->GetSuccessors()[1];
-        HBasicBlock* meet0 = nullptr;
-        HBasicBlock* meet1 = nullptr;
-        if (succ0 != succ1 &&
-            IsGotoBlock(succ0, &meet0) &&
-            IsGotoBlock(succ1, &meet1) &&
-            meet0 == meet1 &&  // meets again
-            meet0 != block &&  // no self-loop
-            meet0->GetPhis().IsEmpty()) {  // not used for merging
-          changed = true;
-          succ0->DisconnectAndDelete();
-          if (block->Dominates(meet0)) {
-            block->RemoveDominatedBlock(meet0);
-            succ1->AddDominatedBlock(meet0);
-            meet0->SetDominator(succ1);
-          }
+    }
+    // Remove trivial control flow blocks from the loop-body.
+    HBasicBlock* succ = nullptr;
+    if (IsGotoBlock(block, &succ) && succ->GetPredecessors().size() == 1) {
+      // Trivial goto block can be removed.
+      HBasicBlock* pred = block->GetSinglePredecessor();
+      simplified_ = true;
+      pred->ReplaceSuccessor(block, succ);
+      block->RemoveDominatedBlock(succ);
+      block->DisconnectAndDelete();
+      pred->AddDominatedBlock(succ);
+      succ->SetDominator(pred);
+    } else if (block->GetSuccessors().size() == 2) {
+      // Trivial if block can be bypassed to either branch.
+      HBasicBlock* succ0 = block->GetSuccessors()[0];
+      HBasicBlock* succ1 = block->GetSuccessors()[1];
+      HBasicBlock* meet0 = nullptr;
+      HBasicBlock* meet1 = nullptr;
+      if (succ0 != succ1 &&
+          IsGotoBlock(succ0, &meet0) &&
+          IsGotoBlock(succ1, &meet1) &&
+          meet0 == meet1 &&  // meets again
+          meet0 != block &&  // no self-loop
+          meet0->GetPhis().IsEmpty()) {  // not used for merging
+        simplified_ = true;
+        succ0->DisconnectAndDelete();
+        if (block->Dominates(meet0)) {
+          block->RemoveDominatedBlock(meet0);
+          succ1->AddDominatedBlock(meet0);
+          meet0->SetDominator(succ1);
         }
       }
     }
-  } while (changed);
+  }
 }
 
 void HLoopOptimization::RemoveIfEmptyInnerLoop(LoopNode* node) {
diff --git a/compiler/optimizing/loop_optimization.h b/compiler/optimizing/loop_optimization.h
index 3391bef..0f05b24 100644
--- a/compiler/optimizing/loop_optimization.h
+++ b/compiler/optimizing/loop_optimization.h
@@ -95,6 +95,9 @@
   // when the induction of inner loops has changed.
   int32_t induction_simplication_count_;
 
+  // Flag that tracks if any simplifications have occurred.
+  bool simplified_;
+
   friend class LoopOptimizationTest;
 
   DISALLOW_COPY_AND_ASSIGN(HLoopOptimization);
diff --git a/test/530-checker-loops4/src/Main.java b/test/530-checker-loops4/src/Main.java
index 2e19c88..7d3d7d9 100644
--- a/test/530-checker-loops4/src/Main.java
+++ b/test/530-checker-loops4/src/Main.java
@@ -88,11 +88,9 @@
   //
   /// CHECK-START: int Main.geo4(int) loop_optimization (after)
   /// CHECK-DAG: <<Par:i\d+>> ParameterValue        loop:none
-  /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0         loop:none
   /// CHECK-DAG: <<Int:i\d+>> IntConstant 7         loop:none
   /// CHECK-DAG: <<Rem:i\d+>> Rem [<<Par>>,<<Int>>] loop:none
-  /// CHECK-DAG: <<Add:i\d+>> Add [<<Rem>>,<<Zer>>] loop:none
-  /// CHECK-DAG:              Return [<<Add>>]      loop:none
+  /// CHECK-DAG:              Return [<<Rem>>]      loop:none
   //
   /// CHECK-START: int Main.geo4(int) loop_optimization (after)
   /// CHECK-NOT: Phi
@@ -104,6 +102,17 @@
   }
 
   // TODO: someday?
+  //
+  /// CHECK-START: int Main.geo1BCE() BCE (before)
+  /// CHECK-DAG: BoundsCheck loop:none
+  /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
+  //
+  /// CHECK-START: int Main.geo1BCE() BCE (after)
+  /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
+  //
+  /// CHECK-START: int Main.geo1BCE() BCE (after)
+  /// CHECK-NOT: BoundsCheck loop:none
+  /// CHECK-NOT: Deoptimize
   public static int geo1BCE() {
     int[] x = {  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
                 11, 12, 13, 14, 15, 16, 17, 19, 19, 20,
@@ -118,6 +127,17 @@
   }
 
   // TODO: someday?
+  //
+  /// CHECK-START: int Main.geo2BCE() BCE (before)
+  /// CHECK-DAG: BoundsCheck loop:none
+  /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
+  //
+  /// CHECK-START: int Main.geo2BCE() BCE (after)
+  /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
+  //
+  /// CHECK-START: int Main.geo2BCE() BCE (after)
+  /// CHECK-NOT: BoundsCheck loop:none
+  /// CHECK-NOT: Deoptimize
   public static int geo2BCE() {
     int[] x = {  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
                 11, 12, 13, 14, 15, 16, 17, 19, 19, 20,
@@ -225,16 +245,20 @@
     return a;
   }
 
-  // TODO: Rem is already optimized away by the time the loop optimizer runs;
-  //       we could still optimize this case with last value on wrap-around!
+  // Even though Rem is already optimized away by the time induction analysis
+  // and the loop optimizer run, the loop is optimized with a trivial
+  // wrap-around induction just as the wrap-around for REM would.
   //
   /// CHECK-START: int Main.geoRemBlackHole(int) loop_optimization (before)
   /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
   /// CHECK-DAG: Phi loop:<<Loop>>
   //
   /// CHECK-START: int Main.geoRemBlackHole(int) loop_optimization (after)
-  /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
-  /// CHECK-DAG: Phi loop:<<Loop>>
+  /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0
+  /// CHECK-DAG:               Return [<<Zero>>]
+  //
+  /// CHECK-START: int Main.geoRemBlackHole(int) loop_optimization (after)
+  /// CHECK-NOT: Phi
   public static int geoRemBlackHole(int a) {
     for (int i = 0; i < 100; i++) {
       a %= 1;
diff --git a/test/530-checker-loops5/expected.txt b/test/530-checker-loops5/expected.txt
new file mode 100644
index 0000000..b0aad4d
--- /dev/null
+++ b/test/530-checker-loops5/expected.txt
@@ -0,0 +1 @@
+passed
diff --git a/test/530-checker-loops5/info.txt b/test/530-checker-loops5/info.txt
new file mode 100644
index 0000000..15dbf37
--- /dev/null
+++ b/test/530-checker-loops5/info.txt
@@ -0,0 +1 @@
+Test on loop optimizations, in particular with polynomial induction.
diff --git a/test/530-checker-loops5/src/Main.java b/test/530-checker-loops5/src/Main.java
new file mode 100644
index 0000000..54b54d0
--- /dev/null
+++ b/test/530-checker-loops5/src/Main.java
@@ -0,0 +1,186 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+//
+// Test on loop optimizations, in particular around polynomial induction.
+//
+public class Main {
+
+  /// CHECK-START: int Main.poly1() loop_optimization (before)
+  /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
+  /// CHECK-DAG: Add loop:<<Loop>>
+  /// CHECK-DAG: Add loop:<<Loop>>
+  //
+  /// CHECK-START: int Main.poly1() loop_optimization (after)
+  /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0         loop:none
+  /// CHECK-DAG: <<Int:i\d+>> IntConstant 55        loop:none
+  /// CHECK-DAG: <<Add:i\d+>> Add [<<Int>>,<<Zer>>] loop:none
+  /// CHECK-DAG:              Return [<<Add>>]      loop:none
+  //
+  /// CHECK-START: int Main.poly1() instruction_simplifier$after_bce (after)
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 55 loop:none
+  /// CHECK-DAG:               Return [<<Int>>]  loop:none
+  //
+  /// CHECK-START: int Main.poly1() loop_optimization (after)
+  /// CHECK-NOT: Phi
+  public static int poly1() {
+    int a = 0;
+    for (int i = 0; i <= 10; i++) {
+      a += i;
+    }
+    return a;
+  }
+
+  // Multiplication in linear induction has been optimized earlier,
+  // but that does not stop the induction variable recognition
+  // and loop optimizer.
+  //
+  /// CHECK-START: int Main.poly2(int) loop_optimization (before)
+  /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
+  /// CHECK-DAG: Shl loop:<<Loop>>
+  /// CHECK-DAG: Add loop:<<Loop>>
+  /// CHECK-DAG: Add loop:<<Loop>>
+  /// CHECK-DAG: Add loop:<<Loop>>
+  /// CHECK-DAG: Add loop:<<Loop>>
+  //
+  /// CHECK-START: int Main.poly2(int) loop_optimization (after)
+  /// CHECK-DAG: <<Par:i\d+>> ParameterValue        loop:none
+  /// CHECK-DAG: <<Int:i\d+>> IntConstant 185       loop:none
+  /// CHECK-DAG: <<Add:i\d+>> Add [<<Int>>,<<Par>>] loop:none
+  /// CHECK-DAG:              Return [<<Add>>]      loop:none
+  //
+  /// CHECK-START: int Main.poly2(int) loop_optimization (after)
+  /// CHECK-NOT: Phi
+  public static int poly2(int a) {
+    for (int i = 0; i < 10; i++) {
+      int k = 3 * i + 5;
+      a += k;
+    }
+    return a;
+  }
+
+  /// CHECK-START: int Main.poly3() loop_optimization (before)
+  /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
+  /// CHECK-DAG: Add loop:<<Loop>>
+  /// CHECK-DAG: Add loop:<<Loop>>
+  //
+  /// CHECK-START: int Main.poly3() loop_optimization (after)
+  /// CHECK-DAG: <<Ini:i\d+>> IntConstant 12345       loop:none
+  /// CHECK-DAG: <<Int:i\d+>> IntConstant -2146736968 loop:none
+  /// CHECK-DAG: <<Add:i\d+>> Add [<<Int>>,<<Ini>>]   loop:none
+  /// CHECK-DAG:              Return [<<Add>>]        loop:none
+  //
+  /// CHECK-START: int Main.poly3() instruction_simplifier$after_bce (after)
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant -2146724623 loop:none
+  /// CHECK-DAG:               Return [<<Int>>]        loop:none
+  //
+  /// CHECK-START: int Main.poly3() loop_optimization (after)
+  /// CHECK-NOT: Phi
+  public static int poly3() {
+    int a = 12345;
+    for (int i = 0; i <= 10; i++) {
+      a += (2147483646 * i + 67890);
+    }
+    return a;
+  }
+
+  /// CHECK-START: int Main.polyBCE1() BCE (before)
+  /// CHECK-DAG: BoundsCheck loop:none
+  /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
+  //
+  /// CHECK-START: int Main.polyBCE1() BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  /// CHECK-NOT: Deoptimize
+  public static int polyBCE1() {
+    int[] x = {  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
+                11, 12, 13, 14, 15, 16, 17, 19, 19, 20,
+                21, 22 };
+    int a = 0;
+    int r = 0;
+    for (int i = 0; i < 8; i++) {
+      r += x[a];
+      a += i;
+    }
+    return r;
+  }
+
+  /// CHECK-START: int Main.polyBCE2() BCE (before)
+  /// CHECK-DAG: BoundsCheck loop:none
+  /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
+  //
+  /// CHECK-START: int Main.polyBCE2() BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  /// CHECK-NOT: Deoptimize
+  public static int polyBCE2() {
+    int[] x = {  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
+                11, 12, 13, 14, 15, 16, 17, 19, 19, 20,
+                21, 22, 23, 24, 25, 26, 27 };
+    int a = 1;
+    int r = 0;
+    for (int i = 0; i < 6; i++) {
+      int k = 2 * i + 1;
+      r -= x[a];
+      a += k;
+    }
+    return r;
+  }
+
+  /// CHECK-START: int Main.polyBCE3() BCE (before)
+  /// CHECK-DAG: BoundsCheck loop:none
+  /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
+  //
+  /// CHECK-START: int Main.polyBCE3() BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  /// CHECK-NOT: Deoptimize
+  public static int polyBCE3() {
+    int[] x = {  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
+                11, 12, 13, 14, 15, 16, 17, 19, 19, 20,
+                21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
+                31, 32, 33, 34, 35, 36, 37, 38 };
+    int r = 0;
+    int a1 = 1;
+    int a2 = 2;
+    for (int i = 0; i < 5; i++) {
+      int t = a1 + a2;  // two polynomials combined into new polynomial
+      r -= x[t];
+      a1 += (3 * i + 1);
+      a2 += (2 * i);
+    }
+    return r;
+  }
+
+  //
+  // Verifier.
+  //
+
+  public static void main(String[] args) {
+    expectEquals(55, poly1());
+    expectEquals(185, poly2(0));
+    expectEquals(192, poly2(7));
+    expectEquals(-2146724623, poly3());
+    expectEquals(64, polyBCE1());
+    expectEquals(-68, polyBCE2());
+    expectEquals(-80, polyBCE3());
+
+    System.out.println("passed");
+  }
+
+  private static void expectEquals(int expected, int result) {
+    if (expected != result) {
+      throw new Error("Expected: " + expected + ", found: " + result);
+    }
+  }
+}
diff --git a/test/618-checker-induction/src/Main.java b/test/618-checker-induction/src/Main.java
index f85479a..87a69b2 100644
--- a/test/618-checker-induction/src/Main.java
+++ b/test/618-checker-induction/src/Main.java
@@ -25,7 +25,7 @@
   /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
   //
   /// CHECK-START: void Main.deadSingleLoop() loop_optimization (after)
-  /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
+  /// CHECK-NOT: Phi
   static void deadSingleLoop() {
     for (int i = 0; i < 4; i++) {
     }
@@ -35,7 +35,7 @@
   /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
   //
   /// CHECK-START: void Main.deadSingleLoop() loop_optimization (after)
-  /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
+  /// CHECK-NOT: Phi
   static void deadSingleLoopN(int n) {
     for (int i = 0; i < n; i++) {
     }
@@ -56,7 +56,7 @@
   /// CHECK-DAG: Phi loop:{{B\d+}}      outer_loop:<<Loop>>
   //
   /// CHECK-START: void Main.deadNestedLoops() loop_optimization (after)
-  /// CHECK-NOT: Phi loop:{{B\d+}}
+  /// CHECK-NOT: Phi
   static void deadNestedLoops() {
     for (int i = 0; i < 4; i++) {
       for (int j = 0; j < 4; j++) {
@@ -74,7 +74,7 @@
   /// CHECK-DAG: Phi loop:{{B\d+}}       outer_loop:none
   //
   /// CHECK-START: void Main.deadNestedAndFollowingLoops() loop_optimization (after)
-  /// CHECK-NOT: Phi loop:{{B\d+}}
+  /// CHECK-NOT: Phi
   static void deadNestedAndFollowingLoops() {
     for (int i = 0; i < 4; i++) {
       for (int j = 0; j < 4; j++) {
@@ -96,7 +96,7 @@
   /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
   //
   /// CHECK-START: void Main.deadConditional(int) loop_optimization (after)
-  /// CHECK-NOT: Phi loop:{{B\d+}}
+  /// CHECK-NOT: Phi
   public static void deadConditional(int n) {
     int k = 0;
     int m = 0;
@@ -116,7 +116,7 @@
   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
   //
   /// CHECK-START: void Main.deadConditionalCycle(int) loop_optimization (after)
-  /// CHECK-NOT: Phi loop:{{B\d+}}
+  /// CHECK-NOT: Phi
   public static void deadConditionalCycle(int n) {
     int k = 0;
     int m = 0;
@@ -215,12 +215,11 @@
   /// CHECK-DAG:               Return [<<Phi1>>] loop:none
   //
   /// CHECK-START: int Main.closedFormInductionUp() loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:none
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   //
   /// CHECK-START: int Main.closedFormInductionUp() instruction_simplifier$after_bce (after)
-  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 12395
-  /// CHECK-DAG:               Return [<<Int>>] loop:none
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 12395 loop:none
+  /// CHECK-DAG:               Return [<<Int>>]  loop:none
   static int closedFormInductionUp() {
     int closed = 12345;
     for (int i = 0; i < 10; i++) {
@@ -235,8 +234,13 @@
   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
   //
   /// CHECK-START: int Main.closedFormInductionInAndDown(int) loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:none
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
+  //
+  /// CHECK-START: int Main.closedFormInductionInAndDown(int) instruction_simplifier$after_bce (after)
+  /// CHECK-DAG: <<Par:i\d+>>  ParameterValue        loop:none
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant -50       loop:none
+  /// CHECK-DAG: <<Add:i\d+>>  Add [<<Int>>,<<Par>>] loop:none
+  /// CHECK-DAG:               Return [<<Add>>]      loop:none
   static int closedFormInductionInAndDown(int closed) {
     for (int i = 0; i < 10; i++) {
       closed -= 5;
@@ -252,12 +256,10 @@
   /// CHECK-DAG:               Return [<<Phi1>>] loop:none
   //
   /// CHECK-START: int Main.closedFormNested() loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:none
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:loop{{B\d+}}
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   //
   /// CHECK-START: int Main.closedFormNested() instruction_simplifier$after_bce (after)
-  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 100
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 100  loop:none
   /// CHECK-DAG:               Return [<<Int>>] loop:none
   static int closedFormNested() {
     int closed = 0;
@@ -277,13 +279,11 @@
   /// CHECK-DAG:               Return [<<Phi1>>] loop:none
   //
   /// CHECK-START: int Main.closedFormNestedAlt() loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:none
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:loop{{B\d+}}
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   //
   /// CHECK-START: int Main.closedFormNestedAlt() instruction_simplifier$after_bce (after)
-  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 15082
-  /// CHECK-DAG:               Return [<<Int>>] loop:none
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 15082 loop:none
+  /// CHECK-DAG:               Return [<<Int>>]  loop:none
   static int closedFormNestedAlt() {
     int closed = 12345;
     for (int i = 0; i < 17; i++) {
@@ -360,11 +360,10 @@
   /// CHECK-DAG:              Return [<<Phi>>] loop:none
   //
   /// CHECK-START: int Main.mainIndexReturned() loop_optimization (after)
-  /// CHECK-NOT:              Phi    loop:{{B\d+}} outer_loop:none
-  /// CHECK-DAG:              Return loop:none
+  /// CHECK-NOT:              Phi
   //
   /// CHECK-START: int Main.mainIndexReturned() instruction_simplifier$after_bce (after)
-  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 10
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 10   loop:none
   /// CHECK-DAG:               Return [<<Int>>] loop:none
   static int mainIndexReturned() {
     int i;
@@ -378,11 +377,10 @@
   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
   //
   /// CHECK-START: int Main.periodicReturned9() loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:none
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   //
   /// CHECK-START: int Main.periodicReturned9() instruction_simplifier$after_bce (after)
-  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 1
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 1    loop:none
   /// CHECK-DAG:               Return [<<Int>>] loop:none
   static int periodicReturned9() {
     int k = 0;
@@ -398,11 +396,10 @@
   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
   //
   /// CHECK-START: int Main.periodicReturned10() loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:none
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   //
   /// CHECK-START: int Main.periodicReturned10() instruction_simplifier$after_bce (after)
-  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 0
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 0    loop:none
   /// CHECK-DAG:               Return [<<Int>>] loop:none
   static int periodicReturned10() {
     int k = 0;
@@ -412,7 +409,18 @@
     return k;
   }
 
-  // If ever replaced by closed form, last value should be correct!
+  /// CHECK-START: int Main.getSum21() 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: <<Phi3:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG:               Return [<<Phi3>>] loop:none
+  //
+  /// CHECK-START: int Main.getSum21() loop_optimization (after)
+  /// CHECK-NOT:               Phi
+  //
+  /// CHECK-START: int Main.getSum21() instruction_simplifier$after_bce (after)
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 21   loop:none
+  /// CHECK-DAG:               Return [<<Int>>] loop:none
   private static int getSum21() {
     int k = 0;
     int sum = 0;
@@ -436,8 +444,7 @@
   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
   //
   /// CHECK-START: int Main.periodicReturnedN(int) loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:none
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   static int periodicReturnedN(int n) {
     int k = 0;
     for (int i = 0; i < n; i++) {
@@ -480,11 +487,10 @@
   /// CHECK-EVAL: "<<Loop1>>" != "<<Loop2>>"
   //
   /// CHECK-START: int Main.closedFeed() loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:none
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   //
   /// CHECK-START: int Main.closedFeed() instruction_simplifier$after_bce (after)
-  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 20
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 20   loop:none
   /// CHECK-DAG:               Return [<<Int>>] loop:none
   private static int closedFeed() {
     int closed = 0;
@@ -505,11 +511,10 @@
   /// CHECK-DAG:               Return [<<Phi1>>] loop:none
   //
   /// CHECK-START: int Main.closedLargeUp() loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:B\d+ outer_loop:none
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   //
   /// CHECK-START: int Main.closedLargeUp() instruction_simplifier$after_bce (after)
-  /// CHECK-DAG: <<Int:i\d+>>  IntConstant -10
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant -10  loop:none
   /// CHECK-DAG:               Return [<<Int>>] loop:none
   private static int closedLargeUp() {
     int closed = 0;
@@ -525,11 +530,10 @@
   /// CHECK-DAG:               Return [<<Phi1>>] loop:none
   //
   /// CHECK-START: int Main.closedLargeDown() loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:B\d+ outer_loop:none
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   //
   /// CHECK-START: int Main.closedLargeDown() instruction_simplifier$after_bce (after)
-  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 10
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 10   loop:none
   /// CHECK-DAG:               Return [<<Int>>] loop:none
   private static int closedLargeDown() {
     int closed = 0;
@@ -548,11 +552,10 @@
   /// CHECK-DAG:               Return [<<Phi5>>] loop:none
   //
   /// CHECK-START: int Main.waterFall() loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:B\d+ outer_loop:none
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   //
   /// CHECK-START: int Main.waterFall() instruction_simplifier$after_bce (after)
-  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 50
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 50   loop:none
   /// CHECK-DAG:               Return [<<Int>>] loop:none
   private static int waterFall() {
     int i = 0;
@@ -570,11 +573,10 @@
   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
   //
   /// CHECK-START: boolean Main.periodicBoolIdiom1() loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:none
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   //
   /// CHECK-START: boolean Main.periodicBoolIdiom1() instruction_simplifier$after_bce (after)
-  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 0
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 0    loop:none
   /// CHECK-DAG:               Return [<<Int>>] loop:none
   private static boolean periodicBoolIdiom1() {
     boolean x = true;
@@ -590,11 +592,10 @@
   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
   //
   /// CHECK-START: boolean Main.periodicBoolIdiom2() loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:none
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   //
   /// CHECK-START: boolean Main.periodicBoolIdiom2() instruction_simplifier$after_bce (after)
-  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 0
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 0    loop:none
   /// CHECK-DAG:               Return [<<Int>>] loop:none
   private static boolean periodicBoolIdiom2() {
     boolean x = true;
@@ -610,11 +611,10 @@
   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
   //
   /// CHECK-START: boolean Main.periodicBoolIdiom3() loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:none
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   //
   /// CHECK-START: boolean Main.periodicBoolIdiom3() instruction_simplifier$after_bce (after)
-  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 0
+  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 0    loop:none
   /// CHECK-DAG:               Return [<<Int>>] loop:none
   private static boolean periodicBoolIdiom3() {
     boolean x = true;
@@ -630,8 +630,7 @@
   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
   //
   /// CHECK-START: boolean Main.periodicBoolIdiom1N(boolean, int) loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:none
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   private static boolean periodicBoolIdiom1N(boolean x, int n) {
     for (int i = 0; i < n; i++) {
       x = !x;
@@ -645,8 +644,7 @@
   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
   //
   /// CHECK-START: boolean Main.periodicBoolIdiom2N(boolean, int) loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:none
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   private static boolean periodicBoolIdiom2N(boolean x, int n) {
     for (int i = 0; i < n; i++) {
       x = (x != true);
@@ -660,8 +658,7 @@
   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
   //
   /// CHECK-START: boolean Main.periodicBoolIdiom3N(boolean, int) loop_optimization (after)
-  /// CHECK-NOT:               Phi    loop:{{B\d+}} outer_loop:none
-  /// CHECK-DAG:               Return loop:none
+  /// CHECK-NOT:               Phi
   private static boolean periodicBoolIdiom3N(boolean x, int n) {
     for (int i = 0; i < n; i++) {
       x = (x == false);