Induction variable analysis (with unit tests).

Rationale:
Induction variable analysis forms the basis of a wide
variety of compiler optimizations. This implementation
finds induction variables using the elegant SSA-based
algorithm defined by [Gerlek et al.].

Change-Id: I79b8dce33ffb8b283c179699a8dff5bd196f75b2

3 files changed, 1164 insertions, 0 deletions

diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
new file mode 100644
index 0000000000..8aaec6804d
--- /dev/null
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -0,0 +1,479 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "induction_var_analysis.h"
+
+namespace art {
+
+/**
+ * Returns true if instruction is invariant within the given loop.
+ */
+static bool IsLoopInvariant(HLoopInformation* loop, HInstruction* instruction) {
+  HLoopInformation* other_loop = instruction->GetBlock()->GetLoopInformation();
+  if (other_loop != loop) {
+    // If instruction does not occur in same loop, it is invariant
+    // if it appears in an outer loop (including no loop at all).
+    return other_loop == nullptr || loop->IsIn(*other_loop);
+  }
+  return false;
+}
+
+/**
+ * Returns true if instruction is proper entry-phi-operation for given loop
+ * (referred to as mu-operation in Gerlek's paper).
+ */
+static bool IsEntryPhi(HLoopInformation* loop, HInstruction* instruction) {
+  return
+      instruction->IsPhi() &&
+      instruction->InputCount() == 2 &&
+      instruction->GetBlock() == loop->GetHeader();
+}
+
+//
+// Class methods.
+//
+
+HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph)
+    : HOptimization(graph, kInductionPassName),
+      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()) {
+}
+
+void HInductionVarAnalysis::Run() {
+  // Detects sequence variables (generalized induction variables) during an
+  // inner-loop-first traversal of all loops using Gerlek's algorithm.
+  for (HPostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) {
+    HBasicBlock* graph_block = it_graph.Current();
+    if (graph_block->IsLoopHeader()) {
+      VisitLoop(graph_block->GetLoopInformation());
+    }
+  }
+}
+
+void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) {
+  // 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());
+  map_.clear();
+
+  for (HBlocksInLoopIterator it_loop(*loop); !it_loop.Done(); it_loop.Advance()) {
+    HBasicBlock* loop_block = it_loop.Current();
+    CHECK(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())) {
+        VisitNode(loop, instruction);
+      }
+    }
+    for (HInstructionIterator it(loop_block->GetInstructions()); !it.Done(); it.Advance()) {
+      HInstruction* instruction = it.Current();
+      if (!IsVisitedNode(instruction->GetId())) {
+        VisitNode(loop, instruction);
+      }
+    }
+  }
+
+  CHECK(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));
+  stack_.push_back(instruction);
+
+  // Visit all descendants.
+  uint32_t low = d1;
+  for (size_t i = 0, count = instruction->InputCount(); i < count; ++i) {
+    low = std::min(low, VisitDescendant(loop, instruction->InputAt(i)));
+  }
+
+  // Lower or found SCC?
+  if (low < d1) {
+    map_.find(id)->second.depth = low;
+  } else {
+    scc_.clear();
+    cycle_.clear();
+
+    // Pop the stack to build the SCC for classification.
+    while (!stack_.empty()) {
+      HInstruction* x = stack_.back();
+      scc_.push_back(x);
+      stack_.pop_back();
+      map_.find(x->GetId())->second.done = true;
+      if (x == instruction) {
+        break;
+      }
+    }
+
+    // Classify the SCC.
+    if (scc_.size() == 1 && !IsEntryPhi(loop, scc_[0])) {
+      ClassifyTrivial(loop, scc_[0]);
+    } else {
+      ClassifyNonTrivial(loop);
+    }
+
+    scc_.clear();
+    cycle_.clear();
+  }
+}
+
+uint32_t HInductionVarAnalysis::VisitDescendant(HLoopInformation* loop, HInstruction* instruction) {
+  // If the definition is either outside the loop (loop invariant entry value)
+  // or assigned in inner loop (inner exit value), the traversal stops.
+  HLoopInformation* otherLoop = instruction->GetBlock()->GetLoopInformation();
+  if (otherLoop != loop) {
+    return global_depth_;
+  }
+
+  // Inspect descendant node.
+  const int id = instruction->GetId();
+  if (!IsVisitedNode(id)) {
+    VisitNode(loop, instruction);
+    return map_.find(id)->second.depth;
+  } else {
+    auto it = map_.find(id);
+    return it->second.done ? global_depth_ : it->second.depth;
+  }
+}
+
+void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) {
+  InductionInfo* info = nullptr;
+  if (instruction->IsPhi()) {
+    for (size_t i = 1, count = instruction->InputCount(); i < count; i++) {
+      info = TransferPhi(LookupInfo(loop, instruction->InputAt(0)),
+                         LookupInfo(loop, instruction->InputAt(i)));
+    }
+  } else if (instruction->IsAdd()) {
+    info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
+                          LookupInfo(loop, instruction->InputAt(1)), kAdd);
+  } else if (instruction->IsSub()) {
+    info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
+                          LookupInfo(loop, instruction->InputAt(1)), kSub);
+  } else if (instruction->IsMul()) {
+    info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
+                       LookupInfo(loop, instruction->InputAt(1)));
+  } else if (instruction->IsNeg()) {
+    info = TransferNeg(LookupInfo(loop, instruction->InputAt(0)));
+  }
+
+  // Successfully classified?
+  if (info != nullptr) {
+    AssignInfo(loop, instruction, info);
+  }
+}
+
+void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
+  const size_t size = scc_.size();
+  CHECK_GE(size, 1u);
+  HInstruction* phi = scc_[size - 1];
+  if (!IsEntryPhi(loop, phi)) {
+    return;
+  }
+  HInstruction* external = phi->InputAt(0);
+  HInstruction* internal = phi->InputAt(1);
+  InductionInfo* initial = LookupInfo(loop, external);
+  if (initial == nullptr || initial->induction_class != kInvariant) {
+    return;
+  }
+
+  // Singleton entry-phi-operation may be a wrap-around induction.
+  if (size == 1) {
+    InductionInfo* update = LookupInfo(loop, internal);
+    if (update != nullptr) {
+      AssignInfo(loop, phi, NewInductionInfo(kWrapAround, kNop, initial, update, nullptr));
+    }
+    return;
+  }
+
+  // Inspect remainder of the cycle that resides in scc_. The cycle_ mapping assigns
+  // temporary meaning to its nodes.
+  cycle_.Overwrite(phi->GetId(), nullptr);
+  for (size_t i = 0; i < size - 1; i++) {
+    HInstruction* operation = 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 (update == nullptr) {
+      return;
+    }
+    cycle_.Overwrite(operation->GetId(), 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]);
+    }
+  }
+}
+
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(InductionInfo* a,
+                                                                         InductionInfo* b) {
+  // Transfer over a phi: if both inputs are identical, result is input.
+  if (InductionEqual(a, b)) {
+    return a;
+  }
+  return nullptr;
+}
+
+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.
+  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);
+    } 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 nullptr;
+}
+
+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.
+  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 nullptr;
+}
+
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a) {
+  // Transfer over a unary negation: invariant or linear input
+  // yields a similar, but negated 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 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());
+  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)) {
+        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);
+        }
+        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;
+    }
+  }
+  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);
+}
+
+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);
+  }
+  return info;
+}
+
+bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1,
+                                           InductionInfo* info2) {
+  // Test structural equality only, without accounting for simplifications.
+  if (info1 != nullptr && info2 != nullptr) {
+    return
+        info1->induction_class == info2->induction_class &&
+        info1->operation       == info2->operation       &&
+        info1->fetch           == info2->fetch           &&
+        InductionEqual(info1->op_a, info2->op_a)         &&
+        InductionEqual(info1->op_b, info2->op_b);
+  }
+  // Otherwise only two nullptrs are considered equal.
+  return info1 == info2;
+}
+
+std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) {
+  if (info != nullptr) {
+    if (info->induction_class == kInvariant) {
+      std::string inv = "(";
+      inv += InductionToString(info->op_a);
+      switch (info->operation) {
+        case kNop: inv += " ? "; break;
+        case kAdd: inv += " + "; break;
+        case kSub:
+        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();
+          break;
+      }
+      inv += InductionToString(info->op_b);
+      return inv + ")";
+    } else {
+      CHECK(info->operation == kNop);
+      if (info->induction_class == kLinear) {
+        return "(" + InductionToString(info->op_a) + " * i + " +
+                     InductionToString(info->op_b) + ")";
+      } else if (info->induction_class == kWrapAround) {
+        return "wrap(" + InductionToString(info->op_a) + ", " +
+                         InductionToString(info->op_b) + ")";
+      } else if (info->induction_class == kPeriodic) {
+        return "periodic(" + InductionToString(info->op_a) + ", " +
+                             InductionToString(info->op_b) + ")";
+      }
+    }
+  }
+  return "";
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
new file mode 100644
index 0000000000..09a0a380a1
--- /dev/null
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -0,0 +1,171 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
+#define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
+
+#include <string>
+
+#include "nodes.h"
+#include "optimization.h"
+
+namespace art {
+
+/**
+ * Induction variable analysis.
+ *
+ * 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).
+ */
+class HInductionVarAnalysis : public HOptimization {
+ 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:
+  static constexpr const char* kInductionPassName = "induction_var_analysis";
+
+  struct NodeInfo {
+    explicit NodeInfo(uint32_t d) : depth(d), done(false) {}
+    uint32_t depth;
+    bool done;
+  };
+
+  enum InductionClass {
+    kNone,
+    kInvariant,
+    kLinear,
+    kWrapAround,
+    kPeriodic,
+    kMonotonic
+  };
+
+  enum InductionOp {
+    kNop,  // no-operation: a true induction
+    kAdd,
+    kSub,
+    kNeg,
+    kMul,
+    kDiv,
+    kFetch
+  };
+
+  /**
+   * Defines a detected induction as:
+   *   (1) invariant:
+   *         operation: a + b, a - b, -b, a * b, a / b
+   *       or
+   *         fetch: fetch from HIR
+   *   (2) linear:
+   *         nop: a * i + b
+   *   (3) wrap-around
+   *         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,
+                  InductionOp op,
+                  InductionInfo* a,
+                  InductionInfo* b,
+                  HInstruction* f)
+        : induction_class(ic),
+          operation(op),
+          op_a(a),
+          op_b(b),
+          fetch(f) {}
+    InductionClass induction_class;
+    InductionOp operation;
+    InductionInfo* op_a;
+    InductionInfo* op_b;
+    HInstruction* fetch;
+  };
+
+  inline bool IsVisitedNode(int id) const {
+    return map_.find(id) != 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);
+  }
+
+  // Methods for analysis.
+  void VisitLoop(HLoopInformation* loop);
+  void VisitNode(HLoopInformation* loop, HInstruction* instruction);
+  uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction);
+  void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction);
+  void ClassifyNonTrivial(HLoopInformation* loop);
+
+  // Transfer operations.
+  InductionInfo* TransferPhi(InductionInfo* a, InductionInfo* b);
+  InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
+  InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
+  InductionInfo* TransferNeg(InductionInfo* a);
+  InductionInfo* TransferCycleOverPhi(HInstruction* phi);
+  InductionInfo* TransferCycleOverAddSub(HLoopInformation* loop,
+                                         HInstruction* x,
+                                         HInstruction* y,
+                                         InductionOp op,
+                                         bool first);
+
+  // 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
+
+  uint32_t global_depth_;
+
+  ArenaVector<HInstruction*> stack_;
+  ArenaVector<HInstruction*> scc_;
+
+  // Mappings of instruction id to node and induction information.
+  ArenaSafeMap<int, NodeInfo> map_;
+  ArenaSafeMap<int, InductionInfo*> cycle_;
+
+  // Mapping from loop id to mapping of instruction id to induction information.
+  ArenaSafeMap<int, ArenaSafeMap<int, InductionInfo*>> induction_;
+
+  DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
new file mode 100644
index 0000000000..2093e3355d
--- /dev/null
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -0,0 +1,514 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <regex>
+
+#include "base/arena_allocator.h"
+#include "builder.h"
+#include "gtest/gtest.h"
+#include "induction_var_analysis.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+
+namespace art {
+
+/**
+ * Fixture class for the InductionVarAnalysis tests.
+ */
+class InductionVarAnalysisTest : public testing::Test {
+ public:
+  InductionVarAnalysisTest() : pool_(), allocator_(&pool_) {
+    graph_ = CreateGraph(&allocator_);
+  }
+
+  ~InductionVarAnalysisTest() { }
+
+  // Builds single for-loop at depth d.
+  void BuildForLoop(int d, int n) {
+    ASSERT_LT(d, n);
+    loop_preheader_[d] = new (&allocator_) HBasicBlock(graph_);
+    graph_->AddBlock(loop_preheader_[d]);
+    loop_header_[d] = new (&allocator_) HBasicBlock(graph_);
+    graph_->AddBlock(loop_header_[d]);
+    loop_preheader_[d]->AddSuccessor(loop_header_[d]);
+    if (d < (n - 1)) {
+      BuildForLoop(d + 1, n);
+    }
+    loop_body_[d] = new (&allocator_) HBasicBlock(graph_);
+    graph_->AddBlock(loop_body_[d]);
+    loop_body_[d]->AddSuccessor(loop_header_[d]);
+    if (d < (n - 1)) {
+      loop_header_[d]->AddSuccessor(loop_preheader_[d + 1]);
+      loop_header_[d + 1]->AddSuccessor(loop_body_[d]);
+    } else {
+      loop_header_[d]->AddSuccessor(loop_body_[d]);
+    }
+  }
+
+  // Builds a n-nested loop in CFG where each loop at depth 0 <= d < n
+  // is defined as "for (int i_d = 0; i_d < 100; i_d++)". Tests can further
+  // populate the loop with instructions to set up interesting scenarios.
+  void BuildLoopNest(int n) {
+    ASSERT_LE(n, 10);
+    graph_->SetNumberOfVRegs(n + 2);
+
+    // Build basic blocks with entry, nested loop, exit.
+    entry_ = new (&allocator_) HBasicBlock(graph_);
+    graph_->AddBlock(entry_);
+    BuildForLoop(0, n);
+    exit_ = new (&allocator_) HBasicBlock(graph_);
+    graph_->AddBlock(exit_);
+    entry_->AddSuccessor(loop_preheader_[0]);
+    loop_header_[0]->AddSuccessor(exit_);
+    graph_->SetEntryBlock(entry_);
+    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);
+    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());
+    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_));
+
+    // 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_header_[d]->AddInstruction(load);
+      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_);
+      loop_body_[d]->AddInstruction(increment_[d]);
+      loop_body_[d]->AddInstruction(
+               new (&allocator_) HStoreLocal(basic_[d], increment_[d]));
+      loop_body_[d]->AddInstruction(new (&allocator_) HGoto());
+    }
+  }
+
+  // Builds if-statement at depth d.
+  void BuildIf(int d, HBasicBlock** ifT, HBasicBlock **ifF) {
+    HBasicBlock* cond = new (&allocator_) HBasicBlock(graph_);
+    HBasicBlock* ifTrue = new (&allocator_) HBasicBlock(graph_);
+    HBasicBlock* ifFalse = new (&allocator_) HBasicBlock(graph_);
+    graph_->AddBlock(cond);
+    graph_->AddBlock(ifTrue);
+    graph_->AddBlock(ifFalse);
+    // Conditional split.
+    loop_header_[d]->ReplaceSuccessor(loop_body_[d], cond);
+    cond->AddSuccessor(ifTrue);
+    cond->AddSuccessor(ifFalse);
+    ifTrue->AddSuccessor(loop_body_[d]);
+    ifFalse->AddSuccessor(loop_body_[d]);
+    cond->AddInstruction(new (&allocator_) HIf(parameter_));
+    *ifT = ifTrue;
+    *ifF = ifFalse;
+  }
+
+  // Inserts instruction right before increment at depth d.
+  HInstruction* InsertInstruction(HInstruction* instruction, int d) {
+    loop_body_[d]->InsertInstructionBefore(instruction, increment_[d]);
+    return instruction;
+  }
+
+  // Inserts local load at depth d.
+  HInstruction* InsertLocalLoad(HLocal* local, int d) {
+    return InsertInstruction(
+        new (&allocator_) HLoadLocal(local, Primitive::kPrimInt), d);
+  }
+
+  // Inserts local store at depth d.
+  HInstruction* InsertLocalStore(HLocal* local, HInstruction* rhs, int d) {
+    return InsertInstruction(new (&allocator_) HStoreLocal(local, rhs), d);
+  }
+
+  // Inserts an array store with given local as subscript at depth d to
+  // enable tests to inspect the computed induction at that point easily.
+  HInstruction* InsertArrayStore(HLocal* subscript, int d) {
+    HInstruction* load = InsertInstruction(
+        new (&allocator_) HLoadLocal(subscript, Primitive::kPrimInt), d);
+    return InsertInstruction(new (&allocator_) HArraySet(
+        parameter_, load, constant0_, Primitive::kPrimInt, 0), d);
+  }
+
+  // Returns loop information of loop at depth d.
+  HLoopInformation* GetLoopInfo(int d) {
+    return loop_body_[d]->GetLoopInformation();
+  }
+
+  // Performs InductionVarAnalysis (after proper set up).
+  void PerformInductionVarAnalysis() {
+    ASSERT_TRUE(graph_->TryBuildingSsa());
+    iva_ = new (&allocator_) HInductionVarAnalysis(graph_);
+    iva_->Run();
+  }
+
+  // General building fields.
+  ArenaPool pool_;
+  ArenaAllocator allocator_;
+  HGraph* graph_;
+  HInductionVarAnalysis* iva_;
+
+  // Fixed basic blocks and instructions.
+  HBasicBlock* entry_;
+  HBasicBlock* exit_;
+  HInstruction* parameter_;  // "this"
+  HInstruction* constant0_;
+  HInstruction* constant1_;
+  HInstruction* constant100_;
+  HLocal* induc_;  // "vreg_n", the "k"
+  HLocal* tmp_;    // "vreg_n+1"
+
+  // Loop specifics.
+  HBasicBlock* loop_preheader_[10];
+  HBasicBlock* loop_header_[10];
+  HBasicBlock* loop_body_[10];
+  HInstruction* increment_[10];
+  HLocal* basic_[10];  // "vreg_d", the "i_d"
+};
+
+//
+// The actual InductionVarAnalysis tests.
+//
+
+TEST_F(InductionVarAnalysisTest, ProperLoopSetup) {
+  // Setup:
+  // for (int i_0 = 0; i_0 < 100; i_0++) {
+  //   ..
+  //     for (int i_9 = 0; i_9 < 100; i_9++) {
+  //     }
+  //   ..
+  // }
+  BuildLoopNest(10);
+  ASSERT_TRUE(graph_->TryBuildingSsa());
+  ASSERT_EQ(entry_->GetLoopInformation(), nullptr);
+  for (int d = 0; d < 1; d++) {
+    ASSERT_EQ(loop_preheader_[d]->GetLoopInformation(),
+              (d == 0) ? nullptr
+                       : loop_header_[d - 1]->GetLoopInformation());
+    ASSERT_NE(loop_header_[d]->GetLoopInformation(), nullptr);
+    ASSERT_NE(loop_body_[d]->GetLoopInformation(), nullptr);
+    ASSERT_EQ(loop_header_[d]->GetLoopInformation(),
+              loop_body_[d]->GetLoopInformation());
+  }
+  ASSERT_EQ(exit_->GetLoopInformation(), nullptr);
+}
+
+TEST_F(InductionVarAnalysisTest, FindBasicInductionVar) {
+  // Setup:
+  // for (int i = 0; i < 100; i++) {
+  //    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());
+}
+
+TEST_F(InductionVarAnalysisTest, FindDerivedInductionVarAdd) {
+  // Setup:
+  // for (int i = 0; i < 100; i++) {
+  //    k = 100 + i;
+  //    a[k] = 0;
+  // }
+  BuildLoopNest(1);
+  HInstruction *add = InsertInstruction(
+      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);
+  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);
+  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 *neg = InsertInstruction(
+      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());
+}
+
+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;
+  // }
+  BuildLoopNest(1);
+  HInstruction *add = InsertInstruction(
+      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);
+  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());
+}
+
+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;
+  // }
+  BuildLoopNest(1);
+  HBasicBlock* ifTrue;
+  HBasicBlock* ifFalse;
+  BuildIf(0, &ifTrue, &ifFalse);
+  // True-branch.
+  HInstruction* load1 = new (&allocator_)
+      HLoadLocal(induc_, Primitive::kPrimInt);
+  ifTrue->AddInstruction(load1);
+  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);
+  ifFalse->AddInstruction(load2);
+  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());
+}
+
+TEST_F(InductionVarAnalysisTest, FindTwoWayDerivedInduction) {
+  // Setup:
+  // for (int i = 0; i < 100; i++) {
+  //    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);
+  ifTrue->AddInstruction(load1);
+  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);
+  ifFalse->AddInstruction(load2);
+  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());
+}
+
+TEST_F(InductionVarAnalysisTest, FindFirstOrderWrapAroundInduction) {
+  // Setup:
+  // k = 0;
+  // for (int i = 0; i < 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);
+  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());
+}
+
+TEST_F(InductionVarAnalysisTest, FindSecondOrderWrapAroundInduction) {
+  // Setup:
+  // k = 0;
+  // t = 100;
+  // for (int i = 0; i < 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);
+  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());
+}
+
+TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) {
+  // Setup:
+  // k = 0;
+  // for (int i_0 = 0; i_0 < 100; i_0++) {
+  //   ..
+  //     for (int i_9 = 0; i_9 < 100; i_9++) {
+  //       k = 1 + k;
+  //       a[k] = 0;
+  //     }
+  //   ..
+  // }
+  BuildLoopNest(10);
+  HInstruction *inc = InsertInstruction(
+      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\\)\\)\\)");
+
+  for (int d = 0; d < 10; d++) {
+    if (d == 9) {
+      EXPECT_TRUE(std::regex_match(
+          iva_->InductionToString(GetLoopInfo(d), store->InputAt(1)), r));
+    } else {
+      EXPECT_STREQ(
+          "",
+          iva_->InductionToString(GetLoopInfo(d), store->InputAt(1)).c_str());
+    }
+    EXPECT_STREQ(
+        "((2:Constant) * i + ((1:Constant) + (2:Constant)))",
+        iva_->InductionToString(GetLoopInfo(d), increment_[d]).c_str());
+  }
+}
+
+}  // namespace art