7 files changed, 610 insertions, 3 deletions

diff --git a/compiler/Android.bp b/compiler/Android.bp
index 7fb009adc0..2556178ddf 100644
--- a/compiler/Android.bp
+++ b/compiler/Android.bp
@@ -63,6 +63,7 @@ art_cc_defaults {
         "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 @@ art_cc_test {
         "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 0000000000..7dfa4f160b
--- /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 0000000000..e7980ce89e
--- /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 0000000000..4e007d4e9a
--- /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 ef9bf23a17..f1ca928851 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -522,7 +522,10 @@ static bool IsLinearOrderWellFormed(const HGraph& graph) {
   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 397abded27..b0e61e6efc 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -366,8 +366,8 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
   // 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 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
   // 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 d3a55dd365..c2fe1b144b 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 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph,
   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 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph,
     licm,
     induction,
     bce,
+    loop,
     fold3,  // evaluates code generated by dynamic bce
     simplify2,
     lse,