Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -3526,6 +3526,34 @@ return true; } +// AnalyzeSwitchCases - Helper function to compute information about switch +// cases, like the minimum and the maximum case. +static void AnalyzeSwitchCases(const SmallVectorImpl &Cases, + const APInt &KnownZeroBitsCond, + const APInt &KnownOneBitsCond, + 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 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. @@ -3568,6 +3596,51 @@ 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; +} + // RemoveSwitchAfterSelectConversion - Helper function to cleanup a switch // instruction that has been converted into a select, fixing up PHI nodes and // basic blocks. @@ -3611,6 +3684,15 @@ 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, @@ -3619,6 +3701,35 @@ 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 + unsigned FirstGroupValidCases = 0, SecondGroupValidCases = 0; + ConstantInt *MinCaseFirst = nullptr, *MinCaseSecond = nullptr, + *MaxCaseFirst = nullptr, *MaxCaseSecond = nullptr; + // Analyze the Switch cases of the two groups, collecting the number of cases + // each groups covers (pessimistically) and which are the minimum and maximum + // case values for each group. + AnalyzeSwitchCases(UniqueResults[0].second, KnownZerosCond, KnownOnesCond, + MinCaseFirst, MaxCaseFirst, FirstGroupValidCases); + AnalyzeSwitchCases(UniqueResults[1].second, KnownZerosCond, KnownOnesCond, + 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; + // Try to convert the switch to a comparison to a pivot value between the two + // groups of cases. + SelectValue = ConvertRangeSwitch( + UniqueResults, Cond, DefaultCanTrigger, + MinCaseFirst, MinCaseSecond, + MaxCaseFirst, MaxCaseSecond, Builder); + if (SelectValue) { + RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, Builder); + return true; + } // The switch couldn't be converted into a select. return false; } Index: test/Transforms/SimplifyCFG/switch-to-select-range.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/switch-to-select-range.ll @@ -0,0 +1,75 @@ +; RUN: opt < %s -simplifycfg -S | FileCheck %s + +; The default case here stops us to be able to optimize, +; because the range has holes. +define i32 @foo2_with_default(i32 %a) { +; CHECK-LABEL: @foo2_with_default +; 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 +} + +; The default case here is unreachable, we detect that and so we can +; optimize to a select. +define i32 @foo2_without_default(i32 %a) { +; CHECK-LABEL: @foo2_without_default +; CHECK: %switch.rangeselect = select i1 %switch.rangesub, i32 20, i32 10 +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 +}