Revert r223049, r223050 and r223051 while investigating test failures.

I didn't foresee affecting the Clang test suite :/

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@223054 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
index ec6a13678836db55454df7d1d4dba17a51cac2d5..fbc1502d50024aa5713d924852eaaf1b5c78efd7 100644 (file)
--- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -2695,57 +2695,32 @@ void SelectionDAGBuilder::visitSwitch(const SwitchInst &SI) {
   if (SwitchMBB + 1 != FuncInfo.MF->end())
     NextBlock = SwitchMBB + 1;
 
-
-  // Create a vector of Cases, sorted so that we can efficiently create a binary
-  // search tree from them.
-  CaseVector Cases;
-  Clusterify(Cases, SI);
-
-  // Get the default destination MBB.
   MachineBasicBlock *Default = FuncInfo.MBBMap[SI.getDefaultDest()];
 
-  if (isa<UnreachableInst>(SI.getDefaultDest()->getFirstNonPHIOrDbg())) {
-    // Replace an unreachable default destination with the most popular case
-    // destination.
-    DenseMap<const BasicBlock*, uint64_t> Popularity;
-    uint64_t 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.
-    Default = FuncInfo.MBBMap[MaxBB];
-
-    // Remove cases that have been replaced by the default.
-    CaseItr I = Cases.begin();
-    while (I != Cases.end()) {
-      if (I->BB == Default) {
-        I = Cases.erase(I);
-        continue;
-      }
-      ++I;
-    }
-  }
-
-  // If there is only the default destination, go there directly.
-  if (Cases.empty()) {
+  // If there is only the default destination, branch to it if it is not the
+  // next basic block.  Otherwise, just fall through.
+  if (!SI.getNumCases()) {
     // Update machine-CFG edges.
     SwitchMBB->addSuccessor(Default);
 
     // If this is not a fall-through branch, emit the branch.
-    if (Default != NextBlock) {
-      DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(), MVT::Other,
-                              getControlRoot(), DAG.getBasicBlock(Default)));
-    }
+    if (Default != NextBlock)
+      DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(),
+                              MVT::Other, getControlRoot(),
+                              DAG.getBasicBlock(Default)));
+
     return;
   }
 
-  // Get the Value to be switched on.
+  // If there are any non-default case statements, create a vector of Cases
+  // representing each one, and sort the vector so that we can efficiently
+  // create a binary search tree from them.
+  CaseVector Cases;
+  Clusterify(Cases, SI);
+
+  // Get the Value to be switched on and default basic blocks, which will be
+  // inserted into CaseBlock records, representing basic blocks in the binary
+  // search tree.
   const Value *SV = SI.getCondition();
 
   // Push the initial CaseRec onto the worklist

diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index 91127b2704650a7132eab4e6e02f81457e3b7e33..daa576cfbdc9fe5e2ef2c80a59439d71fc33ca54 100644 (file)
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -3120,6 +3120,55 @@ bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) {
           --i; --e;
           Changed = true;
         }
+      // If the default value is unreachable, figure out the most popular
+      // destination and make it the default.
+      if (SI->getDefaultDest() == BB) {
+        std::map<BasicBlock*, std::pair<unsigned, unsigned> > Popularity;
+        for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
+             i != e; ++i) {
+          std::pair<unsigned, unsigned> &entry =
+              Popularity[i.getCaseSuccessor()];
+          if (entry.first == 0) {
+            entry.first = 1;
+            entry.second = i.getCaseIndex();
+          } else {
+            entry.first++;
+          }
+        }
+
+        // Find the most popular block.
+        unsigned MaxPop = 0;
+        unsigned MaxIndex = 0;
+        BasicBlock *MaxBlock = nullptr;
+        for (std::map<BasicBlock*, std::pair<unsigned, unsigned> >::iterator
+             I = Popularity.begin(), E = Popularity.end(); I != E; ++I) {
+          if (I->second.first > MaxPop ||
+              (I->second.first == MaxPop && MaxIndex > I->second.second)) {
+            MaxPop = I->second.first;
+            MaxIndex = I->second.second;
+            MaxBlock = I->first;
+          }
+        }
+        if (MaxBlock) {
+          // Make this the new default, allowing us to delete any explicit
+          // edges to it.
+          SI->setDefaultDest(MaxBlock);
+          Changed = true;
+
+          // If MaxBlock has phinodes in it, remove MaxPop-1 entries from
+          // it.
+          if (isa<PHINode>(MaxBlock->begin()))
+            for (unsigned i = 0; i != MaxPop-1; ++i)
+              MaxBlock->removePredecessor(SI->getParent());
+
+          for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
+               i != e; ++i)
+            if (i.getCaseSuccessor() == MaxBlock) {
+              SI->removeCase(i);
+              --i; --e;
+            }
+        }
+      }
     } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
       if (II->getUnwindDest() == BB) {
         // Convert the invoke to a call instruction.  This would be a good
@@ -4134,20 +4183,19 @@ static bool SwitchToLookupTable(SwitchInst *SI,
          "It is impossible for a switch to have more entries than the max "
          "representable value of its input integer type's size.");
 
-  // If the default destination is unreachable, or if the lookup table covers
-  // all values of the conditional variable, branch directly to the lookup table
-  // BB. Otherwise, check that the condition is within the case range.
-  const bool DefaultIsReachable =
-      !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
-  const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
+  // If we have a fully covered lookup table, unconditionally branch to the
+  // lookup table BB. Otherwise, check if the condition value is within the case
+  // range. If it is so, branch to the new BB. Otherwise branch to SI's default
+  // destination.
   BranchInst *RangeCheckBranch = nullptr;
 
-  if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
+  const bool GeneratingCoveredLookupTable = MaxTableSize == TableSize;
+  if (GeneratingCoveredLookupTable) {
     Builder.CreateBr(LookupBB);
     // We cached PHINodes in PHIs, to avoid accessing deleted PHINodes later,
     // do not delete PHINodes here.
     SI->getDefaultDest()->removePredecessor(SI->getParent(),
-                                            true /*DontDeleteUselessPHIs*/);
+                                            true/*DontDeleteUselessPHIs*/);
   } else {
     Value *Cmp = Builder.CreateICmpULT(TableIndex, ConstantInt::get(
                                        MinCaseVal->getType(), TableSize));

diff --git a/test/CodeGen/X86/2013-10-14-FastISel-incorrect-vreg.ll b/test/CodeGen/X86/2013-10-14-FastISel-incorrect-vreg.ll
index 9cd150a2f56db4ff11284727956cf3f93124a5f7..10dc927200b629d9fe571a8d9ee5916cefb59c8b 100644 (file)
--- a/test/CodeGen/X86/2013-10-14-FastISel-incorrect-vreg.ll
+++ b/test/CodeGen/X86/2013-10-14-FastISel-incorrect-vreg.ll
@@ -41,7 +41,7 @@ entry:
     i1 false, label %label_end
   ]
 default:
