diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp --- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -169,7 +169,7 @@ cl::desc("Allow SimplifyCFG to merge invokes together when appropriate")); static cl::opt MaxSwitchCasesPerResult( - "max-switch-cases-per-result", cl::Hidden, cl::init(2), + "max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select")); STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps"); @@ -5710,15 +5710,46 @@ } // Handle the degenerate case where two cases have the same result value. - if (ResultVector.size() == 1 && ResultVector[0].second.size() == 2 && - DefaultResult) { + if (ResultVector.size() == 1 && DefaultResult) { ArrayRef CaseValues = ResultVector[0].second; - Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0], - "switch.selectcmp.case1"); - Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1], - "switch.selectcmp.case2"); - Value *Cmp = Builder.CreateOr(Cmp1, Cmp2, "switch.selectcmp"); - return Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult); + unsigned CaseCount = CaseValues.size(); + // n bits group cases map to the same result: + // case 0,4 -> Cond & 0b1..1011 == 0 ? result : default + // case 0,2,4,6 -> Cond & 0b1..1001 == 0 ? result : default + // case 0,2,8,10 -> Cond & 0b1..0101 == 0 ? result : default + if (isPowerOf2_32(CaseCount)) { + ConstantInt *MinCaseVal = CaseValues[0]; + // Find mininal value. + for (auto Case : CaseValues) + if (Case->getValue().slt(MinCaseVal->getValue())) + MinCaseVal = Case; + + // Mark the bits case number touched. + APInt BitMask = APInt::getZero(MinCaseVal->getBitWidth()); + for (auto Case : CaseValues) + BitMask |= (Case->getValue() - MinCaseVal->getValue()); + + // Check if cases with the same result can cover all number + // in touched bits. + 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 (CaseValues.size() == 2) { + Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0], + "switch.selectcmp.case1"); + Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1], + "switch.selectcmp.case2"); + Value *Cmp = Builder.CreateOr(Cmp1, Cmp2, "switch.selectcmp"); + return Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult); + } } return nullptr; diff --git a/llvm/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll b/llvm/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll --- a/llvm/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll +++ b/llvm/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll @@ -69,9 +69,8 @@ define i1 @switch_to_select_same2_case_results_different_default(i8 %0) { ; CHECK-LABEL: @switch_to_select_same2_case_results_different_default( -; CHECK-NEXT: [[SWITCH_SELECTCMP_CASE1:%.*]] = icmp eq i8 [[TMP0:%.*]], 4 -; CHECK-NEXT: [[SWITCH_SELECTCMP_CASE2:%.*]] = icmp eq i8 [[TMP0]], 0 -; CHECK-NEXT: [[SWITCH_SELECTCMP:%.*]] = or i1 [[SWITCH_SELECTCMP_CASE1]], [[SWITCH_SELECTCMP_CASE2]] +; CHECK-NEXT: [[SWITCH_AND:%.*]] = and i8 [[TMP0:%.*]], -5 +; CHECK-NEXT: [[SWITCH_SELECTCMP:%.*]] = icmp eq i8 [[SWITCH_AND]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = select i1 [[SWITCH_SELECTCMP]], i1 true, i1 false ; CHECK-NEXT: ret i1 [[TMP2]] ; @@ -90,11 +89,11 @@ define i1 @switch_to_select_same2_case_results_different_default_and_positive_offset_for_case(i8 %0) { ; CHECK-LABEL: @switch_to_select_same2_case_results_different_default_and_positive_offset_for_case( -; CHECK-NEXT: [[SWITCH_SELECTCMP_CASE1:%.*]] = icmp eq i8 [[TMP0:%.*]], 43 -; CHECK-NEXT: [[SWITCH_SELECTCMP_CASE2:%.*]] = icmp eq i8 [[TMP0]], 45 -; CHECK-NEXT: [[SWITCH_SELECTCMP:%.*]] = or i1 [[SWITCH_SELECTCMP_CASE1]], [[SWITCH_SELECTCMP_CASE2]] -; CHECK-NEXT: [[TMP2:%.*]] = select i1 [[SWITCH_SELECTCMP]], i1 true, i1 false -; CHECK-NEXT: ret i1 [[TMP2]] +; 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 @@ -112,11 +111,11 @@ define i8 @switch_to_select_same2_case_results_different_default_and_negative_offset_for_case(i32 %i) { ; CHECK-LABEL: @switch_to_select_same2_case_results_different_default_and_negative_offset_for_case( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[SWITCH_SELECTCMP_CASE1:%.*]] = icmp eq i32 [[I:%.*]], -3 -; CHECK-NEXT: [[SWITCH_SELECTCMP_CASE2:%.*]] = icmp eq i32 [[I]], -5 -; CHECK-NEXT: [[SWITCH_SELECTCMP:%.*]] = or i1 [[SWITCH_SELECTCMP_CASE1]], [[SWITCH_SELECTCMP_CASE2]] -; CHECK-NEXT: [[TMP0:%.*]] = select i1 [[SWITCH_SELECTCMP]], i8 3, i8 42 -; CHECK-NEXT: ret i8 [[TMP0]] +; CHECK-NEXT: [[TMP0:%.*]] = sub i32 [[I:%.*]], -5 +; CHECK-NEXT: [[SWITCH_AND:%.*]] = and i32 [[TMP0]], -3 +; CHECK-NEXT: [[SWITCH_SELECTCMP:%.*]] = icmp eq i32 [[SWITCH_AND]], 0 +; CHECK-NEXT: [[TMP1:%.*]] = select i1 [[SWITCH_SELECTCMP]], i8 3, i8 42 +; CHECK-NEXT: ret i8 [[TMP1]] ; entry: switch i32 %i, label %default [ @@ -135,16 +134,9 @@ define i1 @switch_to_select_same4_case_results_different_default(i32 %i) { ; CHECK-LABEL: @switch_to_select_same4_case_results_different_default( ; 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: i32 6, 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: [[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: @@ -166,16 +158,9 @@ define i1 @switch_to_select_same4_case_results_different_default_alt_bitmask(i32 %i) { ; CHECK-LABEL: @switch_to_select_same4_case_results_different_default_alt_bitmask( ; 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 8, label [[LOR_END]] -; CHECK-NEXT: i32 10, 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: [[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: @@ -197,17 +182,11 @@ define i1 @switch_to_select_same4_case_results_different_default_positive_offset(i32 %i) { ; CHECK-LABEL: @switch_to_select_same4_case_results_different_default_positive_offset( ; CHECK-NEXT: entry: -; CHECK-NEXT: switch i32 [[I:%.*]], label [[LOR_RHS:%.*]] [ -; CHECK-NEXT: i32 2, 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]] +; 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 [ @@ -285,6 +264,7 @@ ret i1 %0 } +; TODO: we can produce the optimal code when there is no default also define i8 @switch_to_select_two_case_results_no_default(i32 %i) { ; CHECK-LABEL: @switch_to_select_two_case_results_no_default( ; CHECK-NEXT: entry: