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

6 files changed, 657 insertions, 199 deletions

diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index f2602fbf8c..15615022e3 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -218,20 +218,21 @@ void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction
   } else if (instruction->IsSub()) {
     info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
                           LookupInfo(loop, instruction->InputAt(1)), kSub);
+  } else if (instruction->IsNeg()) {
+    info = TransferNeg(LookupInfo(loop, instruction->InputAt(0)));
   } else if (instruction->IsMul()) {
     info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
                        LookupInfo(loop, instruction->InputAt(1)));
   } else if (instruction->IsShl()) {
-    info = TransferShl(LookupInfo(loop, instruction->InputAt(0)),
-                       LookupInfo(loop, instruction->InputAt(1)),
-                       instruction->InputAt(0)->GetType());
-  } else if (instruction->IsNeg()) {
-    info = TransferNeg(LookupInfo(loop, instruction->InputAt(0)));
+    HInstruction* mulc = GetMultConstantForShift(loop, instruction);
+    if (mulc != nullptr) {
+      info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
+                         LookupInfo(loop, mulc));
+    }
   } else if (instruction->IsTypeConversion()) {
     info = TransferCnv(LookupInfo(loop, instruction->InputAt(0)),
                        instruction->AsTypeConversion()->GetInputType(),
                        instruction->AsTypeConversion()->GetResultType());
-
   } else if (instruction->IsBoundsCheck()) {
     info = LookupInfo(loop, instruction->InputAt(0));  // Pass-through.
   }
@@ -271,7 +272,12 @@ void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
   if (size == 1) {
     InductionInfo* update = TransferPhi(loop, phi, /* input_index */ 1);
     if (update != nullptr) {
-      AssignInfo(loop, phi, CreateInduction(kWrapAround, initial, update, type_));
+      AssignInfo(loop, phi, CreateInduction(kWrapAround,
+                                            kNop,
+                                            initial,
+                                            update,
+                                            /*fetch*/ nullptr,
+                                            type_));
     }
     return;
   }
