Revert "[CodeGen] Omit range checks from jump tables when lowering switches with unreachable default"

This reverts commit 2a0f2c5ef3330846149598220467d9f3c6e8b99c (r355490).

The commit causes an assertion failure when compiling LLVM code:
$ cat repro.cpp
class QQQ {
public:
  bool x() const;
  bool y() const;
  unsigned getSizeInBits() const {
    if (y() || x())
      return getScalarSizeInBits();
    return getScalarSizeInBits() * 2;
  }
  unsigned getScalarSizeInBits() const;
};
int f(const QQQ &Ty) {
  switch (Ty.getSizeInBits()) {
    case 1:
    case 8:
      return 0;
    case 16:
      return 1;
    case 32:
      return 2;
    case 64:
      return 3;
    default:
      __builtin_unreachable();
  }
}
$ clang -O2 -o repro.o repro.cpp
assert.h assertion failed at llvm/include/llvm/ADT/ilist_iterator.h:139 in llvm::ilist_iterator::reference llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::MachineInstr, true, true, void>, true, false>::operator*() const [OptionsT = llvm::ilist_detail::node_options<llvm::MachineInstr, true, true, void>, IsReverse = true, IsConst = false]: !NodePtr->isKnownSentinel()
*** Check failure stack trace: ***
    @     0x558aab4afc10  __assert_fail
    @     0x558aa885479b  llvm::ilist_iterator<>::operator*()
    @     0x558aa8854715  llvm::MachineInstrBundleIterator<>::operator*()
    @     0x558aa92c33c3  llvm::X86InstrInfo::optimizeCompareInstr()
    @     0x558aa9a9c251  (anonymous namespace)::PeepholeOptimizer::optimizeCmpInstr()
    @     0x558aa9a9b371  (anonymous namespace)::PeepholeOptimizer::runOnMachineFunction()
    @     0x558aa99a4fc8  llvm::MachineFunctionPass::runOnFunction()
    @     0x558aab019fc4  llvm::FPPassManager::runOnFunction()
    @     0x558aab01a3a5  llvm::FPPassManager::runOnModule()
    @     0x558aab01aa9b  (anonymous namespace)::MPPassManager::runOnModule()
    @     0x558aab01a635  llvm::legacy::PassManagerImpl::run()
    @     0x558aab01afe1  llvm::legacy::PassManager::run()
    @     0x558aa5914769  (anonymous namespace)::EmitAssemblyHelper::EmitAssembly()
    @     0x558aa5910f44  clang::EmitBackendOutput()
    @     0x558aa5906135  clang::BackendConsumer::HandleTranslationUnit()
    @     0x558aa6d165ad  clang::ParseAST()
    @     0x558aa6a94e22  clang::ASTFrontendAction::ExecuteAction()
    @     0x558aa590255d  clang::CodeGenAction::ExecuteAction()
    @     0x558aa6a94840  clang::FrontendAction::Execute()
    @     0x558aa6a38cca  clang::CompilerInstance::ExecuteAction()
    @     0x558aa4e2294b  clang::ExecuteCompilerInvocation()
    @     0x558aa4df6200  cc1_main()
    @     0x558aa4e1b37f  ExecuteCC1Tool()
    @     0x558aa4e1a725  main
    @     0x7ff20d56abbd  __libc_start_main
    @     0x558aa4df51c9  _start

llvm-svn: 355515

2 files changed, 53 insertions, 32 deletions

diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
index 52b039eb44f..33921a2c56d 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -2388,31 +2388,24 @@ void SelectionDAGBuilder::visitJumpTableHeader(JumpTable &JT,
                                     JumpTableReg, SwitchOp);
   JT.Reg = JumpTableReg;
 
