Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
===================================================================
--- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -9545,10 +9545,13 @@
   }
 
   if (TM.getOptLevel() != CodeGenOpt::None) {
-    // Order cases by probability so the most likely case will be checked first.
-    std::sort(W.FirstCluster, W.LastCluster + 1,
+	// Here, we order cases by probability so the most likely case will be
+	// checked first. However, two clusters can have the same probability in
+	// which case their relative ordering is non-deterministic. So we use Low
+	// as a tie-breaker as clusters are guaranteed to never overlap.
+	std::sort(W.FirstCluster, W.LastCluster + 1,
               [](const CaseCluster &a, const CaseCluster &b) {
-      return a.Prob > b.Prob;
+      return a.Prob != b.Prob ? a.Prob > b.Prob : a.Low < b.Low;
     });
 
     // Rearrange the case blocks so that the last one falls through if possible