Index: llvm/lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -5620,12 +5620,13 @@ // 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, PHINode *&PHI, BasicBlock *&CommonDest, - SwitchCaseResultVectorTy &UniqueResults, - Constant *&DefaultResult, const DataLayout &DL, - const TargetTransformInfo &TTI, - uintptr_t MaxUniqueResults, uintptr_t MaxCasesPerResult) { +static bool InitializeUniqueCases(SwitchInst *SI, PHINode *&PHI, + BasicBlock *&CommonDest, + SwitchCaseResultVectorTy &UniqueResults, + Constant *&DefaultResult, + const DataLayout &DL, + const TargetTransformInfo &TTI, + uintptr_t MaxUniqueResults) { for (auto &I : SI->cases()) { ConstantInt *CaseVal = I.getCaseValue(); @@ -5643,10 +5644,6 @@ const uintptr_t NumCasesForResult = MapCaseToResult(CaseVal, UniqueResults, Results.begin()->second); - // Early out if there are too many cases for this result. - if (NumCasesForResult > MaxCasesPerResult) - return false; - // Early out if there are too many unique results. if (UniqueResults.size() > MaxUniqueResults) return false; @@ -5708,15 +5705,47 @@ SelectValue, "switch.select"); } - // Handle the degenerate case where two cases have the same value. - if (ResultVector.size() == 1 && ResultVector[0].second.size() == 2 && - DefaultResult) { - Value *Cmp1 = Builder.CreateICmpEQ( - Condition, ResultVector[0].second[0], "switch.selectcmp.case1"); - Value *Cmp2 = Builder.CreateICmpEQ( - Condition, ResultVector[0].second[1], "switch.selectcmp.case2"); - Value *Cmp = Builder.CreateOr(Cmp1, Cmp2, "switch.selectcmp"); - return Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult); + if (ResultVector.size() == 1 && DefaultResult) { + unsigned CaseCount = ResultVector[0].second.size(); + if (isPowerOf2_32(CaseCount)) { + // switch (a) { + // case 0: + // case 2: + // case 4: + // case 6: + // return 1; ----> %0 = and i32 %a, -7 + // default: %1 = icmp eq i32 %0, 0 + // return 2; %2 = select i1 %1, i32 1, i32 2 + // } + ConstantInt *MinCaseVal = ResultVector[0].second[0]; + APInt BitMask = APInt::getZero(MinCaseVal->getBitWidth()); + for (auto Case : ResultVector[0].second) { + if (Case->getValue().slt(MinCaseVal->getValue())) + MinCaseVal = Case; + } + for (auto Case : ResultVector[0].second) { + BitMask |= (Case->getValue() - MinCaseVal->getValue()); + } + + if (BitMask.countPopulation() == Log2_32(CaseCount)) { + if (!MinCaseVal->isNullValue()) + Condition = Builder.CreateSub(Condition, MinCaseVal); + Value *And = Builder.CreateAnd(Condition, ~BitMask, "switch.and"); + Value *Cmp = Builder.CreateICmpEQ( + And, Constant::getNullValue(And->getType()), "switch.selectcmp"); + return Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult); + } + } + + // Handle the degenerate case where two cases have the same value. + if (ResultVector[0].second.size() == 2) { + Value *Cmp1 = Builder.CreateICmpEQ(Condition, ResultVector[0].second[0], + "switch.selectcmp.case1"); + Value *Cmp2 = Builder.CreateICmpEQ(Condition, ResultVector[0].second[1], + "switch.selectcmp.case2"); + Value *Cmp = Builder.CreateOr(Cmp1, Cmp2, "switch.selectcmp"); + return Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult); + } } return nullptr; @@ -5771,8 +5800,7 @@ SwitchCaseResultVectorTy UniqueResults; // Collect all the cases that will deliver the same value from the switch. if (!InitializeUniqueCases(SI, PHI, CommonDest, UniqueResults, DefaultResult, - DL, TTI, /*MaxUniqueResults*/2, - /*MaxCasesPerResult*/2)) + DL, TTI, /*MaxUniqueResults*/ 2)) return false; assert(PHI != nullptr && "PHI for value select not found"); Index: llvm/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll =================================================================== --- llvm/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll +++ llvm/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll @@ -66,3 +66,158 @@ %retval.0 = phi i32 [ 4, %sw.epilog ], [ 10, %sw.bb ] ret i32 %retval.0 } + +define i1 @mask0(i8 %0) { +; CHECK-LABEL: @mask0( +; CHECK-NEXT: [[TMP2:%.*]] = sub i8 [[TMP0:%.*]], 43 +; CHECK-NEXT: [[SWITCH_AND:%.*]] = and i8 [[TMP2]], -3 +; CHECK-NEXT: [[SWITCH_SELECTCMP:%.*]] = icmp eq i8 [[SWITCH_AND]], 0 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[SWITCH_SELECTCMP]], i1 true, i1 false +; CHECK-NEXT: ret i1 [[TMP3]] +; + switch i8 %0, label %2 [ + i8 43, label %3 + i8 45, label %3 + ] + +2: + br label %3 + +3: + %4 = phi i1 [ false, %2 ], [ true, %1 ], [ true, %1 ] + ret i1 %4 +} + + +define i1 @mask1(i32 %i) { +; CHECK-LABEL: @mask1( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SWITCH_AND:%.*]] = and i32 [[I:%.*]], -7 +; CHECK-NEXT: [[SWITCH_SELECTCMP:%.*]] = icmp eq i32 [[SWITCH_AND]], 0 +; CHECK-NEXT: [[TMP0:%.*]] = select i1 [[SWITCH_SELECTCMP]], i1 true, i1 false +; CHECK-NEXT: ret i1 [[TMP0]] +; +entry: + switch i32 %i, label %lor.rhs [ + i32 0, label %lor.end + i32 2, label %lor.end + i32 4, label %lor.end + i32 6, label %lor.end + ] + +lor.rhs: + br label %lor.end + +lor.end: + %0 = phi i1 [ true, %entry ], [ false, %lor.rhs ], [ true, %entry ], [ true, %entry ], [ true, %entry ] + ret i1 %0 +} + +define i1 @mask2(i32 %i) { +; CHECK-LABEL: @mask2( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SWITCH_AND:%.*]] = and i32 [[I:%.*]], -11 +; CHECK-NEXT: [[SWITCH_SELECTCMP:%.*]] = icmp eq i32 [[SWITCH_AND]], 0 +; CHECK-NEXT: [[TMP0:%.*]] = select i1 [[SWITCH_SELECTCMP]], i1 true, i1 false +; CHECK-NEXT: ret i1 [[TMP0]] +; +entry: + switch i32 %i, label %lor.rhs [ + i32 0, label %lor.end + i32 2, label %lor.end + i32 8, label %lor.end + i32 10, label %lor.end + ] + +lor.rhs: + br label %lor.end + +lor.end: + %0 = phi i1 [ true, %entry ], [ false, %lor.rhs ], [ true, %entry ], [ true, %entry ], [ true, %entry ] + ret i1 %0 +} + +define i1 @mask3(i32 %i) { +; CHECK-LABEL: @mask3( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = sub i32 [[I:%.*]], 2 +; CHECK-NEXT: [[SWITCH_AND:%.*]] = and i32 [[TMP0]], -11 +; CHECK-NEXT: [[SWITCH_SELECTCMP:%.*]] = icmp eq i32 [[SWITCH_AND]], 0 +; CHECK-NEXT: [[TMP1:%.*]] = select i1 [[SWITCH_SELECTCMP]], i1 true, i1 false +; CHECK-NEXT: ret i1 [[TMP1]] +; +entry: + switch i32 %i, label %lor.rhs [ + i32 2, label %lor.end + i32 4, label %lor.end + i32 10, label %lor.end + i32 12, label %lor.end + ] + +lor.rhs: + br label %lor.end + +lor.end: + %0 = phi i1 [ true, %entry ], [ false, %lor.rhs ], [ true, %entry ], [ true, %entry ], [ true, %entry ] + ret i1 %0 +} + +define i1 @mask4_negative(i32 %i) { +; CHECK-LABEL: @mask4_negative( +; CHECK-NEXT: entry: +; CHECK-NEXT: switch i32 [[I:%.*]], label [[LOR_RHS:%.*]] [ +; CHECK-NEXT: i32 1, label [[LOR_END:%.*]] +; CHECK-NEXT: i32 4, label [[LOR_END]] +; CHECK-NEXT: i32 10, label [[LOR_END]] +; CHECK-NEXT: i32 12, label [[LOR_END]] +; CHECK-NEXT: ] +; CHECK: lor.rhs: +; CHECK-NEXT: br label [[LOR_END]] +; CHECK: lor.end: +; CHECK-NEXT: [[TMP0:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ false, [[LOR_RHS]] ], [ true, [[ENTRY]] ], [ true, [[ENTRY]] ], [ true, [[ENTRY]] ] +; CHECK-NEXT: ret i1 [[TMP0]] +; +entry: + switch i32 %i, label %lor.rhs [ + i32 1, label %lor.end + i32 4, label %lor.end + i32 10, label %lor.end + i32 12, label %lor.end + ] + +lor.rhs: + br label %lor.end + +lor.end: + %0 = phi i1 [ true, %entry ], [ false, %lor.rhs ], [ true, %entry ], [ true, %entry ], [ true, %entry ] + ret i1 %0 +} + +define i1 @mask5_negative(i32 %i) { +; CHECK-LABEL: @mask5_negative( +; CHECK-NEXT: entry: +; CHECK-NEXT: switch i32 [[I:%.*]], label [[LOR_RHS:%.*]] [ +; CHECK-NEXT: i32 0, label [[LOR_END:%.*]] +; CHECK-NEXT: i32 2, label [[LOR_END]] +; CHECK-NEXT: i32 4, label [[LOR_END]] +; CHECK-NEXT: ] +; CHECK: lor.rhs: +; CHECK-NEXT: br label [[LOR_END]] +; CHECK: lor.end: +; CHECK-NEXT: [[TMP0:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ false, [[LOR_RHS]] ], [ true, [[ENTRY]] ], [ true, [[ENTRY]] ] +; CHECK-NEXT: ret i1 [[TMP0]] +; +entry: + switch i32 %i, label %lor.rhs [ + i32 0, label %lor.end + i32 2, label %lor.end + i32 4, label %lor.end + ] + +lor.rhs: + br label %lor.end + +lor.end: + %0 = phi i1 [ true, %entry ], [ false, %lor.rhs ], [ true, %entry ], [ true, %entry ] + ret i1 %0 +}