-  br label %label_end
+  unreachable
 
 label_true:
   br label %label_end
@@ -80,7 +80,7 @@ entry:
     i1 false, label %label_end
   ]
 default:
-  br label %label_end
+  unreachable
 
 label_true:
   br label %label_end
@@ -119,7 +119,7 @@ entry:
     i1 false, label %label_end
   ]
 default:
-  br label %label_end
+  unreachable
 
 label_true:
   br label %label_end

diff --git a/test/CodeGen/X86/asm-label.ll b/test/CodeGen/X86/asm-label.ll
index 1da66e74d34f5055db61a803706644ff31dc72ba..1fc6e2eaf2b73364df674c4e7ad928c110759a7f 100644 (file)
--- a/test/CodeGen/X86/asm-label.ll
+++ b/test/CodeGen/X86/asm-label.ll
@@ -24,7 +24,7 @@ if.end:                                           ; preds = %if.then
   br label %cleanup
 
 cleanup:                                          ; preds = %if.end, %if.then9
-  switch i32 undef, label %default [
+  switch i32 undef, label %unreachable [
     i32 0, label %cleanup.cont
     i32 1, label %if.end11
   ]
@@ -35,6 +35,6 @@ cleanup.cont:                                     ; preds = %cleanup
 if.end11:                                         ; preds = %cleanup.cont, %cleanup, %land.lhs.true, %entry
   ret void
 
-default:                                          ; preds = %cleanup
-  br label %if.end11
+unreachable:                                      ; preds = %cleanup
+  unreachable
 }

diff --git a/test/CodeGen/X86/switch-jump-table.ll b/test/CodeGen/X86/switch-jump-table.ll
deleted file mode 100644 (file)
index 7ae45b5..0000000
--- a/test/CodeGen/X86/switch-jump-table.ll
+++ /dev/null
@@ -1,52 +0,0 @@
-; RUN: llc -march=x86 < %s | FileCheck %s
-
-
-; An unreachable default destination is replaced with the most popular case label.
-
-define void @sum2(i32 %x, i32* %to) {
-; CHECK-LABEL: sum2:
-; CHECK: movl 4(%esp), [[REG:%e[a-z]{2}]]
-; cmpl $3, [[REG]]
-; CHECK: jbe .LBB0_1
-; CHECK: movl $4
-; CHECK: retl
-; CHECK-LABEL: .LBB0_1:
-; CHECK-NEXT: jmpl *.LJTI0_0(,[[REG]],4)
-
-entry:
-  switch i32 %x, label %default [
-    i32 0, label %bb0
-    i32 1, label %bb1
-    i32 2, label %bb2
-    i32 3, label %bb3
-    i32 4, label %bb4
-    i32 5, label %bb4
-  ]
-bb0:
-  store i32 0, i32* %to
-  br label %exit
-bb1:
-  store i32 1, i32* %to
-  br label %exit
-bb2:
-  store i32 2, i32* %to
-  br label %exit
-bb3:
-  store i32 3, i32* %to
-  br label %exit
-bb4:
-  store i32 4, i32* %to
-  br label %exit
-exit:
-  ret void
-default:
-  unreachable
-
-; The jump table has four entries.
-; CHECK-LABEL: .LJTI0_0:
-; CHECK-NEXT: .long  .LBB0_2
-; CHECK-NEXT: .long  .LBB0_3
-; CHECK-NEXT: .long  .LBB0_4
-; CHECK-NEXT: .long  .LBB0_5
-; CHECK-NOT: .long
-}

