From 230b0a147784856eefcc39ad7a51259647c5814f Mon Sep 17 00:00:00 2001 From: Mandeep Singh Grang Date: Tue, 28 Nov 2017 19:55:54 +0000 Subject: [PATCH] [SelectionDAG] Make sorting predicate stronger to remove non-deterministic ordering Summary: Recommitting this with the correct sorting predicate. The Low field of Clusters is a ConstantInt and cannot be directly compared. So we needed to invoke slt (signed less than) to compare correctly. 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 LLVM :: CodeGen/X86/switch-bt.ll LLVM :: CodeGen/X86/switch-density.ll Reviewers: hans, fhahn Reviewed By: hans Subscribers: aemerson, llvm-commits, kristof.beyls Differential Revision: https://reviews.llvm.org/D40541 llvm-svn: 319210 --- llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp | 15 +++++++++++---- 1 file changed, 11 insertions(+), 4 deletions(-) diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index 288afad..97d4cd3 100644 --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -9350,10 +9350,12 @@ bool SelectionDAGBuilder::buildBitTests(CaseClusterVector &Clusters, 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; - return a.Bits > b.Bits; + if (a.Bits != b.Bits) + return a.Bits > b.Bits; + return a.Mask < b.Mask; }); for (auto &CB : CBV) { @@ -9542,10 +9544,15 @@ void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, } 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->getValue().slt(b.Low->getValue()); }); // Rearrange the case blocks so that the last one falls through if possible -- 2.7.4