Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -3670,6 +3670,320 @@ return SI->getNumCases() * 10 >= TableSize * 4; } +// InitializeUniqueCases - Helper function that initializes a map containing +// results for the PHI node of the common destination block for a switch +// instruction. Returns false if multiple PHI nodes have been found or if +// there is not a common destination block for the switch. +static bool InitializeUniqueCases( + SwitchInst *SI, const DataLayout *DL, PHINode *&PHI, + BasicBlock *&CommonDest, + SmallDenseMap> &UniqueResults, + Constant *&DefaultResult) { + for (auto I = SI->case_begin(), E = SI->case_end(); I != E; ++I) { + ConstantInt *CaseVal = I.getCaseValue(); + BasicBlock *CaseSuccessor = I.getCaseSuccessor(); + + // Resulting value at phi nodes for this case value. + typedef SmallVector, 4> ResultsTy; + ResultsTy Results; + if (!GetCaseResults(SI, CaseVal, I.getCaseSuccessor(), &CommonDest, Results, + DL)) + return false; + + BranchInst *BI = dyn_cast(CaseSuccessor->getTerminator()); + // Support only the case where the switch branches directly or through an + // intermediate unconditional block to the common destination. + if (CaseSuccessor != CommonDest && + !(BI && BI->isUnconditional() && BI->getSuccessor(0) == CommonDest)) + return false; + // Only one value per case is permitted + if (Results.size() > 1) + return false; + auto &Result = *Results.begin(); + auto ResultFound = UniqueResults.find(Result.second); + // Append the result from this case to the list and find the PHI + if (PHI == nullptr) + PHI = Result.first; + else if (PHI != Result.first) + return false; + if (ResultFound == UniqueResults.end()) { + UniqueResults[Result.second].push_back(CaseVal); + } else { + // Avoid querying the map again if we already found the result. + ResultFound->second.push_back(CaseVal); + } + } + // Find the default result value + SmallVector, 1> DefaultResults; + BasicBlock *DefaultDest = SI->getDefaultDest(); + GetCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults, + DL); + // No default case makes us assume that default is not possible. + DefaultResult = + DefaultResults.size() == 1 ? DefaultResults.begin()->second : nullptr; + BranchInst *BI = dyn_cast(DefaultDest->getTerminator()); + if (DefaultDest != CommonDest && + !(BI && BI->isUnconditional() && BI->getSuccessor(0) == CommonDest)) + return false; + + return true; +} + +// AnalyzeSwitchCases - Helper function to compute information about switch +// cases, like known ones and zeroes, the minimum and the maximum case and +// the number of case patterns that match the bitmask of the switch value. +static void AnalyzeSwitchCases(const SmallVectorImpl &Cases, + const APInt &KnownZeroesCond, + const APInt &KnownOnesCond, APInt &KnownZeroes, + APInt &KnownOnes, ConstantInt *&MinCase, + ConstantInt *&MaxCase, unsigned &PossibleHits) { + // Compute the number of patterns covered by the cases of each result, + // the minimum and maximum cases and the zeroes and ones for this case group. + for (auto &Case : Cases) { + bool CaseMatchesCondPattern = + ((~Case->getValue() & KnownZeroesCond) == KnownZeroesCond) && + ((Case->getValue() & KnownOnesCond) == KnownOnesCond); + + if (CaseMatchesCondPattern) + ++PossibleHits; + + KnownZeroes &= ~(Case->getValue()); + KnownOnes &= Case->getValue(); + if (MinCase->getValue().sgt(Case->getValue())) + MinCase = Case; + if (MaxCase->getValue().slt(Case->getValue())) + MaxCase = Case; + } +} + +// ConvertTwoCaseSwitch - Helper function that checks if it is possible to +// transform a switch with only two cases that produces a result into a value +// select. +static Value * +ConvertTwoCaseSwitch(const SmallVectorImpl &FirstGroupCases, + const SmallVectorImpl &SecondGroupCases, + Constant *FirstGroupResult, Constant *SecondGroupResult, + Constant *DefaultResult, Value *Condition, + const APInt &KnownZeroCond, const APInt &KnownOneCond, + unsigned Bits, IRBuilder<> &Builder) { + const unsigned CondStuckBits = + (KnownZeroCond | KnownOneCond).countPopulation(); + // If we are selecting between only two cases transform into a simple + // select or a two-way select if default is possible. + if (FirstGroupCases.size() == 1 && SecondGroupCases.size() == 1) { + ConstantInt *const FirstCase = FirstGroupCases[0]; + ConstantInt *const SecondCase = SecondGroupCases[0]; + // In this case we have only one case per result. From the analysis of + // the condition value done above we can determine if the condition value + // can assume the value of the case or if the case is dead. + const unsigned FirstCanHit = + ((~FirstCase->getValue() & KnownZeroCond) == KnownZeroCond) && + ((FirstCase->getValue() & KnownOneCond) == KnownOneCond); + const unsigned SecondCanHit = + ((~SecondCase->getValue() & KnownZeroCond) == KnownZeroCond) && + ((SecondCase->getValue() & KnownOneCond) == KnownOneCond); + + // The default case can trigger if a default value has been found and + // if there are some possible bit combination of the condition value + // that are not covered from the case labels + bool DefaultCanTrigger = + ((1 << (Bits - CondStuckBits)) - (FirstCanHit + SecondCanHit) != 0); + DefaultCanTrigger &= (DefaultResult != nullptr); + Value *SelectValue = SecondGroupResult; + if (DefaultCanTrigger) { + Value *const ValueCompare = + Builder.CreateICmpEQ(Condition, SecondCase, "switch.selectcmp"); + SelectValue = Builder.CreateSelect(ValueCompare, SecondGroupResult, + DefaultResult, "switch.select"); + } + Value *const ValueCompare = + Builder.CreateICmpEQ(Condition, FirstCase, "switch.selectcmp"); + return Builder.CreateSelect(ValueCompare, FirstGroupResult, SelectValue, + "switch.select"); + } + + return nullptr; +} + +// ConvertRangeSwitch - Helper function that checks if it is possible to +// transform a switch with cases arranged into two ordered not overlapping +// groups into a value select +static Value * +ConvertRangeSwitch(Constant *FirstGroupResult, Constant *SecondGroupResult, + Value *Condition, bool DefaultCanTrigger, + ConstantInt *MinCaseFirst, ConstantInt *MinCaseSecond, + ConstantInt *MaxCaseFirst, ConstantInt *MaxCaseSecond, + IRBuilder<> &Builder) { + const bool FirstIsBigger = + MaxCaseSecond->getValue().slt(MinCaseFirst->getValue()); + const bool SecondIsBigger = + MaxCaseFirst->getValue().slt(MinCaseSecond->getValue()); + // If the case statements ranges do not overlap use a comparison to + // distinguish between the two groups. + if (!DefaultCanTrigger && (FirstIsBigger || SecondIsBigger)) { + ConstantInt *Pivot = SecondIsBigger ? MaxCaseFirst : MaxCaseSecond; + Value *const SelectLHS = + SecondIsBigger ? FirstGroupResult : SecondGroupResult; + Value *const SelectRHS = + SecondIsBigger ? SecondGroupResult : FirstGroupResult; + Value *const ValueCompare = + Builder.CreateICmpSLE(Condition, Pivot, "switch.rangesub"); + return Builder.CreateSelect(ValueCompare, SelectLHS, SelectRHS, + "switch.rangeselect"); + } + + return nullptr; +} + +// ConvertBitPatternSwitch - Helper function that checks if it is possible to +// transform a switch with cases that are groupable by some bit pattern into +// a value select. +static Value *ConvertBitPatternSwitch( + Constant *FirstGroupResult, Constant *SecondGroupResult, Value *Condition, + bool DefaultCanTrigger, const APInt &KnownZeroFirst, APInt KnownOneFirst, + const APInt &KnownZeroSecond, APInt KnownOneSecond, IRBuilder<> &Builder) { + // If there is no default case and we have unambiguous + // patterns do it with one select and one compare. + if (!DefaultCanTrigger && ((KnownOneFirst & KnownZeroSecond) != 0 || + (KnownOneSecond & KnownZeroFirst) != 0)) { + Value *ValueCompare = nullptr; + // KnownOneFirst and KnownOneSecond after this assignment + // are bitvectors containing the bits that are always one + // in a group of case labels and always zero in the other + KnownOneFirst &= KnownZeroSecond; + KnownOneSecond &= KnownZeroFirst; + // The comparison checks for ones that are always present in + // one of the groups that are always zero in the other. + if (KnownOneFirst != 0) { + ConstantInt *const MaskValue = + ConstantInt::get(Condition->getContext(), KnownOneFirst); + ValueCompare = + Builder.CreateAnd(Condition, MaskValue, "switch.selectmask"); + ValueCompare = Builder.CreateICmpNE( + ValueCompare, ConstantInt::get(Condition->getType(), 0), + "switch.selectcmp"); + } else if (KnownOneSecond != 0) { + ConstantInt *const MaskValue = + ConstantInt::get(Condition->getContext(), KnownOneSecond); + ValueCompare = + Builder.CreateAnd(Condition, MaskValue, "switch.selectmask"); + ValueCompare = Builder.CreateICmpEQ( + ValueCompare, ConstantInt::get(Condition->getType(), 0), + "switch.selectcmp"); + } + return Builder.CreateSelect(ValueCompare, FirstGroupResult, + SecondGroupResult, "switch.select"); + } + + return nullptr; +} + +/// SwitchToSelect - If the switch is only used to initialize one or more +/// phi nodes in a common successor block with only two different +/// constant values, replace the switch with select. +static bool SwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, + const DataLayout *DL) { + Value *const Cond = SI->getCondition(); + PHINode *PHI = nullptr; + BasicBlock *CommonDest = nullptr; + Type *ResultType; + Constant *DefaultResult; + + SmallDenseMap> UniqueResults; + // Collect all the cases that will deliver the same value from the switch. + if (!InitializeUniqueCases(SI, DL, PHI, CommonDest, UniqueResults, + DefaultResult)) + return false; + // Selects choose between two values only. + if (UniqueResults.size() != 2) + return false; + assert(PHI != nullptr && "PHI for value select not found"); + ResultType = PHI->getType(); + + const unsigned Bits = Cond->getType()->getIntegerBitWidth(); + + auto FirstResult = UniqueResults.begin(); + auto SecondResult = FirstResult; + ++SecondResult; + // SmallDenseMap is unordered. Enforce a stable ordering here. + if (isa(SecondResult->first) || + (!isa(FirstResult->first) && + FirstResult->first->getUniqueInteger().sgt( + SecondResult->first->getUniqueInteger()))) { + std::swap(FirstResult, SecondResult); + } + + APInt KnownZeroCond(Bits, 0), KnownOneCond(Bits, 0); + computeKnownBits(Cond, KnownZeroCond, KnownOneCond); + // Number of bits that are fixed in the switch condition value. + const unsigned CondStuckBits = + (KnownZeroCond | KnownOneCond).countPopulation(); + Value *SelectValue = nullptr; + + Builder.SetInsertPoint(SI); + SelectValue = ConvertTwoCaseSwitch(FirstResult->second, SecondResult->second, + FirstResult->first, SecondResult->first, + DefaultResult, Cond, KnownZeroCond, + KnownOneCond, Bits, Builder); + + bool DefaultCanTrigger; + APInt KnownZeroFirst(Bits, ~(0ULL)), KnownOneFirst(Bits, ~(0ULL)), + KnownZeroSecond(Bits, ~(0ULL)), KnownOneSecond(Bits, ~(0ULL)); + // The switch has more than only two cases. Check to see if we can + // still transform it into a select + if (SelectValue == nullptr) { + unsigned FirstPossibleHits = 0, SecondPossibleHits = 0; + ConstantInt *MinCaseFirst = FirstResult->second[0], + *MinCaseSecond = SecondResult->second[0], + *MaxCaseFirst = FirstResult->second[0], + *MaxCaseSecond = SecondResult->second[0]; + AnalyzeSwitchCases(FirstResult->second, KnownZeroCond, KnownOneCond, + KnownZeroFirst, KnownOneFirst, MinCaseFirst, + MaxCaseFirst, FirstPossibleHits); + AnalyzeSwitchCases(SecondResult->second, KnownZeroCond, KnownOneCond, + KnownZeroSecond, KnownOneSecond, MinCaseSecond, + MaxCaseSecond, SecondPossibleHits); + // The default case can trigger if a default value has been found and + // if there are some possible bit combination of the condition value + // that are not covered from the case labels + DefaultCanTrigger = (((1 << (Bits - CondStuckBits)) - + (FirstPossibleHits + SecondPossibleHits)) != 0); + DefaultCanTrigger &= DefaultResult != nullptr; + + SelectValue = ConvertRangeSwitch( + FirstResult->first, SecondResult->first, Cond, DefaultCanTrigger, + MinCaseFirst, MinCaseSecond, MaxCaseFirst, MaxCaseSecond, Builder); + } + + // If we couldn't split the switch results into two ranges of values + // try finding a bit pattern that covers the cases and test on that + if (SelectValue == nullptr) { + SelectValue = ConvertBitPatternSwitch( + FirstResult->first, SecondResult->first, Cond, DefaultCanTrigger, + KnownZeroFirst, KnownOneFirst, KnownZeroSecond, KnownOneSecond, + Builder); + } + // The switch couldn't be converted into a select. + if (SelectValue == nullptr) + return false; + + PHI->addIncoming(SelectValue, SI->getParent()); + + Builder.CreateBr(CommonDest); + + // Remove the switch. + for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) { + BasicBlock *Succ = SI->getSuccessor(i); + + if (Succ == SI->getDefaultDest()) + continue; + Succ->removePredecessor(SI->getParent()); + } + SI->eraseFromParent(); + + return true; +} + /// SwitchToLookupTable - If the switch is only used to initialize one or more /// phi nodes in a common successor block with different constant values, /// replace the switch with lookup tables. @@ -3923,6 +4237,9 @@ if (ForwardSwitchConditionToPHI(SI)) return SimplifyCFG(BB, TTI, DL) | true; + if (SwitchToSelect(SI, Builder, DL)) + return SimplifyCFG(BB, TTI, DL) | true; + if (SwitchToLookupTable(SI, Builder, TTI, DL)) return SimplifyCFG(BB, TTI, DL) | true; Index: test/Transforms/SimplifyCFG/2014-06-19-SwitchToSelectBitPattern.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/2014-06-19-SwitchToSelectBitPattern.ll @@ -0,0 +1,95 @@ +; RUN: opt < %s -simplifycfg -S | FileCheck %s + +; int foo3_with_def(int a) { +; switch (a) { +; case 0: +; return 1; +; case 1: +; return 2; +; case 2: +; return 1; +; case 3: +; return 2; +; default: +; return 10; +; } +; } +; +; int foo3_without_def(int a) { +; a &= 0x6; +; switch (a) { +; case 0: +; return 1; +; case 2: +; return 2; +; case 4: +; return 1; +; case 6: +; return 2; +; default: +; return 10; +; } +; } + +define i32 @foo3_with_def(i32 %a) #0 { +; CHECK-LABEL: @foo3_with_def +; CHECK: switch i32 +entry: + switch i32 %a, label %sw.default [ + i32 0, label %sw.bb + i32 1, label %sw.bb1 + i32 2, label %sw.bb2 + i32 3, label %sw.bb3 + ] + +sw.bb: + br label %return + +sw.bb1: + br label %return + +sw.bb2: + br label %return + +sw.bb3: + br label %return + +sw.default: + br label %return + +return: + %retval.0 = phi i32 [ 10, %sw.default ], [ 2, %sw.bb3 ], [ 1, %sw.bb2 ], [ 2, %sw.bb1 ], [ 1, %sw.bb ] + ret i32 %retval.0 +} + +define i32 @foo3_without_def(i32 %a) #0 { +; CHECK-LABEL: @foo3_without_def +; CHECK: select +entry: + %and = and i32 %a, 6 + switch i32 %and, label %sw.default [ + i32 0, label %sw.bb + i32 2, label %sw.bb1 + i32 4, label %sw.bb2 + i32 6, label %sw.bb3 + ] + +sw.bb: + br label %return + +sw.bb1: + br label %return + +sw.bb2: + br label %return + +sw.bb3: + br label %return + +sw.default: + br label %return + +return: + %retval.0 = phi i32 [ 10, %sw.default ], [ 2, %sw.bb3 ], [ 1, %sw.bb2 ], [ 2, %sw.bb1 ], [ 1, %sw.bb ] + ret i32 %retval.0 +} Index: test/Transforms/SimplifyCFG/2014-06-19-SwitchToSelectRange.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/2014-06-19-SwitchToSelectRange.ll @@ -0,0 +1,71 @@ +; RUN: opt < %s -simplifycfg -S | FileCheck %s + +define i32 @foo2_with_def(i32 %a) #0 { +; CHECK-LABEL: @foo2_with_def +; CHECK-NOT: select +entry: + switch i32 %a, label %sw.default [ + i32 10, label %sw.bb + i32 11, label %sw.bb + i32 12, label %sw.bb + i32 13, label %sw.bb + i32 14, label %sw.bb + i32 15, label %sw.bb + i32 19, label %sw.bb1 + i32 20, label %sw.bb1 + i32 21, label %sw.bb1 + i32 22, label %sw.bb1 + ] + +sw.bb: + br label %return + +sw.bb1: + br label %return + +sw.default: + br label %return + +return: + %retval.0 = phi i32 [ 30, %sw.default ], [ 20, %sw.bb1 ], [ 10, %sw.bb ] + ret i32 %retval.0 +} + +define i32 @foo2_without_def(i32 %a) #0 { +; CHECK-LABEL: @foo2_without_def +; CHECK: select +entry: + %shl = shl i32 %a, 1 + %and = and i32 %shl, 30 + switch i32 %and, label %sw.default [ + i32 0, label %sw.bb + i32 2, label %sw.bb + i32 4, label %sw.bb + i32 6, label %sw.bb + i32 8, label %sw.bb + i32 10, label %sw.bb + i32 12, label %sw.bb + i32 14, label %sw.bb + i32 16, label %sw.bb1 + i32 18, label %sw.bb1 + i32 20, label %sw.bb1 + i32 22, label %sw.bb1 + i32 24, label %sw.bb1 + i32 26, label %sw.bb1 + i32 28, label %sw.bb1 + i32 30, label %sw.bb1 + ] + +sw.bb: + br label %return + +sw.bb1: + br label %return + +sw.default: + br label %return + +return: + %retval.0 = phi i32 [ 30, %sw.default ], [ 20, %sw.bb1 ], [ 10, %sw.bb ] + ret i32 %retval.0 +} Index: test/Transforms/SimplifyCFG/2014-06-19-SwitchToSelectTwoCase.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/2014-06-19-SwitchToSelectTwoCase.ll @@ -0,0 +1,72 @@ +; RUN: opt < %s -simplifycfg -S | FileCheck %s + +; int foo1_with_def(int a) { +; switch(a) { +; case 10: +; return 10; +; case 20: +; return 2; +; } +; return 4; +; } +; +; int foo1_without_def(int a) { +; switch(a) { +; case 10: +; return 10; +; case 20: +; return 2; +; } +; __builtin_unreachable(); +; } + +define i32 @foo1_with_def(i32 %a) #0 { +; CHECK-LABEL: @foo1_with_def +; CHECK: icmp eq i32 +; CHECK-NEXT: select i1 +; CHECK-NEXT: icmp eq i32 +; CHECK-NEXT: select i1 +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: + br label %return + +return: + %retval.0 = phi i32 [ 4, %sw.epilog ], [ 2, %sw.bb1 ], [ 10, %sw.bb ] + ret i32 %retval.0 +} + +define i32 @foo1_without_def(i32 %a) #0 { +; CHECK-LABEL: @foo1_without_def +; CHECK: icmp eq i32 +; CHECK-NEXT: select i1 +; 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 +} Index: test/Transforms/SimplifyCFG/UnreachableEliminate.ll =================================================================== --- test/Transforms/SimplifyCFG/UnreachableEliminate.ll +++ test/Transforms/SimplifyCFG/UnreachableEliminate.ll @@ -48,11 +48,13 @@ ; PR9450 define i32 @test4(i32 %v) { +; CHECK-LABEL: @test4( ; CHECK: entry: -; CHECK-NEXT: switch i32 %v, label %T [ -; CHECK-NEXT: i32 3, label %V -; CHECK-NEXT: i32 2, label %U -; CHECK-NEXT: ] +; CHECK: %switch.selectcmp = icmp eq i32 %v, 3 +; CHECK-NEXT: %switch.select = select i1 %switch.selectcmp, i32 7, i32 2 +; CHECK-NEXT: %switch.selectcmp1 = icmp eq i32 %v, 2 +; CHECK-NEXT: %switch.select2 = select i1 %switch.selectcmp1, i32 1, i32 %switch.select +; CHECK-NEXT: ret i32 %switch.select2 entry: br label %SWITCH 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 @@ -915,6 +915,10 @@ %x = phi i32 [ 3, %sw.default ], [ 7, %sw.bb1 ], [ 9, %entry ] ret i32 %x ; CHECK-LABEL: @twocases( -; CHECK: switch i32 +; CHECK-NOT: switch i32 ; CHECK-NOT: @switch.table +; CHECK: %switch.selectcmp +; CHECK-NEXT: %switch.select +; CHECK-NEXT: %switch.selectcmp1 +; CHECK-NEXT: %switch.select2 }