From dc9de50902b34e4995f73bfa33a0ad40b4928518 Mon Sep 17 00:00:00 2001 From: Mandeep Singh Grang Date: Mon, 20 Nov 2017 18:46:11 +0000 Subject: [SelectionDAG] Make sorting predicate stronger to remove non-deterministic ordering 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 Reviewers: hans, efriedma Reviewed By: hans Subscribers: fhahn, aemerson, kristof.beyls, llvm-commits Differential Revision: https://reviews.llvm.org/D39995 llvm-svn: 318680 --- llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-) (limited to 'llvm/lib/CodeGen/SelectionDAG') diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index f49e22b8288..3c2ca50a10f 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,13 @@ 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 < b.Low; }); // Rearrange the case blocks so that the last one falls through if possible -- cgit v1.2.3