diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 97f2aee..719feec 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -969,6 +969,38 @@
     return false;
   }
 
+  bool IsLinearOrderWellFormed(const HGraph& graph) {
+    for (HBasicBlock* header : graph.GetBlocks()) {
+      if (!header->IsLoopHeader()) {
+        continue;
+      }
+
+      HLoopInformation* loop = header->GetLoopInformation();
+      size_t num_blocks = loop->GetBlocks().NumSetBits();
+      size_t found_blocks = 0u;
+
+      for (HLinearOrderIterator it(graph); !it.Done(); it.Advance()) {
+        HBasicBlock* current = it.Current();
+        if (loop->Contains(*current)) {
+          found_blocks++;
+          if (found_blocks == 1u && current != header) {
+            // First block is not the header.
+            return false;
+          } else if (found_blocks == num_blocks && !loop->IsBackEdge(*current)) {
+            // Last block is not a back edge.
+            return false;
+          }
+        } else if (found_blocks != 0u && found_blocks != num_blocks) {
+          // Blocks are not adjacent.
+          return false;
+        }
+      }
+      DCHECK_EQ(found_blocks, num_blocks);
+    }
+
+    return true;
+  }
+
   void AddBackEdgeUses(const HBasicBlock& block_at_use) {
     DCHECK(block_at_use.IsInLoop());
     // Add synthesized uses at the back edge of loops to help the register allocator.
@@ -995,12 +1027,30 @@
       if ((first_use_ != nullptr) && (first_use_->GetPosition() <= back_edge_use_position)) {
         // There was a use already seen in this loop. Therefore the previous call to `AddUse`
         // already inserted the backedge use. We can stop going outward.
-        DCHECK(HasSynthesizeUseAt(back_edge_use_position));
+        if (kIsDebugBuild) {
+          if (!HasSynthesizeUseAt(back_edge_use_position)) {
+            // There exists a use prior to `back_edge_use_position` but there is
+            // no synthesized use at the back edge. This can happen in the presence
+            // of irreducible loops, when blocks of the loop are not adjacent in
+            // linear order, i.e. when there is an out-of-loop block between
+            // `block_at_use` and `back_edge_position` that uses this interval.
+            DCHECK(block_at_use.GetGraph()->HasIrreducibleLoops());
+            DCHECK(!IsLinearOrderWellFormed(*block_at_use.GetGraph()));
+          }
+        }
         break;
       }
 
-      DCHECK(last_in_new_list == nullptr
-             || back_edge_use_position > last_in_new_list->GetPosition());
+      if (last_in_new_list != nullptr &&
+          back_edge_use_position <= last_in_new_list->GetPosition()) {
+        // Loops are not properly nested in the linear order, i.e. the back edge
+        // of an outer loop preceeds blocks of an inner loop. This can happen
+        // in the presence of irreducible loops.
+        DCHECK(block_at_use.GetGraph()->HasIrreducibleLoops());
+        DCHECK(!IsLinearOrderWellFormed(*block_at_use.GetGraph()));
+        // We must bail out, otherwise we would generate an unsorted use list.
+        break;
+      }
 
       UsePosition* new_use = new (allocator_) UsePosition(
           /* user */ nullptr,
diff --git a/test/594-checker-regression-irreducible-linorder/expected.txt b/test/594-checker-regression-irreducible-linorder/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/594-checker-regression-irreducible-linorder/expected.txt
diff --git a/test/594-checker-regression-irreducible-linorder/info.txt b/test/594-checker-regression-irreducible-linorder/info.txt
new file mode 100644
index 0000000..a1783f8
--- /dev/null
+++ b/test/594-checker-regression-irreducible-linorder/info.txt
@@ -0,0 +1,2 @@
+Regression test for a failing DCHECK in SSA liveness analysis in the presence
+of irreducible loops.
diff --git a/test/594-checker-regression-irreducible-linorder/smali/IrreducibleLoop.smali b/test/594-checker-regression-irreducible-linorder/smali/IrreducibleLoop.smali
new file mode 100644
index 0000000..8e01084
--- /dev/null
+++ b/test/594-checker-regression-irreducible-linorder/smali/IrreducibleLoop.smali
@@ -0,0 +1,64 @@
+# 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.
+
+.class public LIrreducibleLoop;
+.super Ljava/lang/Object;
+
+# Test case where liveness analysis produces linear order where loop blocks are
+# not adjacent.
+
+## CHECK-START: int IrreducibleLoop.liveness(boolean, boolean, boolean, int) builder (after)
+## CHECK-DAG:     Add loop:none
+## CHECK-DAG:     Mul loop:<<Loop:B\d+>>
+## CHECK-DAG:     Not loop:<<Loop>>
+
+## CHECK-START: int IrreducibleLoop.liveness(boolean, boolean, boolean, int) liveness (after)
+## CHECK-DAG:     Add liveness:<<LPreEntry:\d+>>
+## CHECK-DAG:     Mul liveness:<<LHeader:\d+>>
+## CHECK-DAG:     Not liveness:<<LBackEdge:\d+>>
+## CHECK-EVAL:    (<<LHeader>> < <<LPreEntry>>) and (<<LPreEntry>> < <<LBackEdge>>)
+
+.method public static liveness(ZZZI)I
+   .registers 10
+   const/16 v0, 42
+
+   if-eqz p0, :header
+
+   :pre_entry
+   add-int/2addr p3, p3
+   invoke-static {v0}, Ljava/lang/System;->exit(I)V
+   goto :body1
+
+   :header
+   mul-int/2addr p3, p3
+   if-eqz p1, :body2
+
+   :body1
+   goto :body_merge
+
+   :body2
+   invoke-static {v0}, Ljava/lang/System;->exit(I)V
+   goto :body_merge
+
+   :body_merge
+   if-eqz p2, :exit
+
+   :back_edge
+   not-int p3, p3
+   goto :header
+
+   :exit
+   return p3
+
+.end method
diff --git a/test/594-checker-regression-irreducible-linorder/src/Main.java b/test/594-checker-regression-irreducible-linorder/src/Main.java
new file mode 100644
index 0000000..38b2ab4
--- /dev/null
+++ b/test/594-checker-regression-irreducible-linorder/src/Main.java
@@ -0,0 +1,25 @@
+/*
+ * 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.
+ */
+
+public class Main {
+  // Workaround for b/18051191.
+  class InnerClass {}
+
+  public static void main(String[] args) {
+    // Nothing to run. This regression test merely makes sure the smali test
+    // case successfully compiles.
+  }
+}