diff --git a/compiler/dex/dataflow_iterator-inl.h b/compiler/dex/dataflow_iterator-inl.h
index 83dfc28..e9402e3 100644
--- a/compiler/dex/dataflow_iterator-inl.h
+++ b/compiler/dex/dataflow_iterator-inl.h
@@ -181,10 +181,16 @@
     idx_ += 1;
     BasicBlock* bb = mir_graph_->GetBasicBlock((*block_id_list_)[idx]);
     DCHECK(bb != nullptr);
+    if ((*loop_ends_)[idx] != 0u) {
+      // If bb->visited is false, the loop needs to be processed from scratch.
+      // Otherwise we mark it as recalculating; for a natural loop we will not
+      // need to recalculate any block in the loop anyway, and for unnatural
+      // loops we will recalculate the loop head only if one of its predecessors
+      // actually changes.
+      bool recalculating = bb->visited;
+      loop_head_stack_->push_back(std::make_pair(idx, recalculating));
+    }
     if (!bb->visited) {
-      if ((*loop_ends_)[idx] != 0u) {
-        loop_head_stack_->push_back(std::make_pair(idx, false));  // Not recalculating.
-      }
       return bb;
     }
   }
diff --git a/compiler/dex/mir_graph_test.cc b/compiler/dex/mir_graph_test.cc
index b3ad040..49b7511 100644
--- a/compiler/dex/mir_graph_test.cc
+++ b/compiler/dex/mir_graph_test.cc
@@ -15,6 +15,7 @@
  */
 
 #include "compiler_ir.h"
+#include "dataflow_iterator-inl.h"
 #include "mir_graph.h"
 #include "gtest/gtest.h"
 
@@ -374,4 +375,72 @@
   CheckLoopEnds(loop_ends);
 }
 
+TEST_F(TopologicalSortOrderTest, UnnaturalLoops) {
+  const BBDef bbs[] = {
+      DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
+      DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
+      DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(10)),
+      DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED1(1)),
+      DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED2(11, 3)),  // Unnatural loop head (top-level).
+      DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED2(3, 4)),
+      DEF_BB(kDalvikByteCode, DEF_SUCC2(9, 7), DEF_PRED1(5)),
+      DEF_BB(kDalvikByteCode, DEF_SUCC1(8), DEF_PRED1(6)),
+      DEF_BB(kDalvikByteCode, DEF_SUCC1(9), DEF_PRED2(10, 7)),  // Unnatural loop head (nested).
+      DEF_BB(kDalvikByteCode, DEF_SUCC1(10), DEF_PRED2(6, 8)),
+      DEF_BB(kDalvikByteCode, DEF_SUCC2(8, 11), DEF_PRED1(9)),
+      DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 2), DEF_PRED1(10)),
+  };
+  const BasicBlockId expected_order[] = {
+      1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 2
+  };
+  const uint16_t loop_ends[] = {
+      0, 0, 10, 0, 0, 0, 9, 0, 0, 0, 0,
+  };
+
+  PrepareBasicBlocks(bbs);
+  ComputeTopologicalSortOrder();
+  CheckOrder(expected_order);
+  CheckLoopEnds(loop_ends);
+
+  const std::pair<BasicBlockId, bool> expected_and_change[] = {
+      { 1, false },
+      { 3, false },
+      { 4, true },    // Initial run of the outer loop.
+      { 5, true },
+      { 6, true },
+      { 7, true },
+      { 8, true },    // Initial run of the inner loop.
+      { 9, true },
+      { 10, true },
+      { 8, true },    // Recalculation of the inner loop - changed.
+      { 9, true },
+      { 10, true },
+      { 8, false },   // Recalculation of the inner loop - unchanged.
+      { 11, true },
+      { 4, true },    // Recalculation of the outer loop - changed.
+      { 5, true },
+      { 6, true },
+      { 7, false },   // No change: skip inner loop head because inputs are unchanged.
+      { 9, true },
+      { 10, true },
+      { 8, true },    // Recalculation of the inner loop - changed.
+      { 9, true },
+      { 10, true },
+      { 8, false },   // Recalculation of the inner loop - unchanged.
+      { 11, true },
+      { 4, false },   // Recalculation of the outer loop - unchanged.
+      { 2, false },
+  };
+  size_t pos = 0;
+  LoopRepeatingTopologicalSortIterator iter(cu_.mir_graph.get());
+  bool change = false;
+  for (BasicBlock* bb = iter.Next(change); bb != nullptr; bb = iter.Next(change)) {
+    ASSERT_NE(arraysize(expected_and_change), pos);
+    ASSERT_EQ(expected_and_change[pos].first, bb->id) << pos;
+    change = expected_and_change[pos].second;
+    ++pos;
+  }
+  ASSERT_EQ(arraysize(expected_and_change), pos);
+}
+
 }  // namespace art
diff --git a/compiler/dex/mir_optimization.cc b/compiler/dex/mir_optimization.cc
index 7b1ec39..645511e 100644
--- a/compiler/dex/mir_optimization.cc
+++ b/compiler/dex/mir_optimization.cc
@@ -1790,7 +1790,8 @@
         pred_mask_union |= pred_mask;
       }
     }
-    DCHECK_EQ(((1u << (IsLoopHead(bb->id) ? bb->nesting_depth - 1u: bb->nesting_depth)) - 1u),
+    // DCHECK_EQ() may not hold for unnatural loop heads, so use DCHECK_GE().
+    DCHECK_GE(((1u << (IsLoopHead(bb->id) ? bb->nesting_depth - 1u: bb->nesting_depth)) - 1u),
               pred_mask_union);
     suspend_checks_in_loops &= pred_mask_union;
   }