diff --git a/test/Transforms/SimplifyCFG/UnreachableEliminate.ll b/test/Transforms/SimplifyCFG/UnreachableEliminate.ll
index 22b144b5cb80cbedf9ed38f22fbc28a29a276a06..21428c62f5316233edfe7b220c0a45bb593ae02c 100644 (file)
--- a/test/Transforms/SimplifyCFG/UnreachableEliminate.ll
+++ b/test/Transforms/SimplifyCFG/UnreachableEliminate.ll
@@ -46,6 +46,32 @@ T:
         ret i32 2
 }
 
+; PR9450
+define i32 @test4(i32 %v, i32 %w) {
+; CHECK: entry:
+; CHECK-NEXT:  switch i32 %v, label %T [
+; CHECK-NEXT:    i32 3, label %V
+; CHECK-NEXT:    i32 2, label %U
+; CHECK-NEXT:  ]
+
+entry:
+        br label %SWITCH
+V:
+        ret i32 7
+SWITCH:
+        switch i32 %v, label %default [
+                 i32 1, label %T
+                 i32 2, label %U
+                 i32 3, label %V
+        ]
+default:
+        unreachable
+U:
+        ret i32 %w
+T:
+        ret i32 2
+}
+
 
 ;; We can either convert the following control-flow to a select or remove the
 ;; unreachable control flow because of the undef store of null. Make sure we do

diff --git a/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll b/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll
index 29f1a35fb144febe842a32e890c0ab4923208d64..95c9cc539d29a289a0f4e4d13be7c6d61bc5a235 100644 (file)
--- a/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll
+++ b/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll
@@ -21,8 +21,8 @@ target triple = "x86_64-unknown-linux-gnu"
 ; The table for @cprop
 ; CHECK: @switch.table5 = private unnamed_addr constant [7 x i32] [i32 5, i32 42, i32 126, i32 -452, i32 128, i32 6, i32 7]
 
-; The table for @unreachable_case
-; CHECK: @switch.table6 = private unnamed_addr constant [9 x i32] [i32 0, i32 0, i32 0, i32 2, i32 -1, i32 1, i32 1, i32 1, i32 1]
+; The table for @unreachable
+; CHECK: @switch.table6 = private unnamed_addr constant [5 x i32] [i32 0, i32 0, i32 0, i32 1, i32 -1]
 
 ; A simple int-to-int selection switch.
 ; It is dense enough to be replaced by table lookup.
@@ -752,7 +752,7 @@ return:
 ; CHECK: %switch.gep = getelementptr inbounds [7 x i32]* @switch.table5, i32 0, i32 %switch.tableidx
 }
 
-define i32 @unreachable_case(i32 %x)  {
+define i32 @unreachable(i32 %x)  {
 entry:
   switch i32 %x, label %sw.default [
     i32 0, label %sw.bb
@@ -770,44 +770,15 @@ sw.bb: br label %return
 sw.bb1: unreachable
 sw.bb2: br label %return
 sw.bb3: br label %return
-sw.default: br label %return
+sw.default: unreachable
 
 return:
-  %retval.0 = phi i32 [ 1, %sw.bb3 ], [ -1, %sw.bb2 ], [ 0, %sw.bb ], [ 2, %sw.default ]
+  %retval.0 = phi i32 [ 1, %sw.bb3 ], [ -1, %sw.bb2 ], [ 0, %sw.bb ]
   ret i32 %retval.0
 
-; CHECK-LABEL: @unreachable_case(
+; CHECK-LABEL: @unreachable(
 ; CHECK: switch.lookup:
-; CHECK: getelementptr inbounds [9 x i32]* @switch.table6, i32 0, i32 %switch.tableidx
-}
-
-define i32 @unreachable_default(i32 %x)  {
-entry:
-  switch i32 %x, label %default [
-    i32 0, label %bb0
-    i32 1, label %bb1
-    i32 2, label %bb2
-    i32 3, label %bb3
-  ]
-
-bb0: br label %return
-bb1: br label %return
-bb2: br label %return
-bb3: br label %return
-default: unreachable
-
-return:
-  %retval = phi i32 [ 42, %bb0 ], [ 52, %bb1 ], [ 1, %bb2 ], [ 2, %bb3 ]
-  ret i32 %retval
-
-; CHECK-LABEL: @unreachable_default(
-; CHECK: entry:
-; CHECK-NEXT: %switch.tableidx = sub i32 %x, 0
-; CHECK-NOT: icmp
-; CHECK-NOT: br 1i
-; CHECK-NEXT: %switch.gep = getelementptr inbounds [4 x i32]* @switch.table7, i32 0, i32 %switch.tableidx
-; CHECK-NEXT: %switch.load = load i32* %switch.gep
-; CHECK-NEXT: ret i32 %switch.load
+; CHECK: getelementptr inbounds [5 x i32]* @switch.table6, i32 0, i32 %switch.tableidx
 }
 
 ; Don't create a table with illegal type