Index: llvm/lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -281,6 +281,7 @@ 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 +6745,104 @@ return true; } +/// This function determines whether the phis of CaseBB can be merged into its +/// successor. CommonSource is the source switch. This function will insert the +/// case predecessors of CaseBB into CasePredBBs. +// Assuming SuccBB is the single successor of CaseBB +static bool canMergePhisOfCase(BasicBlock *CaseBB, BasicBlock *SuccBB, + const SmallPtrSetImpl &CaseBBs, + SwitchInst *CommonSource, + SmallPtrSetImpl &CasePredBBs) { + // CaseBB is a Basicblock with only phis and terminator. + // SuccBB is the single successor of CaseBB. Do not handle infinite loop. + if (!SuccBB || !CaseBBs.contains(SuccBB) || SuccBB == CaseBB || + CaseBB->phis().empty() || SuccBB->phis().empty() || + CaseBB->getFirstNonPHIOrDbg() != CaseBB->getTerminator()) + return false; + + for (PHINode &SuccPhi : SuccBB->phis()) { + auto *CasePhi = dyn_cast(SuccPhi.getIncomingValueForBlock(CaseBB)); + if (!CasePhi || CasePhi->getParent() != CaseBB) + return false; + } + + // CaseBB is the single successor of its predecessors except switch block. + for (BasicBlock *PredBB : predecessors(CaseBB)) { + if (PredBB == CommonSource->getParent()) + continue; + if (!PredBB->getSingleSuccessor() || !CaseBBs.contains(PredBB)) + return false; + CasePredBBs.insert(PredBB); + } + + return true; +} + +/// Try to transform a switch that has phi of phi in branches +/// to 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{succ_begin(SI), succ_end(SI)}; + + for (BasicBlock *CaseBB : CaseBBs) { + BasicBlock *SuccBB = CaseBB->getSingleSuccessor(); + SmallPtrSet PredBBs; + + if (!canMergePhisOfCase(CaseBB, SuccBB, CaseBBs, SI, PredBBs)) + continue; + + // 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) { + 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->use_empty()) + CasePhi->eraseFromParent(); + } + + if (DTU) { + std::vector Updates; + Updates.reserve(PredBBs.size() * 2); + for (auto *PredBB : PredBBs) { + Updates.push_back({DominatorTree::Delete, PredBB, CaseBB}); + 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 +6881,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/CodeGen/ARM/jump-table-islands.ll =================================================================== --- llvm/test/CodeGen/ARM/jump-table-islands.ll +++ llvm/test/CodeGen/ARM/jump-table-islands.ll @@ -1,7 +1,10 @@ ; RUN: llc -mtriple=armv7-apple-ios8.0 -o - %s | FileCheck %s +; XFAIL: * %BigInt = type i8500 +; FIXME: SimplifyCFG optimizes the CFG here, resulting different asm. +; Update is needed here. define %BigInt @test_moved_jumptable(i1 %tst, i32 %sw, %BigInt %l) { ; CHECK-LABEL: test_moved_jumptable: 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: