diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 6703695..cf67e1a 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -206,6 +206,22 @@
   return instruction;
 }
 
+static bool UpdateDominatorOfSuccessor(HBasicBlock* block, HBasicBlock* successor) {
+  DCHECK(ContainsElement(block->GetSuccessors(), successor));
+
+  HBasicBlock* old_dominator = successor->GetDominator();
+  HBasicBlock* new_dominator =
+      (old_dominator == nullptr) ? block
+                                 : CommonDominator::ForPair(old_dominator, block);
+
+  if (old_dominator == new_dominator) {
+    return false;
+  } else {
+    successor->SetDominator(new_dominator);
+    return true;
+  }
+}
+
 void HGraph::ComputeDominanceInformation() {
   DCHECK(reverse_post_order_.empty());
   reverse_post_order_.reserve(blocks_.size());
@@ -228,15 +244,7 @@
       worklist.pop_back();
     } else {
       HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++];
-
-      if (successor->GetDominator() == nullptr) {
-        successor->SetDominator(current);
-      } else {
-        // The CommonDominator can work for multiple blocks as long as the
-        // domination information doesn't change. However, since we're changing
-        // that information here, we can use the finder only for pairs of blocks.
-        successor->SetDominator(CommonDominator::ForPair(successor->GetDominator(), current));
-      }
+      UpdateDominatorOfSuccessor(current, successor);
 
       // Once all the forward edges have been visited, we know the immediate
       // dominator of the block. We can then start visiting its successors.
@@ -248,6 +256,44 @@
     }
   }
 
+  // Check if the graph has back edges not dominated by their respective headers.
+  // If so, we need to update the dominators of those headers and recursively of
+  // their successors. We do that with a fix-point iteration over all blocks.
+  // The algorithm is guaranteed to terminate because it loops only if the sum
+  // of all dominator chains has decreased in the current iteration.
+  bool must_run_fix_point = false;
+  for (HBasicBlock* block : blocks_) {
+    if (block != nullptr &&
+        block->IsLoopHeader() &&
+        block->GetLoopInformation()->HasBackEdgeNotDominatedByHeader()) {
+      must_run_fix_point = true;
+      break;
+    }
+  }
+  if (must_run_fix_point) {
+    bool update_occurred = true;
+    while (update_occurred) {
+      update_occurred = false;
+      for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
+        HBasicBlock* block = it.Current();
+        for (HBasicBlock* successor : block->GetSuccessors()) {
+          update_occurred |= UpdateDominatorOfSuccessor(block, successor);
+        }
+      }
+    }
+  }
+
+  // Make sure that there are no remaining blocks whose dominator information
+  // needs to be updated.
+  if (kIsDebugBuild) {
+    for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
+      HBasicBlock* block = it.Current();
+      for (HBasicBlock* successor : block->GetSuccessors()) {
+        DCHECK(!UpdateDominatorOfSuccessor(block, successor));
+      }
+    }
+  }
+
   // Populate `dominated_blocks_` information after computing all dominators.
   // The potential presence of irreducible loops requires to do it after.
   for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
@@ -595,14 +641,7 @@
   blocks_.SetBit(header_->GetBlockId());
   header_->SetInLoop(this);
 
-  bool is_irreducible_loop = false;
-  for (HBasicBlock* back_edge : GetBackEdges()) {
-    DCHECK(back_edge->GetDominator() != nullptr);
-    if (!header_->Dominates(back_edge)) {
-      is_irreducible_loop = true;
-      break;
-    }
-  }
+  bool is_irreducible_loop = HasBackEdgeNotDominatedByHeader();
 
   if (is_irreducible_loop) {
     ArenaBitVector visited(graph->GetArena(),
@@ -667,6 +706,16 @@
   return last_position;
 }
 
+bool HLoopInformation::HasBackEdgeNotDominatedByHeader() const {
+  for (HBasicBlock* back_edge : GetBackEdges()) {
+    DCHECK(back_edge->GetDominator() != nullptr);
+    if (!header_->Dominates(back_edge)) {
+      return true;
+    }
+  }
+  return false;
+}
+
 bool HBasicBlock::Dominates(HBasicBlock* other) const {
   // Walk up the dominator tree from `other`, to find out if `this`
   // is an ancestor.
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index afb995d..1c0ad6a 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -725,6 +725,8 @@
     blocks_.ClearAllBits();
   }
 
+  bool HasBackEdgeNotDominatedByHeader() const;
+
  private:
   // Internal recursive implementation of `Populate`.
   void PopulateRecursive(HBasicBlock* block);
diff --git a/test/598-checker-irreducible-dominance/expected.txt b/test/598-checker-irreducible-dominance/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/598-checker-irreducible-dominance/expected.txt
diff --git a/test/598-checker-irreducible-dominance/info.txt b/test/598-checker-irreducible-dominance/info.txt
new file mode 100644
index 0000000..8ca4e63
--- /dev/null
+++ b/test/598-checker-irreducible-dominance/info.txt
@@ -0,0 +1,2 @@
+Regression test for HGraphBuilder which would compute wrong dominance information
+in the presence of irreducible loops.
\ No newline at end of file
diff --git a/test/598-checker-irreducible-dominance/smali/IrreducibleLoop.smali b/test/598-checker-irreducible-dominance/smali/IrreducibleLoop.smali
new file mode 100644
index 0000000..4d8b515
--- /dev/null
+++ b/test/598-checker-irreducible-dominance/smali/IrreducibleLoop.smali
@@ -0,0 +1,52 @@
+# 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 in which `inner_back_edge` is not dominated by `inner_header` and
+# causes `outer_back_edge` to not be dominated by `outer_header`. HGraphBuilder
+# not do a fix-point iteration and would miss the path to `outer_back_edge`
+# through `inner_back_edge` and incorrectly label the outer loop non-irreducible.
+
+## CHECK-START: int IrreducibleLoop.dominance(int) builder (after)
+## CHECK:         Add irreducible:true
+
+.method public static dominance(I)I
+    .registers 2
+
+    if-eqz p0, :outer_header
+    goto :inner_back_edge
+
+    :outer_header
+    if-eqz p0, :inner_header
+
+    :outer_branch_exit
+    if-eqz p0, :outer_merge
+    return p0
+
+    :inner_header
+    goto :outer_merge
+
+    :inner_back_edge
+    goto :inner_header
+
+    :outer_merge
+    if-eqz p0, :inner_back_edge
+
+    :outer_back_edge
+    add-int/2addr p0, p0
+    goto :outer_header
+
+.end method
diff --git a/test/598-checker-irreducible-dominance/src/Main.java b/test/598-checker-irreducible-dominance/src/Main.java
new file mode 100644
index 0000000..38b2ab4
--- /dev/null
+++ b/test/598-checker-irreducible-dominance/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.
+  }
+}