From 9bad7de9a3fb844f1ca2965f35d0c2a3d1e11775 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Sun, 4 Apr 2021 10:49:59 +0200 Subject: [PATCH] [SimplifyCFG] Handle two equal cases in switch to select When converting a switch with two cases and a default into a select, also handle the denegerate case where two cases have the same value. Generate this case directly as %or = or i1 %cmp1, %cmp2 %res = select i1 %or, i32 %val, i32 %default rather than %sel1 = select i1 %cmp1, i32 %val, i32 %default %res = select i1 %cmp2, i32 %val, i32 %sel1 as InstCombine is going to canonicalize to the former anyway. --- llvm/lib/Transforms/Utils/SimplifyCFG.cpp | 24 ++++++++++++++-------- .../Transforms/PhaseOrdering/partialord-ule.ll | 17 ++------------- .../SimplifyCFG/switch-to-select-two-case.ll | 14 +++++-------- 3 files changed, 23 insertions(+), 32 deletions(-) diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp index 9a5e864..7ffb2c1 100644 --- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -5287,11 +5287,9 @@ InitializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, 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 && + if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 && ResultVector[1].second.size() == 1) { ConstantInt *const FirstCase = ResultVector[0].second[0]; ConstantInt *const SecondCase = ResultVector[1].second[0]; @@ -5310,6 +5308,17 @@ static Value *ConvertTwoCaseSwitch(const SwitchCaseResultVectorTy &ResultVector, 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); + } + return nullptr; } @@ -5334,13 +5343,14 @@ static void RemoveSwitchAfterSelectConversion(SwitchInst *SI, PHINode *PHI, PHI->removeIncomingValue(SelectBB); PHI->addIncoming(SelectValue, SelectBB); + SmallPtrSet RemovedSuccessors; for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) { BasicBlock *Succ = SI->getSuccessor(i); if (Succ == DestBB) continue; Succ->removePredecessor(SelectBB); - if (DTU) + if (DTU && RemovedSuccessors.insert(Succ).second) Updates.push_back({DominatorTree::Delete, SelectBB, Succ}); } SI->eraseFromParent(); @@ -5361,10 +5371,8 @@ static bool switchToSelect(SwitchInst *SI, IRBuilder<> &Builder, SwitchCaseResultVectorTy UniqueResults; // Collect all the cases that will deliver the same value from the switch. if (!InitializeUniqueCases(SI, PHI, CommonDest, UniqueResults, DefaultResult, - DL, TTI, 2, 1)) - return false; - // Selects choose between maximum two values. - if (UniqueResults.size() != 2) + DL, TTI, /*MaxUniqueResults*/2, + /*MaxCasesPerResult*/2)) return false; assert(PHI != nullptr && "PHI for value select not found"); diff --git a/llvm/test/Transforms/PhaseOrdering/partialord-ule.ll b/llvm/test/Transforms/PhaseOrdering/partialord-ule.ll index 5ad1905..23a82c2 100644 --- a/llvm/test/Transforms/PhaseOrdering/partialord-ule.ll +++ b/llvm/test/Transforms/PhaseOrdering/partialord-ule.ll @@ -6,21 +6,8 @@ define i1 @ule(i32 %a, i32 %b) { ; CHECK-LABEL: @ule( ; CHECK-NEXT: start: -; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[CMP2:%.*]] = icmp ult i32 [[A]], [[B]] -; CHECK-NEXT: [[CMP3:%.*]] = icmp ne i32 [[A]], [[B]] -; CHECK-NEXT: [[ZEXT:%.*]] = zext i1 [[CMP3]] to i64 -; CHECK-NEXT: [[SEL1:%.*]] = select i1 [[CMP2]], i64 -1, i64 [[ZEXT]] -; CHECK-NEXT: [[SEL2:%.*]] = select i1 [[CMP1]], i64 0, i64 [[SEL1]] -; CHECK-NEXT: switch i64 [[SEL2]], label [[EXIT:%.*]] [ -; CHECK-NEXT: i64 -1, label [[BB:%.*]] -; CHECK-NEXT: i64 0, label [[BB]] -; CHECK-NEXT: ] -; CHECK: bb: -; CHECK-NEXT: br label [[EXIT]] -; CHECK: exit: -; CHECK-NEXT: [[RES:%.*]] = phi i1 [ true, [[BB]] ], [ false, [[START:%.*]] ] -; CHECK-NEXT: ret i1 [[RES]] +; CHECK-NEXT: [[DOTNOT:%.*]] = icmp ule i32 [[A:%.*]], [[B:%.*]] +; CHECK-NEXT: ret i1 [[DOTNOT]] ; start: %cmp1 = icmp eq i32 %a, %b diff --git a/llvm/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll b/llvm/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll index 5ac7284..8abcfd5 100644 --- a/llvm/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll +++ b/llvm/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll @@ -44,15 +44,11 @@ return: define i32 @same_value(i32 %a) { ; CHECK-LABEL: @same_value( ; CHECK-NEXT: entry: -; CHECK-NEXT: switch i32 [[A:%.*]], label [[SW_EPILOG:%.*]] [ -; CHECK-NEXT: i32 10, label [[RETURN:%.*]] -; CHECK-NEXT: i32 20, label [[RETURN]] -; CHECK-NEXT: ] -; CHECK: sw.epilog: -; CHECK-NEXT: br label [[RETURN]] -; CHECK: return: -; CHECK-NEXT: [[RETVAL_0:%.*]] = phi i32 [ 4, [[SW_EPILOG]] ], [ 10, [[ENTRY:%.*]] ], [ 10, [[ENTRY]] ] -; CHECK-NEXT: ret i32 [[RETVAL_0]] +; CHECK-NEXT: [[SWITCH_SELECTCMP_CASE1:%.*]] = icmp eq i32 [[A:%.*]], 10 +; CHECK-NEXT: [[SWITCH_SELECTCMP_CASE2:%.*]] = icmp eq i32 [[A]], 20 +; CHECK-NEXT: [[SWITCH_SELECTCMP:%.*]] = or i1 [[SWITCH_SELECTCMP_CASE1]], [[SWITCH_SELECTCMP_CASE2]] +; CHECK-NEXT: [[TMP0:%.*]] = select i1 [[SWITCH_SELECTCMP]], i32 10, i32 4 +; CHECK-NEXT: ret i32 [[TMP0]] ; entry: switch i32 %a, label %sw.epilog [ -- 2.7.4