diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 40dab74..1141fd1 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -1003,6 +1003,15 @@
 
   void AddBackEdgeUses(const HBasicBlock& block_at_use) {
     DCHECK(block_at_use.IsInLoop());
+    if (block_at_use.GetGraph()->HasIrreducibleLoops()) {
+      // Linear order may not be well formed when irreducible loops are present,
+      // i.e. loop blocks may not be adjacent and a back edge may not be last,
+      // which violates assumptions made in this method.
+      return;
+    }
+
+    DCHECK(IsLinearOrderWellFormed(*block_at_use.GetGraph()));
+
     // Add synthesized uses at the back edge of loops to help the register allocator.
     // Note that this method is called in decreasing liveness order, to faciliate adding
     // uses at the head of the `first_use_` linked list. Because below
@@ -1027,30 +1036,12 @@
       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.
-        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()));
-          }
-        }
+        DCHECK(HasSynthesizeUseAt(back_edge_use_position));
         break;
       }
 
-      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;
-      }
+      DCHECK(last_in_new_list == nullptr ||
+             back_edge_use_position > last_in_new_list->GetPosition());
 
       UsePosition* new_use = new (allocator_) UsePosition(
           /* user */ nullptr,
diff --git a/test/594-checker-irreducible-linorder/smali/IrreducibleLoop.smali b/test/594-checker-irreducible-linorder/smali/IrreducibleLoop.smali
index 366c7b9..ef53ee8 100644
--- a/test/594-checker-irreducible-linorder/smali/IrreducibleLoop.smali
+++ b/test/594-checker-irreducible-linorder/smali/IrreducibleLoop.smali
@@ -67,3 +67,57 @@
    return p3
 
 .end method
+
+## CHECK-START: int IrreducibleLoop.liveness2(boolean, boolean, boolean, int) builder (after)
+## CHECK-DAG:     Mul loop:<<Loop:B\d+>>
+## CHECK-DAG:     Not loop:<<Loop>>
+
+## CHECK-START: int IrreducibleLoop.liveness2(boolean, boolean, boolean, int) liveness (after)
+## CHECK-DAG:     Mul liveness:<<LPreEntry2:\d+>>
+## CHECK-DAG:     Not liveness:<<LBackEdge1:\d+>>
+## CHECK-EVAL:    <<LBackEdge1>> < <<LPreEntry2>>
+
+.method public liveness2(ZZZI)I
+    .registers 10
+
+    const v1, 1
+
+    :header1
+    if-eqz p0, :body1
+
+    :exit
+    return p3
+
+    :body1
+    # The test will generate an incorrect linear order when the following IF swaps
+    # its successors. To do that, load a boolean value and compare NotEqual to 1.
+    sget-boolean v2, LIrreducibleLoop;->f:Z
+    const v3, 1
+    if-ne v2, v3, :pre_header2
+
+    :pre_entry2
+    # This constant has a use in a phi in :back_edge2 and a back edge use in
+    # :back_edge1. Because the linear order is wrong, the back edge use has
+    # a lower liveness than the phi use.
+    const v0, 42
+    mul-int/2addr p3, p3
+    goto :back_edge2
+
+    :back_edge2
+    add-int/2addr p3, v0
+    add-int/2addr v0, v1
+    goto :header2
+
+    :header2
+    if-eqz p2, :back_edge2
+
+    :back_edge1
+    not-int p3, p3
+    goto :header1
+
+    :pre_header2
+    const v0, 42
+    goto :header2
+.end method
+
+.field public static f:Z