Index: lib/Transforms/Utils/PredicateInfo.cpp
===================================================================
--- lib/Transforms/Utils/PredicateInfo.cpp
+++ lib/Transforms/Utils/PredicateInfo.cpp
@@ -551,6 +551,16 @@
   // Sort OpsToRename since we are going to iterate it.
   SmallVector<Value *, 8> OpsToRename(OpSet.begin(), OpSet.end());
   auto Comparator = [&](const Value *A, const Value *B) {
+    // Order instructions in different basic blocks by their dominator tree
+    // DFSIn number, which guarantees a deterministic ordering and that
+    // dominated instructions come after the instructions that dominate them.
+    const Instruction *InstA = dyn_cast_or_null<Instruction>(A);
+    const Instruction *InstB = dyn_cast_or_null<Instruction>(B);
+    if (InstA && InstB && InstA->getParent() != InstB->getParent()) {
+      DomTreeNode *DA = DT.getNode(InstA->getParent());
+      DomTreeNode *DB = DT.getNode(InstB->getParent());
+      return DA->getDFSNumIn() < DB->getDFSNumIn();
+    }
     return valueComesBefore(OI, A, B);
   };
   llvm::sort(OpsToRename.begin(), OpsToRename.end(), Comparator);