diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 8aaec68..8b38414 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -42,6 +42,33 @@
       instruction->GetBlock() == loop->GetHeader();
 }
 
+/**
+ * Returns true for 32/64-bit integral constant, passing its value as output parameter.
+ */
+static bool IsIntAndGet(HInstruction* instruction, int64_t* value) {
+  if (instruction->IsIntConstant()) {
+    *value = instruction->AsIntConstant()->GetValue();
+    return true;
+  } else if (instruction->IsLongConstant()) {
+    *value = instruction->AsLongConstant()->GetValue();
+    return true;
+  }
+  return false;
+}
+
+/**
+ * Returns a string representation of an instruction
+ * (for testing and debugging only).
+ */
+static std::string InstructionToString(HInstruction* instruction) {
+  if (instruction->IsIntConstant()) {
+    return std::to_string(instruction->AsIntConstant()->GetValue());
+  } else if (instruction->IsLongConstant()) {
+    return std::to_string(instruction->AsLongConstant()->GetValue()) + "L";
+  }
+  return std::to_string(instruction->GetId()) + ":" + instruction->DebugName();
+}
+
 //
 // Class methods.
 //
@@ -51,14 +78,15 @@
       global_depth_(0),
       stack_(graph->GetArena()->Adapter()),
       scc_(graph->GetArena()->Adapter()),
-      map_(std::less<int>(), graph->GetArena()->Adapter()),
-      cycle_(std::less<int>(), graph->GetArena()->Adapter()),
-      induction_(std::less<int>(), graph->GetArena()->Adapter()) {
+      map_(std::less<HInstruction*>(), graph->GetArena()->Adapter()),
+      cycle_(std::less<HInstruction*>(), graph->GetArena()->Adapter()),
+      induction_(std::less<HLoopInformation*>(), graph->GetArena()->Adapter()) {
 }
 
 void HInductionVarAnalysis::Run() {
-  // Detects sequence variables (generalized induction variables) during an
-  // inner-loop-first traversal of all loops using Gerlek's algorithm.
+  // Detects sequence variables (generalized induction variables) during an inner-loop-first
+  // traversal of all loops using Gerlek's algorithm. The order is only relevant if outer
+  // loops would use induction information of inner loops (not currently done).
   for (HPostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) {
     HBasicBlock* graph_block = it_graph.Current();
     if (graph_block->IsLoopHeader()) {
@@ -71,38 +99,37 @@
   // Find strongly connected components (SSCs) in the SSA graph of this loop using Tarjan's
   // algorithm. Due to the descendant-first nature, classification happens "on-demand".
   global_depth_ = 0;
-  CHECK(stack_.empty());
+  DCHECK(stack_.empty());
   map_.clear();
 
   for (HBlocksInLoopIterator it_loop(*loop); !it_loop.Done(); it_loop.Advance()) {
     HBasicBlock* loop_block = it_loop.Current();
-    CHECK(loop_block->IsInLoop());
+    DCHECK(loop_block->IsInLoop());
     if (loop_block->GetLoopInformation() != loop) {
       continue;  // Inner loops already visited.
     }
     // Visit phi-operations and instructions.
     for (HInstructionIterator it(loop_block->GetPhis()); !it.Done(); it.Advance()) {
       HInstruction* instruction = it.Current();
-      if (!IsVisitedNode(instruction->GetId())) {
+      if (!IsVisitedNode(instruction)) {
         VisitNode(loop, instruction);
       }
     }
     for (HInstructionIterator it(loop_block->GetInstructions()); !it.Done(); it.Advance()) {
       HInstruction* instruction = it.Current();
-      if (!IsVisitedNode(instruction->GetId())) {
+      if (!IsVisitedNode(instruction)) {
         VisitNode(loop, instruction);
       }
     }
   }
 
-  CHECK(stack_.empty());
+  DCHECK(stack_.empty());
   map_.clear();
 }
 
 void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* instruction) {
-  const int id = instruction->GetId();
   const uint32_t d1 = ++global_depth_;
-  map_.Put(id, NodeInfo(d1));
+  map_.Put(instruction, NodeInfo(d1));
   stack_.push_back(instruction);
 
   // Visit all descendants.
@@ -113,7 +140,7 @@
 
   // Lower or found SCC?
   if (low < d1) {
-    map_.find(id)->second.depth = low;
+    map_.find(instruction)->second.depth = low;
   } else {
     scc_.clear();
     cycle_.clear();
@@ -123,7 +150,7 @@
       HInstruction* x = stack_.back();
       scc_.push_back(x);
       stack_.pop_back();
-      map_.find(x->GetId())->second.done = true;
+      map_.find(x)->second.done = true;
       if (x == instruction) {
         break;
       }
@@ -150,12 +177,11 @@
   }
 
   // Inspect descendant node.
-  const int id = instruction->GetId();
-  if (!IsVisitedNode(id)) {
+  if (!IsVisitedNode(instruction)) {
     VisitNode(loop, instruction);
-    return map_.find(id)->second.depth;
+    return map_.find(instruction)->second.depth;
   } else {
-    auto it = map_.find(id);
+    auto it = map_.find(instruction);
     return it->second.done ? global_depth_ : it->second.depth;
   }
 }
@@ -176,8 +202,20 @@
   } 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)));
+  } else if (instruction->IsBoundsCheck()) {
+    info = LookupInfo(loop, instruction->InputAt(0));  // Pass-through.
+  } else if (instruction->IsTypeConversion()) {
+    HTypeConversion* conversion = instruction->AsTypeConversion();
+    // TODO: accept different conversion scenarios.
+    if (conversion->GetResultType() == conversion->GetInputType()) {
+      info = LookupInfo(loop, conversion->GetInput());
+    }
   }
 
   // Successfully classified?
@@ -188,7 +226,7 @@
 
 void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
   const size_t size = scc_.size();
