From d5c2318adc7bde590d9f9369ef97fe7adde3f1a4 Mon Sep 17 00:00:00 2001 From: Hans Wennborg Date: Mon, 26 Jan 2015 19:52:32 +0000 Subject: [PATCH] SimplifyCFG: don't remove unreachable default switch destinations An unreachable default destination can be exploited by other optimizations and allows for more efficient lowering. Both the SDag switch lowering and LowerSwitch can exploit unreachable defaults. Also make TurnSwitchRangeICmp handle switches with unreachable default. This is kind of separate change, but it cannot be tested without the change above, and I don't want to land the change above without this since that would regress other tests. Differential Revision: http://reviews.llvm.org/D6471 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@227125 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/SimplifyCFG.cpp | 181 +++++++++--------- .../SimplifyCFG/UnreachableEliminate.ll | 26 --- .../SimplifyCFG/X86/switch_to_lookup_table.ll | 14 +- .../SimplifyCFG/switch-range-to-icmp.ll | 27 +++ .../SimplifyCFG/switch-to-select-two-case.ll | 35 ---- 5 files changed, 126 insertions(+), 157 deletions(-) diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index cd8584313f8..0b9568b91dc 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -3107,55 +3107,6 @@ 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 @@ -3189,70 +3140,122 @@ bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) { 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->empty()) 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 > UINT32_MAX || FalseWeight > UINT32_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; diff --git a/test/Transforms/SimplifyCFG/UnreachableEliminate.ll b/test/Transforms/SimplifyCFG/UnreachableEliminate.ll index 21428c62f53..22b144b5cb8 100644 --- a/test/Transforms/SimplifyCFG/UnreachableEliminate.ll +++ b/test/Transforms/SimplifyCFG/UnreachableEliminate.ll @@ -46,32 +46,6 @@ 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 22f18cd4d43..9cf57b38dfe 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 -; 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 @@ return: ; 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,15 @@ sw.bb: br label %return 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 } ; Don't create a table with illegal type diff --git a/test/Transforms/SimplifyCFG/switch-range-to-icmp.ll b/test/Transforms/SimplifyCFG/switch-range-to-icmp.ll index 8bf2b04520b..a109b317c73 100644 --- a/test/Transforms/SimplifyCFG/switch-range-to-icmp.ll +++ b/test/Transforms/SimplifyCFG/switch-range-to-icmp.ll @@ -48,3 +48,30 @@ 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 +} diff --git a/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll b/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll index 69f97e5f9f9..f4d171ad2b1 100644 --- a/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll +++ b/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll @@ -35,38 +35,3 @@ return: %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 -} -- 2.34.1