Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -75,6 +75,16 @@ STATISTIC(NumSpeculations, "Number of speculative executed instructions"); namespace { + // The first field contains the value that the switch produces when a certain + // case group is selected, and the second field is a vector containing the cases + // composing the case group. + typedef SmallVector>, 2> + SwitchCaseResultVectorTy; + // The first field contains the phi node that generates a result of the switch + // and the second field contains the value generated for a certain case in the switch + // for that PHI. + typedef SmallVector, 4> SwitchCaseResultsTy; + /// ValueEqualityComparisonCase - Represents a case of a switch. struct ValueEqualityComparisonCase { ConstantInt *Value; @@ -3428,6 +3438,366 @@ return Res.size() > 0; } +// MapCaseToResult - This is an helper function used to +// add CaseVal to the list of cases that generate Result. +static void MapCaseToResult(ConstantInt *CaseVal, + SwitchCaseResultVectorTy &UniqueResults, + Constant *Result) { + for (auto &I : UniqueResults) { + if (I.first == Result) { + I.second.push_back(CaseVal); + return; + } + } + UniqueResults.push_back(std::make_pair(Result, + SmallVector(1, CaseVal))); +} + +// 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, + SwitchCaseResultVectorTy &UniqueResults, + Constant *&DefaultResult) { + for (auto &I : SI->cases()) { + ConstantInt *CaseVal = I.getCaseValue(); + + // Resulting value at phi nodes for this case value. + SwitchCaseResultsTy Results; + if (!GetCaseResults(SI, CaseVal, I.getCaseSuccessor(), &CommonDest, Results, + DL)) + return false; + + // Only one value per case is permitted + if (Results.size() > 1) + return false; + MapCaseToResult(CaseVal, UniqueResults, Results.begin()->second); + + // Check the PHI consistency. + if (!PHI) + PHI = Results[0].first; + else if (PHI != Results[0].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; + if ((!DefaultResult && + !isa(DefaultDest->getFirstNonPHIOrDbg()))) + 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. +// KnownBitsCond parameters are a bit vector containing respectively the bits +// that are known to be one or zero of the condition of the switch. +// KnownBitsCase are instead the bits known to be one or zero for all the case +// values contained in the vector of cases passed as input. +static void AnalyzeSwitchCases(const SmallVectorImpl &Cases, + const APInt &KnownZeroBitsCond, + const APInt &KnownOneBitsCond, + APInt &KnownZeroBitsCase, + APInt &KnownOneBitsCase, ConstantInt *&MinCase, + ConstantInt *&MaxCase, unsigned &ValidCases) { + 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() & KnownZeroBitsCond) == KnownZeroBitsCond) && + ((Case->getValue() & KnownOneBitsCond) == KnownOneBitsCond); + + // Increment the number of cases covered by + // the condition pattern in the group. + if (CaseMatchesCondPattern) + ++ValidCases; + + // Compute the known ones and zeros of this case group. + KnownZeroBitsCase &= ~(Case->getValue()); + KnownOneBitsCase &= Case->getValue(); + // Compute the minimum and maximum case. + 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, 10 +// 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(const SwitchCaseResultVectorTy &ResultVector, + Constant *DefaultResult, Value *Condition, + IRBuilder<> &Builder) { + assert(ResultVector.size() == 2 && + "We should have exactly two unique results at this point"); + // 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; + 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(const SwitchCaseResultVectorTy &ResultVector, + Value *Condition, + bool DefaultCanTrigger, ConstantInt *MinCaseFirst, + ConstantInt *MinCaseSecond, ConstantInt *MaxCaseFirst, + ConstantInt *MaxCaseSecond, IRBuilder<> &Builder) { + const bool FirstIsBigger = + MinCaseFirst->getValue().sgt(MaxCaseSecond->getValue()); + const bool SecondIsBigger = + MinCaseSecond->getValue().sgt(MaxCaseFirst->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.CreateICmpSGT(Condition, Pivot, "switch.rangesub"); + return Builder.CreateSelect(ValueCompare, SelectRHS, SelectLHS, + "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(const SwitchCaseResultVectorTy &ResultVector, + Value *Condition, + bool DefaultCanTrigger, const APInt &FirstResultGroupZeroBits, + const APInt &FirstResultGroupOneBits, + const APInt &SecondResultGroupZeroBits, + const APInt &SecondResultGroupOneBits, IRBuilder<> &Builder) { + + if (DefaultCanTrigger) + return nullptr; + // FirstResultGroupSelectBits and SecondResultGroupSelectBits + // are bitvectors containing the bits that are always one + // in a group of case labels and always zero in the other + APInt FirstResultGroupSelectBits = FirstResultGroupOneBits & + SecondResultGroupZeroBits; + APInt SecondResultGroupSelectBits = SecondResultGroupOneBits & + FirstResultGroupZeroBits; + // If there is no default case and we have unambiguous + // patterns do it with one select and one compare. + if (FirstResultGroupSelectBits != 0 || SecondResultGroupSelectBits != 0) { + Value *ValueCompare = nullptr; + // The comparison checks for ones that are always present in + // one of the groups that are always zero in the other. + if (FirstResultGroupSelectBits != 0) { + ConstantInt *const MaskValue = + ConstantInt::get(Condition->getContext(), FirstResultGroupSelectBits); + ValueCompare = + Builder.CreateAnd(Condition, MaskValue, "switch.selectmask"); + ValueCompare = Builder.CreateICmpNE( + ValueCompare, ConstantInt::get(Condition->getType(), 0), + "switch.selectcmp"); + } else { + assert(SecondResultGroupSelectBits != 0 && + "One of the two select bit patterns should be different from zero"); + ConstantInt *const MaskValue = + ConstantInt::get(Condition->getContext(), SecondResultGroupSelectBits); + 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, + IRBuilder<> &Builder) { + BasicBlock *SelectBB = SI->getParent(); + if (PHI->getBasicBlockIndex(SelectBB) >= 0) + PHI->removeIncomingValue(SelectBB); + PHI->addIncoming(SelectValue, SelectBB); + + Builder.CreateBr(PHI->getParent()); + + // Remove the switch. + for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) { + BasicBlock *Succ = SI->getSuccessor(i); + + if (Succ == PHI->getParent()) + continue; + Succ->removePredecessor(SelectBB); + } + 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; + Constant *DefaultResult; + SwitchCaseResultVectorTy 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 maximum two values. + if (UniqueResults.size() != 2) + return false; + assert(PHI != nullptr && "PHI for value select not found"); + + const unsigned BitWidth = Cond->getType()->getIntegerBitWidth(); + + APInt KnownZerosCond(BitWidth, 0), KnownOnesCond(BitWidth, 0); + // Compute known bits of the Condition of the Switch statement. + computeKnownBits(Cond, KnownZerosCond, KnownOnesCond, DL, 0, AT, SI); + // Number of bits that are fixed in the switch condition value. + const unsigned NumKnownCondBits = + (KnownZerosCond | KnownOnesCond).countPopulation(); + + Builder.SetInsertPoint(SI); + Value *SelectValue = ConvertTwoCaseSwitch( + UniqueResults, + DefaultResult, Cond, Builder); + if (SelectValue) { + RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, Builder); + return true; + } + + // The switch has more than only two cases. Check to see if we can + // still transform it into a select + APInt FirstResultGroupZeroBits = APInt::getAllOnesValue(BitWidth); + APInt FirstResultGroupOneBits = APInt::getAllOnesValue(BitWidth); + APInt SecondResultGroupZeroBits = APInt::getAllOnesValue(BitWidth); + APInt SecondResultGroupOneBits = APInt::getAllOnesValue(BitWidth); + unsigned FirstGroupValidCases = 0, SecondGroupValidCases = 0; + ConstantInt *MinCaseFirst = nullptr, *MinCaseSecond = nullptr, + *MaxCaseFirst = nullptr, *MaxCaseSecond = nullptr; + AnalyzeSwitchCases(UniqueResults[0].second, KnownZerosCond, KnownOnesCond, + FirstResultGroupZeroBits, FirstResultGroupOneBits, + MinCaseFirst, MaxCaseFirst, FirstGroupValidCases); + AnalyzeSwitchCases(UniqueResults[1].second, KnownZerosCond, KnownOnesCond, + SecondResultGroupZeroBits, SecondResultGroupOneBits, + MinCaseSecond, MaxCaseSecond, SecondGroupValidCases); + // 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 << (BitWidth - NumKnownCondBits)) - + (FirstGroupValidCases + SecondGroupValidCases)) != 0); + DefaultCanTrigger &= (bool)DefaultResult; + + SelectValue = ConvertRangeSwitch( + UniqueResults, Cond, DefaultCanTrigger, + MinCaseFirst, MinCaseSecond, + MaxCaseFirst, MaxCaseSecond, Builder); + + if (SelectValue) { + RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, 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, + FirstResultGroupZeroBits, FirstResultGroupOneBits, + SecondResultGroupZeroBits, SecondResultGroupOneBits, Builder); + + if (SelectValue) { + RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, 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 +4296,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 @@ -47,7 +47,7 @@ } ; PR9450 -define i32 @test4(i32 %v) { +define i32 @test4(i32 %v, i32 %w) { ; CHECK: entry: ; CHECK-NEXT: switch i32 %v, label %T [ ; CHECK-NEXT: i32 3, label %V @@ -67,7 +67,7 @@ default: unreachable U: - ret i32 1 + ret i32 %w T: ret i32 2 } 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,144 @@ +; RUN: opt < %s -simplifycfg -S | FileCheck %s + +; int foo3_with_default(int a) { +; switch (a) { +; case 0: +; return 1; +; case 1: +; return 2; +; case 2: +; return 1; +; case 3: +; return 2; +; default: +; return 10; +; } +; } +; +; This switch cannot be transformed , because the algorithm +; doesn't handle cases with reachable default cases. + +define i32 @foo3_with_default(i32 %a) { +; CHECK-LABEL: @foo3_with_default +; 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 +} + +; int foo3_without_default(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; +; } +; } +; +; The default in this switch case is unreachable. +; This is detected and the switch is then processed. + +define i32 @foo3_without_default(i32 %a) { +; CHECK-LABEL: @foo3_without_default +; CHECK: %switch.select = select i1 %switch.selectcmp, i32 1, i32 2 +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 +} + +; int foo3_explicit_without_default(int a) { +; a &= 0x6; +; switch (a) { +; case 0: +; return 1; +; case 2: +; return 2; +; case 6: +; return 2; +; case 4: +; return 1; +; } +; } +; +; The default in this switch case is not present and the result is undef +; This is detected and the switch is then processed + +define i32 @foo3_explicit_without_default(i32 %a) { + %1 = and i32 %a, 6 + switch i32 %1, label %6 [ + i32 0, label %2 + i32 2, label %3 + i32 6, label %4 + i32 4, label %5 + ] + +;