diff --git a/compiler/Android.bp b/compiler/Android.bp
index 7fb009a..2556178 100644
--- a/compiler/Android.bp
+++ b/compiler/Android.bp
@@ -63,6 +63,7 @@
         "optimizing/licm.cc",
         "optimizing/load_store_elimination.cc",
         "optimizing/locations.cc",
+        "optimizing/loop_optimization.cc",
         "optimizing/nodes.cc",
         "optimizing/optimization.cc",
         "optimizing/optimizing_compiler.cc",
@@ -318,6 +319,7 @@
         "optimizing/induction_var_range_test.cc",
         "optimizing/licm_test.cc",
         "optimizing/live_interval_test.cc",
+        "optimizing/loop_optimization_test.cc",
         "optimizing/nodes_test.cc",
         "optimizing/parallel_move_test.cc",
         "optimizing/pretty_printer_test.cc",
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
new file mode 100644
index 0000000..7dfa4f1
--- /dev/null
+++ b/compiler/optimizing/loop_optimization.cc
@@ -0,0 +1,317 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "loop_optimization.h"
+
+#include "base/arena_containers.h"
+#include "induction_var_range.h"
+#include "ssa_liveness_analysis.h"
+#include "nodes.h"
+
+namespace art {
+
+// TODO: Generalize to cycles, as found by induction analysis?
+static bool IsPhiAddSub(HPhi* phi, /*out*/ HInstruction** addsub_out) {
+  HInputsRef inputs = phi->GetInputs();
+  if (inputs.size() == 2 && (inputs[1]->IsAdd() || inputs[1]->IsSub())) {
+    HInstruction* addsub = inputs[1];
+    if (addsub->InputAt(0) == phi || addsub->InputAt(1) == phi) {
+      if (addsub->GetUses().HasExactlyOneElement()) {
+        *addsub_out = addsub;
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+static bool IsOnlyUsedAfterLoop(const HLoopInformation& loop_info,
+                                HPhi* phi, HInstruction* addsub) {
+  for (const HUseListNode<HInstruction*>& use : phi->GetUses()) {
+    if (use.GetUser() != addsub) {
+      HLoopInformation* other_loop_info = use.GetUser()->GetBlock()->GetLoopInformation();
+      if (other_loop_info != nullptr && other_loop_info->IsIn(loop_info)) {
+        return false;
+      }
+    }
+  }
+  return true;
+}
+
+// Find: phi: Phi(init, addsub)
+//       s:   SuspendCheck
+//       c:   Condition(phi, bound)
+//       i:   If(c)
+// TODO: Find a less pattern matching approach?
+static bool IsEmptyHeader(HBasicBlock* block, /*out*/ HInstruction** addsub) {
+  HInstruction* phi = block->GetFirstPhi();
+  if (phi != nullptr && phi->GetNext() == nullptr && IsPhiAddSub(phi->AsPhi(), addsub)) {
+    HInstruction* s = block->GetFirstInstruction();
+    if (s != nullptr && s->IsSuspendCheck()) {
+      HInstruction* c = s->GetNext();
+      if (c != nullptr && c->IsCondition() && c->GetUses().HasExactlyOneElement()) {
+        HInstruction* i = c->GetNext();
+        if (i != nullptr && i->IsIf() && i->InputAt(0) == c) {
+          // Check that phi is only used inside loop as expected.
+          for (const HUseListNode<HInstruction*>& use : phi->GetUses()) {
+            if (use.GetUser() != *addsub && use.GetUser() != c) {
+              return false;
+            }
+          }
+          return true;
+        }
+      }
+    }
+  }
+  return false;
+}
+
+static bool IsEmptyBody(HBasicBlock* block, HInstruction* addsub) {
+  HInstruction* phi = block->GetFirstPhi();
+  HInstruction* i = block->GetFirstInstruction();
+  return phi == nullptr && i == addsub && i->GetNext() != nullptr && i->GetNext()->IsGoto();
+}
+
+static HBasicBlock* TryRemovePreHeader(HBasicBlock* preheader, HBasicBlock* entry_block) {
+  if (preheader->GetPredecessors().size() == 1) {
+    HBasicBlock* entry = preheader->GetSinglePredecessor();
+    HInstruction* anchor = entry->GetLastInstruction();
+    // If the pre-header has a single predecessor we can remove it too if
+    // either the pre-header just contains a goto, or if the predecessor
+    // is not the entry block so we can push instructions backward
+    // (moving computation into the entry block is too dangerous!).
+    if (preheader->GetFirstInstruction() == nullptr ||
+        preheader->GetFirstInstruction()->IsGoto() ||
+        (entry != entry_block && anchor->IsGoto())) {
+      // Push non-goto statements backward to empty the pre-header.
+      for (HInstructionIterator it(preheader->GetInstructions()); !it.Done(); it.Advance()) {
+        HInstruction* instruction = it.Current();
+        if (!instruction->IsGoto()) {
+          if (!instruction->CanBeMoved()) {
+            return nullptr;  // pushing failed to move all
+          }
+          it.Current()->MoveBefore(anchor);
+        }
+      }
+      return entry;
+    }
+  }
+  return nullptr;
+}
+
+static void RemoveFromCycle(HInstruction* instruction) {
+  // A bit more elaborate than the usual instruction removal,
+  // since there may be a cycle in the use structure.
+  instruction->RemoveAsUserOfAllInputs();
+  instruction->RemoveEnvironmentUsers();
+  instruction->GetBlock()->RemoveInstructionOrPhi(instruction, /*ensure_safety=*/ false);
+}
+
+//
+// Class methods.
+//
+
+HLoopOptimization::HLoopOptimization(HGraph* graph,
+                                     HInductionVarAnalysis* induction_analysis)
+    : HOptimization(graph, kLoopOptimizationPassName),
+      induction_range_(induction_analysis),
+      loop_allocator_(graph_->GetArena()->GetArenaPool()),  // phase-local allocator on global pool
+      top_loop_(nullptr),
+      last_loop_(nullptr) {
+}
+
+void HLoopOptimization::Run() {
+  // Well-behaved loops only.
+  // TODO: make this less of a sledgehammer.
+  if (graph_-> HasTryCatch() || graph_->HasIrreducibleLoops()) {
+    return;
+  }
+
+  // Build the linear order. This step enables building a loop hierarchy that
+  // properly reflects the outer-inner and previous-next relation.
+  graph_->Linearize();
+  // Build the loop hierarchy.
+  for (HLinearOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) {
+    HBasicBlock* block = it_graph.Current();
+    if (block->IsLoopHeader()) {
+      AddLoop(block->GetLoopInformation());
+    }
+  }
+  if (top_loop_ == nullptr) {
+    return;  // no loops
+  }
+  // Traverse the loop hierarchy inner-to-outer and optimize.
+  TraverseLoopsInnerToOuter(top_loop_);
+}
+
+void HLoopOptimization::AddLoop(HLoopInformation* loop_info) {
+  DCHECK(loop_info != nullptr);
+  LoopNode* node = new (&loop_allocator_) LoopNode(loop_info);  // phase-local allocator
+  if (last_loop_ == nullptr) {
+    // First loop.
+    DCHECK(top_loop_ == nullptr);
+    last_loop_ = top_loop_ = node;
+  } else if (loop_info->IsIn(*last_loop_->loop_info)) {
+    // Inner loop.
+    node->outer = last_loop_;
+    DCHECK(last_loop_->inner == nullptr);
+    last_loop_ = last_loop_->inner = node;
+  } else {
+    // Subsequent loop.
+    while (last_loop_->outer != nullptr && !loop_info->IsIn(*last_loop_->outer->loop_info)) {
+      last_loop_ = last_loop_->outer;
+    }
+    node->outer = last_loop_->outer;
+    node->previous = last_loop_;
+    DCHECK(last_loop_->next == nullptr);
+    last_loop_ = last_loop_->next = node;
+  }
+}
+
+void HLoopOptimization::RemoveLoop(LoopNode* node) {
+  DCHECK(node != nullptr);
+  // TODO: implement when needed (for current set of optimizations, we don't
+  // need to keep recorded loop hierarchy up to date, but as we get different
+  // traversal, we may want to remove the node from the hierarchy here.
+}
+
+void HLoopOptimization::TraverseLoopsInnerToOuter(LoopNode* node) {
+  for ( ; node != nullptr; node = node->next) {
+    if (node->inner != nullptr) {
+      TraverseLoopsInnerToOuter(node->inner);
+    }
+    // Visit loop after its inner loops have been visited.
+    SimplifyInduction(node);
+    RemoveIfEmptyLoop(node);
+  }
+}
+
+void HLoopOptimization::SimplifyInduction(LoopNode* node) {
+  HBasicBlock* header = node->loop_info->GetHeader();
+  HBasicBlock* preheader = node->loop_info->GetPreHeader();
+  // Scan the phis in the header to find opportunities to optimize induction.
+  for (HInstructionIterator it(header->GetPhis()); !it.Done(); it.Advance()) {
+    HPhi* phi = it.Current()->AsPhi();
+    HInstruction* addsub = nullptr;
+    // Find phi-add/sub cycle.
+    if (IsPhiAddSub(phi, &addsub)) {
+      // Simple case, the induction is only used by itself. Although redundant,
+      // later phases do not easily detect this property. Thus, eliminate here.
+      // Example: for (int i = 0; x != null; i++) { .... no i .... }
+      if (phi->GetUses().HasExactlyOneElement()) {
+        // Remove the cycle, including all uses. Even environment uses can be removed,
+        // since these computations have no effect at all.
+        RemoveFromCycle(phi);  // removes environment uses too
+        RemoveFromCycle(addsub);
+        continue;
+      }
+      // Closed form case. Only the last value of the induction is needed. Remove all
+      // overhead from the loop, and replace subsequent uses with the last value.
+      // Example: for (int i = 0; i < 10; i++, k++) { .... no k .... } return k;
+      if (IsOnlyUsedAfterLoop(*node->loop_info, phi, addsub) &&
+          induction_range_.CanGenerateLastValue(phi)) {
+        HInstruction* last = induction_range_.GenerateLastValue(phi, graph_, preheader);
+        // Remove the cycle, replacing all uses. Even environment uses can consume the final
+        // value, since any first real use is outside the loop (although this may imply
+        // that deopting may look "ahead" a bit on the phi value).
+        ReplaceAllUses(phi, last, addsub);
+        RemoveFromCycle(phi);  // removes environment uses too
+        RemoveFromCycle(addsub);
+      }
+    }
+  }
+}
+
+void HLoopOptimization::RemoveIfEmptyLoop(LoopNode* node) {
+  HBasicBlock* header = node->loop_info->GetHeader();
+  HBasicBlock* preheader = node->loop_info->GetPreHeader();
+  // Ensure there is only a single loop-body (besides the header).
+  HBasicBlock* body = nullptr;
+  for (HBlocksInLoopIterator it(*node->loop_info); !it.Done(); it.Advance()) {
+    if (it.Current() != header) {
+      if (body != nullptr) {
+        return;
+      }
+      body = it.Current();
+    }
+  }
+  // Ensure there is only a single exit point.
+  if (header->GetSuccessors().size() != 2) {
+    return;
+  }
+  HBasicBlock* exit = (header->GetSuccessors()[0] == body)
+      ? header->GetSuccessors()[1]
+      : header->GetSuccessors()[0];
+  // Ensure exit can only be reached by exiting loop (this seems typically the
+  // case anyway, and simplifies code generation below; TODO: perhaps relax?).
+  if (exit->GetPredecessors().size() != 1) {
+    return;
+  }
+  // Detect an empty loop: no side effects other than plain iteration.
+  HInstruction* addsub = nullptr;
+  if (IsEmptyHeader(header, &addsub) && IsEmptyBody(body, addsub)) {
+    HBasicBlock* entry = TryRemovePreHeader(preheader, graph_->GetEntryBlock());
+    body->DisconnectAndDelete();
+    exit->RemovePredecessor(header);
+    header->RemoveSuccessor(exit);
+    header->ClearDominanceInformation();
+    header->SetDominator(preheader);  // needed by next disconnect.
+    header->DisconnectAndDelete();
+    // If allowed, remove preheader too, which may expose next outer empty loop
+    // Otherwise, link preheader directly to exit to restore the flow graph.
+    if (entry != nullptr) {
+      entry->ReplaceSuccessor(preheader, exit);
+      entry->AddDominatedBlock(exit);
+      exit->SetDominator(entry);
+      preheader->DisconnectAndDelete();
+    } else {
+      preheader->AddSuccessor(exit);
+      preheader->AddInstruction(new (graph_->GetArena()) HGoto());  // global allocator
+      preheader->AddDominatedBlock(exit);
+      exit->SetDominator(preheader);
+    }
+    // Update hierarchy.
+    RemoveLoop(node);
+  }
+}
+
+void HLoopOptimization::ReplaceAllUses(HInstruction* instruction,
+                                       HInstruction* replacement,
+                                       HInstruction* exclusion) {
+  const HUseList<HInstruction*>& uses = instruction->GetUses();
+  for (auto it = uses.begin(), end = uses.end(); it != end;) {
+    HInstruction* user = it->GetUser();
+    size_t index = it->GetIndex();
+    ++it;  // increment before replacing
+    if (user != exclusion) {
+      user->ReplaceInput(replacement, index);
+      induction_range_.Replace(user, instruction, replacement);  // update induction
+    }
+  }
+  const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses();
+  for (auto it = env_uses.begin(), end = env_uses.end(); it != end;) {
+    HEnvironment* user = it->GetUser();
+    size_t index = it->GetIndex();
+    ++it;  // increment before replacing
+    if (user->GetHolder() != exclusion) {
+      user->RemoveAsUserOfInput(index);
+      user->SetRawEnvAt(index, replacement);
+      replacement->AddEnvUseAt(user, index);
+    }
+  }
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/loop_optimization.h b/compiler/optimizing/loop_optimization.h
new file mode 100644
index 0000000..e7980ce
--- /dev/null
+++ b/compiler/optimizing/loop_optimization.h
@@ -0,0 +1,88 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_LOOP_OPTIMIZATION_H_
+#define ART_COMPILER_OPTIMIZING_LOOP_OPTIMIZATION_H_
+
+#include <string>
+
+#include "induction_var_range.h"
+#include "nodes.h"
+#include "optimization.h"
+
+namespace art {
+
+/**
+ * Loop optimizations. Builds a loop hierarchy and applies optimizations to
+ * the detected nested loops, such as removal of dead induction and empty loops.
+ */
+class HLoopOptimization : public HOptimization {
+ public:
+  HLoopOptimization(HGraph* graph, HInductionVarAnalysis* induction_analysis);
+
+  void Run() OVERRIDE;
+
+  static constexpr const char* kLoopOptimizationPassName = "loop_optimization";
+
+ private:
+  /**
+   * A single loop inside the loop hierarchy representation.
+   */
+  struct LoopNode : public ArenaObject<kArenaAllocInductionVarAnalysis> {
+    explicit LoopNode(HLoopInformation* lp_info)
+        : loop_info(lp_info),
+          outer(nullptr),
+          inner(nullptr),
+          previous(nullptr),
+          next(nullptr) {}
+    const HLoopInformation* const loop_info;
+    LoopNode* outer;
+    LoopNode* inner;
+    LoopNode* previous;
+    LoopNode* next;
+  };
+
+  void AddLoop(HLoopInformation* loop_info);
+  void RemoveLoop(LoopNode* node);
+
+  void TraverseLoopsInnerToOuter(LoopNode* node);
+
+  void SimplifyInduction(LoopNode* node);
+  void RemoveIfEmptyLoop(LoopNode* node);
+
+  void ReplaceAllUses(HInstruction* instruction,
+                      HInstruction* replacement,
+                      HInstruction* exclusion);
+
+  // Range analysis based on induction variables.
+  InductionVarRange induction_range_;
+
+  // Phase-local heap memory allocator for the loop optimizer. Storage obtained
+  // through this allocator is released when the loop optimizer is done.
+  ArenaAllocator loop_allocator_;
+
+  // Entries into the loop hierarchy representation.
+  LoopNode* top_loop_;
+  LoopNode* last_loop_;
+
+  friend class LoopOptimizationTest;
+
+  DISALLOW_COPY_AND_ASSIGN(HLoopOptimization);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_LOOP_OPTIMIZATION_H_
diff --git a/compiler/optimizing/loop_optimization_test.cc b/compiler/optimizing/loop_optimization_test.cc
new file mode 100644
index 0000000..4e007d4
--- /dev/null
+++ b/compiler/optimizing/loop_optimization_test.cc
@@ -0,0 +1,193 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "loop_optimization.h"
+#include "optimizing_unit_test.h"
+
+namespace art {
+
+/**
+ * Fixture class for the loop optimization tests. These unit tests focus
+ * constructing the loop hierarchy. Actual optimizations are tested
+ * through the checker tests.
+ */
+class LoopOptimizationTest : public CommonCompilerTest {
+ public:
+  LoopOptimizationTest()
+      : pool_(),
+        allocator_(&pool_),
+        graph_(CreateGraph(&allocator_)),
+        iva_(new (&allocator_) HInductionVarAnalysis(graph_)),
+        loop_opt_(new (&allocator_) HLoopOptimization(graph_, iva_)) {
+    BuildGraph();
+  }
+
+  ~LoopOptimizationTest() { }
+
+  /** Constructs bare minimum graph. */
+  void BuildGraph() {
+    graph_->SetNumberOfVRegs(1);
+    entry_block_ = new (&allocator_) HBasicBlock(graph_);
+    return_block_ = new (&allocator_) HBasicBlock(graph_);
+    exit_block_ = new (&allocator_) HBasicBlock(graph_);
+    graph_->AddBlock(entry_block_);
+    graph_->AddBlock(return_block_);
+    graph_->AddBlock(exit_block_);
+    graph_->SetEntryBlock(entry_block_);
+    graph_->SetExitBlock(exit_block_);
+    parameter_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt);
+    entry_block_->AddInstruction(parameter_);
+    return_block_->AddInstruction(new (&allocator_) HReturnVoid());
+    exit_block_->AddInstruction(new (&allocator_) HExit());
+    entry_block_->AddSuccessor(return_block_);
+    return_block_->AddSuccessor(exit_block_);
+  }
+
+  /** Adds a loop nest at given position before successor. */
+  HBasicBlock* AddLoop(HBasicBlock* position, HBasicBlock* successor) {
+    HBasicBlock* header = new (&allocator_) HBasicBlock(graph_);
+    HBasicBlock* body = new (&allocator_) HBasicBlock(graph_);
+    graph_->AddBlock(header);
+    graph_->AddBlock(body);
+    // Control flow.
+    position->ReplaceSuccessor(successor, header);
+    header->AddSuccessor(body);
+    header->AddSuccessor(successor);
+    header->AddInstruction(new (&allocator_) HIf(parameter_));
+    body->AddSuccessor(header);
+    body->AddInstruction(new (&allocator_) HGoto());
+    return header;
+  }
+
+  /** Performs analysis. */
+  void PerformAnalysis() {
+    graph_->BuildDominatorTree();
+    iva_->Run();
+    loop_opt_->Run();
+  }
+
+  /** Constructs string representation of computed loop hierarchy. */
+  std::string LoopStructure() {
+    return LoopStructureRecurse(loop_opt_->top_loop_);
+  }
+
+  // Helper method
+  std::string LoopStructureRecurse(HLoopOptimization::LoopNode* node) {
+    std::string s;
+    for ( ; node != nullptr; node = node->next) {
+      s.append("[");
+      s.append(LoopStructureRecurse(node->inner));
+      s.append("]");
+    }
+    return s;
+  }
+
+  // General building fields.
+  ArenaPool pool_;
+  ArenaAllocator allocator_;
+  HGraph* graph_;
+  HInductionVarAnalysis* iva_;
+  HLoopOptimization* loop_opt_;
+
+  HBasicBlock* entry_block_;
+  HBasicBlock* return_block_;
+  HBasicBlock* exit_block_;
+
+  HInstruction* parameter_;
+};
+
+//
+// The actual tests.
+//
+
+TEST_F(LoopOptimizationTest, NoLoops) {
+  PerformAnalysis();
+  EXPECT_EQ("", LoopStructure());
+}
+
+TEST_F(LoopOptimizationTest, SingleLoop) {
+  AddLoop(entry_block_, return_block_);
+  PerformAnalysis();
+  EXPECT_EQ("[]", LoopStructure());
+}
+
+TEST_F(LoopOptimizationTest, LoopNest10) {
+  HBasicBlock* b = entry_block_;
+  HBasicBlock* s = return_block_;
+  for (int i = 0; i < 10; i++) {
+    s = AddLoop(b, s);
+    b = s->GetSuccessors()[0];
+  }
+  PerformAnalysis();
+  EXPECT_EQ("[[[[[[[[[[]]]]]]]]]]", LoopStructure());
+}
+
+TEST_F(LoopOptimizationTest, LoopSequence10) {
+  HBasicBlock* b = entry_block_;
+  HBasicBlock* s = return_block_;
+  for (int i = 0; i < 10; i++) {
+    b = AddLoop(b, s);
+    s = b->GetSuccessors()[1];
+  }
+  PerformAnalysis();
+  EXPECT_EQ("[][][][][][][][][][]", LoopStructure());
+}
+
+TEST_F(LoopOptimizationTest, LoopSequenceOfNests) {
+  HBasicBlock* b = entry_block_;
+  HBasicBlock* s = return_block_;
+  for (int i = 0; i < 10; i++) {
+    b = AddLoop(b, s);
+    s = b->GetSuccessors()[1];
+    HBasicBlock* bi = b->GetSuccessors()[0];
+    HBasicBlock* si = b;
+    for (int j = 0; j < i; j++) {
+      si = AddLoop(bi, si);
+      bi = si->GetSuccessors()[0];
+    }
+  }
+  PerformAnalysis();
+  EXPECT_EQ("[]"
+            "[[]]"
+            "[[[]]]"
+            "[[[[]]]]"
+            "[[[[[]]]]]"
+            "[[[[[[]]]]]]"
+            "[[[[[[[]]]]]]]"
+            "[[[[[[[[]]]]]]]]"
+            "[[[[[[[[[]]]]]]]]]"
+            "[[[[[[[[[[]]]]]]]]]]",
+            LoopStructure());
+}
+
+TEST_F(LoopOptimizationTest, LoopNestWithSequence) {
+  HBasicBlock* b = entry_block_;
+  HBasicBlock* s = return_block_;
+  for (int i = 0; i < 10; i++) {
+    s = AddLoop(b, s);
+    b = s->GetSuccessors()[0];
+  }
+  b = s;
+  s = b->GetSuccessors()[1];
+  for (int i = 0; i < 9; i++) {
+    b = AddLoop(b, s);
+    s = b->GetSuccessors()[1];
+  }
+  PerformAnalysis();
+  EXPECT_EQ("[[[[[[[[[[][][][][][][][][][]]]]]]]]]]", LoopStructure());
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index ef9bf23..f1ca928 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -522,7 +522,10 @@
   return true;
 }
 
+// TODO: return order, and give only liveness analysis ownership of graph's linear_order_?
 void HGraph::Linearize() {
+  linear_order_.clear();
+
   // Create a reverse post ordering with the following properties:
   // - Blocks in a loop are consecutive,
   // - Back-edge is the last block before loop exits.
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 397abde..b0e61e6 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -366,8 +366,8 @@
   // is a throw-catch loop, i.e. the header is a catch block.
   GraphAnalysisResult AnalyzeLoops() const;
 
-  // Computes the linear order (should be called before using HLinearOrderIterator).
-  // Linearizes the graph such that:
+  // Computes a linear order for the current graph (should be called before
+  // using HLinearOrderIterator). Linearizes the graph such that:
   // (1): a block is always after its dominator,
   // (2): blocks of loops are contiguous.
   // This creates a natural and efficient ordering when visualizing live ranges.
@@ -586,7 +586,8 @@
   // List of blocks to perform a reverse post order tree traversal.
   ArenaVector<HBasicBlock*> reverse_post_order_;
 
-  // List of blocks to perform a linear order tree traversal.
+  // List of blocks to perform a linear order tree traversal. Unlike the reverse
+  // post order, this order is not incrementally kept up-to-date.
   ArenaVector<HBasicBlock*> linear_order_;
 
   HBasicBlock* entry_block_;
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index d3a55dd..c2fe1b1 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -76,6 +76,7 @@
 #include "jni/quick/jni_compiler.h"
 #include "licm.h"
 #include "load_store_elimination.h"
+#include "loop_optimization.h"
 #include "nodes.h"
 #include "oat_quick_method_header.h"
 #include "prepare_for_register_allocation.h"
@@ -737,6 +738,7 @@
   LoadStoreElimination* lse = new (arena) LoadStoreElimination(graph, *side_effects);
   HInductionVarAnalysis* induction = new (arena) HInductionVarAnalysis(graph);
   BoundsCheckElimination* bce = new (arena) BoundsCheckElimination(graph, *side_effects, induction);
+  HLoopOptimization* loop = new (arena) HLoopOptimization(graph, induction);
   HSharpening* sharpening = new (arena) HSharpening(graph, codegen, dex_compilation_unit, driver);
   InstructionSimplifier* simplify2 = new (arena) InstructionSimplifier(
       graph, stats, "instruction_simplifier$after_bce");
@@ -765,6 +767,7 @@
     licm,
     induction,
     bce,
+    loop,
     fold3,  // evaluates code generated by dynamic bce
     simplify2,
     lse,
diff --git a/test/482-checker-loop-back-edge-use/src/Main.java b/test/482-checker-loop-back-edge-use/src/Main.java
index f8f0aa3..65dfd41 100644
--- a/test/482-checker-loop-back-edge-use/src/Main.java
+++ b/test/482-checker-loop-back-edge-use/src/Main.java
@@ -115,7 +115,9 @@
     // 'incoming' must have a use only at the first loop's back edge.
     for (long i = System.nanoTime(); i < 42; ++i) {
       System.out.println(incoming);
-      for (long j = System.currentTimeMillis(); j != 42; ++j) {}
+      for (long j = System.currentTimeMillis(); j != 42; ++j) {
+        System.out.print(j);  // non-empty body
+      }
     }
   }
 
diff --git a/test/618-checker-induction/expected.txt b/test/618-checker-induction/expected.txt
new file mode 100644
index 0000000..b0aad4d
--- /dev/null
+++ b/test/618-checker-induction/expected.txt
@@ -0,0 +1 @@
+passed
diff --git a/test/618-checker-induction/info.txt b/test/618-checker-induction/info.txt
new file mode 100644
index 0000000..0c5ea55
--- /dev/null
+++ b/test/618-checker-induction/info.txt
@@ -0,0 +1 @@
+Test on loop optimizations on induction.
diff --git a/test/618-checker-induction/src/Main.java b/test/618-checker-induction/src/Main.java
new file mode 100644
index 0000000..a68c383
--- /dev/null
+++ b/test/618-checker-induction/src/Main.java
@@ -0,0 +1,422 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/**
+ * Tests on loop optimizations related to induction.
+ */
+public class Main {
+
+  static int[] a = new int[10];
+
+  /// CHECK-START: void Main.deadSingleLoop() loop_optimization (before)
+  /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
+  //
+  /// CHECK-START: void Main.deadSingleLoop() loop_optimization (after)
+  /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
+  static void deadSingleLoop() {
+    for (int i = 0; i < 4; i++) {
+    }
+  }
+
+  /// CHECK-START: void Main.deadNestedLoops() loop_optimization (before)
+  /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: Phi loop:{{B\d+}}      outer_loop:<<Loop>>
+  //
+  /// CHECK-START: void Main.deadNestedLoops() loop_optimization (after)
+  /// CHECK-NOT: Phi loop:{{B\d+}}
+  static void deadNestedLoops() {
+    for (int i = 0; i < 4; i++) {
+      for (int j = 0; j < 4; j++) {
+      }
+    }
+  }
+
+  /// CHECK-START: void Main.deadNestedAndFollowingLoops() loop_optimization (before)
+  /// CHECK-DAG: Phi loop:<<Loop1:B\d+>> outer_loop:none
+  /// CHECK-DAG: Phi loop:<<Loop2:B\d+>> outer_loop:<<Loop1>>
+  /// CHECK-DAG: Phi loop:{{B\d+}}       outer_loop:<<Loop2>>
+  /// CHECK-DAG: Phi loop:{{B\d+}}       outer_loop:<<Loop2>>
+  /// CHECK-DAG: Phi loop:<<Loop3:B\d+>> outer_loop:<<Loop1>>
+  /// CHECK-DAG: Phi loop:{{B\d+}}       outer_loop:<<Loop3>>
+  /// CHECK-DAG: Phi loop:{{B\d+}}       outer_loop:none
+  //
+  /// CHECK-START: void Main.deadNestedAndFollowingLoops() loop_optimization (after)
+  /// CHECK-NOT: Phi loop:{{B\d+}}
+  static void deadNestedAndFollowingLoops() {
+    for (int i = 0; i < 4; i++) {
+      for (int j = 0; j < 4; j++) {
+        for (int k = 0; k < 4; k++) {
+        }
+        for (int k = 0; k < 4; k++) {
+        }
+      }
+      for (int j = 0; j < 4; j++) {
+        for (int k = 0; k < 4; k++) {
+        }
+      }
+    }
+    for (int i = 0; i < 4; i++) {
+    }
+  }
+
+  /// CHECK-START: void Main.deadInduction() loop_optimization (before)
+  /// CHECK-DAG: Phi      loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: Phi      loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG: ArraySet loop:<<Loop>>      outer_loop:none
+  //
+  /// CHECK-START: void Main.deadInduction() loop_optimization (after)
+  /// CHECK-DAG: Phi      loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-NOT: Phi      loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG: ArraySet loop:<<Loop>>      outer_loop:none
+  static void deadInduction() {
+    int dead = 0;
+    for (int i = 0; i < a.length; i++) {
+      a[i] = 1;
+      dead += 5;
+    }
+  }
+
+  /// CHECK-START: void Main.deadManyInduction() loop_optimization (before)
+  /// CHECK-DAG: Phi      loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: Phi      loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG: Phi      loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG: Phi      loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG: ArraySet loop:<<Loop>>      outer_loop:none
+  //
+  /// CHECK-START: void Main.deadManyInduction() loop_optimization (after)
+  /// CHECK-DAG: Phi      loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-NOT: Phi      loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG: ArraySet loop:<<Loop>>      outer_loop:none
+  static void deadManyInduction() {
+    int dead1 = 0, dead2 = 1, dead3 = 3;
+    for (int i = 0; i < a.length; i++) {
+      dead1 += 5;
+      a[i] = 2;
+      dead2 += 10;
+      dead3 += 100;
+    }
+  }
+
+  /// CHECK-START: void Main.deadSequence() loop_optimization (before)
+  /// CHECK-DAG: Phi      loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: Phi      loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG: ArraySet loop:<<Loop>>      outer_loop:none
+  //
+  /// CHECK-START: void Main.deadSequence() loop_optimization (after)
+  /// CHECK-DAG: Phi      loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-NOT: Phi      loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG: ArraySet loop:<<Loop>>      outer_loop:none
+  static void deadSequence() {
+    int dead = 0;
+    for (int i = 0; i < a.length; i++) {
+      a[i] = 3;
+      // Increment value defined inside loop,
+      // but sequence itself not used anywhere.
+      dead += i;
+    }
+  }
+
+  /// CHECK-START: void Main.deadCycleWithException(int) loop_optimization (before)
+  /// CHECK-DAG: Phi      loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: Phi      loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG: ArraySet loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG: ArrayGet loop:<<Loop>>      outer_loop:none
+  //
+  /// CHECK-START: void Main.deadCycleWithException(int) loop_optimization (after)
+  /// CHECK-DAG: Phi      loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-NOT: Phi      loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG: ArraySet loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG: ArrayGet loop:<<Loop>>      outer_loop:none
+  static void deadCycleWithException(int k) {
+    int dead = 0;
+    for (int i = 0; i < a.length; i++) {
+      a[i] = 4;
+      // Increment value of dead cycle may throw exception.
+      dead += a[k];
+    }
+  }
+
+  /// CHECK-START: int Main.closedFormInductionUp() loop_optimization (before)
+  /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG:               Return [<<Phi1>>] loop:none
+  //
+  /// CHECK-START: int Main.closedFormInductionUp() loop_optimization (after)
+  /// CHECK-NOT:               Phi    loop:B\d+ outer_loop:none
+  /// CHECK-DAG:               Return loop:none
+  static int closedFormInductionUp() {
+    int closed = 12345;
+    for (int i = 0; i < 10; i++) {
+      closed += 5;
+    }
+    return closed;  // only needs last value
+  }
+
+  /// CHECK-START: int Main.closedFormInductionInAndDown(int) loop_optimization (before)
+  /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG:               Return [<<Phi2>>] loop:none
+  //
+  /// CHECK-START: int Main.closedFormInductionInAndDown(int) loop_optimization (after)
+  /// CHECK-NOT:               Phi    loop:B\d+ outer_loop:none
+  /// CHECK-DAG:               Return loop:none
+  static int closedFormInductionInAndDown(int closed) {
+    for (int i = 0; i < 10; i++) {
+      closed -= 5;
+    }
+    return closed;  // only needs last value
+  }
+
+  // TODO: taken test around closed form?
+  static int closedFormInductionUpN(int n) {
+    int closed = 12345;
+    for (int i = 0; i < n; i++) {
+      closed += 5;
+    }
+    return closed;  // only needs last value
+  }
+
+  // TODO: taken test around closed form?
+  static int closedFormInductionInAndDownN(int closed, int n) {
+    for (int i = 0; i < n; i++) {
+      closed -= 5;
+    }
+    return closed;  // only needs last value
+  }
+
+  // TODO: move closed form even further out?
+  static int closedFormNested(int n) {
+    int closed = 0;
+    for (int i = 0; i < n; i++) {
+      for (int j = 0; j < 10; j++) {
+        closed++;
+      }
+    }
+    return closed;  // only needs last-value
+  }
+
+  // TODO: handle as closed/empty eventually?
+  static int mainIndexReturned(int n) {
+    int i;
+    for (i = 0; i < n; i++);
+    return i;
+  }
+
+  // If ever replaced by closed form, last value should be correct!
+  static int periodicReturned(int n) {
+    int k = 0;
+    for (int i = 0; i < n; i++) {
+      k = 1 - k;
+    }
+    return k;
+  }
+
+  // Same here.
+  private static int getSum(int n) {
+    int k = 0;
+    int sum = 0;
+    for (int i = 0; i < n; i++) {
+      k++;
+      sum += k;
+    }
+    return sum;
+  }
+
+  // Same here.
+  private static int getSum21() {
+    int k = 0;
+    int sum = 0;
+    for (int i = 0; i < 6; i++) {
+      k++;
+      sum += k;
+    }
+    return sum;
+  }
+
+  // Same here.
+  private static int closedTwice() {
+    int closed = 0;
+    for (int i = 0; i < 10; i++) {
+      closed++;
+    }
+    // Closed form of first loop defines trip count of second loop.
+    int other_closed = 0;
+    for (int i = 0; i < closed; i++) {
+      other_closed++;
+    }
+    return other_closed;
+  }
+
+  /// CHECK-START: int Main.closedFeed() loop_optimization (before)
+  /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop1:B\d+>> outer_loop:none
+  /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop1>>      outer_loop:none
+  /// CHECK-DAG: <<Phi3:i\d+>> Phi               loop:<<Loop2:B\d+>> outer_loop:none
+  /// CHECK-DAG: <<Phi4:i\d+>> Phi               loop:<<Loop2>>      outer_loop:none
+  /// CHECK-DAG:               Return [<<Phi3>>] loop:none
+  /// CHECK-EVAL: "<<Loop1>>" != "<<Loop2>>"
+  //
+  /// CHECK-START: int Main.closedFeed() loop_optimization (after)
+  /// CHECK-NOT:               Phi    loop:B\d+ outer_loop:none
+  /// CHECK-DAG:               Return loop:none
+  private static int closedFeed() {
+    int closed = 0;
+    for (int i = 0; i < 10; i++) {
+      closed++;
+    }
+    // Closed form of first loop feeds into initial value of second loop,
+    // used when generating closed form for the latter.
+    for (int i = 0; i < 10; i++) {
+      closed++;
+    }
+    return closed;
+  }
+
+  /// CHECK-START: int Main.closedLargeUp() loop_optimization (before)
+  /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG:               Return [<<Phi1>>] loop:none
+  //
+  /// CHECK-START: int Main.closedLargeUp() loop_optimization (after)
+  /// CHECK-NOT:               Phi    loop:B\d+ outer_loop:none
+  /// CHECK-DAG:               Return loop:none
+  private static int closedLargeUp() {
+    int closed = 0;
+    for (int i = 0; i < 10; i++) {
+      closed += 0x7fffffff;
+    }
+    return closed;
+  }
+
+  /// CHECK-START: int Main.closedLargeDown() loop_optimization (before)
+  /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
+  /// CHECK-DAG:               Return [<<Phi1>>] loop:none
+  //
+  /// CHECK-START: int Main.closedLargeDown() loop_optimization (after)
+  /// CHECK-NOT:               Phi    loop:B\d+ outer_loop:none
+  /// CHECK-DAG:               Return loop:none
+  private static int closedLargeDown() {
+    int closed = 0;
+    for (int i = 0; i < 10; i++) {
+      closed -= 0x7fffffff;
+    }
+    return closed;
+  }
+
+  private static int exceptionExitBeforeAdd() {
+    int k = 0;
+    try {
+      for (int i = 0; i < 10; i++) {
+        a[i] = 0;
+        k += 10;  // increment last
+      }
+    } catch(Exception e) {
+      // Flag error by returning current
+      // value of k negated.
+      return -k-1;
+    }
+    return k;
+  }
+
+  private static int exceptionExitAfterAdd() {
+    int k = 0;
+    try {
+      for (int i = 0; i < 10; i++) {
+        k += 10;  // increment first
+        a[i] = 0;
+      }
+    } catch(Exception e) {
+      // Flag error by returning current
+      // value of k negated.
+      return -k-1;
+    }
+    return k;
+  }
+
+  public static void main(String[] args) {
+    deadSingleLoop();
+    deadNestedLoops();
+    deadNestedAndFollowingLoops();
+
+    deadInduction();
+    for (int i = 0; i < a.length; i++) {
+      expectEquals(1, a[i]);
+    }
+    deadManyInduction();
+    for (int i = 0; i < a.length; i++) {
+      expectEquals(2, a[i]);
+    }
+    deadSequence();
+    for (int i = 0; i < a.length; i++) {
+      expectEquals(3, a[i]);
+    }
+    try {
+      deadCycleWithException(-1);
+      throw new Error("Expected: IOOB exception");
+    } catch (IndexOutOfBoundsException e) {
+    }
+    for (int i = 0; i < a.length; i++) {
+      expectEquals(i == 0 ? 4 : 3, a[i]);
+    }
+    deadCycleWithException(0);
+    for (int i = 0; i < a.length; i++) {
+      expectEquals(4, a[i]);
+    }
+
+    int c = closedFormInductionUp();
+    expectEquals(12395, c);
+    c = closedFormInductionInAndDown(12345);
+    expectEquals(12295, c);
+    for (int n = -4; n < 10; n++) {
+      int tc = (n <= 0) ? 0 : n;
+      c = closedFormInductionUpN(n);
+      expectEquals(12345 + tc * 5, c);
+      c = closedFormInductionInAndDownN(12345, n);
+      expectEquals(12345 - tc * 5, c);
+      c = closedFormNested(n);
+      expectEquals(tc * 10, c);
+    }
+
+    for (int n = -4; n < 4; n++) {
+      int tc = (n <= 0) ? 0 : n;
+      expectEquals(tc, mainIndexReturned(n));
+      expectEquals(tc & 1, periodicReturned(n));
+      expectEquals((tc * (tc + 1)) / 2, getSum(n));
+    }
+    expectEquals(21, getSum21());
+    expectEquals(10, closedTwice());
+    expectEquals(20, closedFeed());
+    expectEquals(-10, closedLargeUp());
+    expectEquals(10, closedLargeDown());
+
+    expectEquals(100, exceptionExitBeforeAdd());
+    expectEquals(100, exceptionExitAfterAdd());
+    a = null;
+    expectEquals(-1, exceptionExitBeforeAdd());
+    expectEquals(-11, exceptionExitAfterAdd());
+    a = new int[4];
+    expectEquals(-41, exceptionExitBeforeAdd());
+    expectEquals(-51, exceptionExitAfterAdd());
+
+    System.out.println("passed");
+  }
+
+  private static void expectEquals(int expected, int result) {
+    if (expected != result) {
+      throw new Error("Expected: " + expected + ", found: " + result);
+    }
+  }
+}