@@ -289,6 +295,20 @@ void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
     } else if (instruction->IsSub()) {
       update = SolveAddSub(
           loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true);
+    } else if (instruction->IsMul()) {
+      update = SolveGeo(
+          loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kMul);
+    } else if (instruction->IsDiv()) {
+      update = SolveGeo(
+          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);
+    } else if (instruction->IsShl()) {
+      HInstruction* mulc = GetMultConstantForShift(loop, instruction);
+      if (mulc != nullptr) {
+        update = SolveGeo(loop, phi, instruction, instruction->InputAt(0), mulc, kMul);
+      }
     } else if (instruction->IsXor()) {
       update = SolveXor(loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1));
     } else if (instruction->IsEqual()) {
@@ -309,9 +329,14 @@ void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
   if (induction != nullptr) {
     switch (induction->induction_class) {
       case kInvariant:
+        // Construct combined stride of the linear induction.
+        induction = CreateInduction(kLinear, kNop, induction, initial, /*fetch*/ nullptr, type_);
+        FALLTHROUGH_INTENDED;
+      case kPolynomial:
+      case kGeometric:
         // Classify first phi and then the rest of the cycle "on-demand".
         // Statements are scanned in order.
-        AssignInfo(loop, phi, CreateInduction(kLinear, induction, initial, type_));
+        AssignInfo(loop, phi, induction);
         for (size_t i = 1; i < size; i++) {
           ClassifyTrivial(loop, scc_[i]);
         }
@@ -341,10 +366,19 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::RotatePeriodicInduc
   //   (b, c, d, e, a)
   // in preparation of assigning this to the previous variable in the sequence.
   if (induction->induction_class == kInvariant) {
-    return CreateInduction(kPeriodic, induction, last, type_);
+    return CreateInduction(kPeriodic,
+                           kNop,
+                           induction,
+                           last,
+                           /*fetch*/ nullptr,
+                           type_);
   }
-  return CreateInduction(
-      kPeriodic, induction->op_a, RotatePeriodicInduction(induction->op_b, last), type_);
+  return CreateInduction(kPeriodic,
+                         kNop,
+                         induction->op_a,
+                         RotatePeriodicInduction(induction->op_b, last),
+                         /*fetch*/ nullptr,
+                         type_);
 }
 
 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(HLoopInformation* loop,
@@ -366,36 +400,55 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(HLoopIn
 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(InductionInfo* a,
                                                                             InductionInfo* b,
                                                                             InductionOp op) {
-  // Transfer over an addition or subtraction: any invariant, linear, wrap-around, or periodic
-  // can be combined with an invariant to yield a similar result. Even two linear inputs can
-  // be combined. All other combinations fail, however.
+  // 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.
   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,
                              TransferAddSub(a->op_a, b->op_a, op),
                              TransferAddSub(a->op_b, b->op_b, op),
+                             /*fetch*/ nullptr,
                              type_);
     } else if (a->induction_class == kInvariant) {
       InductionInfo* new_a = b->op_a;
       InductionInfo* new_b = TransferAddSub(a, b->op_b, op);
-      if (b->induction_class != kLinear) {
-        DCHECK(b->induction_class == kWrapAround || b->induction_class == kPeriodic);
+      if (b->induction_class == kWrapAround || b->induction_class == kPeriodic) {
         new_a = TransferAddSub(a, new_a, op);
       } else if (op == kSub) {  // Negation required.
         new_a = TransferNeg(new_a);
       }
-      return CreateInduction(b->induction_class, new_a, new_b, type_);
+      return CreateInduction(b->induction_class, b->operation, new_a, new_b, b->fetch, type_);
     } else if (b->induction_class == kInvariant) {
       InductionInfo* new_a = a->op_a;
       InductionInfo* new_b = TransferAddSub(a->op_b, b, op);
-      if (a->induction_class != kLinear) {
-        DCHECK(a->induction_class == kWrapAround || a->induction_class == kPeriodic);
+      if (a->induction_class == kWrapAround || a->induction_class == kPeriodic) {
         new_a = TransferAddSub(new_a, b, op);
       }
-      return CreateInduction(a->induction_class, new_a, new_b, type_);
+      return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type_);
+    }
+  }
+  return nullptr;
+}
+
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a) {
+  // Transfer over a unary negation: an invariant, linear, polynomial, geometric (mul),
+  // wrap-around, or periodic input yields a similar but negated induction as result.
+  if (a != nullptr) {
+    type_ = Narrowest(type_, a->type);
+    if (a->induction_class == kInvariant) {
+      return CreateInvariantOp(kNeg, nullptr, a);
+    } else if (a->induction_class != kGeometric || a->operation == kMul) {
+      return CreateInduction(a->induction_class,
+                             a->operation,
+                             TransferNeg(a->op_a),
+                             TransferNeg(a->op_b),
+                             a->fetch,
+                             type_);
     }
   }
   return nullptr;
@@ -403,72 +456,45 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(Indu
 
 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferMul(InductionInfo* a,
                                                                          InductionInfo* b) {
-  // Transfer over a multiplication: any invariant, linear, wrap-around, or periodic
-  // can be multiplied with an invariant to yield a similar but multiplied result.
-  // Two non-invariant inputs cannot be multiplied, however.
+  // Transfer over a multiplication: any invariant, linear, polynomial, geometric (mul),
+  // wrap-around, or periodic can be multiplied with an invariant to yield a similar
+  // but multiplied result. Two non-invariant inputs cannot be multiplied, however.
   if (a != nullptr && b != nullptr) {
     type_ = Narrowest(type_, Narrowest(a->type, b->type));
     if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
       return CreateInvariantOp(kMul, a, b);
-    } else if (a->induction_class == kInvariant) {
+    } else if (a->induction_class == kInvariant && (b->induction_class != kGeometric ||
+                                                    b->operation == kMul)) {
       return CreateInduction(b->induction_class,
+                             b->operation,
                              TransferMul(a, b->op_a),
                              TransferMul(a, b->op_b),
+                             b->fetch,
                              type_);
-    } else if (b->induction_class == kInvariant) {
+    } else if (b->induction_class == kInvariant && (a->induction_class != kGeometric ||
+                                                    a->operation == kMul)) {
       return CreateInduction(a->induction_class,
+                             a->operation,
                              TransferMul(a->op_a, b),
                              TransferMul(a->op_b, b),
+                             a->fetch,
                              type_);
     }
   }
   return nullptr;
 }
 
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferShl(InductionInfo* a,
-                                                                         InductionInfo* b,
-                                                                         Primitive::Type type) {
-  // Transfer over a shift left: treat shift by restricted constant as equivalent multiplication.
-  int64_t value = -1;
-  if (a != nullptr && IsExact(b, &value)) {
-    // Obtain the constant needed for the multiplication. This yields an existing instruction
-    // if the constants 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.
-    if ((type == Primitive::kPrimInt  && 0 <= value && value < 31) ||
-        (type == Primitive::kPrimLong && 0 <= value && value < 63)) {
-      return TransferMul(a, CreateConstant(1 << value, type));
-    }
-  }
-  return nullptr;
-}
-
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a) {
-  // Transfer over a unary negation: an invariant, linear, wrap-around, or periodic input
-  // yields a similar but negated induction as result.
-  if (a != nullptr) {
-    type_ = Narrowest(type_, a->type);
-    if (a->induction_class == kInvariant) {
-      return CreateInvariantOp(kNeg, nullptr, a);
-    }
-    return CreateInduction(a->induction_class, TransferNeg(a->op_a), TransferNeg(a->op_b), type_);
-  }
-  return nullptr;
-}
-
 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferCnv(InductionInfo* a,
                                                                          Primitive::Type from,
                                                                          Primitive::Type to) {
   if (a != nullptr) {
-    // Allow narrowing conversion in certain cases.
+    // Allow narrowing conversion on linear induction in certain cases.
     if (IsNarrowingIntegralConversion(from, to)) {
       if (a->induction_class == kLinear) {
         if (a->type == to || (a->type == from && IsNarrowingIntegralConversion(from, to))) {
-          return CreateInduction(kLinear, a->op_a, a->op_b, to);
+          return CreateInduction(kLinear, kNop, a->op_a, a->op_b, /*fetch*/ nullptr, to);
         }
       }
-      // TODO: other cases useful too?
     }
   }
   return nullptr;
@@ -511,11 +537,11 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhiAllInputs(
     if (a != nullptr && a->induction_class == kInvariant) {
       if (phi->InputAt(1) == entry_phi) {
         InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
-        return CreateInduction(kPeriodic, a, initial, type_);
+        return CreateInduction(kPeriodic, kNop, a, initial, /*fetch*/ nullptr, type_);
       }
       InductionInfo* b = SolvePhi(phi, /* input_index */ 1);
       if (b != nullptr && b->induction_class == kPeriodic) {
-        return CreateInduction(kPeriodic, a, b, type_);
+        return CreateInduction(kPeriodic, kNop, a, b, /*fetch*/ nullptr, type_);
       }
     }
   }
@@ -530,7 +556,7 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopIn
                                                                          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 induction.
+  // invariant value, seeded from phi, keeps adding to the stride of the linear induction.
   InductionInfo* b = LookupInfo(loop, y);
   if (b != nullptr && b->induction_class == kInvariant) {
     if (x == entry_phi) {
@@ -553,12 +579,17 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopIn
     }
   } else if (op == kSub) {
     // Solve within a tight cycle that is formed by exactly two instructions,
-    // one phi and one update, for a periodic idiom of the form k = c - k;
+    // one phi and one update, for a periodic idiom of the form k = c - k.
     if (y == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) {
       InductionInfo* a = LookupInfo(loop, x);
       if (a != nullptr && a->induction_class == kInvariant) {
         InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
-        return CreateInduction(kPeriodic, CreateInvariantOp(kSub, a, initial), initial, type_);
+        return CreateInduction(kPeriodic,
+                               kNop,
+                               CreateInvariantOp(kSub, a, initial),
+                               initial,
+                               /*fetch*/ nullptr,
+                               type_);
       }
     }
   }
@@ -566,21 +597,54 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopIn
   return nullptr;
 }
 
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveGeo(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 x = c ^ x or x = x ^ c.
+  // Solve within a tight cycle on periodic idiom of the form x = c ^ x or x = x ^ c.
   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, CreateInvariantOp(kXor, a, initial), initial, type_);
+      return CreateInduction(kPeriodic,
+                             kNop,
+                             CreateInvariantOp(kXor, a, initial),
+                             initial,
+                             /*fetch*/ nullptr,
+                             type_);
     }
     InductionInfo* b = LookupInfo(loop, y);
     if (b != nullptr && b->induction_class == kInvariant && entry_phi == x) {
-      return CreateInduction(kPeriodic, CreateInvariantOp(kXor, initial, b), initial, type_);
+      return CreateInduction(kPeriodic,
+                             kNop,
+                             CreateInvariantOp(kXor, initial, b),
+                             initial,
+                             /*fetch*/ nullptr,
+                             type_);
     }
   }
   return nullptr;