-  CHECK_GE(size, 1u);
+  DCHECK_GE(size, 1u);
   HInstruction* phi = scc_[size - 1];
   if (!IsEntryPhi(loop, phi)) {
     return;
@@ -204,41 +242,74 @@
   if (size == 1) {
     InductionInfo* update = LookupInfo(loop, internal);
     if (update != nullptr) {
-      AssignInfo(loop, phi, NewInductionInfo(kWrapAround, kNop, initial, update, nullptr));
+      AssignInfo(loop, phi, NewInduction(kWrapAround, initial, update));
     }
     return;
   }
 
   // Inspect remainder of the cycle that resides in scc_. The cycle_ mapping assigns
-  // temporary meaning to its nodes.
-  cycle_.Overwrite(phi->GetId(), nullptr);
+  // temporary meaning to its nodes, seeded from the phi instruction and back.
   for (size_t i = 0; i < size - 1; i++) {
-    HInstruction* operation = scc_[i];
+    HInstruction* instruction = scc_[i];
     InductionInfo* update = nullptr;
-    if (operation->IsPhi()) {
-      update = TransferCycleOverPhi(operation);
-    } else if (operation->IsAdd()) {
-      update = TransferCycleOverAddSub(loop, operation->InputAt(0), operation->InputAt(1), kAdd, true);
-    } else if (operation->IsSub()) {
-      update = TransferCycleOverAddSub(loop, operation->InputAt(0), operation->InputAt(1), kSub, true);
+    if (instruction->IsPhi()) {
+      update = SolvePhi(loop, phi, instruction);
+    } else if (instruction->IsAdd()) {
+      update = SolveAddSub(
+          loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kAdd, true);
+    } else if (instruction->IsSub()) {
+      update = SolveAddSub(
+          loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true);
     }
     if (update == nullptr) {
       return;
     }
-    cycle_.Overwrite(operation->GetId(), update);
+    cycle_.Put(instruction, update);
   }
 
-  // Success if the internal link received accumulated nonzero update.
-  auto it = cycle_.find(internal->GetId());
-  if (it != cycle_.end() && it->second != nullptr) {
-    // Classify header phi and feed the cycle "on-demand".
-    AssignInfo(loop, phi, NewInductionInfo(kLinear, kNop, it->second, initial, nullptr));
-    for (size_t i = 0; i < size - 1; i++) {
-      ClassifyTrivial(loop, scc_[i]);
+  // Success if the internal link received a meaning.
+  auto it = cycle_.find(internal);
+  if (it != cycle_.end()) {
+    InductionInfo* induction = it->second;
+    switch (induction->induction_class) {
+      case kInvariant:
+        // Classify phi (last element in scc_) and then the rest of the cycle "on-demand".
+        // Statements are scanned in the Tarjan SCC order, with phi first.
+        AssignInfo(loop, phi, NewInduction(kLinear, induction, initial));
+        for (size_t i = 0; i < size - 1; i++) {
+          ClassifyTrivial(loop, scc_[i]);
+        }
+        break;
+      case kPeriodic:
+        // Classify all elements in the cycle with the found periodic induction while rotating
+        // each first element to the end. Lastly, phi (last element in scc_) is classified.
+        // Statements are scanned in the reverse Tarjan SCC order, with phi last.
+        for (size_t i = 2; i <= size; i++) {
+          AssignInfo(loop, scc_[size - i], induction);
+          induction = RotatePeriodicInduction(induction->op_b, induction->op_a);
+        }
+        AssignInfo(loop, phi, induction);
+        break;
+      default:
+        break;
     }
   }
 }
 
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::RotatePeriodicInduction(
+    InductionInfo* induction,
+    InductionInfo* last) {
+  // Rotates a periodic induction of the form
+  //   (a, b, c, d, e)
+  // into
+  //   (b, c, d, e, a)
+  // in preparation of assigning this to the previous variable in the sequence.
+  if (induction->induction_class == kInvariant) {
+    return NewInduction(kPeriodic, induction, last);
+  }
+  return NewInduction(kPeriodic, induction->op_a, RotatePeriodicInduction(induction->op_b, last));
+}
+
 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(InductionInfo* a,
                                                                          InductionInfo* b) {
   // Transfer over a phi: if both inputs are identical, result is input.
@@ -251,36 +322,33 @@
 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(InductionInfo* a,
                                                                             InductionInfo* b,
                                                                             InductionOp op) {
-  // Transfer over an addition or subtraction: invariant or linear
-  // inputs combine into new invariant or linear result.
+  // 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.
   if (a != nullptr && b != nullptr) {
     if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
-      return NewInductionInfo(kInvariant, op, a, b, nullptr);
-    } else if (a->induction_class == kLinear && b->induction_class == kInvariant) {
-      return NewInductionInfo(
-          kLinear,
-          kNop,
-          a->op_a,
-          NewInductionInfo(kInvariant, op, a->op_b, b, nullptr),
-          nullptr);
-    } else if (a->induction_class == kInvariant && b->induction_class == kLinear) {
-      InductionInfo* ba = b->op_a;
-      if (op == kSub) {  // negation required
-        ba = NewInductionInfo(kInvariant, kNeg, nullptr, ba, nullptr);
-      }
-      return NewInductionInfo(
-          kLinear,
-          kNop,
-          ba,
-          NewInductionInfo(kInvariant, op, a, b->op_b, nullptr),
-          nullptr);
+      return NewInvariantOp(op, a, b);
     } else if (a->induction_class == kLinear && b->induction_class == kLinear) {
-      return NewInductionInfo(
-          kLinear,
-          kNop,
-          NewInductionInfo(kInvariant, op, a->op_a, b->op_a, nullptr),
-          NewInductionInfo(kInvariant, op, a->op_b, b->op_b, nullptr),
-          nullptr);
+      return NewInduction(
+          kLinear, TransferAddSub(a->op_a, b->op_a, op), TransferAddSub(a->op_b, b->op_b, op));
+    } 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);
+        new_a = TransferAddSub(a, new_a, op);
+      } else if (op == kSub) {  // Negation required.
+        new_a = TransferNeg(new_a);
+      }
+      return NewInduction(b->induction_class, new_a, new_b);
+    } 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);
+        new_a = TransferAddSub(new_a, b, op);
+      }
+      return NewInduction(a->induction_class, new_a, new_b);
     }
   }
   return nullptr;
