Index: include/llvm/Support/GenericDomTreeConstruction.h
===================================================================
--- include/llvm/Support/GenericDomTreeConstruction.h
+++ include/llvm/Support/GenericDomTreeConstruction.h
@@ -700,9 +700,17 @@
       return;
 
     // Recalculate the set of roots.
-    auto Roots = FindRoots(DT, BUI);
-    if (DT.Roots.size() != Roots.size() ||
-        !std::is_permutation(DT.Roots.begin(), DT.Roots.end(), Roots.begin())) {
+    RootsT Roots = FindRoots(DT, BUI);
+    bool Same = DT.Roots.size() == Roots.size();
+    if (Same) {
+      SmallPtrSet<NodePtr, 4> RootSet(Roots.begin(), Roots.end());
+      for (const NodePtr N : DT.Roots)
+        if (!RootSet.count(N)) {
+          Same = false;
+          break;
+        }
+    }
+    if (!Same) {
       // The roots chosen in the CFG have changed. This is because the
       // incremental algorithm does not really know or use the set of roots and
       // can make a different (implicit) decision about which node within an
@@ -713,7 +721,6 @@
       // It may be possible to update the tree without recalculating it, but
       // we do not know yet how to do it, and it happens rarely in practise.
       CalculateFromScratch(DT, BUI);
-      return;
     }
   }
 
@@ -1258,9 +1265,15 @@
     }
 
     RootsT ComputedRoots = FindRoots(DT, nullptr);
-    if (DT.Roots.size() != ComputedRoots.size() ||
-        !std::is_permutation(DT.Roots.begin(), DT.Roots.end(),
-                             ComputedRoots.begin())) {
+    bool Same = DT.Roots.size() == ComputedRoots.size();
+    if (Same) {
+      SmallPtrSet<NodePtr, 4> RootSet(ComputedRoots.begin(),
+                                      ComputedRoots.end());
+      for (const NodePtr N : DT.Roots)
+        if (!RootSet.count(N))
+          Same = false;
+    }
+    if (!Same) {
       errs() << "Tree has different roots than freshly computed ones!\n";
       errs() << "\tPDT roots: ";
       for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", ";