@@ -590,7 +654,7 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveTest(HLoopInfo
                                                                        HInstruction* entry_phi,
                                                                        HInstruction* instruction,
                                                                        int64_t opposite_value) {
-  // Detect hidden XOR construction in tight cycles on x = (x == 0) or x = (x != 1).
+  // Detect hidden XOR construction in x = (x == false) or x = (x != true).
   int64_t value = -1;
   HInstruction* x = instruction->InputAt(0);
   HInstruction* y = instruction->InputAt(1);
@@ -881,11 +945,14 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(HLoopInf
 
 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateConstant(int64_t value,
                                                                             Primitive::Type type) {
-  if (type == Primitive::kPrimInt) {
-    return CreateInvariantFetch(graph_->GetIntConstant(value));
+  HInstruction* constant;
+  switch (type) {
+    case Primitive::kPrimDouble: constant = graph_->GetDoubleConstant(value); break;
+    case Primitive::kPrimFloat:  constant = graph_->GetFloatConstant(value);  break;
+    case Primitive::kPrimLong:   constant = graph_->GetLongConstant(value);   break;
+    default:                     constant = graph_->GetIntConstant(value);    break;
   }
-  DCHECK_EQ(type, Primitive::kPrimLong);
-  return CreateInvariantFetch(graph_->GetLongConstant(value));
+  return CreateInvariantFetch(constant);
 }
 
 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInvariant(
@@ -948,6 +1015,26 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv
   return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr, b->type);
 }
 
+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
+  // 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.
+  InductionInfo* b = LookupInfo(loop, instruction->InputAt(1));
+  int64_t value = -1;
+  if (IsExact(b, &value)) {
+    Primitive::Type type = instruction->InputAt(0)->GetType();
+    if (type == Primitive::kPrimInt && 0 <= value && value < 31) {
+      return graph_->GetIntConstant(1 << value);
+    }
+    if (type == Primitive::kPrimLong && 0 <= value && value < 63) {
+      return graph_->GetLongConstant(1L << value);
+    }
+  }
+  return nullptr;
+}
 
 void HInductionVarAnalysis::AssignCycle(HPhi* phi) {
   ArenaSet<HInstruction*>* set = &cycles_.Put(phi, ArenaSet<HInstruction*>(
@@ -993,6 +1080,16 @@ bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1,
   return info1 == info2;
 }
 
+std::string HInductionVarAnalysis::FetchToString(HInstruction* fetch) {
+  DCHECK(fetch != nullptr);
+  if (fetch->IsIntConstant()) {
+    return std::to_string(fetch->AsIntConstant()->GetValue());
+  } else if (fetch->IsLongConstant()) {
+    return std::to_string(fetch->AsLongConstant()->GetValue());
+  }
+  return std::to_string(fetch->GetId()) + ":" + fetch->DebugName();
+}
+
 std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) {
   if (info != nullptr) {
     if (info->induction_class == kInvariant) {
@@ -1010,16 +1107,7 @@ std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) {
         case kLE:    inv += " <= "; break;
         case kGT:    inv += " > ";  break;
         case kGE:    inv += " >= "; break;
-        case kFetch:
-          DCHECK(info->fetch);
-          if (info->fetch->IsIntConstant()) {
-            inv += std::to_string(info->fetch->AsIntConstant()->GetValue());
-          } else if (info->fetch->IsLongConstant()) {
-            inv += std::to_string(info->fetch->AsLongConstant()->GetValue());
-          } else {
-            inv += std::to_string(info->fetch->GetId()) + ":" + info->fetch->DebugName();
-          }
-          break;
+        case kFetch: inv += FetchToString(info->fetch); break;
         case kTripCountInLoop:       inv += " (TC-loop) ";        break;
         case kTripCountInBody:       inv += " (TC-body) ";        break;
         case kTripCountInLoopUnsafe: inv += " (TC-loop-unsafe) "; break;
@@ -1029,11 +1117,28 @@ std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) {
       inv += ")";
       return inv;
     } else {
-      DCHECK(info->operation == kNop);
       if (info->induction_class == kLinear) {
         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) + ") + " +
+                                InductionToString(info->op_b) + "):" +
+                                Primitive::PrettyDescriptor(info->type);
+      } else if (info->induction_class == kGeometric) {
+        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);
+        }
       } else if (info->induction_class == kWrapAround) {
         return "wrap(" + InductionToString(info->op_a) + ", " +
                          InductionToString(info->op_b) + "):" +
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 70271799d2..94afc71c3d 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -51,14 +51,15 @@ class HInductionVarAnalysis : public HOptimization {
   enum InductionClass {
     kInvariant,
     kLinear,
+    kPolynomial,
+    kGeometric,
     kWrapAround,
     kPeriodic
   };
 
   enum InductionOp {
-    // No-operation: a true induction.
+    // Operations.
     kNop,
-    // Various invariant operations.
     kAdd,
     kSub,
     kNeg,
@@ -81,16 +82,18 @@ class HInductionVarAnalysis : public HOptimization {
   /**
    * Defines a detected induction as:
    *   (1) invariant:
-   *         operation: a + b, a - b, -b, a * b, a / b
-   *       or:
-   *         fetch: fetch from HIR
+   *         op: a + b, a - b, -b, a * b, a / b, a % b, a ^ b, fetch
    *   (2) linear:
    *         nop: a * i + b
-   *   (3) wrap-around
+   *   (3) polynomial:                        // TODO: coming soon
+   *         nop: sum_i(a) + b, for linear a
+   *   (4) geometric:
+   *         op: a * fetch^i + b, a * fetch^-i + b, a mod_i fetch + b
+   *   (5) wrap-around
    *         nop: a, then defined by b
-   *   (4) periodic
+   *   (6) periodic
    *         nop: a, then defined by b (repeated when exhausted)
-   *   (5) trip-count:
+   *   (7) trip-count:
    *         tc: defined by a, taken-test in b
    */
   struct InductionInfo : public ArenaObject<kArenaAllocInductionVarAnalysis> {
@@ -138,11 +141,13 @@ class HInductionVarAnalysis : public HOptimization {
   }
 
   InductionInfo* CreateInduction(InductionClass ic,
+                                 InductionOp op,
                                  InductionInfo* a,
                                  InductionInfo* b,
+                                 HInstruction* f,
                                  Primitive::Type type) {
     DCHECK(a != nullptr && b != nullptr);
-    return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr, type);
+    return new (graph_->GetArena()) InductionInfo(ic, op, a, b, f, type);
   }
 
   // Methods for analysis.
@@ -156,9 +161,8 @@ class HInductionVarAnalysis : public HOptimization {
   // Transfer operations.
   InductionInfo* TransferPhi(HLoopInformation* loop, HInstruction* phi, size_t input_index);
   InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
-  InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
-  InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type type);
   InductionInfo* TransferNeg(InductionInfo* a);
+  InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
   InductionInfo* TransferCnv(InductionInfo* a, Primitive::Type from, Primitive::Type to);
 
   // Solvers.
@@ -173,6 +177,12 @@ class HInductionVarAnalysis : public HOptimization {
                              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,
@@ -214,6 +224,7 @@ class HInductionVarAnalysis : public HOptimization {
   InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
   InductionInfo* CreateConstant(int64_t value, Primitive::Type type);
   InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);
+  HInstruction* GetMultConstantForShift(HLoopInformation* loop, HInstruction* instruction);
   void AssignCycle(HPhi* phi);
   ArenaSet<HInstruction*>* LookupCycle(HPhi* phi);
 
@@ -224,6 +235,7 @@ class HInductionVarAnalysis : public HOptimization {
 
   // Helpers.
   static bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
+  static std::string FetchToString(HInstruction* fetch);
   static std::string InductionToString(InductionInfo* info);
 
   // TODO: fine tune the following data structures, only keep relevant data.
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();
 
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 235793d8d2..75619a3c01 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -57,6 +57,21 @@ static bool IsIntAndGet(HInstruction* instruction, int64_t* value) {
   return false;
 }
 
+/** Returns b^e for b,e >= 1. */
+static int64_t IntPow(int64_t b, int64_t e) {
+  DCHECK_GE(b, 1);
+  DCHECK_GE(e, 1);
+  int64_t pow = 1;
+  while (e) {
+    if (e & 1) {
+      pow *= b;
+    }
+    e >>= 1;
+    b *= b;
+  }
+  return pow;
+}
+
 /**
  * Detects an instruction that is >= 0. As long as the value is carried by
  * a single instruction, arithmetic wrap-around cannot occur.
@@ -399,6 +414,8 @@ bool InductionVarRange::HasInductionInfo(
     /*out*/ HLoopInformation** loop,
     /*out*/ HInductionVarAnalysis::InductionInfo** info,
     /*out*/ HInductionVarAnalysis::InductionInfo** trip) const {
+  DCHECK(context != nullptr);
+  DCHECK(context->GetBlock() != nullptr);
   HLoopInformation* lp = context->GetBlock()->GetLoopInformation();  // closest enveloping loop
   if (lp != nullptr) {
     HInductionVarAnalysis::InductionInfo* i = induction_analysis_->LookupInfo(lp, instruction);
@@ -474,6 +491,8 @@ InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::Ind
                                                       HInductionVarAnalysis::InductionInfo* trip,
                                                       bool in_body,
                                                       bool is_min) const {
+  DCHECK(info != nullptr);
+  DCHECK(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
@@ -520,6 +539,30 @@ InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::Ind
                   GetVal(info->op_b, trip, in_body, is_min));
 }
 
+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);
+  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.
+    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));
+    }
+  }
+  return Value();
+}
+
 InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction,
                                                      HInductionVarAnalysis::InductionInfo* trip,
                                                      bool in_body,
@@ -631,6 +674,10 @@ InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::Induct
         break;
       case HInductionVarAnalysis::kLinear:
         return CorrectForType(GetLinear(info, trip, in_body, is_min), info->type);
+      case HInductionVarAnalysis::kPolynomial:
+        break;
+      case HInductionVarAnalysis::kGeometric:
+        return GetGeometric(info, trip, in_body, is_min);
       case HInductionVarAnalysis::kWrapAround:
       case HInductionVarAnalysis::kPeriodic:
         return MergeVal(GetVal(info->op_a, trip, in_body, is_min),
@@ -842,17 +889,21 @@ bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context,
   *needs_taken_test = IsBodyTripCount(trip);
   // Handle last value request.
   if (is_last_value) {
-    if (info->induction_class == HInductionVarAnalysis::kLinear) {
-      if (*stride_value > 0) {
-        lower = nullptr;
-      } else {
-        upper = nullptr;
-      }
-    } else if (info->induction_class == HInductionVarAnalysis::kPeriodic) {
-      DCHECK(!in_body);
-      return GenerateLastValuePeriodic(info, trip, graph, block, lower, needs_taken_test);
-    } else {
-      return false;
+    DCHECK(!in_body);
+    switch (info->induction_class) {
+      case HInductionVarAnalysis::kLinear:
+        if (*stride_value > 0) {
+          lower = nullptr;
+        } else {
+          upper = nullptr;
+        }
+        break;
+      case HInductionVarAnalysis::kGeometric:
+        return GenerateLastValueGeometric(info, trip, graph, block, lower);
+      case HInductionVarAnalysis::kPeriodic:
+        return GenerateLastValuePeriodic(info, trip, graph, block, lower, needs_taken_test);
+      default:
+        return false;
     }
   }
   // Code generation for taken test: generate the code when requested or otherwise analyze
@@ -874,12 +925,68 @@ bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context,
       GenerateCode(info, trip, graph, block, upper, in_body, /* is_min */ 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);
+  // Detect known base and trip count (always taken).
+  int64_t f = 0;
+  int64_t t = 0;
+  if (IsIntAndGet(info->fetch, &f) && f >= 1 && IsConstant(trip->op_a, kExact, &t) && t >= 1) {
+    HInstruction* opa = nullptr;
+    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) {
+        DCHECK(info->type == Primitive::kPrimInt);  // due to codegen, generalize?
+        if (fpowt == 0) {
+          // Special case: repeated mul/div always yields zero.
+          *result = graph->GetIntConstant(0);
+        } else if (info->operation == HInductionVarAnalysis::kMul) {
+          // Last value multiplication: a * f ^ t + b.
+          HInstruction* mul = Insert(block,
+                                     new (graph->GetArena()) HMul(info->type,
+                                                                  opa,
+                                                                  graph->GetIntConstant(fpowt)));
+          *result = Insert(block, new (graph->GetArena()) HAdd(info->type, mul, opb));
+        } else {
+          // Last value multiplication: a * f ^ -t + b.
+          DCHECK_EQ(info->operation, HInductionVarAnalysis::kDiv);
+          HInstruction* div = Insert(block,
+                                     new (graph->GetArena()) HDiv(info->type,
+                                                                  opa,
+                                                                  graph->GetIntConstant(fpowt),
+                                                                  kNoDexPc));
+          *result = Insert(block, new (graph->GetArena()) HAdd(info->type, div, opb));
+        }
+      }
+      return true;
+    }
+  }
+  return false;
+}
+
 bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::InductionInfo* info,
                                                   HInductionVarAnalysis::InductionInfo* trip,
                                                   HGraph* graph,
                                                   HBasicBlock* block,
                                                   /*out*/HInstruction** result,
                                                   /*out*/bool* needs_taken_test) const {
+  DCHECK(info != nullptr);
   DCHECK(info->induction_class == HInductionVarAnalysis::kPeriodic);
   // Count period.
   int32_t period = 1;
@@ -937,6 +1044,7 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info,
       return true;
     }
     // Verify type safety.
