Index: llvm/lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -281,6 +281,8 @@ bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select); bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI); bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder); + bool MergePhisInSwitch(SwitchInst* SI, IRBuilder<>& Builder); + public: SimplifyCFGOpt(const TargetTransformInfo &TTI, DomTreeUpdater *DTU, @@ -6744,6 +6746,107 @@ return true; } +/// Try to transform a switch that has phi of phi in branches +/// to the one with only one phi. +/// +/// A switch such as: +/// +/// switch(i) { +/// case 0: br case 2 +/// case 1: br case 2 +/// case 2: phi(case 0, case 1, entry) ; br case 3 +/// case 3: phi(case 2 %phi, entry) ; br end +/// } +/// +/// can be folded into: +/// +/// switch(i) { +/// case 0: br case 3 +/// case 1: br case 3 +/// case 2: br case 3 +/// case 3: phi(case 0, case 1, case 2, entry) ; br end +/// } +/// +/// This converts a complex switch into a regular switch that +/// has a common destination + +bool SimplifyCFGOpt::MergePhisInSwitch(SwitchInst* SI, IRBuilder<>& Builder){ + SmallPtrSet CaseBBs; + + for (const auto &Case : SI->cases()) { + CaseBBs.insert(Case.getCaseSuccessor()); + } + + for (BasicBlock *CaseBB : CaseBBs) { + BasicBlock *SuccBB = CaseBB->getSingleSuccessor(); + + // CaseBB is a Basicblock with only phis and terminator. + // SuccBB is the single successor of CaseBB. + // Avoid infinite loop + if (!SuccBB || !CaseBBs.contains(SuccBB) || SuccBB == CaseBB || + CaseBB->phis().empty() || SuccBB->phis().empty() || + CaseBB->getFirstNonPHI() != CaseBB->getTerminator()) + continue; + + bool IsMatched = true; + SmallPtrSet PredBBs; + // CaseBB is the single successor of its predecessors except switch block. + for (BasicBlock *PredBB : predecessors(CaseBB)) { + if (!PredBB->getSingleSuccessor() && !CaseBBs.contains(PredBB) && + PredBB != SI->getParent()) { + IsMatched = false; + break; + } + + if (PredBB != SI->getParent()) + PredBBs.insert(PredBB); + } + + if (!IsMatched) + continue; + + for (PHINode &SuccPhi : SuccBB->phis()) { + auto *CasePhi = + dyn_cast(SuccPhi.getIncomingValueForBlock(CaseBB)); + if (!CasePhi || CasePhi->getParent() != CaseBB) { + IsMatched = false; + break; + } + } + + if (!IsMatched) + continue; + + // CaseBB must be a BasicBlock with only phis and terminator. + // Merge the phis of CaseBB into the phis of SuccBB + for (PHINode &SuccPhi : SuccBB->phis()) { + auto *CasePhi = cast(SuccPhi.getIncomingValueForBlock(CaseBB)); + for (auto *PredBB : PredBBs) { + cast(PredBB->getTerminator())->setSuccessor(0, SuccBB); + SuccPhi.addIncoming(CasePhi->getIncomingValueForBlock(PredBB), PredBB); + } + SuccPhi.setIncomingValueForBlock( + CaseBB, CasePhi->getIncomingValueForBlock(SI->getParent())); + // Note: one phi of CaseBB can be used by multiple phis of SuccBB. + // Therefore, we need to erase CasePhi when it's not used + if (!CasePhi->hasNUsesOrMore(1)) + CasePhi->eraseFromParent(); + } + + if (DTU) { + std::vector Updates; + Updates.reserve(PredBBs.size()); + for (auto *PredBB : PredBBs) + Updates.push_back({DominatorTree::Insert, PredBB, SuccBB}); + DTU->applyUpdates(Updates); + } + + return true; + } + + return false; +} + bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) { BasicBlock *BB = SI->getParent(); @@ -6782,6 +6885,9 @@ if (Options.ForwardSwitchCondToPhi && ForwardSwitchConditionToPHI(SI)) return requestResimplify(); + if (MergePhisInSwitch(SI, Builder)) + return requestResimplify(); + // The conversion from switch to lookup tables results in difficult-to-analyze // code and makes pruning branches much harder. This is a problem if the // switch expression itself can still be restricted as a result of inlining or Index: llvm/test/Transforms/SimplifyCFG/merge-phis-in-switch.ll =================================================================== --- llvm/test/Transforms/SimplifyCFG/merge-phis-in-switch.ll +++ llvm/test/Transforms/SimplifyCFG/merge-phis-in-switch.ll @@ -17,12 +17,11 @@ ; CHECK: unreachable: ; CHECK-NEXT: unreachable ; CHECK: case1: -; CHECK-NEXT: br label [[CASE01]] +; CHECK-NEXT: br label [[END]] ; CHECK: case01: -; CHECK-NEXT: [[PHI1:%.*]] = phi i8 [ 2, [[CASE1]] ], [ 1, [[START:%.*]] ] ; CHECK-NEXT: br label [[END]] ; CHECK: end: -; CHECK-NEXT: [[PHI2:%.*]] = phi i8 [ [[PHI1]], [[CASE01]] ], [ 3, [[START]] ] +; CHECK-NEXT: [[PHI2:%.*]] = phi i8 [ 1, [[CASE01]] ], [ 3, [[START:%.*]] ], [ 2, [[CASE1]] ] ; CHECK-NEXT: ret i8 [[PHI2]] ; start: @@ -58,14 +57,13 @@ ; CHECK: unreachable: ; CHECK-NEXT: unreachable ; CHECK: case1: -; CHECK-NEXT: br label [[CASE012]] +; CHECK-NEXT: br label [[END]] ; CHECK: case2: -; CHECK-NEXT: br label [[CASE012]] +; CHECK-NEXT: br label [[END]] ; CHECK: case012: -; CHECK-NEXT: [[PHI1:%.*]] = phi i8 [ 3, [[CASE2]] ], [ 2, [[CASE1]] ], [ 1, [[START:%.*]] ] ; CHECK-NEXT: br label [[END]] ; CHECK: end: -; CHECK-NEXT: [[PHI2:%.*]] = phi i8 [ [[PHI1]], [[CASE012]] ], [ 4, [[START]] ] +; CHECK-NEXT: [[PHI2:%.*]] = phi i8 [ 1, [[CASE012]] ], [ 4, [[START:%.*]] ], [ 3, [[CASE2]] ], [ 2, [[CASE1]] ] ; CHECK-NEXT: ret i8 [[PHI2]] ; start: @@ -105,17 +103,15 @@ ; CHECK: unreachable: ; CHECK-NEXT: unreachable ; CHECK: case1: -; CHECK-NEXT: br label [[CASE012]] +; CHECK-NEXT: br label [[END]] ; CHECK: case2: -; CHECK-NEXT: br label [[CASE012]] +; CHECK-NEXT: br label [[END]] ; CHECK: case012: -; CHECK-NEXT: [[PHI1_1:%.*]] = phi i8 [ 3, [[CASE2]] ], [ 2, [[CASE1]] ], [ 1, [[START:%.*]] ] -; CHECK-NEXT: [[PHI1_2:%.*]] = phi i8 [ 6, [[CASE2]] ], [ 5, [[CASE1]] ], [ 4, [[START]] ] ; CHECK-NEXT: br label [[END]] ; CHECK: end: -; CHECK-NEXT: [[PHI2_1:%.*]] = phi i8 [ [[PHI1_1]], [[CASE012]] ], [ 4, [[START]] ] -; CHECK-NEXT: [[PHI2_2:%.*]] = phi i8 [ [[PHI1_1]], [[CASE012]] ], [ 5, [[START]] ] -; CHECK-NEXT: [[PHI2_3:%.*]] = phi i8 [ [[PHI1_2]], [[CASE012]] ], [ 3, [[START]] ] +; CHECK-NEXT: [[PHI2_1:%.*]] = phi i8 [ 1, [[CASE012]] ], [ 4, [[START:%.*]] ], [ 3, [[CASE2]] ], [ 2, [[CASE1]] ] +; CHECK-NEXT: [[PHI2_2:%.*]] = phi i8 [ 1, [[CASE012]] ], [ 5, [[START]] ], [ 3, [[CASE2]] ], [ 2, [[CASE1]] ] +; CHECK-NEXT: [[PHI2_3:%.*]] = phi i8 [ 4, [[CASE012]] ], [ 3, [[START]] ], [ 6, [[CASE2]] ], [ 5, [[CASE1]] ] ; CHECK-NEXT: call void @use(i8 [[PHI2_1]]) ; CHECK-NEXT: call void @use(i8 [[PHI2_2]]) ; CHECK-NEXT: call void @use(i8 [[PHI2_3]]) @@ -166,19 +162,17 @@ ; CHECK: unreachable: ; CHECK-NEXT: unreachable ; CHECK: case0: -; CHECK-NEXT: br label [[CASE0123]] +; CHECK-NEXT: br label [[END]] ; CHECK: case1: -; CHECK-NEXT: br label [[CASE0123]] +; CHECK-NEXT: br label [[END]] ; CHECK: case2: -; CHECK-NEXT: br label [[CASE0123]] +; CHECK-NEXT: br label [[END]] ; CHECK: case0123: -; CHECK-NEXT: [[PHI1:%.*]] = phi i8 [ 4, [[START:%.*]] ], [ 3, [[CASE2]] ], [ 2, [[CASE1]] ], [ 1, [[CASE0]] ] -; CHECK-NEXT: br label [[CASE01234]] +; CHECK-NEXT: br label [[END]] ; CHECK: case01234: -; CHECK-NEXT: [[PHI2:%.*]] = phi i8 [ [[PHI1]], [[CASE0123]] ], [ 5, [[START]] ] ; CHECK-NEXT: br label [[END]] ; CHECK: end: -; CHECK-NEXT: [[PHI3:%.*]] = phi i8 [ [[PHI2]], [[CASE01234]] ], [ 6, [[START]] ] +; CHECK-NEXT: [[PHI3:%.*]] = phi i8 [ 5, [[CASE01234]] ], [ 6, [[START:%.*]] ], [ 1, [[CASE0]] ], [ 2, [[CASE1]] ], [ 3, [[CASE2]] ], [ 4, [[CASE0123]] ] ; CHECK-NEXT: ret i8 [[PHI3]] ; start: @@ -231,21 +225,19 @@ ; CHECK: unreachable: ; CHECK-NEXT: unreachable ; CHECK: case0: -; CHECK-NEXT: br label [[CASE012]] +; CHECK-NEXT: br label [[CASE0123456]] ; CHECK: case1: -; CHECK-NEXT: br label [[CASE012]] +; CHECK-NEXT: br label [[CASE0123456]] ; CHECK: case012: -; CHECK-NEXT: [[PHI123:%.*]] = phi i8 [ 3, [[START:%.*]] ], [ 2, [[CASE1]] ], [ 1, [[CASE0]] ] ; CHECK-NEXT: br label [[CASE0123456]] ; CHECK: case3: -; CHECK-NEXT: br label [[CASE345]] +; CHECK-NEXT: br label [[CASE0123456]] ; CHECK: case4: -; CHECK-NEXT: br label [[CASE345]] +; CHECK-NEXT: br label [[CASE0123456]] ; CHECK: case345: -; CHECK-NEXT: [[PHI456:%.*]] = phi i8 [ 6, [[START]] ], [ 5, [[CASE4]] ], [ 4, [[CASE3]] ] ; CHECK-NEXT: br label [[CASE0123456]] ; CHECK: case0123456: -; CHECK-NEXT: [[PHI1234567:%.*]] = phi i8 [ 7, [[START]] ], [ [[PHI456]], [[CASE345]] ], [ [[PHI123]], [[CASE012]] ] +; CHECK-NEXT: [[PHI1234567:%.*]] = phi i8 [ 7, [[START:%.*]] ], [ 6, [[CASE345]] ], [ 3, [[CASE012]] ], [ 2, [[CASE1]] ], [ 1, [[CASE0]] ], [ 5, [[CASE4]] ], [ 4, [[CASE3]] ] ; CHECK-NEXT: ret i8 [[PHI1234567]] ; start: