From c9605b6067c64ab92c6e50207e2f0b1c444bfeab Mon Sep 17 00:00:00 2001 From: Hans Wennborg Date: Mon, 1 Dec 2014 17:36:43 +0000 Subject: [PATCH] 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 --- .../SelectionDAG/SelectionDAGBuilder.cpp | 59 +++++------------ lib/Transforms/Utils/SimplifyCFG.cpp | 64 ++++++++++++++++--- .../X86/2013-10-14-FastISel-incorrect-vreg.ll | 6 +- test/CodeGen/X86/asm-label.ll | 6 +- test/CodeGen/X86/switch-jump-table.ll | 52 --------------- .../SimplifyCFG/UnreachableEliminate.ll | 26 ++++++++ .../SimplifyCFG/X86/switch_to_lookup_table.ll | 43 ++----------- 7 files changed, 112 insertions(+), 144 deletions(-) delete mode 100644 test/CodeGen/X86/switch-jump-table.ll diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index ec6a1367883..fbc1502d500 100644 --- 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(SI.getDefaultDest()->getFirstNonPHIOrDbg())) { - // Replace an unreachable default destination with the most popular case - // destination. - DenseMap 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 91127b27046..daa576cfbdc 100644 --- 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 > Popularity; + for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); + i != e; ++i) { + std::pair &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 >::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(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(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(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 9cd150a2f56..10dc927200b 100644 --- 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 1da66e74d34..1fc6e2eaf2b 100644 --- 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 index 7ae45b56641..00000000000 --- 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 22b144b5cb8..21428c62f53 100644 --- 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 29f1a35fb14..95c9cc539d2 100644 --- 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 -- 2.34.1