+    // TODO: generalize
     Primitive::Type type = Primitive::kPrimInt;
     if (info->type != Primitive::kPrimInt && info->type != Primitive::kPrimBoolean) {
       return false;
@@ -1058,6 +1166,9 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info,
         }
         break;
       }
+      case HInductionVarAnalysis::kPolynomial:
+      case HInductionVarAnalysis::kGeometric:
+        break;
       case HInductionVarAnalysis::kWrapAround:
       case HInductionVarAnalysis::kPeriodic: {
         // Wrap-around and periodic inductions are restricted to constants only, so that extreme
@@ -1071,8 +1182,6 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info,
         }
         break;
       }
-      default:
-        break;
     }
   }
   return false;
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index 034cf32b2d..f7360e83db 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -190,6 +190,10 @@ class InductionVarRange {
                   HInductionVarAnalysis::InductionInfo* trip,
                   bool in_body,
                   bool is_min) const;
+  Value GetGeometric(HInductionVarAnalysis::InductionInfo* info,
+                     HInductionVarAnalysis::InductionInfo* trip,
+                     bool in_body,
+                     bool is_min) const;
   Value GetFetch(HInstruction* instruction,
                  HInductionVarAnalysis::InductionInfo* trip,
                  bool in_body,
@@ -245,6 +249,12 @@ class InductionVarRange {
                                 /*out*/ bool* needs_finite_test,
                                 /*out*/ bool* needs_taken_test) const;
 
+  bool GenerateLastValueGeometric(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 4c99e3cb6e..510841eb68 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -170,22 +170,46 @@ class InductionVarRangeTest : public CommonCompilerTest {
 
   /** Constructs a linear a * i + b induction. */
   HInductionVarAnalysis::InductionInfo* CreateLinear(int32_t a, int32_t b) {
-    return iva_->CreateInduction(
-        HInductionVarAnalysis::kLinear, CreateConst(a), CreateConst(b), Primitive::kPrimInt);
+    return iva_->CreateInduction(HInductionVarAnalysis::kLinear,
+                                 HInductionVarAnalysis::kNop,
+                                 CreateConst(a),
+                                 CreateConst(b),
+                                 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,
+                                 CreateConst(a),
+                                 CreateConst(b),
+                                 graph_->GetIntConstant(f),
+                                 Primitive::kPrimInt);
   }
 
   /** Constructs a range [lo, hi] using a periodic induction. */
   HInductionVarAnalysis::InductionInfo* CreateRange(int32_t lo, int32_t hi) {
-    return iva_->CreateInduction(
-        HInductionVarAnalysis::kPeriodic, CreateConst(lo), CreateConst(hi), Primitive::kPrimInt);
+    return iva_->CreateInduction(HInductionVarAnalysis::kPeriodic,
+                                 HInductionVarAnalysis::kNop,
+                                 CreateConst(lo),
+                                 CreateConst(hi),
+                                 nullptr,
+                                 Primitive::kPrimInt);
   }
 
   /** Constructs a wrap-around induction consisting of a constant, followed info */
   HInductionVarAnalysis::InductionInfo* CreateWrapAround(
       int32_t initial,
       HInductionVarAnalysis::InductionInfo* info) {
-    return iva_->CreateInduction(
-        HInductionVarAnalysis::kWrapAround, CreateConst(initial), info, Primitive::kPrimInt);
+    return iva_->CreateInduction(HInductionVarAnalysis::kWrapAround,
+                                 HInductionVarAnalysis::kNop,
+                                 CreateConst(initial),
+                                 info,
+                                 nullptr,
+                                 Primitive::kPrimInt);
   }
 
   /** Constructs a wrap-around induction consisting of a constant, followed by a range. */
@@ -414,6 +438,33 @@ TEST_F(InductionVarRangeTest, GetMinMaxWrapAround) {
   ExpectEqual(Value(20), GetMax(CreateWrapAround(20, -1, 10), nullptr));
 }
 
+TEST_F(InductionVarRangeTest, GetMinMaxGeometricMul) {
+  ExpectEqual(Value(), GetMin(CreateGeometric(1, 1, 1, '*'), nullptr));
+  ExpectEqual(Value(), GetMax(CreateGeometric(1, 1, 1, '*'), nullptr));
+}
+
+TEST_F(InductionVarRangeTest, GetMinMaxGeometricDiv) {
+  ExpectEqual(Value(5), GetMin(CreateGeometric(11, 5, 3, '/'), nullptr));
+  ExpectEqual(Value(16), GetMax(CreateGeometric(11, 5, 3, '/'), nullptr));
+  ExpectEqual(Value(-5), 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(5), GetMax(CreateGeometric(-11, 5, 3, '/'), nullptr));
+  ExpectEqual(Value(-16), GetMin(CreateGeometric(-11, -5, 3, '/'), nullptr));
+  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));