Index: lib/Transforms/Utils/Local.cpp =================================================================== --- lib/Transforms/Utils/Local.cpp +++ lib/Transforms/Utils/Local.cpp @@ -110,11 +110,17 @@ } if (SwitchInst *SI = dyn_cast(T)) { - // If we are switching on a constant, we can convert the switch into a - // single branch instruction! + // If we are switching on a constant, we can convert the switch to an + // unconditional branch. ConstantInt *CI = dyn_cast(SI->getCondition()); - BasicBlock *TheOnlyDest = SI->getDefaultDest(); - BasicBlock *DefaultDest = TheOnlyDest; + BasicBlock *DefaultDest = SI->getDefaultDest(); + BasicBlock *TheOnlyDest = DefaultDest; + + // If the default is unreachable, ignore it when searching for TheOnlyDest. + if (isa(DefaultDest->getFirstNonPHIOrDbg()) && + SI->getNumCases() > 0) { + TheOnlyDest = SI->case_begin().getCaseSuccessor(); + } // Figure out which case it goes to. for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -3120,55 +3120,6 @@ --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 @@ -3202,70 +3153,122 @@ return Changed; } -/// TurnSwitchRangeIntoICmp - Turns a switch with that contains only a -/// integer range comparison into a sub, an icmp and a branch. -static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) { - assert(SI->getNumCases() > 1 && "Degenerate switch?"); +static bool CasesAreContiguous(SmallVectorImpl &Cases) { + assert(Cases.size() >= 1); - // Make sure all cases point to the same destination and gather the values. - SmallVector Cases; - SwitchInst::CaseIt I = SI->case_begin(); - Cases.push_back(I.getCaseValue()); - SwitchInst::CaseIt PrevI = I++; - for (SwitchInst::CaseIt E = SI->case_end(); I != E; PrevI = I++) { - if (PrevI.getCaseSuccessor() != I.getCaseSuccessor()) + array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate); + for (size_t I = 1, E = Cases.size(); I != E; ++I) { + if (Cases[I - 1]->getValue() != Cases[I]->getValue() + 1) return false; - Cases.push_back(I.getCaseValue()); } - assert(Cases.size() == SI->getNumCases() && "Not all cases gathered"); + return true; +} - // Sort the case values, then check if they form a range we can transform. - array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate); - for (unsigned I = 1, E = Cases.size(); I != E; ++I) { - if (Cases[I-1]->getValue() != Cases[I]->getValue()+1) - return false; +/// Turn a switch with two reachable destinations into an integer range +/// comparison and branch. +static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) { + assert(SI->getNumCases() > 1 && "Degenerate switch?"); + + bool HasDefault = + !isa(SI->getDefaultDest()->getFirstNonPHIOrDbg()); + + // Partition the cases into two sets with different destinations. + BasicBlock *DestA = HasDefault ? SI->getDefaultDest() : nullptr; + BasicBlock *DestB = nullptr; + SmallVector CasesA; + SmallVector CasesB; + + for (SwitchInst::CaseIt I : SI->cases()) { + BasicBlock *Dest = I.getCaseSuccessor(); + if (!DestA) DestA = Dest; + if (Dest == DestA) { + CasesA.push_back(I.getCaseValue()); + continue; + } + if (!DestB) DestB = Dest; + if (Dest == DestB) { + CasesB.push_back(I.getCaseValue()); + continue; + } + return false; // More than two destinations. } - Constant *Offset = ConstantExpr::getNeg(Cases.back()); - Constant *NumCases = ConstantInt::get(Offset->getType(), SI->getNumCases()); + assert(DestA && DestB && "Single-destination switch should have been folded."); + assert(DestA != DestB); + assert(DestB != SI->getDefaultDest()); + assert(!CasesB.empty() && "There must be non-default cases."); + assert(!CasesA.empty() || HasDefault); + + // Figure out if one of the sets of cases form a contiguous range. + SmallVectorImpl *ContiguousCases = nullptr; + BasicBlock *ContiguousDest = nullptr; + BasicBlock *OtherDest = nullptr; + if (!CasesA.empty() && CasesAreContiguous(CasesA)) { + ContiguousCases = &CasesA; + ContiguousDest = DestA; + OtherDest = DestB; + } else if (CasesAreContiguous(CasesB)) { + ContiguousCases = &CasesB; + ContiguousDest = DestB; + OtherDest = DestA; + } else + return false; + + // Start building the compare and branch. + + Constant *Offset = ConstantExpr::getNeg(ContiguousCases->back()); + Constant *NumCases = ConstantInt::get(Offset->getType(), ContiguousCases->size()); Value *Sub = SI->getCondition(); if (!Offset->isNullValue()) - Sub = Builder.CreateAdd(Sub, Offset, Sub->getName()+".off"); + Sub = Builder.CreateAdd(Sub, Offset, Sub->getName() + ".off"); + Value *Cmp; // If NumCases overflowed, then all possible values jump to the successor. - if (NumCases->isNullValue() && SI->getNumCases() != 0) + if (NumCases->isNullValue() && ContiguousCases->size() != 0) Cmp = ConstantInt::getTrue(SI->getContext()); else Cmp = Builder.CreateICmpULT(Sub, NumCases, "switch"); - BranchInst *NewBI = Builder.CreateCondBr( - Cmp, SI->case_begin().getCaseSuccessor(), SI->getDefaultDest()); + BranchInst *NewBI = Builder.CreateCondBr(Cmp, ContiguousDest, OtherDest); // Update weight for the newly-created conditional branch. - SmallVector Weights; - bool HasWeights = HasBranchWeights(SI); - if (HasWeights) { + if (HasBranchWeights(SI)) { + SmallVector Weights; GetBranchWeights(SI, Weights); if (Weights.size() == 1 + SI->getNumCases()) { - // Combine all weights for the cases to be the true weight of NewBI. - // We assume that the sum of all weights for a Terminator can fit into 32 - // bits. - uint32_t NewTrueWeight = 0; - for (unsigned I = 1, E = Weights.size(); I != E; ++I) - NewTrueWeight += (uint32_t)Weights[I]; + uint64_t TrueWeight = 0; + uint64_t FalseWeight = 0; + for (size_t I = 0, E = Weights.size(); I != E; ++I) { + if (SI->getSuccessor(I) == ContiguousDest) + TrueWeight += Weights[I]; + else + FalseWeight += Weights[I]; + } + while (TrueWeight > UINT_MAX || FalseWeight > UINT_MAX) { + TrueWeight /= 2; + FalseWeight /= 2; + } NewBI->setMetadata(LLVMContext::MD_prof, - MDBuilder(SI->getContext()). - createBranchWeights(NewTrueWeight, - (uint32_t)Weights[0])); + MDBuilder(SI->getContext()).createBranchWeights( + (uint32_t)TrueWeight, (uint32_t)FalseWeight)); } } - // Prune obsolete incoming values off the successor's PHI nodes. - for (BasicBlock::iterator BBI = SI->case_begin().getCaseSuccessor()->begin(); - isa(BBI); ++BBI) { - for (unsigned I = 0, E = SI->getNumCases()-1; I != E; ++I) + // Prune obsolete incoming values off the successors' PHI nodes. + for (auto BBI = ContiguousDest->begin(); isa(BBI); ++BBI) { + unsigned PreviousEdges = ContiguousCases->size(); + if (ContiguousDest == SI->getDefaultDest()) ++PreviousEdges; + for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I) cast(BBI)->removeIncomingValue(SI->getParent()); } + for (auto BBI = OtherDest->begin(); isa(BBI); ++BBI) { + unsigned PreviousEdges = SI->getNumCases() - ContiguousCases->size(); + if (OtherDest == SI->getDefaultDest()) ++PreviousEdges; + for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I) + cast(BBI)->removeIncomingValue(SI->getParent()); + } + + // Drop the switch. SI->eraseFromParent(); return true; @@ -4183,19 +4186,20 @@ "It is impossible for a switch to have more entries than the max " "representable value of its input integer type's size."); - // 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. + // 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); BranchInst *RangeCheckBranch = nullptr; - const bool GeneratingCoveredLookupTable = MaxTableSize == TableSize; - if (GeneratingCoveredLookupTable) { + if (!DefaultIsReachable || 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)); Index: test/Transforms/SimplifyCFG/UnreachableEliminate.ll =================================================================== --- test/Transforms/SimplifyCFG/UnreachableEliminate.ll +++ test/Transforms/SimplifyCFG/UnreachableEliminate.ll @@ -46,32 +46,6 @@ 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 Index: test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll =================================================================== --- test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll +++ test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll @@ -21,8 +21,8 @@ ; 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 -; CHECK: @switch.table6 = private unnamed_addr constant [5 x i32] [i32 0, i32 0, i32 0, i32 1, i32 -1] +; 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] ; A simple int-to-int selection switch. ; It is dense enough to be replaced by table lookup. @@ -752,7 +752,7 @@ ; CHECK: %switch.gep = getelementptr inbounds [7 x i32]* @switch.table5, i32 0, i32 %switch.tableidx } -define i32 @unreachable(i32 %x) { +define i32 @unreachable_case(i32 %x) { entry: switch i32 %x, label %sw.default [ i32 0, label %sw.bb @@ -770,15 +770,44 @@ sw.bb1: unreachable sw.bb2: br label %return sw.bb3: br label %return -sw.default: unreachable +sw.default: br label %return return: - %retval.0 = phi i32 [ 1, %sw.bb3 ], [ -1, %sw.bb2 ], [ 0, %sw.bb ] + %retval.0 = phi i32 [ 1, %sw.bb3 ], [ -1, %sw.bb2 ], [ 0, %sw.bb ], [ 2, %sw.default ] ret i32 %retval.0 -; CHECK-LABEL: @unreachable( +; CHECK-LABEL: @unreachable_case( ; CHECK: switch.lookup: -; CHECK: getelementptr inbounds [5 x i32]* @switch.table6, i32 0, i32 %switch.tableidx +; 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 } ; Don't create a table with illegal type Index: test/Transforms/SimplifyCFG/switch-range-to-icmp.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/switch-range-to-icmp.ll @@ -0,0 +1,77 @@ +; RUN: opt %s -simplifycfg -S | FileCheck %s + +declare i32 @f(i32) + +define i32 @basic(i32 %x) { +; CHECK-LABEL: @basic +; CHECK: x.off = add i32 %x, -5 +; CHECK: %switch = icmp ult i32 %x.off, 3 +; CHECK: br i1 %switch, label %a, label %default + +entry: + switch i32 %x, label %default [ + i32 5, label %a + i32 6, label %a + i32 7, label %a + ] +default: + %0 = call i32 @f(i32 0) + ret i32 %0 +a: + %1 = call i32 @f(i32 1) + ret i32 %1 +} + + +define i32 @unreachable(i32 %x) { +; CHECK-LABEL: @unreachable +; CHECK: x.off = add i32 %x, -5 +; CHECK: %switch = icmp ult i32 %x.off, 3 +; CHECK: br i1 %switch, label %a, label %b + +entry: + switch i32 %x, label %unreachable [ + i32 5, label %a + i32 6, label %a + i32 7, label %a + i32 10, label %b + i32 20, label %b + i32 30, label %b + i32 40, label %b + ] +unreachable: + unreachable +a: + %0 = call i32 @f(i32 0) + ret i32 %0 +b: + %1 = call i32 @f(i32 1) + ret i32 %1 +} + + +define i32 @unreachable2(i32 %x) { +; CHECK-LABEL: @unreachable2 +; CHECK: x.off = add i32 %x, -5 +; CHECK: %switch = icmp ult i32 %x.off, 3 +; CHECK: br i1 %switch, label %a, label %b + +entry: + ; Note: folding the most popular case destination into the default + ; would prevent switch-to-icmp here. + switch i32 %x, label %unreachable [ + i32 5, label %a + i32 6, label %a + i32 7, label %a + i32 10, label %b + i32 20, label %b + ] +unreachable: + unreachable +a: + %0 = call i32 @f(i32 0) + ret i32 %0 +b: + %1 = call i32 @f(i32 1) + ret i32 %1 +} Index: test/Transforms/SimplifyCFG/switch-to-br.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/switch-to-br.ll @@ -0,0 +1,64 @@ +; RUN: opt %s -simplifycfg -S | FileCheck %s + +declare i32 @f(i32) + +define i32 @basic(i32 %x) { +; CHECK-LABEL: @basic +; CHECK-LABEL: entry: +; CHECK-NEXT: call i32 @f(i32 0) +; CHECK-NEXT: ret i32 %0 + +entry: + switch i32 %x, label %default [ + i32 5, label %default + i32 6, label %default + i32 7, label %default + ] +default: + %0 = call i32 @f(i32 0) + ret i32 %0 +} + + +define i32 @constant() { +; CHECK-LABEL: @constant +; CHECK-LABEL: entry: +; CHECK-NEXT: call i32 @f(i32 1) +; CHECK-NEXT: ret i32 %0 + +entry: + switch i32 42, label %default [ + i32 41, label %default + i32 42, label %a + i32 43, label %b + ] +default: + %0 = call i32 @f(i32 0) + ret i32 %0 +a: + %1 = call i32 @f(i32 1) + ret i32 %1 +b: + %2 = call i32 @f(i32 2) + ret i32 %2 +} + + +define i32 @unreachable() { +; CHECK-LABEL: @unreachable +; CHECK-LABEL: entry: +; CHECK-NEXT: call i32 @f(i32 0) +; CHECK-NEXT: ret i32 %0 + +entry: + switch i32 42, label %unreachable [ + i32 5, label %a + i32 6, label %a + i32 7, label %a + ] +unreachable: + unreachable +a: + %0 = call i32 @f(i32 0) + ret i32 %0 +} Index: test/Transforms/SimplifyCFG/switch-to-select-two-case.ll =================================================================== --- test/Transforms/SimplifyCFG/switch-to-select-two-case.ll +++ test/Transforms/SimplifyCFG/switch-to-select-two-case.ll @@ -35,38 +35,3 @@ %retval.0 = phi i32 [ 4, %sw.epilog ], [ 2, %sw.bb1 ], [ 10, %sw.bb ] ret i32 %retval.0 } - -; int foo1_without_default(int a) { -; switch(a) { -; case 10: -; return 10; -; case 20: -; return 2; -; } -; __builtin_unreachable(); -; } - -define i32 @foo1_without_default(i32 %a) { -; CHECK-LABEL: @foo1_without_default -; CHECK: %switch.selectcmp = icmp eq i32 %a, 10 -; CHECK-NEXT: %switch.select = select i1 %switch.selectcmp, i32 10, i32 2 -; CHECK-NOT: %switch.selectcmp1 -entry: - switch i32 %a, label %sw.epilog [ - i32 10, label %sw.bb - i32 20, label %sw.bb1 - ] - -sw.bb: - br label %return - -sw.bb1: - br label %return - -sw.epilog: - unreachable - -return: - %retval.0 = phi i32 [ 2, %sw.bb1 ], [ 10, %sw.bb ] - ret i32 %retval.0 -}