[SelectionDAG] Make sorting predicate stronger to remove non-deterministic ordering

[mgrang]

Summary

This fixes failures in the following tests uncovered by D39245:

LLVM :: CodeGen/ARM/ifcvt3.ll
LLVM :: CodeGen/ARM/switch-minsize.ll
LLVM :: CodeGen/X86/switch.ll

[fhahn]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

9551

I might be missing something but could we still end up with multiple clusters where a.Prob == b.Prob && a.Low == b.Low ? Then the order of those nodes would still be non-deterministic, no?

[mgrang]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

9551

@fhahn Thanks! I am not sure if we two clusters can have the same Low. How about I add another predicate a.High < b.High?

The fallback option is to simply change this to use std::stable_sort but I wanted to avoid this if we can simply get by adding stronger predicates.

[hans]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

9551

The CaseClusters can't overlap, so having the same Low should not be possible.

I like this fix. Please expand the "Order cases by probability" comment to explain what's going on here. It would also be nice to have a test for this.

[fhahn]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

9551

The CaseClusters can't overlap, so having the same Low should not be possible

Ok great, thanks for confirming

[mgrang]

Added comment to explain what's going on.

[mgrang]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

9551

I believe writing individual test cases for such scenarios is difficult as well as an overkill.

Once all failures uncovered by shuffling std::sort containers are fixed, I will push patches to change all std:sort to llvm::sort, which will shuffle containers by default in a +asserts build. Once that is done, the existing tests will automatically become test cases to uncover such non-determinism.

[mgrang]

Fixed another instance of non-deterministic ordering causing failure in CodeGen/X86/switch.ll.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

for (unsigned i = First; i <= Last; ++i) {
     CB->Mask |= (-1ULL >> (63 - (Hi - Lo))) << Lo;
     CB->Bits += Hi - Lo + 1;
     CB->ExtraProb += Clusters[i].Prob;
     TotalProb += Clusters[i].Prob;
   }
 
   BitTestInfo BTI;
   std::sort(CBV.begin(), CBV.end(), [](const CaseBits &a, const CaseBits &b) {
-    // Sort by probability first, number of bits second.
+    // Sort by probability first, number of bits second, bit mask third.
     if (a.ExtraProb != b.ExtraProb)
       return a.ExtraProb > b.ExtraProb;
+    if (a.Bits != b.Bits)
       return a.Bits > b.Bits;
+    return a.Mask < b.Mask;
   });
 
   for (auto &CB : CBV) {
     MachineBasicBlock *BitTestBB =
         FuncInfo.MF->CreateMachineBasicBlock(SI->getParent());
     BTI.push_back(BitTestCase(CB.Mask, BitTestBB, CB.BB, CB.ExtraProb));
   }
   BitTestCases.emplace_back(std::move(LowBound), std::move(CmpRange),
if (Small.Low == Small.High && Big.Low == Big.High &&
 
         DAG.setRoot(BrCond);
         return;
       }
     }
   }
 
   if (TM.getOptLevel() != CodeGenOpt::None) {
-    // Order cases by probability so the most likely case will be checked first.
+    // 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
     // without without changing the order of probabilities.
     for (CaseClusterIt I = W.LastCluster; I > W.FirstCluster; ) {
       --I;
       if (I->Prob > W.LastCluster->Prob)
         break;