-  if (!JTH.OmitRangeCheck) {
-    // Emit the range check for the jump table, and branch to the default block
-    // for the switch statement if the value being switched on exceeds the
-    // largest case in the switch.
-    SDValue CMP = DAG.getSetCC(
-        dl, TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(),
-                                   Sub.getValueType()),
-        Sub, DAG.getConstant(JTH.Last - JTH.First, dl, VT), ISD::SETUGT);
-
-    SDValue BrCond = DAG.getNode(ISD::BRCOND, dl,
-                                 MVT::Other, CopyTo, CMP,
-                                 DAG.getBasicBlock(JT.Default));
-
-    // Avoid emitting unnecessary branches to the next block.
-    if (JT.MBB != NextBlock(SwitchBB))
-      BrCond = DAG.getNode(ISD::BR, dl, MVT::Other, BrCond,
-                           DAG.getBasicBlock(JT.MBB));
- 
-    DAG.setRoot(BrCond);
-  } else {
-    SDValue BrCond = DAG.getNode(ISD::BR, dl, MVT::Other, CopyTo,
-                                 DAG.getBasicBlock(JT.MBB));
-    DAG.setRoot(BrCond);
-    SwitchBB->removeSuccessor(JT.Default, true);
-  }
+  // Emit the range check for the jump table, and branch to the default block
+  // for the switch statement if the value being switched on exceeds the largest
+  // case in the switch.
+  SDValue CMP = DAG.getSetCC(
+      dl, TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(),
+                                 Sub.getValueType()),
+      Sub, DAG.getConstant(JTH.Last - JTH.First, dl, VT), ISD::SETUGT);
+
+  SDValue BrCond = DAG.getNode(ISD::BRCOND, dl,
+                               MVT::Other, CopyTo, CMP,
+                               DAG.getBasicBlock(JT.Default));
+
+  // Avoid emitting unnecessary branches to the next block.
+  if (JT.MBB != NextBlock(SwitchBB))
+    BrCond = DAG.getNode(ISD::BR, dl, MVT::Other, BrCond,
+                         DAG.getBasicBlock(JT.MBB));
+
+  DAG.setRoot(BrCond);
 }
 
 /// Create a LOAD_STACK_GUARD node, and let it carry the target specific global
@@ -9797,13 +9790,10 @@ bool SelectionDAGBuilder::buildJumpTable(const CaseClusterVector &Clusters,
                      ->createJumpTableIndex(Table);
 
   // Set up the jump table info.
-  bool UnreachableDefault =
-      isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
-  bool OmitRangeCheck = UnreachableDefault;
   JumpTable JT(-1U, JTI, JumpTableMBB, nullptr);
   JumpTableHeader JTH(Clusters[First].Low->getValue(),
                       Clusters[Last].High->getValue(), SI->getCondition(),
-                      nullptr, false, OmitRangeCheck);
+                      nullptr, false);
   JTCases.emplace_back(std::move(JTH), std::move(JT));
 
   JTCluster = CaseCluster::jumpTable(Clusters[First].Low, Clusters[Last].High,
@@ -10609,6 +10599,38 @@ void SelectionDAGBuilder::visitSwitch(const SwitchInst &SI) {
   // if there are many clusters.
   sortAndRangeify(Clusters);
 
+  if (TM.getOptLevel() != CodeGenOpt::None) {
+    // Replace an unreachable default with the most popular destination.
+    // FIXME: Exploit unreachable default more aggressively.
+    bool UnreachableDefault =
+        isa<UnreachableInst>(SI.getDefaultDest()->getFirstNonPHIOrDbg());
+    if (UnreachableDefault && !Clusters.empty()) {
+      DenseMap<const BasicBlock *, unsigned> Popularity;
+      unsigned MaxPop = 0;
+      const BasicBlock *MaxBB = nullptr;
+      for (auto I : SI.cases()) {
+        const BasicBlock *BB = I.getCaseSuccessor();
+        if (++Popularity[BB] > MaxPop) {
+          MaxPop = Popularity[BB];
+          MaxBB = BB;
+        }
+      }
+      // Set new default.
+      assert(MaxPop > 0 && MaxBB);
+      DefaultMBB = FuncInfo.MBBMap[MaxBB];
+
+      // Remove cases that were pointing to the destination that is now the
+      // default.
+      CaseClusterVector New;
+      New.reserve(Clusters.size());
+      for (CaseCluster &CC : Clusters) {
+        if (CC.MBB != DefaultMBB)
+          New.push_back(CC);
+      }
+      Clusters = std::move(New);
+    }
+  }
+
   // The branch probablity of the peeled case.
   BranchProbability PeeledCaseProb = BranchProbability::getZero();
   MachineBasicBlock *PeeledSwitchMBB =
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
index 09dd7afd925..e84214dbf5e 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
@@ -277,12 +277,11 @@ private:
     const Value *SValue;
     MachineBasicBlock *HeaderBB;
     bool Emitted;
-    bool OmitRangeCheck;
 
     JumpTableHeader(APInt F, APInt L, const Value *SV, MachineBasicBlock *H,
-                    bool E = false, bool ORC = false)
+                    bool E = false)
         : First(std::move(F)), Last(std::move(L)), SValue(SV), HeaderBB(H),
-          Emitted(E), OmitRangeCheck(ORC) {}
+          Emitted(E) {}
   };
   using JumpTableBlock = std::pair<JumpTableHeader, JumpTable>;