@@ -288,141 +356,164 @@
 
 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferMul(InductionInfo* a,
                                                                          InductionInfo* b) {
-  // Transfer over a multiplication: invariant or linear
-  // inputs combine into new invariant or linear result.
-  // Two linear inputs would become quadratic.
+  // 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.
   if (a != nullptr && b != nullptr) {
     if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
-      return NewInductionInfo(kInvariant, kMul, a, b, nullptr);
-    } else if (a->induction_class == kLinear && b->induction_class == kInvariant) {
-      return NewInductionInfo(
-          kLinear,
-          kNop,
-          NewInductionInfo(kInvariant, kMul, a->op_a, b, nullptr),
-          NewInductionInfo(kInvariant, kMul, a->op_b, b, nullptr),
-          nullptr);
-    } else if (a->induction_class == kInvariant && b->induction_class == kLinear) {
-      return NewInductionInfo(
-          kLinear,
-          kNop,
-          NewInductionInfo(kInvariant, kMul, a, b->op_a, nullptr),
-          NewInductionInfo(kInvariant, kMul, a, b->op_b, nullptr),
-          nullptr);
+      return NewInvariantOp(kMul, a, b);
+    } else if (a->induction_class == kInvariant) {
+      return NewInduction(b->induction_class, TransferMul(a, b->op_a), TransferMul(a, b->op_b));
+    } else if (b->induction_class == kInvariant) {
+      return NewInduction(a->induction_class, TransferMul(a->op_a, b), TransferMul(a->op_b, b));
+    }
+  }
+  return nullptr;
+}
+
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferShl(InductionInfo* a,
+                                                                         InductionInfo* b,
+                                                                         Primitive::Type t) {
+  // Transfer over a shift left: treat shift by restricted constant as equivalent multiplication.
+  if (a != nullptr && b != nullptr && b->induction_class == kInvariant && b->operation == kFetch) {
+    int64_t value = -1;
+    // 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 (IsIntAndGet(b->fetch, &value)) {
+      if (t == Primitive::kPrimInt && 0 <= value && value < 31) {
+        return TransferMul(a, NewInvariantFetch(graph_->GetIntConstant(1 << value)));
+      } else if (t == Primitive::kPrimLong && 0 <= value && value < 63) {
+        return TransferMul(a, NewInvariantFetch(graph_->GetLongConstant(1L << value)));
+      }
     }
   }
   return nullptr;
 }
 
 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a) {
-  // Transfer over a unary negation: invariant or linear input
-  // yields a similar, but negated result.
+  // Transfer over a unary negation: an invariant, linear, wrap-around, or periodic input
+  // yields a similar but negated induction as result.
   if (a != nullptr) {
     if (a->induction_class == kInvariant) {
-      return NewInductionInfo(kInvariant, kNeg, nullptr, a, nullptr);
-    } else if (a->induction_class == kLinear) {
-      return NewInductionInfo(
-          kLinear,
-          kNop,
-          NewInductionInfo(kInvariant, kNeg, nullptr, a->op_a, nullptr),
-          NewInductionInfo(kInvariant, kNeg, nullptr, a->op_b, nullptr),
-          nullptr);
+      return NewInvariantOp(kNeg, nullptr, a);
     }
+    return NewInduction(a->induction_class, TransferNeg(a->op_a), TransferNeg(a->op_b));
   }
   return nullptr;
 }
 
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferCycleOverPhi(HInstruction* phi) {
-  // Transfer within a cycle over a phi: only identical inputs
-  // can be combined into that input as result.
-  const size_t count = phi->InputCount();
-  CHECK_GT(count, 0u);
-  auto ita = cycle_.find(phi->InputAt(0)->GetId());
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi(HLoopInformation* loop,
+                                                                      HInstruction* phi,
+                                                                      HInstruction* instruction) {
+  // Solve within a cycle over a phi: identical inputs are combined into that input as result.
+  const size_t count = instruction->InputCount();
+  DCHECK_GT(count, 0u);
+  auto ita = cycle_.find(instruction->InputAt(0));
   if (ita != cycle_.end()) {
     InductionInfo* a = ita->second;
     for (size_t i = 1; i < count; i++) {
-      auto itb = cycle_.find(phi->InputAt(i)->GetId());
-      if (itb == cycle_.end() ||!HInductionVarAnalysis::InductionEqual(a, itb->second)) {
+      auto itb = cycle_.find(instruction->InputAt(i));
+      if (itb == cycle_.end() || !HInductionVarAnalysis::InductionEqual(a, itb->second)) {
         return nullptr;
       }
     }
     return a;
   }
-  return nullptr;
-}
 
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferCycleOverAddSub(
-    HLoopInformation* loop,
-    HInstruction* x,
-    HInstruction* y,
-    InductionOp op,
-    bool first) {
-  // Transfer within a cycle over an addition or subtraction: adding or
-  // subtracting an invariant value adds to the stride of the induction,
-  // starting with the phi value denoted by the unusual nullptr value.
-  auto it = cycle_.find(x->GetId());
-  if (it != cycle_.end()) {
-    InductionInfo* a = it->second;
-    InductionInfo* b = LookupInfo(loop, y);
-    if (b != nullptr && b->induction_class == kInvariant) {
-      if (a == nullptr) {
-        if (op == kSub) {  // negation required
-          return NewInductionInfo(kInvariant, kNeg, nullptr, b, nullptr);
+  // Solve within a cycle over another entry-phi: add invariants into a periodic.
+  if (IsEntryPhi(loop, instruction)) {
+    InductionInfo* a = LookupInfo(loop, instruction->InputAt(0));
+    if (a != nullptr && a->induction_class == kInvariant) {
+      if (instruction->InputAt(1) == phi) {
+        InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
+        return NewInduction(kPeriodic, a, initial);
+      }
+      auto it = cycle_.find(instruction->InputAt(1));
+      if (it != cycle_.end()) {
+        InductionInfo* b = it->second;
+        if (b->induction_class == kPeriodic) {
+          return NewInduction(kPeriodic, a, b);
         }
-        return b;
-      } else if (a->induction_class == kInvariant) {
-        return NewInductionInfo(kInvariant, op, a, b, nullptr);
       }
     }
   }
-  // On failure, try alternatives.
-  if (op == kAdd) {
-    // Try the other way around for an addition.
-    if (first) {
-      return TransferCycleOverAddSub(loop, y, x, op, false);
-    }
-  }
+
   return nullptr;
 }
 
-void HInductionVarAnalysis::PutInfo(int loop_id, int id, InductionInfo* info) {
-  auto it = induction_.find(loop_id);
-  if (it == induction_.end()) {
-    it = induction_.Put(
-        loop_id, ArenaSafeMap<int, InductionInfo*>(std::less<int>(), graph_->GetArena()->Adapter()));
-  }
-  it->second.Overwrite(id, info);
-}
-
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::GetInfo(int loop_id, int id) {
-  auto it = induction_.find(loop_id);
-  if (it != induction_.end()) {
-    auto loop_it = it->second.find(id);
-    if (loop_it != it->second.end()) {
-      return loop_it->second;
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopInformation* loop,
+                                                                         HInstruction* phi,
+                                                                         HInstruction* instruction,
+                                                                         HInstruction* x,
+                                                                         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 induction.
+  InductionInfo* b = LookupInfo(loop, y);
+  if (b != nullptr && b->induction_class == kInvariant) {
+    if (x == phi) {
+      return (op == kAdd) ? b : NewInvariantOp(kNeg, nullptr, b);
+    }
+    auto it = cycle_.find(x);
+    if (it != cycle_.end()) {
+      InductionInfo* a = it->second;
+      if (a->induction_class == kInvariant) {
+        return NewInvariantOp(op, a, b);
+      }
     }
   }
+
+  // Try some alternatives before failing.
+  if (op == kAdd) {
+    // Try the other way around for an addition if considered for first time.
+    if (is_first_call) {
+      return SolveAddSub(loop, phi, instruction, y, x, op, false);
+    }
+  } else if (op == kSub) {
+    // Solve within a tight cycle for a periodic idiom k = c - k;
+    if (y == phi && instruction == phi->InputAt(1)) {
+      InductionInfo* a = LookupInfo(loop, x);
+      if (a != nullptr && a->induction_class == kInvariant) {
+        InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
+        return NewInduction(kPeriodic, NewInvariantOp(kSub, a, initial), initial);
+      }
+    }
+  }
+
   return nullptr;
 }
 
 void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop,
                                        HInstruction* instruction,
                                        InductionInfo* info) {
-  const int loopId = loop->GetHeader()->GetBlockId();
-  const int id = instruction->GetId();
-  PutInfo(loopId, id, info);
+  auto it = induction_.find(loop);
+  if (it == induction_.end()) {
+    it = induction_.Put(loop,
+                        ArenaSafeMap<HInstruction*, InductionInfo*>(
+                            std::less<HInstruction*>(), graph_->GetArena()->Adapter()));
+  }
+  it->second.Put(instruction, info);
 }
 
-HInductionVarAnalysis::InductionInfo*
-HInductionVarAnalysis::LookupInfo(HLoopInformation* loop,
-                                  HInstruction* instruction) {
-  const int loop_id = loop->GetHeader()->GetBlockId();
-  const int id = instruction->GetId();
-  InductionInfo* info = GetInfo(loop_id, id);
-  if (info == nullptr && IsLoopInvariant(loop, instruction)) {
-    info = NewInductionInfo(kInvariant, kFetch, nullptr, nullptr, instruction);
-    PutInfo(loop_id, id, info);
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(HLoopInformation* loop,
+                                                                        HInstruction* instruction) {
+  auto it = induction_.find(loop);
+  if (it != induction_.end()) {
+    auto loop_it = it->second.find(instruction);
+    if (loop_it != it->second.end()) {
+      return loop_it->second;
+    }
   }
-  return info;
+  if (IsLoopInvariant(loop, instruction)) {
+    InductionInfo* info = NewInvariantFetch(instruction);
+    AssignInfo(loop, instruction, info);
+    return info;
+  }
+  return nullptr;
 }
 
 bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1,
@@ -446,21 +537,21 @@
       std::string inv = "(";
       inv += InductionToString(info->op_a);
       switch (info->operation) {
-        case kNop: inv += " ? "; break;
-        case kAdd: inv += " + "; break;
+        case kNop:   inv += " @ "; break;
+        case kAdd:   inv += " + "; break;
         case kSub:
-        case kNeg: inv += " - "; break;
-        case kMul: inv += " * "; break;
-        case kDiv: inv += " / "; break;
+        case kNeg:   inv += " - "; break;
+        case kMul:   inv += " * "; break;
+        case kDiv:   inv += " / "; break;
         case kFetch:
-          CHECK(info->fetch != nullptr);
-          inv += std::to_string(info->fetch->GetId()) + ":" + info->fetch->DebugName();
+          DCHECK(info->fetch);
+          inv += InstructionToString(info->fetch);
           break;
       }
       inv += InductionToString(info->op_b);
       return inv + ")";
     } else {
-      CHECK(info->operation == kNop);
+      DCHECK(info->operation == kNop);
       if (info->induction_class == kLinear) {
         return "(" + InductionToString(info->op_a) + " * i + " +
                      InductionToString(info->op_b) + ")";
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 09a0a38..db00f58 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -25,9 +25,11 @@
 namespace art {
 
 /**
- * Induction variable analysis.
+ * Induction variable analysis. This class does not have a direct public API.
+ * Instead, the results of induction variable analysis can be queried through
+ * friend classes, such as InductionVarRange.
  *
- * Based on the paper by M. Gerlek et al.
+ * The analysis implementation is based on the paper by M. Gerlek et al.
  * "Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form"
  * (ACM Transactions on Programming Languages and Systems, Volume 17 Issue 1, Jan. 1995).
  */
@@ -35,16 +37,6 @@
  public:
   explicit HInductionVarAnalysis(HGraph* graph);
 
-  // TODO: design public API useful in later phases
-
-  /**
-   * Returns string representation of induction found for the instruction
-   * in the given loop (for testing and debugging only).
-   */
-  std::string InductionToString(HLoopInformation* loop, HInstruction* instruction) {
-    return InductionToString(LookupInfo(loop, instruction));
-  }
-
   void Run() OVERRIDE;
 
  private:
@@ -57,12 +49,10 @@
   };
 
   enum InductionClass {
-    kNone,
     kInvariant,
     kLinear,
     kWrapAround,
-    kPeriodic,
-    kMonotonic
+    kPeriodic
   };
 
   enum InductionOp {
@@ -79,7 +69,7 @@
    * Defines a detected induction as:
    *   (1) invariant:
    *         operation: a + b, a - b, -b, a * b, a / b
-   *       or
+   *       or:
    *         fetch: fetch from HIR
    *   (2) linear:
    *         nop: a * i + b
@@ -87,8 +77,6 @@
    *         nop: a, then defined by b
    *   (4) periodic
    *         nop: a, then defined by b (repeated when exhausted)
-   *   (5) monotonic
-   *         // TODO: determine representation
    */
   struct InductionInfo : public ArenaObject<kArenaAllocMisc> {
     InductionInfo(InductionClass ic,
@@ -108,17 +96,23 @@
     HInstruction* fetch;
   };
 
-  inline bool IsVisitedNode(int id) const {
-    return map_.find(id) != map_.end();
+  bool IsVisitedNode(HInstruction* instruction) const {
+    return map_.find(instruction) != map_.end();
   }
 
-  inline InductionInfo* NewInductionInfo(
-      InductionClass c,
-      InductionOp op,
-      InductionInfo* a,
-      InductionInfo* b,
-      HInstruction* i) {
-    return new (graph_->GetArena()) InductionInfo(c, op, a, b, i);
+  InductionInfo* NewInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) {
+    DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr);
+    return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr);
+  }
+
+  InductionInfo* NewInvariantFetch(HInstruction* f) {
+    DCHECK(f != nullptr);
+    return new (graph_->GetArena()) InductionInfo(kInvariant, kFetch, nullptr, nullptr, f);
+  }
+
+  InductionInfo* NewInduction(InductionClass ic, InductionInfo* a, InductionInfo* b) {
+    DCHECK(a != nullptr && b != nullptr);
+    return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr);
   }
 
   // Methods for analysis.
@@ -132,36 +126,46 @@
   InductionInfo* TransferPhi(InductionInfo* a, InductionInfo* b);
   InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
   InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
+  InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type t);
   InductionInfo* TransferNeg(InductionInfo* a);
-  InductionInfo* TransferCycleOverPhi(HInstruction* phi);
-  InductionInfo* TransferCycleOverAddSub(HLoopInformation* loop,
-                                         HInstruction* x,
-                                         HInstruction* y,
-                                         InductionOp op,
-                                         bool first);
+
+  // Solvers.
+  InductionInfo* SolvePhi(HLoopInformation* loop,
+                          HInstruction* phi,
+                          HInstruction* instruction);
+  InductionInfo* SolveAddSub(HLoopInformation* loop,
+                             HInstruction* phi,
+                             HInstruction* instruction,
+                             HInstruction* x,
+                             HInstruction* y,
+                             InductionOp op,
+                             bool is_first_call);
+  InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
 
   // Assign and lookup.
-  void PutInfo(int loop_id, int id, InductionInfo* info);
-  InductionInfo* GetInfo(int loop_id, int id);
   void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
   InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
-  bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
-  std::string InductionToString(InductionInfo* info);
 
-  // Bookkeeping during and after analysis.
-  // TODO: fine tune data structures, only keep relevant data
+  // Helpers.
+  static bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
+  static std::string InductionToString(InductionInfo* info);
 
+  // TODO: fine tune the following data structures, only keep relevant data.
+
+  // Temporary book-keeping during the analysis.
   uint32_t global_depth_;
-
   ArenaVector<HInstruction*> stack_;
   ArenaVector<HInstruction*> scc_;
+  ArenaSafeMap<HInstruction*, NodeInfo> map_;
+  ArenaSafeMap<HInstruction*, InductionInfo*> cycle_;
 
-  // Mappings of instruction id to node and induction information.
-  ArenaSafeMap<int, NodeInfo> map_;
-  ArenaSafeMap<int, InductionInfo*> cycle_;
+  /**
+   * Maintains the results of the analysis as a mapping from loops to a mapping from instructions
+   * to the induction information for that instruction in that loop.
+   */
+  ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_;
 
-  // Mapping from loop id to mapping of instruction id to induction information.
-  ArenaSafeMap<int, ArenaSafeMap<int, InductionInfo*>> induction_;
+  friend class InductionVarAnalysisTest;
 
   DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis);
 };
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index 2093e33..b569fbe 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -63,7 +63,7 @@
   // populate the loop with instructions to set up interesting scenarios.
   void BuildLoopNest(int n) {
     ASSERT_LE(n, 10);
-    graph_->SetNumberOfVRegs(n + 2);
+    graph_->SetNumberOfVRegs(n + 3);
 
     // Build basic blocks with entry, nested loop, exit.
     entry_ = new (&allocator_) HBasicBlock(graph_);
@@ -77,47 +77,36 @@
     graph_->SetExitBlock(exit_);
 
     // Provide entry and exit instructions.
-    // 0 : parameter
-    // 1 : constant 0
-    // 2 : constant 1
-    // 3 : constant 100
-    parameter_ = new (&allocator_)
-        HParameterValue(0, Primitive::kPrimNot, true);
+    parameter_ = new (&allocator_) HParameterValue(0, Primitive::kPrimNot, true);
     entry_->AddInstruction(parameter_);
-    constant0_ = new (&allocator_) HConstant(Primitive::kPrimInt);
-    entry_->AddInstruction(constant0_);
-    constant1_ = new (&allocator_) HConstant(Primitive::kPrimInt);
-    entry_->AddInstruction(constant1_);
-    constant100_ = new (&allocator_) HConstant(Primitive::kPrimInt);
-    entry_->AddInstruction(constant100_);
-    exit_->AddInstruction(new (&allocator_) HExit());
+    constant0_ = graph_->GetIntConstant(0);
+    constant1_ = graph_->GetIntConstant(1);
+    constant100_ = graph_->GetIntConstant(100);
     induc_ = new (&allocator_) HLocal(n);
     entry_->AddInstruction(induc_);
     entry_->AddInstruction(new (&allocator_) HStoreLocal(induc_, constant0_));
     tmp_ = new (&allocator_) HLocal(n + 1);
     entry_->AddInstruction(tmp_);
     entry_->AddInstruction(new (&allocator_) HStoreLocal(tmp_, constant100_));
+    dum_ = new (&allocator_) HLocal(n + 2);
+    entry_->AddInstruction(dum_);
+    exit_->AddInstruction(new (&allocator_) HExit());
 
     // Provide loop instructions.
     for (int d = 0; d < n; d++) {
       basic_[d] = new (&allocator_) HLocal(d);
       entry_->AddInstruction(basic_[d]);
-      loop_preheader_[d]->AddInstruction(
-           new (&allocator_) HStoreLocal(basic_[d], constant0_));
-      HInstruction* load = new (&allocator_)
-          HLoadLocal(basic_[d], Primitive::kPrimInt);
+      loop_preheader_[d]->AddInstruction(new (&allocator_) HStoreLocal(basic_[d], constant0_));
+      HInstruction* load = new (&allocator_) HLoadLocal(basic_[d], Primitive::kPrimInt);
       loop_header_[d]->AddInstruction(load);
-      HInstruction* compare = new (&allocator_)
-          HGreaterThanOrEqual(load, constant100_);
+      HInstruction* compare = new (&allocator_) HGreaterThanOrEqual(load, constant100_);
       loop_header_[d]->AddInstruction(compare);
       loop_header_[d]->AddInstruction(new (&allocator_) HIf(compare));
       load = new (&allocator_) HLoadLocal(basic_[d], Primitive::kPrimInt);
       loop_body_[d]->AddInstruction(load);
-      increment_[d] = new (&allocator_)
-          HAdd(Primitive::kPrimInt, load, constant1_);
+      increment_[d] = new (&allocator_) HAdd(Primitive::kPrimInt, load, constant1_);
       loop_body_[d]->AddInstruction(increment_[d]);
-      loop_body_[d]->AddInstruction(
-               new (&allocator_) HStoreLocal(basic_[d], increment_[d]));
+      loop_body_[d]->AddInstruction(new (&allocator_) HStoreLocal(basic_[d], increment_[d]));
       loop_body_[d]->AddInstruction(new (&allocator_) HGoto());
     }
   }
@@ -149,8 +138,7 @@
 
   // Inserts local load at depth d.
   HInstruction* InsertLocalLoad(HLocal* local, int d) {
-    return InsertInstruction(
-        new (&allocator_) HLoadLocal(local, Primitive::kPrimInt), d);
+    return InsertInstruction(new (&allocator_) HLoadLocal(local, Primitive::kPrimInt), d);
   }
 
   // Inserts local store at depth d.
@@ -167,9 +155,10 @@
         parameter_, load, constant0_, Primitive::kPrimInt, 0), d);
   }
 
-  // Returns loop information of loop at depth d.
-  HLoopInformation* GetLoopInfo(int d) {
-    return loop_body_[d]->GetLoopInformation();
+  // Returns induction information of instruction in loop at depth d.
+  std::string GetInductionInfo(HInstruction* instruction, int d) {
+    return HInductionVarAnalysis::InductionToString(
+        iva_->LookupInfo(loop_body_[d]->GetLoopInformation(), instruction));
   }
 
   // Performs InductionVarAnalysis (after proper set up).
@@ -194,6 +183,7 @@
   HInstruction* constant100_;
   HLocal* induc_;  // "vreg_n", the "k"
   HLocal* tmp_;    // "vreg_n+1"
+  HLocal* dum_;    // "vreg_n+2"
 
   // Loop specifics.
   HBasicBlock* loop_preheader_[10];
@@ -230,222 +220,156 @@
   ASSERT_EQ(exit_->GetLoopInformation(), nullptr);
 }
 
-TEST_F(InductionVarAnalysisTest, FindBasicInductionVar) {
+TEST_F(InductionVarAnalysisTest, FindBasicInduction) {
   // Setup:
   // for (int i = 0; i < 100; i++) {
-  //    a[i] = 0;
+  //   a[i] = 0;
   // }
   BuildLoopNest(1);
   HInstruction* store = InsertArrayStore(basic_[0], 0);
   PerformInductionVarAnalysis();
 
-  EXPECT_STREQ(
-      "((2:Constant) * i + (1:Constant))",
-      iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
-  EXPECT_STREQ(
-      "((2:Constant) * i + ((1:Constant) + (2:Constant)))",
-      iva_->InductionToString(GetLoopInfo(0), increment_[0]).c_str());
+  EXPECT_STREQ("((1) * i + (0))", GetInductionInfo(store->InputAt(1), 0).c_str());
+  EXPECT_STREQ("((1) * i + ((0) + (1)))", GetInductionInfo(increment_[0], 0).c_str());
 }
 
-TEST_F(InductionVarAnalysisTest, FindDerivedInductionVarAdd) {
+TEST_F(InductionVarAnalysisTest, FindDerivedInduction) {
   // Setup:
   // for (int i = 0; i < 100; i++) {
-  //    k = 100 + i;
-  //    a[k] = 0;
+  //   k = 100 + i;
+  //   k = 100 - i;
+  //   k = 100 * i;
+  //   k = i << 1;
+  //   k = - i;
   // }
   BuildLoopNest(1);
   HInstruction *add = InsertInstruction(
-      new (&allocator_) HAdd(
-          Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
+      new (&allocator_) HAdd(Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
   InsertLocalStore(induc_, add, 0);
-  HInstruction* store = InsertArrayStore(induc_, 0);
-  PerformInductionVarAnalysis();
-
-  EXPECT_STREQ(
-      "((2:Constant) * i + ((3:Constant) + (1:Constant)))",
-      iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
-}
-
-TEST_F(InductionVarAnalysisTest, FindDerivedInductionVarSub) {
-  // Setup:
-  // for (int i = 0; i < 100; i++) {
-  //    k = 100 - i;
-  //    a[k] = 0;
-  // }
-  BuildLoopNest(1);
   HInstruction *sub = InsertInstruction(
-      new (&allocator_) HSub(
-          Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
+      new (&allocator_) HSub(Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
   InsertLocalStore(induc_, sub, 0);
-  HInstruction* store = InsertArrayStore(induc_, 0);
-  PerformInductionVarAnalysis();
-
-  EXPECT_STREQ(
-      "(( - (2:Constant)) * i + ((3:Constant) - (1:Constant)))",
-      iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
-}
-
-TEST_F(InductionVarAnalysisTest, FindDerivedInductionVarMul) {
-  // Setup:
-  // for (int i = 0; i < 100; i++) {
-  //    k = 100 * i;
-  //    a[k] = 0;
-  // }
-  BuildLoopNest(1);
   HInstruction *mul = InsertInstruction(
-      new (&allocator_) HMul(
-          Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
+      new (&allocator_) HMul(Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
   InsertLocalStore(induc_, mul, 0);
-  HInstruction* store = InsertArrayStore(induc_, 0);
-  PerformInductionVarAnalysis();
-
-  EXPECT_STREQ(
-      "(((3:Constant) * (2:Constant)) * i + ((3:Constant) * (1:Constant)))",
-      iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
-}
-
-TEST_F(InductionVarAnalysisTest, FindDerivedInductionVarNeg) {
-  // Setup:
-  // for (int i = 0; i < 100; i++) {
-  //    k = - i;
-  //    a[k] = 0;
-  // }
-  BuildLoopNest(1);
+  HInstruction *shl = InsertInstruction(
+      new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(basic_[0], 0), constant1_), 0);
+  InsertLocalStore(induc_, shl, 0);
   HInstruction *neg = InsertInstruction(
-      new (&allocator_) HNeg(
-          Primitive::kPrimInt, InsertLocalLoad(basic_[0], 0)), 0);
+      new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(basic_[0], 0)), 0);
   InsertLocalStore(induc_, neg, 0);
-  HInstruction* store = InsertArrayStore(induc_, 0);
   PerformInductionVarAnalysis();
 
-  EXPECT_STREQ(
-      "(( - (2:Constant)) * i + ( - (1:Constant)))",
-      iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
+  EXPECT_STREQ("((1) * i + ((100) + (0)))", GetInductionInfo(add, 0).c_str());
+  EXPECT_STREQ("(( - (1)) * i + ((100) - (0)))", GetInductionInfo(sub, 0).c_str());
+  EXPECT_STREQ("(((100) * (1)) * i + ((100) * (0)))", GetInductionInfo(mul, 0).c_str());
+  EXPECT_STREQ("(((1) * (2)) * i + ((0) * (2)))", GetInductionInfo(shl, 0).c_str());
+  EXPECT_STREQ("(( - (1)) * i + ( - (0)))", GetInductionInfo(neg, 0).c_str());
 }
 
 TEST_F(InductionVarAnalysisTest, FindChainInduction) {
   // Setup:
   // k = 0;
   // for (int i = 0; i < 100; i++) {
-  //    k = k + 100;
-  //    a[k] = 0;
-  //    k = k - 1;
-  //    a[k] = 0;
+  //   k = k + 100;
+  //   a[k] = 0;
+  //   k = k - 1;
+  //   a[k] = 0;
   // }
   BuildLoopNest(1);
   HInstruction *add = InsertInstruction(
-      new (&allocator_) HAdd(
-          Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+      new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
   InsertLocalStore(induc_, add, 0);
   HInstruction* store1 = InsertArrayStore(induc_, 0);
   HInstruction *sub = InsertInstruction(
-      new (&allocator_) HSub(
-          Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
+      new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
   InsertLocalStore(induc_, sub, 0);
   HInstruction* store2 = InsertArrayStore(induc_, 0);
   PerformInductionVarAnalysis();
 
-  EXPECT_STREQ(
-      "(((3:Constant) - (2:Constant)) * i + ((1:Constant) + (3:Constant)))",
-      iva_->InductionToString(GetLoopInfo(0), store1->InputAt(1)).c_str());
-  EXPECT_STREQ(
-      "(((3:Constant) - (2:Constant)) * i + "
-      "(((1:Constant) + (3:Constant)) - (2:Constant)))",
-      iva_->InductionToString(GetLoopInfo(0), store2->InputAt(1)).c_str());
+  EXPECT_STREQ("(((100) - (1)) * i + ((0) + (100)))",
+               GetInductionInfo(store1->InputAt(1), 0).c_str());
+  EXPECT_STREQ("(((100) - (1)) * i + (((0) + (100)) - (1)))",
+               GetInductionInfo(store2->InputAt(1), 0).c_str());
 }
 
 TEST_F(InductionVarAnalysisTest, FindTwoWayBasicInduction) {
   // Setup:
   // k = 0;
   // for (int i = 0; i < 100; i++) {
-  //    if () k = k + 1;
-  //    else  k = k + 1;
-  //    a[k] = 0;
+  //   if () k = k + 1;
+  //   else  k = k + 1;
+  //   a[k] = 0;
   // }
   BuildLoopNest(1);
   HBasicBlock* ifTrue;
   HBasicBlock* ifFalse;
   BuildIf(0, &ifTrue, &ifFalse);
   // True-branch.
-  HInstruction* load1 = new (&allocator_)
-      HLoadLocal(induc_, Primitive::kPrimInt);
+  HInstruction* load1 = new (&allocator_) HLoadLocal(induc_, Primitive::kPrimInt);
   ifTrue->AddInstruction(load1);
-  HInstruction* inc1 = new (&allocator_)
-      HAdd(Primitive::kPrimInt, load1, constant1_);
+  HInstruction* inc1 = new (&allocator_) HAdd(Primitive::kPrimInt, load1, constant1_);
   ifTrue->AddInstruction(inc1);
   ifTrue->AddInstruction(new (&allocator_) HStoreLocal(induc_, inc1));
   // False-branch.
-  HInstruction* load2 = new (&allocator_)
-      HLoadLocal(induc_, Primitive::kPrimInt);
+  HInstruction* load2 = new (&allocator_) HLoadLocal(induc_, Primitive::kPrimInt);
   ifFalse->AddInstruction(load2);
-  HInstruction* inc2 = new (&allocator_)
-        HAdd(Primitive::kPrimInt, load2, constant1_);
+  HInstruction* inc2 = new (&allocator_) HAdd(Primitive::kPrimInt, load2, constant1_);
   ifFalse->AddInstruction(inc2);
   ifFalse->AddInstruction(new (&allocator_) HStoreLocal(induc_, inc2));
   // Merge over a phi.
   HInstruction* store = InsertArrayStore(induc_, 0);
   PerformInductionVarAnalysis();
 
-  EXPECT_STREQ(
-      "((2:Constant) * i + ((1:Constant) + (2:Constant)))",
-      iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
+  EXPECT_STREQ("((1) * i + ((0) + (1)))", GetInductionInfo(store->InputAt(1), 0).c_str());
 }
 
 TEST_F(InductionVarAnalysisTest, FindTwoWayDerivedInduction) {
   // Setup:
   // for (int i = 0; i < 100; i++) {
-  //    if () k = i + 1;
-  //    else  k = i + 1;
-  //    a[k] = 0;
+  //   if () k = i + 1;
+  //   else  k = i + 1;
+  //   a[k] = 0;
   // }
   BuildLoopNest(1);
   HBasicBlock* ifTrue;
   HBasicBlock* ifFalse;
   BuildIf(0, &ifTrue, &ifFalse);
   // True-branch.
-  HInstruction* load1 = new (&allocator_)
-      HLoadLocal(basic_[0], Primitive::kPrimInt);
+  HInstruction* load1 = new (&allocator_) HLoadLocal(basic_[0], Primitive::kPrimInt);
   ifTrue->AddInstruction(load1);
-  HInstruction* inc1 = new (&allocator_)
-      HAdd(Primitive::kPrimInt, load1, constant1_);
+  HInstruction* inc1 = new (&allocator_) HAdd(Primitive::kPrimInt, load1, constant1_);
   ifTrue->AddInstruction(inc1);
   ifTrue->AddInstruction(new (&allocator_) HStoreLocal(induc_, inc1));
   // False-branch.
-  HInstruction* load2 = new (&allocator_)
-      HLoadLocal(basic_[0], Primitive::kPrimInt);
+  HInstruction* load2 = new (&allocator_) HLoadLocal(basic_[0], Primitive::kPrimInt);
   ifFalse->AddInstruction(load2);
-  HInstruction* inc2 = new (&allocator_)
-        HAdd(Primitive::kPrimInt, load2, constant1_);
+  HInstruction* inc2 = new (&allocator_) HAdd(Primitive::kPrimInt, load2, constant1_);
   ifFalse->AddInstruction(inc2);
   ifFalse->AddInstruction(new (&allocator_) HStoreLocal(induc_, inc2));
   // Merge over a phi.
   HInstruction* store = InsertArrayStore(induc_, 0);
   PerformInductionVarAnalysis();
 
-  EXPECT_STREQ(
-      "((2:Constant) * i + ((1:Constant) + (2:Constant)))",
-      iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
+  EXPECT_STREQ("((1) * i + ((0) + (1)))", GetInductionInfo(store->InputAt(1), 0).c_str());
 }
 
 TEST_F(InductionVarAnalysisTest, FindFirstOrderWrapAroundInduction) {
   // Setup:
   // k = 0;
   // for (int i = 0; i < 100; i++) {
-  //    a[k] = 0;
-  //    k = 100 - i;
+  //   a[k] = 0;
+  //   k = 100 - i;
   // }
   BuildLoopNest(1);
   HInstruction* store = InsertArrayStore(induc_, 0);
   HInstruction *sub = InsertInstruction(
-      new (&allocator_) HSub(
-          Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
+      new (&allocator_) HSub(Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
   InsertLocalStore(induc_, sub, 0);
   PerformInductionVarAnalysis();
 
-  EXPECT_STREQ(
-      "wrap((1:Constant), "
-      "(( - (2:Constant)) * i + ((3:Constant) - (1:Constant))))",
-      iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
+  EXPECT_STREQ("wrap((0), (( - (1)) * i + ((100) - (0))))",
+               GetInductionInfo(store->InputAt(1), 0).c_str());
 }
 
 TEST_F(InductionVarAnalysisTest, FindSecondOrderWrapAroundInduction) {
@@ -453,23 +377,149 @@
   // k = 0;
   // t = 100;
   // for (int i = 0; i < 100; i++) {
-  //    a[k] = 0;
-  //    k = t;
-  //    t = 100 - i;
+  //   a[k] = 0;
+  //   k = t;
+  //   t = 100 - i;
   // }
   BuildLoopNest(1);
   HInstruction* store = InsertArrayStore(induc_, 0);
   InsertLocalStore(induc_, InsertLocalLoad(tmp_, 0), 0);
   HInstruction *sub = InsertInstruction(
-       new (&allocator_) HSub(
-           Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
+       new (&allocator_) HSub(Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
   InsertLocalStore(tmp_, sub, 0);
   PerformInductionVarAnalysis();
 
-  EXPECT_STREQ(
-      "wrap((1:Constant), wrap((3:Constant), "
-      "(( - (2:Constant)) * i + ((3:Constant) - (1:Constant)))))",
-      iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
+  EXPECT_STREQ("wrap((0), wrap((100), (( - (1)) * i + ((100) - (0)))))",
+               GetInductionInfo(store->InputAt(1), 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindWrapAroundDerivedInduction) {
+  // Setup:
+  // k = 0;
+  // for (int i = 0; i < 100; i++) {
+  //   t = k + 100;
+  //   t = k - 100;
+  //   t = k * 100;
+  //   t = k << 1;
+  //   t = - k;
+  //   k = i << 1;
+  // }
+  BuildLoopNest(1);
+  HInstruction *add = InsertInstruction(
+      new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+  InsertLocalStore(tmp_, add, 0);
+  HInstruction *sub = InsertInstruction(
+       new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+  InsertLocalStore(tmp_, sub, 0);
+  HInstruction *mul = InsertInstruction(
+       new (&allocator_) HMul(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+  InsertLocalStore(tmp_, mul, 0);
+  HInstruction *shl = InsertInstruction(
+       new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
+  InsertLocalStore(tmp_, shl, 0);
+  HInstruction *neg = InsertInstruction(
+       new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
+  InsertLocalStore(tmp_, neg, 0);
+  InsertLocalStore(
+      induc_,
+      InsertInstruction(
+          new (&allocator_)
+          HShl(Primitive::kPrimInt, InsertLocalLoad(basic_[0], 0), constant1_), 0), 0);
+  PerformInductionVarAnalysis();
+
+  EXPECT_STREQ("wrap(((0) + (100)), (((1) * (2)) * i + (((0) * (2)) + (100))))",
+               GetInductionInfo(add, 0).c_str());
+  EXPECT_STREQ("wrap(((0) - (100)), (((1) * (2)) * i + (((0) * (2)) - (100))))",
+               GetInductionInfo(sub, 0).c_str());
+  EXPECT_STREQ("wrap(((0) * (100)), ((((1) * (2)) * (100)) * i + (((0) * (2)) * (100))))",
+               GetInductionInfo(mul, 0).c_str());
+  EXPECT_STREQ("wrap(((0) * (2)), ((((1) * (2)) * (2)) * i + (((0) * (2)) * (2))))",
+               GetInductionInfo(shl, 0).c_str());
+  EXPECT_STREQ("wrap(( - (0)), (( - ((1) * (2))) * i + ( - ((0) * (2)))))",
+               GetInductionInfo(neg, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindPeriodicInduction) {
+  // Setup:
+  // k = 0;
+  // t = 100;
+  // for (int i = 0; i < 100; i++) {
+  //   a[k] = 0;
+  //   a[t] = 0;
+  //   // Swap t <-> k.
+  //   d = t;
+  //   t = k;
+  //   k = d;
+  // }
+  BuildLoopNest(1);
+  HInstruction* store1 = InsertArrayStore(induc_, 0);
+  HInstruction* store2 = InsertArrayStore(tmp_, 0);
+  InsertLocalStore(dum_, InsertLocalLoad(tmp_, 0), 0);
+  InsertLocalStore(tmp_, InsertLocalLoad(induc_, 0), 0);
+  InsertLocalStore(induc_, InsertLocalLoad(dum_, 0), 0);
+  PerformInductionVarAnalysis();
+
+  EXPECT_STREQ("periodic((0), (100))", GetInductionInfo(store1->InputAt(1), 0).c_str());
+  EXPECT_STREQ("periodic((100), (0))", GetInductionInfo(store2->InputAt(1), 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindIdiomaticPeriodicInduction) {
+  // Setup:
+  // k = 0;
+  // for (int i = 0; i < 100; i++) {
+  //   a[k] = 0;
+  //   k = 1 - k;
+  // }
+  BuildLoopNest(1);
+  HInstruction* store = InsertArrayStore(induc_, 0);
+  HInstruction *sub = InsertInstruction(
+         new (&allocator_) HSub(Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 0)), 0);
+  InsertLocalStore(induc_, sub, 0);
+  PerformInductionVarAnalysis();
+
+  EXPECT_STREQ("periodic((0), ((1) - (0)))", GetInductionInfo(store->InputAt(1), 0).c_str());
+  EXPECT_STREQ("periodic(((1) - (0)), (0))", GetInductionInfo(sub, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) {
+  // Setup:
+  // k = 0;
+  // for (int i = 0; i < 100; i++) {
+  //   k = 1 - k;
+  //   t = k + 100;
+  //   t = k - 100;
+  //   t = k * 100;
+  //   t = k << 1;
+  //   t = - k;
+  // }
+  BuildLoopNest(1);
+  InsertLocalStore(
+      induc_,
+      InsertInstruction(new (&allocator_)
+                        HSub(Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 0)), 0), 0);
+  // Derived expressions.
+  HInstruction *add = InsertInstruction(
+       new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+  InsertLocalStore(tmp_, add, 0);
+  HInstruction *sub = InsertInstruction(
+       new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+  InsertLocalStore(tmp_, sub, 0);
+  HInstruction *mul = InsertInstruction(
+       new (&allocator_) HMul(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+  InsertLocalStore(tmp_, mul, 0);
+  HInstruction *shl = InsertInstruction(
+       new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
+  InsertLocalStore(tmp_, shl, 0);
+  HInstruction *neg = InsertInstruction(
+       new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
+  InsertLocalStore(tmp_, neg, 0);
+  PerformInductionVarAnalysis();
+
+  EXPECT_STREQ("periodic((((1) - (0)) + (100)), ((0) + (100)))", GetInductionInfo(add, 0).c_str());
+  EXPECT_STREQ("periodic((((1) - (0)) - (100)), ((0) - (100)))", GetInductionInfo(sub, 0).c_str());
+  EXPECT_STREQ("periodic((((1) - (0)) * (100)), ((0) * (100)))", GetInductionInfo(mul, 0).c_str());
+  EXPECT_STREQ("periodic((((1) - (0)) * (2)), ((0) * (2)))", GetInductionInfo(shl, 0).c_str());
+  EXPECT_STREQ("periodic(( - ((1) - (0))), ( - (0)))", GetInductionInfo(neg, 0).c_str());
 }
 
 TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) {
@@ -485,29 +535,22 @@
   // }
   BuildLoopNest(10);
   HInstruction *inc = InsertInstruction(
-      new (&allocator_) HAdd(
-          Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 9)), 9);
+      new (&allocator_) HAdd(Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 9)), 9);
   InsertLocalStore(induc_, inc, 9);
   HInstruction* store = InsertArrayStore(induc_, 9);
   PerformInductionVarAnalysis();
 
-  // Match exact number of constants, but be less strict on phi number,
-  // since that depends on the SSA building phase.
-  std::regex r("\\(\\(2:Constant\\) \\* i \\+ "
-               "\\(\\(2:Constant\\) \\+ \\(\\d+:Phi\\)\\)\\)");
+  // Avoid exact phi number, since that depends on the SSA building phase.
+  std::regex r("\\(\\(1\\) \\* i \\+ "
+               "\\(\\(1\\) \\+ \\(\\d+:Phi\\)\\)\\)");
 
   for (int d = 0; d < 10; d++) {
     if (d == 9) {
-      EXPECT_TRUE(std::regex_match(
-          iva_->InductionToString(GetLoopInfo(d), store->InputAt(1)), r));
+      EXPECT_TRUE(std::regex_match(GetInductionInfo(store->InputAt(1), d), r));
     } else {
-      EXPECT_STREQ(
-          "",
-          iva_->InductionToString(GetLoopInfo(d), store->InputAt(1)).c_str());
+      EXPECT_STREQ("", GetInductionInfo(store->InputAt(1), d).c_str());
     }
-    EXPECT_STREQ(
-        "((2:Constant) * i + ((1:Constant) + (2:Constant)))",
-        iva_->InductionToString(GetLoopInfo(d), increment_[d]).c_str());
+    EXPECT_STREQ("((1) * i + ((0) + (1)))", GetInductionInfo(increment_[d], d).c_str());
   }
 }