Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -75,6 +75,9 @@ STATISTIC(NumSpeculations, "Number of speculative executed instructions"); namespace { + typedef SmallVector>, 2> + ResultVectorTy; + /// ValueEqualityComparisonCase - Represents a case of a switch. struct ValueEqualityComparisonCase { ConstantInt *Value; @@ -3428,6 +3431,364 @@ return Res.size() > 0; } +// 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, + SmallVectorImpl>> + &UniqueResults, + Constant *&DefaultResult) { + struct CompareConstant { + const Constant *C; + bool operator()(const ResultVectorTy::value_type &t) const { + return t.first == C; + } + CompareConstant(const Constant* c) : C(c) {} + }; + 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 = std::find_if(UniqueResults.begin(), UniqueResults.end(), + CompareConstant(Result.second)); + if (ResultFound == UniqueResults.end()) { + UniqueResults.push_back(std::make_pair(Result.second, + SmallVector(1, CaseVal))); + } else { + // Avoid querying the map again if we already found the result. + ResultFound->second.push_back(CaseVal); + } + + // 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; + } + // Find the default result value + SmallVector, 1> DefaultResults; + BasicBlock *DefaultDest = SI->getDefaultDest(); + GetCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults, + DL); + // If the default value is not found abort unless the default destination + // is unreachable. + DefaultResult = + DefaultResults.size() == 1 ? DefaultResults.begin()->second : nullptr; + BranchInst *BI = dyn_cast(DefaultDest->getTerminator()); + UnreachableInst *UI = dyn_cast(DefaultDest->getTerminator()); + if ((DefaultResult == nullptr && !UI) || + (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) { + MinCase = Cases[0]; + MaxCase = Cases[0]; + // 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 (or two cases + default) +// that produces a result into a value select. +// Example: +// switch (a) { +// case 10: %0 = icmp eq i32 %a, 1 +// return 10; %1 = select i1 %0, i32 10, i32 4 +// case 20: ----> %2 = icmp eq i32 %a, 20 +// return 2; %3 = select i1 %2, i32 2, i32 %1 +// default: +// return 4; +// } +static Value * +ConvertTwoCaseSwitch(ResultVectorTy &ResultVector, + Constant *DefaultResult, Value *Condition, + IRBuilder<> &Builder) { + // If we are selecting between only two cases transform into a simple + // select or a two-way select if default is possible. + if (ResultVector[0].second.size() == 1 && + ResultVector[1].second.size() == 1) { + ConstantInt *const FirstCase = ResultVector[0].second[0]; + ConstantInt *const SecondCase = ResultVector[1].second[0]; + + bool DefaultCanTrigger = (DefaultResult != nullptr); + Value *SelectValue = ResultVector[1].first; + if (DefaultCanTrigger) { + Value *const ValueCompare = + Builder.CreateICmpEQ(Condition, SecondCase, "switch.selectcmp"); + SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first, + DefaultResult, "switch.select"); + } + Value *const ValueCompare = + Builder.CreateICmpEQ(Condition, FirstCase, "switch.selectcmp"); + return Builder.CreateSelect(ValueCompare, ResultVector[0].first, 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. +// +// Example: +// switch (a) { +// case 0: case 2: +// case 4: case 6: +// case 8: case 10: +// case 12: case 14: +// return 10; ----> %0 = icmp ult i32 %a, 15 +// %1 = select i1 %0, i32 10, i32 20 +// case 16: case 18: +// case 20: case 22: +// case 24: case 26: +// case 28: case 30: +// return 20; +// } +static Value * +ConvertRangeSwitch(ResultVectorTy &ResultVector, + 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 ? ResultVector[0].first : ResultVector[1].first; + Value *const SelectRHS = + SecondIsBigger ? ResultVector[1].first : ResultVector[0].first; + 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. +// +// Example: +// a &= 0x6; +// switch (a) { +// case 0: +// return 1; +// case 2: +// return 2; +// case 4: ----> %0 = and i32 %a, 6 +// return 1; %1 = and i32 %0, 2 +// case 6: %2 = icmp eq i32 %1, 0 +// return 2; %3 = select i1 %3, i32 1, i32 2 +// default: +// return 10; +// } +static Value *ConvertBitPatternSwitch(ResultVectorTy &ResultVector, + 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, ResultVector[0].first, + ResultVector[1].first, "switch.select"); + } + + return nullptr; +} + +// RemoveSwitchAfterSelectConversion - Helper function to cleanup a switch +// instruction that has been converted into a select, fixing up PHI nodes and +// basic blocks. +static void RemoveSwitchAfterSelectConversion(SwitchInst *SI, PHINode *PHI, + Value *SelectValue, + BasicBlock *Destination, + IRBuilder<> &Builder) { + PHI->addIncoming(SelectValue, SI->getParent()); + + Builder.CreateBr(Destination); + + // 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(); +} + +/// 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, AssumptionTracker *AT) { + Value *const Cond = SI->getCondition(); + PHINode *PHI = nullptr; + BasicBlock *CommonDest = nullptr; + Type *ResultType; + Constant *DefaultResult; + + ResultVectorTy UniqueResults; + // Collect all the cases that will deliver the same value from the switch. + if (!InitializeUniqueCases(SI, DL, PHI, CommonDest, UniqueResults, + DefaultResult)) + return false; + const unsigned NumOfResults = UniqueResults.size(); + // Selects choose between maximum two values. + if (NumOfResults != 2) + return false; + assert(PHI != nullptr && "PHI for value select not found"); + ResultType = PHI->getType(); + + const unsigned Bits = Cond->getType()->getIntegerBitWidth(); + + APInt KnownZeroCond(Bits, 0), KnownOneCond(Bits, 0); + computeKnownBits(Cond, KnownZeroCond, KnownOneCond, DL, 0, AT, SI); + // 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( + UniqueResults, + DefaultResult, Cond, Builder); + if (SelectValue != nullptr) { + RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, CommonDest, + Builder); + return true; + } + + // The switch has more than only two cases. Check to see if we can + // still transform it into a select + bool DefaultCanTrigger; + APInt KnownZeroFirst(Bits, ~(0ULL)), KnownOneFirst(Bits, ~(0ULL)), + KnownZeroSecond(Bits, ~(0ULL)), KnownOneSecond(Bits, ~(0ULL)); + unsigned FirstPossibleHits = 0, SecondPossibleHits = 0; + ConstantInt *MinCaseFirst = nullptr, *MinCaseSecond = nullptr, + *MaxCaseFirst = nullptr, *MaxCaseSecond = nullptr; + AnalyzeSwitchCases(UniqueResults[0].second, KnownZeroCond, KnownOneCond, + KnownZeroFirst, KnownOneFirst, MinCaseFirst, + MaxCaseFirst, FirstPossibleHits); + AnalyzeSwitchCases(UniqueResults[1].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( + UniqueResults, Cond, DefaultCanTrigger, + MinCaseFirst, MinCaseSecond, + MaxCaseFirst, MaxCaseSecond, Builder); + + if (SelectValue != nullptr) { + RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, CommonDest, + Builder); + return true; + } + + // 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 + SelectValue = ConvertBitPatternSwitch(UniqueResults, + Cond, DefaultCanTrigger, + KnownZeroFirst, KnownOneFirst, KnownZeroSecond, KnownOneSecond, Builder); + + if (SelectValue != nullptr) { + RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, CommonDest, + Builder); + return true; + } + + // The switch couldn't be converted into a select. + return false; +} + namespace { /// SwitchLookupTable - This class represents a lookup table that can be used /// to replace a switch. @@ -3926,9 +4287,12 @@ if (EliminateDeadSwitchCases(SI, DL, AT)) return SimplifyCFG(BB, TTI, DL, AT) | true; - if (ForwardSwitchConditionToPHI(SI)) + if (SwitchToSelect(SI, Builder, DL, AT)) return SimplifyCFG(BB, TTI, DL, AT) | true; + if (ForwardSwitchConditionToPHI(SI)) + return SimplifyCFG(BB, TTI, DL, AT) | true; + if (SwitchToLookupTable(SI, Builder, TTI, DL)) return SimplifyCFG(BB, TTI, DL, AT) | true; 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, 2 +; CHECK-NEXT: %switch.select = select i1 %switch.selectcmp, i32 1, i32 2 +; CHECK-NEXT: %switch.selectcmp1 = icmp eq i32 %v, 3 +; CHECK-NEXT: %switch.select2 = select i1 %switch.selectcmp1, i32 7, 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,8 +915,12 @@ %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 } ; Don't build tables for switches with TLS variables. Index: test/Transforms/SimplifyCFG/switch-to-select-bitpattern.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/switch-to-select-bitpattern.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/switch-to-select-range.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/switch-to-select-range.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/switch-to-select-two-case.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/switch-to-select-two-case.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 +}