Index: llvm/trunk/include/llvm/CodeGen/GlobalISel/IRTranslator.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/GlobalISel/IRTranslator.h +++ llvm/trunk/include/llvm/CodeGen/GlobalISel/IRTranslator.h @@ -24,6 +24,7 @@ #include "llvm/CodeGen/GlobalISel/Types.h" #include "llvm/CodeGen/SwiftErrorValueTracking.h" #include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/SwitchLoweringUtils.h" #include "llvm/IR/Intrinsics.h" #include "llvm/Support/Allocator.h" #include @@ -37,6 +38,7 @@ class CallLowering; class Constant; class DataLayout; +class FunctionLoweringInfo; class Instruction; class MachineBasicBlock; class MachineFunction; @@ -293,7 +295,42 @@ /// \pre \p U is a branch instruction. bool translateBr(const User &U, MachineIRBuilder &MIRBuilder); + // Begin switch lowering functions. + bool emitJumpTableHeader(SwitchCG::JumpTable &JT, + SwitchCG::JumpTableHeader &JTH, + MachineBasicBlock *SwitchBB, + MachineIRBuilder &MIB); + void emitJumpTable(SwitchCG::JumpTable &JT, MachineBasicBlock *MBB); + + void emitSwitchCase(SwitchCG::CaseBlock &CB, MachineBasicBlock *SwitchBB, + MachineIRBuilder &MIB); + + bool lowerJumpTableWorkItem(SwitchCG::SwitchWorkListItem W, + MachineBasicBlock *SwitchMBB, + MachineBasicBlock *DefaultMBB, + MachineIRBuilder &MIB, + MachineFunction::iterator BBI, + BranchProbability UnhandledProbs, + SwitchCG::CaseClusterIt I, + MachineBasicBlock *Fallthrough, + bool FallthroughUnreachable); + + bool lowerSwitchRangeWorkItem(SwitchCG::CaseClusterIt I, + Value *Cond, + MachineBasicBlock *Fallthrough, + bool FallthroughUnreachable, + BranchProbability UnhandledProbs, + MachineBasicBlock *CurMBB, + MachineIRBuilder &MIB, + MachineBasicBlock *SwitchMBB); + + bool lowerSwitchWorkItem(SwitchCG::SwitchWorkListItem W, Value *Cond, + MachineBasicBlock *SwitchMBB, + MachineBasicBlock *DefaultMBB, + MachineIRBuilder &MIB); + bool translateSwitch(const User &U, MachineIRBuilder &MIRBuilder); + // End switch lowering section. bool translateIndirectBr(const User &U, MachineIRBuilder &MIRBuilder); @@ -481,12 +518,43 @@ /// Current optimization remark emitter. Used to report failures. std::unique_ptr ORE; + FunctionLoweringInfo FuncInfo; + + // True when either the Target Machine specifies no optimizations or the + // function has the optnone attribute. + bool EnableOpts = false; + + /// Switch analysis and optimization. + class GISelSwitchLowering : public SwitchCG::SwitchLowering { + public: + GISelSwitchLowering(IRTranslator *irt, FunctionLoweringInfo &funcinfo) + : SwitchLowering(funcinfo), IRT(irt) { + assert(irt && "irt is null!"); + } + + virtual void addSuccessorWithProb( + MachineBasicBlock *Src, MachineBasicBlock *Dst, + BranchProbability Prob = BranchProbability::getUnknown()) override { + IRT->addSuccessorWithProb(Src, Dst, Prob); + } + + virtual ~GISelSwitchLowering() = default; + + private: + IRTranslator *IRT; + }; + + std::unique_ptr SL; + // * Insert all the code needed to materialize the constants // at the proper place. E.g., Entry block or dominator block // of each constant depending on how fancy we want to be. // * Clear the different maps. void finalizeFunction(); + // Handle emitting jump tables for each basic block. + void finalizeBasicBlock(); + /// Get the VRegs that represent \p Val. /// Non-aggregate types have just one corresponding VReg and the list can be /// used as a single "unsigned". Aggregates get flattened. If such VRegs do @@ -537,6 +605,14 @@ return SmallVector(1, &getMBB(*Edge.first)); } + /// Return branch probability calculated by BranchProbabilityInfo for IR + /// blocks. + BranchProbability getEdgeProbability(const MachineBasicBlock *Src, + const MachineBasicBlock *Dst) const; + + void addSuccessorWithProb(MachineBasicBlock *Src, MachineBasicBlock *Dst, + BranchProbability Prob); + public: // Ctor, nothing fancy. IRTranslator(); Index: llvm/trunk/include/llvm/CodeGen/SwitchLoweringUtils.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/SwitchLoweringUtils.h +++ llvm/trunk/include/llvm/CodeGen/SwitchLoweringUtils.h @@ -101,10 +101,19 @@ /// SDISel for the code generation of additional basic blocks needed by /// multi-case switch statements. struct CaseBlock { - // The condition code to use for the case block's setcc node. - // Besides the integer condition codes, this can also be SETTRUE, in which - // case no comparison gets emitted. - ISD::CondCode CC; + // For the GISel interface. + struct PredInfoPair { + CmpInst::Predicate Pred; + // Set when no comparison should be emitted. + bool NoCmp; + }; + union { + // The condition code to use for the case block's setcc node. + // Besides the integer condition codes, this can also be SETTRUE, in which + // case no comparison gets emitted. + ISD::CondCode CC; + struct PredInfoPair PredInfo; + }; // The LHS/MHS/RHS of the comparison to emit. // Emit by default LHS op RHS. MHS is used for range comparisons: @@ -120,10 +129,12 @@ /// The debug location of the instruction this CaseBlock was /// produced from. SDLoc DL; + DebugLoc DbgLoc; // Branch weights. BranchProbability TrueProb, FalseProb; + // Constructor for SelectionDAG. CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs, const Value *cmpmiddle, MachineBasicBlock *truebb, MachineBasicBlock *falsebb, MachineBasicBlock *me, SDLoc dl, @@ -132,6 +143,17 @@ : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs), TrueBB(truebb), FalseBB(falsebb), ThisBB(me), DL(dl), TrueProb(trueprob), FalseProb(falseprob) {} + + // Constructor for GISel. + CaseBlock(CmpInst::Predicate pred, bool nocmp, const Value *cmplhs, + const Value *cmprhs, const Value *cmpmiddle, + MachineBasicBlock *truebb, MachineBasicBlock *falsebb, + MachineBasicBlock *me, DebugLoc dl, + BranchProbability trueprob = BranchProbability::getUnknown(), + BranchProbability falseprob = BranchProbability::getUnknown()) + : PredInfo({pred, nocmp}), CmpLHS(cmplhs), CmpMHS(cmpmiddle), + CmpRHS(cmprhs), TrueBB(truebb), FalseBB(falsebb), ThisBB(me), + DbgLoc(dl), TrueProb(trueprob), FalseProb(falseprob) {} }; struct JumpTable { Index: llvm/trunk/lib/CodeGen/GlobalISel/IRTranslator.cpp =================================================================== --- llvm/trunk/lib/CodeGen/GlobalISel/IRTranslator.cpp +++ llvm/trunk/lib/CodeGen/GlobalISel/IRTranslator.cpp @@ -15,9 +15,11 @@ #include "llvm/ADT/ScopeExit.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/CodeGen/Analysis.h" +#include "llvm/CodeGen/FunctionLoweringInfo.h" #include "llvm/CodeGen/GlobalISel/CallLowering.h" #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h" #include "llvm/CodeGen/LowLevelType.h" @@ -402,48 +404,423 @@ return true; } -bool IRTranslator::translateSwitch(const User &U, - MachineIRBuilder &MIRBuilder) { - // For now, just translate as a chain of conditional branches. - // FIXME: could we share most of the logic/code in - // SelectionDAGBuilder::visitSwitch between SelectionDAG and GlobalISel? - // At first sight, it seems most of the logic in there is independent of - // SelectionDAG-specifics and a lot of work went in to optimize switch - // lowering in there. - - const SwitchInst &SwInst = cast(U); - const unsigned SwCondValue = getOrCreateVReg(*SwInst.getCondition()); - const BasicBlock *OrigBB = SwInst.getParent(); - - LLT LLTi1 = getLLTForType(*Type::getInt1Ty(U.getContext()), *DL); - for (auto &CaseIt : SwInst.cases()) { - const unsigned CaseValueReg = getOrCreateVReg(*CaseIt.getCaseValue()); - const unsigned Tst = MRI->createGenericVirtualRegister(LLTi1); - MIRBuilder.buildICmp(CmpInst::ICMP_EQ, Tst, CaseValueReg, SwCondValue); - MachineBasicBlock &CurMBB = MIRBuilder.getMBB(); - const BasicBlock *TrueBB = CaseIt.getCaseSuccessor(); - MachineBasicBlock &TrueMBB = getMBB(*TrueBB); - - MIRBuilder.buildBrCond(Tst, TrueMBB); - CurMBB.addSuccessor(&TrueMBB); - addMachineCFGPred({OrigBB, TrueBB}, &CurMBB); - - MachineBasicBlock *FalseMBB = - MF->CreateMachineBasicBlock(SwInst.getParent()); - // Insert the comparison blocks one after the other. - MF->insert(std::next(CurMBB.getIterator()), FalseMBB); - MIRBuilder.buildBr(*FalseMBB); - CurMBB.addSuccessor(FalseMBB); - - MIRBuilder.setMBB(*FalseMBB); - } - // handle default case - const BasicBlock *DefaultBB = SwInst.getDefaultDest(); - MachineBasicBlock &DefaultMBB = getMBB(*DefaultBB); - MIRBuilder.buildBr(DefaultMBB); - MachineBasicBlock &CurMBB = MIRBuilder.getMBB(); - CurMBB.addSuccessor(&DefaultMBB); - addMachineCFGPred({OrigBB, DefaultBB}, &CurMBB); +void IRTranslator::addSuccessorWithProb(MachineBasicBlock *Src, + MachineBasicBlock *Dst, + BranchProbability Prob) { + if (!FuncInfo.BPI) { + Src->addSuccessorWithoutProb(Dst); + return; + } + if (Prob.isUnknown()) + Prob = getEdgeProbability(Src, Dst); + Src->addSuccessor(Dst, Prob); +} + +BranchProbability +IRTranslator::getEdgeProbability(const MachineBasicBlock *Src, + const MachineBasicBlock *Dst) const { + const BasicBlock *SrcBB = Src->getBasicBlock(); + const BasicBlock *DstBB = Dst->getBasicBlock(); + if (!FuncInfo.BPI) { + // If BPI is not available, set the default probability as 1 / N, where N is + // the number of successors. + auto SuccSize = std::max(succ_size(SrcBB), 1); + return BranchProbability(1, SuccSize); + } + return FuncInfo.BPI->getEdgeProbability(SrcBB, DstBB); +} + +bool IRTranslator::translateSwitch(const User &U, MachineIRBuilder &MIB) { + using namespace SwitchCG; + // Extract cases from the switch. + const SwitchInst &SI = cast(U); + BranchProbabilityInfo *BPI = FuncInfo.BPI; + CaseClusterVector Clusters; + Clusters.reserve(SI.getNumCases()); + for (auto &I : SI.cases()) { + MachineBasicBlock *Succ = &getMBB(*I.getCaseSuccessor()); + assert(Succ && "Could not find successor mbb in mapping"); + const ConstantInt *CaseVal = I.getCaseValue(); + BranchProbability Prob = + BPI ? BPI->getEdgeProbability(SI.getParent(), I.getSuccessorIndex()) + : BranchProbability(1, SI.getNumCases() + 1); + Clusters.push_back(CaseCluster::range(CaseVal, CaseVal, Succ, Prob)); + } + + MachineBasicBlock *DefaultMBB = &getMBB(*SI.getDefaultDest()); + + // Cluster adjacent cases with the same destination. We do this at all + // optimization levels because it's cheap to do and will make codegen faster + // if there are many clusters. + sortAndRangeify(Clusters); + + MachineBasicBlock *SwitchMBB = &getMBB(*SI.getParent()); + + // If there is only the default destination, jump there directly. + if (Clusters.empty()) { + SwitchMBB->addSuccessor(DefaultMBB); + if (DefaultMBB != SwitchMBB->getNextNode()) + MIB.buildBr(*DefaultMBB); + return true; + } + + SL->findJumpTables(Clusters, &SI, DefaultMBB); + + LLVM_DEBUG({ + dbgs() << "Case clusters: "; + for (const CaseCluster &C : Clusters) { + if (C.Kind == CC_JumpTable) + dbgs() << "JT:"; + if (C.Kind == CC_BitTests) + dbgs() << "BT:"; + + C.Low->getValue().print(dbgs(), true); + if (C.Low != C.High) { + dbgs() << '-'; + C.High->getValue().print(dbgs(), true); + } + dbgs() << ' '; + } + dbgs() << '\n'; + }); + + assert(!Clusters.empty()); + SwitchWorkList WorkList; + CaseClusterIt First = Clusters.begin(); + CaseClusterIt Last = Clusters.end() - 1; + auto DefaultProb = getEdgeProbability(SwitchMBB, DefaultMBB); + WorkList.push_back({SwitchMBB, First, Last, nullptr, nullptr, DefaultProb}); + + // FIXME: At the moment we don't do any splitting optimizations here like + // SelectionDAG does, so this worklist only has one entry. + while (!WorkList.empty()) { + SwitchWorkListItem W = WorkList.back(); + WorkList.pop_back(); + if (!lowerSwitchWorkItem(W, SI.getCondition(), SwitchMBB, DefaultMBB, MIB)) + return false; + } + return true; +} + +void IRTranslator::emitJumpTable(SwitchCG::JumpTable &JT, + MachineBasicBlock *MBB) { + // Emit the code for the jump table + assert(JT.Reg != -1U && "Should lower JT Header first!"); + MachineIRBuilder MIB(*MBB->getParent()); + MIB.setMBB(*MBB); + MIB.setDebugLoc(CurBuilder->getDebugLoc()); + + Type *PtrIRTy = Type::getInt8PtrTy(MF->getFunction().getContext()); + const LLT PtrTy = getLLTForType(*PtrIRTy, *DL); + + auto Table = MIB.buildJumpTable(PtrTy, JT.JTI); + MIB.buildBrJT(Table.getReg(0), JT.JTI, JT.Reg); +} + +bool IRTranslator::emitJumpTableHeader(SwitchCG::JumpTable &JT, + SwitchCG::JumpTableHeader &JTH, + MachineBasicBlock *SwitchBB, + MachineIRBuilder &MIB) { + DebugLoc dl = MIB.getDebugLoc(); + + const Value &SValue = *JTH.SValue; + // Subtract the lowest switch case value from the value being switched on. + const LLT SwitchTy = getLLTForType(*SValue.getType(), *DL); + unsigned SwitchOpReg = getOrCreateVReg(SValue); + auto FirstCst = MIB.buildConstant(SwitchTy, JTH.First); + auto Sub = MIB.buildSub({SwitchTy}, SwitchOpReg, FirstCst); + + // This value may be smaller or larger than the target's pointer type, and + // therefore require extension or truncating. + Type *PtrIRTy = SValue.getType()->getPointerTo(); + const LLT PtrScalarTy = LLT::scalar(DL->getTypeSizeInBits(PtrIRTy)); + Sub = MIB.buildZExtOrTrunc(PtrScalarTy, Sub); + + JT.Reg = Sub.getReg(0); + + if (JTH.OmitRangeCheck) { + if (JT.MBB != SwitchBB->getNextNode()) + MIB.buildBr(*JT.MBB); + return true; + } + + // Emit the range check for the jump table, and branch to the default block + // for the switch statement if the value being switched on exceeds the + // largest case in the switch. + auto Cst = getOrCreateVReg( + *ConstantInt::get(SValue.getType(), JTH.Last - JTH.First)); + Cst = MIB.buildZExtOrTrunc(PtrScalarTy, Cst).getReg(0); + auto Cmp = MIB.buildICmp(CmpInst::ICMP_UGT, LLT::scalar(1), Sub, Cst); + + auto BrCond = MIB.buildBrCond(Cmp.getReg(0), *JT.Default); + + // Avoid emitting unnecessary branches to the next block. + if (JT.MBB != SwitchBB->getNextNode()) + BrCond = MIB.buildBr(*JT.MBB); + return true; +} + +void IRTranslator::emitSwitchCase(SwitchCG::CaseBlock &CB, + MachineBasicBlock *SwitchBB, + MachineIRBuilder &MIB) { + unsigned CondLHS = getOrCreateVReg(*CB.CmpLHS); + unsigned Cond = 0; + DebugLoc OldDbgLoc = MIB.getDebugLoc(); + MIB.setDebugLoc(CB.DbgLoc); + MIB.setMBB(*CB.ThisBB); + + if (CB.PredInfo.NoCmp) { + // Branch or fall through to TrueBB. + addSuccessorWithProb(CB.ThisBB, CB.TrueBB, CB.TrueProb); + addMachineCFGPred({SwitchBB->getBasicBlock(), CB.TrueBB->getBasicBlock()}, + CB.ThisBB); + CB.ThisBB->normalizeSuccProbs(); + if (CB.TrueBB != CB.ThisBB->getNextNode()) + MIB.buildBr(*CB.TrueBB); + MIB.setDebugLoc(OldDbgLoc); + return; + } + + const LLT i1Ty = LLT::scalar(1); + // Build the compare. + if (!CB.CmpMHS) { + unsigned CondRHS = getOrCreateVReg(*CB.CmpRHS); + Cond = MIB.buildICmp(CB.PredInfo.Pred, i1Ty, CondLHS, CondRHS).getReg(0); + } else { + assert(CB.PredInfo.Pred == CmpInst::ICMP_ULE && + "Can only handle ULE ranges"); + + const APInt& Low = cast(CB.CmpLHS)->getValue(); + const APInt& High = cast(CB.CmpRHS)->getValue(); + + unsigned CmpOpReg = getOrCreateVReg(*CB.CmpMHS); + if (cast(CB.CmpLHS)->isMinValue(true)) { + unsigned CondRHS = getOrCreateVReg(*CB.CmpRHS); + Cond = + MIB.buildICmp(CmpInst::ICMP_ULE, i1Ty, CmpOpReg, CondRHS).getReg(0); + } else { + const LLT &CmpTy = MRI->getType(CmpOpReg); + auto Sub = MIB.buildSub({CmpTy}, CmpOpReg, CondLHS); + auto Diff = MIB.buildConstant(CmpTy, High - Low); + Cond = MIB.buildICmp(CmpInst::ICMP_ULE, i1Ty, Sub, Diff).getReg(0); + } + } + + // Update successor info + addSuccessorWithProb(CB.ThisBB, CB.TrueBB, CB.TrueProb); + + addMachineCFGPred({SwitchBB->getBasicBlock(), CB.TrueBB->getBasicBlock()}, + CB.ThisBB); + + // TrueBB and FalseBB are always different unless the incoming IR is + // degenerate. This only happens when running llc on weird IR. + if (CB.TrueBB != CB.FalseBB) + addSuccessorWithProb(CB.ThisBB, CB.FalseBB, CB.FalseProb); + CB.ThisBB->normalizeSuccProbs(); + + addMachineCFGPred({SwitchBB->getBasicBlock(), CB.FalseBB->getBasicBlock()}, + CB.ThisBB); + // If the lhs block is the next block, invert the condition so that we can + // fall through to the lhs instead of the rhs block. + if (CB.TrueBB == CB.ThisBB->getNextNode()) { + std::swap(CB.TrueBB, CB.FalseBB); + auto True = MIB.buildConstant(i1Ty, 1); + Cond = MIB.buildInstr(TargetOpcode::G_XOR, {i1Ty}, {Cond, True}, None) + .getReg(0); + } + + MIB.buildBrCond(Cond, *CB.TrueBB); + MIB.buildBr(*CB.FalseBB); + MIB.setDebugLoc(OldDbgLoc); +} + +bool IRTranslator::lowerJumpTableWorkItem(SwitchCG::SwitchWorkListItem W, + MachineBasicBlock *SwitchMBB, + MachineBasicBlock *DefaultMBB, + MachineIRBuilder &MIB, + MachineFunction::iterator BBI, + BranchProbability UnhandledProbs, + SwitchCG::CaseClusterIt I, + MachineBasicBlock *Fallthrough, + bool FallthroughUnreachable) { + using namespace SwitchCG; + MachineFunction *CurMF = SwitchMBB->getParent(); + // FIXME: Optimize away range check based on pivot comparisons. + JumpTableHeader *JTH = &SL->JTCases[I->JTCasesIndex].first; + SwitchCG::JumpTable *JT = &SL->JTCases[I->JTCasesIndex].second; + BranchProbability DefaultProb = W.DefaultProb; + MachineBasicBlock *CurMBB = W.MBB; + + // The jump block hasn't been inserted yet; insert it here. + MachineBasicBlock *JumpMBB = JT->MBB; + CurMF->insert(BBI, JumpMBB); + + // Since the jump table block is separate from the switch block, we need + // to keep track of it as a machine predecessor to the default block, + // otherwise we lose the phi edges. + addMachineCFGPred({SwitchMBB->getBasicBlock(), DefaultMBB->getBasicBlock()}, + SwitchMBB); + addMachineCFGPred({SwitchMBB->getBasicBlock(), DefaultMBB->getBasicBlock()}, + JumpMBB); + + auto JumpProb = I->Prob; + auto FallthroughProb = UnhandledProbs; + + // If the default statement is a target of the jump table, we evenly + // distribute the default probability to successors of CurMBB. Also + // update the probability on the edge from JumpMBB to Fallthrough. + for (MachineBasicBlock::succ_iterator SI = JumpMBB->succ_begin(), + SE = JumpMBB->succ_end(); + SI != SE; ++SI) { + if (*SI == DefaultMBB) { + JumpProb += DefaultProb / 2; + FallthroughProb -= DefaultProb / 2; + JumpMBB->setSuccProbability(SI, DefaultProb / 2); + JumpMBB->normalizeSuccProbs(); + break; + } + } + + // Skip the range check if the fallthrough block is unreachable. + if (FallthroughUnreachable) + JTH->OmitRangeCheck = true; + + if (!JTH->OmitRangeCheck) + addSuccessorWithProb(CurMBB, Fallthrough, FallthroughProb); + addSuccessorWithProb(CurMBB, JumpMBB, JumpProb); + CurMBB->normalizeSuccProbs(); + + // The jump table header will be inserted in our current block, do the + // range check, and fall through to our fallthrough block. + JTH->HeaderBB = CurMBB; + JT->Default = Fallthrough; // FIXME: Move Default to JumpTableHeader. + + // If we're in the right place, emit the jump table header right now. + if (CurMBB == SwitchMBB) { + if (!emitJumpTableHeader(*JT, *JTH, SwitchMBB, MIB)) + return false; + JTH->Emitted = true; + } + return true; +} +bool IRTranslator::lowerSwitchRangeWorkItem(SwitchCG::CaseClusterIt I, + Value *Cond, + MachineBasicBlock *Fallthrough, + bool FallthroughUnreachable, + BranchProbability UnhandledProbs, + MachineBasicBlock *CurMBB, + MachineIRBuilder &MIB, + MachineBasicBlock *SwitchMBB) { + using namespace SwitchCG; + const Value *RHS, *LHS, *MHS; + CmpInst::Predicate Pred; + if (I->Low == I->High) { + // Check Cond == I->Low. + Pred = CmpInst::ICMP_EQ; + LHS = Cond; + RHS = I->Low; + MHS = nullptr; + } else { + // Check I->Low <= Cond <= I->High. + Pred = CmpInst::ICMP_ULE; + LHS = I->Low; + MHS = Cond; + RHS = I->High; + } + + // If Fallthrough is unreachable, fold away the comparison. + // The false probability is the sum of all unhandled cases. + CaseBlock CB(Pred, FallthroughUnreachable, LHS, RHS, MHS, I->MBB, Fallthrough, + CurMBB, MIB.getDebugLoc(), I->Prob, UnhandledProbs); + + emitSwitchCase(CB, SwitchMBB, MIB); + return true; +} + +bool IRTranslator::lowerSwitchWorkItem(SwitchCG::SwitchWorkListItem W, + Value *Cond, + MachineBasicBlock *SwitchMBB, + MachineBasicBlock *DefaultMBB, + MachineIRBuilder &MIB) { + using namespace SwitchCG; + MachineFunction *CurMF = FuncInfo.MF; + MachineBasicBlock *NextMBB = nullptr; + MachineFunction::iterator BBI(W.MBB); + if (++BBI != FuncInfo.MF->end()) + NextMBB = &*BBI; + + if (EnableOpts) { + // Here, we order cases by probability so the most likely case will be + // checked first. However, two clusters can have the same probability in + // which case their relative ordering is non-deterministic. So we use Low + // as a tie-breaker as clusters are guaranteed to never overlap. + llvm::sort(W.FirstCluster, W.LastCluster + 1, + [](const CaseCluster &a, const CaseCluster &b) { + return a.Prob != b.Prob + ? a.Prob > b.Prob + : a.Low->getValue().slt(b.Low->getValue()); + }); + + // Rearrange the case blocks so that the last one falls through if possible + // without changing the order of probabilities. + for (CaseClusterIt I = W.LastCluster; I > W.FirstCluster;) { + --I; + if (I->Prob > W.LastCluster->Prob) + break; + if (I->Kind == CC_Range && I->MBB == NextMBB) { + std::swap(*I, *W.LastCluster); + break; + } + } + } + + // Compute total probability. + BranchProbability DefaultProb = W.DefaultProb; + BranchProbability UnhandledProbs = DefaultProb; + for (CaseClusterIt I = W.FirstCluster; I <= W.LastCluster; ++I) + UnhandledProbs += I->Prob; + + MachineBasicBlock *CurMBB = W.MBB; + for (CaseClusterIt I = W.FirstCluster, E = W.LastCluster; I <= E; ++I) { + bool FallthroughUnreachable = false; + MachineBasicBlock *Fallthrough; + if (I == W.LastCluster) { + // For the last cluster, fall through to the default destination. + Fallthrough = DefaultMBB; + FallthroughUnreachable = isa( + DefaultMBB->getBasicBlock()->getFirstNonPHIOrDbg()); + } else { + Fallthrough = CurMF->CreateMachineBasicBlock(CurMBB->getBasicBlock()); + CurMF->insert(BBI, Fallthrough); + } + UnhandledProbs -= I->Prob; + + switch (I->Kind) { + case CC_BitTests: { + LLVM_DEBUG(dbgs() << "Switch to bit test optimization unimplemented"); + return false; // Bit tests currently unimplemented. + } + case CC_JumpTable: { + if (!lowerJumpTableWorkItem(W, SwitchMBB, DefaultMBB, MIB, BBI, + UnhandledProbs, I, Fallthrough, + FallthroughUnreachable)) { + LLVM_DEBUG(dbgs() << "Failed to lower jump table"); + return false; + } + break; + } + case CC_Range: { + if (!lowerSwitchRangeWorkItem(I, Cond, Fallthrough, + FallthroughUnreachable, UnhandledProbs, + CurMBB, MIB, SwitchMBB)) { + LLVM_DEBUG(dbgs() << "Failed to lower switch range"); + return false; + } + break; + } + } + CurMBB = Fallthrough; + } return true; } @@ -1689,22 +2066,14 @@ Verifier.setCurrentInst(PI); #endif // ifndef NDEBUG - // All MachineBasicBlocks exist, add them to the PHI. We assume IRTranslator - // won't create extra control flow here, otherwise we need to find the - // dominating predecessor here (or perhaps force the weirder IRTranslators - // to provide a simple boundary). - SmallSet HandledPreds; - + SmallSet SeenPreds; for (unsigned i = 0; i < PI->getNumIncomingValues(); ++i) { auto IRPred = PI->getIncomingBlock(i); - if (HandledPreds.count(IRPred)) - continue; - - HandledPreds.insert(IRPred); ArrayRef ValRegs = getOrCreateVRegs(*PI->getIncomingValue(i)); for (auto Pred : getMachinePredBBs({IRPred, PI->getParent()})) { - assert(Pred->isSuccessor(ComponentPHIs[0]->getParent()) && - "incorrect CFG at MachineBasicBlock level"); + if (SeenPreds.count(Pred)) + continue; + SeenPreds.insert(Pred); for (unsigned j = 0; j < ValRegs.size(); ++j) { MachineInstrBuilder MIB(*MF, ComponentPHIs[j]); MIB.addUse(ValRegs[j]); @@ -1808,6 +2177,12 @@ return true; } +void IRTranslator::finalizeBasicBlock() { + for (auto &JTCase : SL->JTCases) + emitJumpTable(JTCase.second, JTCase.second.MBB); + SL->JTCases.clear(); +} + void IRTranslator::finalizeFunction() { // Release the memory used by the different maps we // needed during the translation. @@ -1820,6 +2195,7 @@ // destroying it twice (in ~IRTranslator() and ~LLVMContext()) EntryBuilder.reset(); CurBuilder.reset(); + FuncInfo.clear(); } bool IRTranslator::runOnMachineFunction(MachineFunction &CurMF) { @@ -1852,6 +2228,14 @@ MRI = &MF->getRegInfo(); DL = &F.getParent()->getDataLayout(); ORE = llvm::make_unique(&F); + FuncInfo.MF = MF; + FuncInfo.BPI = nullptr; + const auto &TLI = *MF->getSubtarget().getTargetLowering(); + const TargetMachine &TM = MF->getTarget(); + SL = make_unique(this, FuncInfo); + SL->init(TLI, TM, *DL); + + EnableOpts = TM.getOptLevel() != CodeGenOpt::None && !skipFunction(F); assert(PendingPHIs.empty() && "stale PHIs"); @@ -1975,6 +2359,8 @@ reportTranslationError(*MF, *TPC, *ORE, R); return false; } + + finalizeBasicBlock(); } #ifndef NDEBUG WrapperObserver.removeObserver(&Verifier); Index: llvm/trunk/lib/CodeGen/SwitchLoweringUtils.cpp =================================================================== --- llvm/trunk/lib/CodeGen/SwitchLoweringUtils.cpp +++ llvm/trunk/lib/CodeGen/SwitchLoweringUtils.cpp @@ -52,6 +52,7 @@ assert(Clusters[i - 1].High->getValue().slt(Clusters[i].Low->getValue())); #endif + assert(TLI && "TLI not set!"); if (!TLI->areJTsAllowed(SI->getParent()->getParent())) return; Index: llvm/trunk/test/CodeGen/AArch64/GlobalISel/arm64-irtranslator-switch.ll =================================================================== --- llvm/trunk/test/CodeGen/AArch64/GlobalISel/arm64-irtranslator-switch.ll +++ llvm/trunk/test/CodeGen/AArch64/GlobalISel/arm64-irtranslator-switch.ll @@ -0,0 +1,273 @@ +; NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py +; RUN: llc -mtriple aarch64 -O0 -aarch64-enable-atomic-cfg-tidy=0 -stop-after=irtranslator -global-isel -verify-machineinstrs %s -o - 2>&1 | FileCheck %s + +define i32 @switch(i32 %argc) { + ; CHECK-LABEL: name: switch + ; CHECK: bb.1.entry: + ; CHECK: successors: %bb.3(0x40000000), %bb.6(0x40000000) + ; CHECK: liveins: $w0 + ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0 + ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 100 + ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 200 + ; CHECK: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 2 + ; CHECK: [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 1 + ; CHECK: [[C4:%[0-9]+]]:_(s32) = G_CONSTANT i32 0 + ; CHECK: [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), [[COPY]](s32), [[C]] + ; CHECK: G_BRCOND [[ICMP]](s1), %bb.3 + ; CHECK: G_BR %bb.6 + ; CHECK: bb.6.entry: + ; CHECK: successors: %bb.4(0x40000000), %bb.2(0x40000000) + ; CHECK: [[ICMP1:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), [[COPY]](s32), [[C1]] + ; CHECK: G_BRCOND [[ICMP1]](s1), %bb.4 + ; CHECK: G_BR %bb.2 + ; CHECK: bb.2.default: + ; CHECK: successors: %bb.5(0x80000000) + ; CHECK: [[ADD:%[0-9]+]]:_(s32) = G_ADD [[COPY]], [[C4]] + ; CHECK: G_BR %bb.5 + ; CHECK: bb.3.case100: + ; CHECK: successors: %bb.5(0x80000000) + ; CHECK: [[ADD1:%[0-9]+]]:_(s32) = G_ADD [[COPY]], [[C3]] + ; CHECK: G_BR %bb.5 + ; CHECK: bb.4.case200: + ; CHECK: successors: %bb.5(0x80000000) + ; CHECK: [[ADD2:%[0-9]+]]:_(s32) = G_ADD [[COPY]], [[C2]] + ; CHECK: bb.5.return: + ; CHECK: [[PHI:%[0-9]+]]:_(s32) = G_PHI [[ADD]](s32), %bb.2, [[ADD1]](s32), %bb.3, [[ADD2]](s32), %bb.4 + ; CHECK: $w0 = COPY [[PHI]](s32) + ; CHECK: RET_ReallyLR implicit $w0 +entry: + switch i32 %argc, label %default [ + i32 100, label %case100 + i32 200, label %case200 + ] + +default: + %tmp0 = add i32 %argc, 0 + br label %return + +case100: + %tmp1 = add i32 %argc, 1 + br label %return + +case200: + %tmp2 = add i32 %argc, 2 + br label %return + +return: + %res = phi i32 [ %tmp0, %default ], [ %tmp1, %case100 ], [ %tmp2, %case200 ] + ret i32 %res +} + +define i32 @test_cfg_remap(i32 %in) { + ; CHECK-LABEL: name: test_cfg_remap + ; CHECK: bb.1.entry: + ; CHECK: successors: %bb.2(0x40000000), %bb.5(0x40000000) + ; CHECK: liveins: $w0 + ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0 + ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 1 + ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 57 + ; CHECK: [[DEF:%[0-9]+]]:_(s32) = G_IMPLICIT_DEF + ; CHECK: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 42 + ; CHECK: [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), [[COPY]](s32), [[C]] + ; CHECK: G_BRCOND [[ICMP]](s1), %bb.2 + ; CHECK: G_BR %bb.5 + ; CHECK: bb.5.entry: + ; CHECK: successors: %bb.3(0x40000000), %bb.4(0x40000000) + ; CHECK: [[ICMP1:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), [[COPY]](s32), [[C1]] + ; CHECK: G_BRCOND [[ICMP1]](s1), %bb.3 + ; CHECK: G_BR %bb.4 + ; CHECK: bb.2.next: + ; CHECK: successors: %bb.4(0x80000000) + ; CHECK: G_BR %bb.4 + ; CHECK: bb.3.other: + ; CHECK: $w0 = COPY [[DEF]](s32) + ; CHECK: RET_ReallyLR implicit $w0 + ; CHECK: bb.4.phi.block: + ; CHECK: [[PHI:%[0-9]+]]:_(s32) = G_PHI [[C]](s32), %bb.5, [[C2]](s32), %bb.2 + ; CHECK: $w0 = COPY [[PHI]](s32) + ; CHECK: RET_ReallyLR implicit $w0 +entry: + switch i32 %in, label %phi.block [i32 1, label %next + i32 57, label %other] + +next: + br label %phi.block + +other: + ret i32 undef + +phi.block: + %res = phi i32 [1, %entry], [42, %next] + ret i32 %res +} + +define i32 @test_cfg_remap_multiple_preds(i32 %in) { + ; CHECK-LABEL: name: test_cfg_remap_multiple_preds + ; CHECK: bb.1.entry: + ; CHECK: successors: %bb.3(0x40000000), %bb.6(0x40000000) + ; CHECK: liveins: $w0 + ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0 + ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 1 + ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 57 + ; CHECK: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 128 + ; CHECK: [[DEF:%[0-9]+]]:_(s32) = G_IMPLICIT_DEF + ; CHECK: [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 12 + ; CHECK: [[C4:%[0-9]+]]:_(s32) = G_CONSTANT i32 42 + ; CHECK: [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), [[COPY]](s32), [[C]] + ; CHECK: G_BRCOND [[ICMP]](s1), %bb.3 + ; CHECK: G_BR %bb.6 + ; CHECK: bb.6.entry: + ; CHECK: successors: %bb.4(0x40000000), %bb.7(0x40000000) + ; CHECK: [[ICMP1:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), [[COPY]](s32), [[C1]] + ; CHECK: G_BRCOND [[ICMP1]](s1), %bb.4 + ; CHECK: G_BR %bb.7 + ; CHECK: bb.7.entry: + ; CHECK: successors: %bb.5(0x40000000), %bb.8(0x40000000) + ; CHECK: [[ICMP2:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), [[COPY]](s32), [[C2]] + ; CHECK: G_BRCOND [[ICMP2]](s1), %bb.5 + ; CHECK: G_BR %bb.8 + ; CHECK: bb.8.entry: + ; CHECK: successors: %bb.5(0x80000000) + ; CHECK: G_BR %bb.5 + ; CHECK: bb.2.odd: + ; CHECK: successors: + ; CHECK: bb.3.next: + ; CHECK: successors: %bb.5(0x80000000) + ; CHECK: G_BR %bb.5 + ; CHECK: bb.4.other: + ; CHECK: $w0 = COPY [[DEF]](s32) + ; CHECK: RET_ReallyLR implicit $w0 + ; CHECK: bb.5.phi.block: + ; CHECK: [[PHI:%[0-9]+]]:_(s32) = G_PHI [[C]](s32), %bb.7, [[C]](s32), %bb.8, [[C4]](s32), %bb.3 + ; CHECK: $w0 = COPY [[C3]](s32) + ; CHECK: RET_ReallyLR implicit $w0 +entry: + switch i32 %in, label %odd [i32 1, label %next + i32 57, label %other + i32 128, label %phi.block + i32 256, label %phi.block] +odd: + unreachable + +next: + br label %phi.block + +other: + ret i32 undef + +phi.block: + %res = phi i32 [1, %entry], [1, %entry], [42, %next] + ret i32 12 +} + +define i32 @jt_test(i32 %x) { + ; CHECK-LABEL: name: jt_test + ; CHECK: bb.1.entry: + ; CHECK: successors: %bb.4(0x40000000), %bb.5(0x40000000) + ; CHECK: liveins: $w0 + ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0 + ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 71 + ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 3 + ; CHECK: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 42 + ; CHECK: [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 0 + ; CHECK: [[C4:%[0-9]+]]:_(s32) = G_CONSTANT i32 4 + ; CHECK: [[SUB:%[0-9]+]]:_(s32) = G_SUB [[COPY]], [[C4]] + ; CHECK: [[ZEXT:%[0-9]+]]:_(s64) = G_ZEXT [[SUB]](s32) + ; CHECK: [[ZEXT1:%[0-9]+]]:_(s64) = G_ZEXT [[C]](s32) + ; CHECK: [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(ugt), [[ZEXT]](s64), [[ZEXT1]] + ; CHECK: G_BRCOND [[ICMP]](s1), %bb.4 + ; CHECK: bb.5.entry: + ; CHECK: successors: %bb.3(0x2aaaaaab), %bb.4(0x2aaaaaab), %bb.2(0x2aaaaaab) + ; CHECK: [[JUMP_TABLE:%[0-9]+]]:_(p0) = G_JUMP_TABLE %jump-table.0 + ; CHECK: G_BRJT [[JUMP_TABLE]](p0), %jump-table.0, [[ZEXT]](s64) + ; CHECK: bb.2.sw.bb: + ; CHECK: successors: %bb.4(0x80000000) + ; CHECK: %11:_(s32) = nsw G_ADD [[COPY]], [[C2]] + ; CHECK: G_BR %bb.4 + ; CHECK: bb.3.sw.bb1: + ; CHECK: successors: %bb.4(0x80000000) + ; CHECK: %9:_(s32) = nsw G_MUL [[COPY]], [[C1]] + ; CHECK: bb.4.return: + ; CHECK: [[PHI:%[0-9]+]]:_(s32) = G_PHI %9(s32), %bb.3, %11(s32), %bb.2, [[C3]](s32), %bb.1, [[C3]](s32), %bb.5 + ; CHECK: $w0 = COPY [[PHI]](s32) + ; CHECK: RET_ReallyLR implicit $w0 +entry: + switch i32 %x, label %return [ + i32 75, label %sw.bb + i32 34, label %sw.bb + i32 56, label %sw.bb + i32 35, label %sw.bb + i32 40, label %sw.bb + i32 4, label %sw.bb1 + i32 5, label %sw.bb1 + i32 6, label %sw.bb1 + ] + +sw.bb: + %add = add nsw i32 %x, 42 + br label %return + +sw.bb1: + %mul = mul nsw i32 %x, 3 + br label %return + +return: + %retval.0 = phi i32 [ %mul, %sw.bb1 ], [ %add, %sw.bb ], [ 0, %entry ] + ret i32 %retval.0 +} + +define i32 @range_test(i32 %x) { + ; CHECK-LABEL: name: range_test + ; CHECK: bb.1.entry: + ; CHECK: successors: %bb.3(0x40000000), %bb.5(0x40000000) + ; CHECK: liveins: $w0 + ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0 + ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 6 + ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 24 + ; CHECK: [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 3 + ; CHECK: [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 42 + ; CHECK: [[C4:%[0-9]+]]:_(s32) = G_CONSTANT i32 0 + ; CHECK: [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), [[COPY]](s32), [[C]] + ; CHECK: G_BRCOND [[ICMP]](s1), %bb.3 + ; CHECK: G_BR %bb.5 + ; CHECK: bb.5.entry: + ; CHECK: successors: %bb.2(0x40000000), %bb.4(0x40000000) + ; CHECK: [[SUB:%[0-9]+]]:_(s32) = G_SUB [[COPY]], [[C1]] + ; CHECK: [[C5:%[0-9]+]]:_(s32) = G_CONSTANT i32 2 + ; CHECK: [[ICMP1:%[0-9]+]]:_(s1) = G_ICMP intpred(ule), [[SUB]](s32), [[C5]] + ; CHECK: [[C6:%[0-9]+]]:_(s1) = G_CONSTANT i1 true + ; CHECK: [[XOR:%[0-9]+]]:_(s1) = G_XOR [[ICMP1]], [[C6]] + ; CHECK: G_BRCOND [[XOR]](s1), %bb.4 + ; CHECK: G_BR %bb.2 + ; CHECK: bb.2.sw.bb: + ; CHECK: successors: %bb.4(0x80000000) + ; CHECK: %12:_(s32) = nsw G_ADD [[COPY]], [[C3]] + ; CHECK: G_BR %bb.4 + ; CHECK: bb.3.sw.bb1: + ; CHECK: successors: %bb.4(0x80000000) + ; CHECK: %10:_(s32) = nsw G_MUL [[COPY]], [[C2]] + ; CHECK: bb.4.return: + ; CHECK: [[PHI:%[0-9]+]]:_(s32) = G_PHI %10(s32), %bb.3, %12(s32), %bb.2, [[C4]](s32), %bb.5 + ; CHECK: $w0 = COPY [[PHI]](s32) + ; CHECK: RET_ReallyLR implicit $w0 +entry: + switch i32 %x, label %return [ + i32 24, label %sw.bb + i32 25, label %sw.bb + i32 26, label %sw.bb + i32 6, label %sw.bb1 + ] + +sw.bb: + %add = add nsw i32 %x, 42 + br label %return + +sw.bb1: + %mul = mul nsw i32 %x, 3 + br label %return + +return: + %retval.0 = phi i32 [ %mul, %sw.bb1 ], [ %add, %sw.bb ], [ 0, %entry ] + ret i32 %retval.0 +} + Index: llvm/trunk/test/CodeGen/AArch64/GlobalISel/arm64-irtranslator.ll =================================================================== --- llvm/trunk/test/CodeGen/AArch64/GlobalISel/arm64-irtranslator.ll +++ llvm/trunk/test/CodeGen/AArch64/GlobalISel/arm64-irtranslator.ll @@ -129,129 +129,6 @@ ret void } -; Tests for switch. -; This gets lowered to a very straightforward sequence of comparisons for now. -; CHECK-LABEL: name: switch -; CHECK: body: -; -; CHECK: bb.{{[a-zA-Z0-9.]+}}: -; CHECK-NEXT: successors: %[[BB_CASE100:bb.[0-9]+]](0x40000000), %[[BB_NOTCASE100_CHECKNEXT:bb.[0-9]+]](0x40000000) -; CHECK: %0:_(s32) = COPY $w0 -; CHECK: %[[reg100:[0-9]+]]:_(s32) = G_CONSTANT i32 100 -; CHECK: %[[reg200:[0-9]+]]:_(s32) = G_CONSTANT i32 200 -; CHECK: %[[reg2:[0-9]+]]:_(s32) = G_CONSTANT i32 2 -; CHECK: %[[reg1:[0-9]+]]:_(s32) = G_CONSTANT i32 1 -; CHECK: %[[reg0:[0-9]+]]:_(s32) = G_CONSTANT i32 0 -; CHECK: %[[regicmp100:[0-9]+]]:_(s1) = G_ICMP intpred(eq), %[[reg100]](s32), %0 -; CHECK: G_BRCOND %[[regicmp100]](s1), %[[BB_CASE100]] -; CHECK: G_BR %[[BB_NOTCASE100_CHECKNEXT]] -; -; CHECK: [[BB_NOTCASE100_CHECKNEXT]].{{[a-zA-Z0-9.]+}}: -; CHECK-NEXT: successors: %[[BB_CASE200:bb.[0-9]+]](0x40000000), %[[BB_NOTCASE200_CHECKNEXT:bb.[0-9]+]](0x40000000) -; CHECK: %[[regicmp200:[0-9]+]]:_(s1) = G_ICMP intpred(eq), %[[reg200]](s32), %0 -; CHECK: G_BRCOND %[[regicmp200]](s1), %[[BB_CASE200]] -; CHECK: G_BR %[[BB_NOTCASE200_CHECKNEXT]] -; -; CHECK: [[BB_NOTCASE200_CHECKNEXT]].{{[a-zA-Z0-9.]+}}: -; CHECK-NEXT: successors: %[[BB_DEFAULT:bb.[0-9]+]](0x80000000) -; CHECK: G_BR %[[BB_DEFAULT]] -; -; CHECK: [[BB_DEFAULT]].{{[a-zA-Z0-9.]+}}: -; CHECK-NEXT: successors: %[[BB_RET:bb.[0-9]+]](0x80000000) -; CHECK: %[[regretdefault:[0-9]+]]:_(s32) = G_ADD %0, %[[reg0]] -; CHECK: G_BR %[[BB_RET]] -; -; CHECK: [[BB_CASE100]].{{[a-zA-Z0-9.]+}}: -; CHECK-NEXT: successors: %[[BB_RET:bb.[0-9]+]](0x80000000) -; CHECK: %[[regretc100:[0-9]+]]:_(s32) = G_ADD %0, %[[reg1]] -; CHECK: G_BR %[[BB_RET]] -; -; CHECK: [[BB_CASE200]].{{[a-zA-Z0-9.]+}}: -; CHECK-NEXT: successors: %[[BB_RET]](0x80000000) -; CHECK: %[[regretc200:[0-9]+]]:_(s32) = G_ADD %0, %[[reg2]] -; -; CHECK: [[BB_RET]].{{[a-zA-Z0-9.]+}}: -; CHECK-NEXT: %[[regret:[0-9]+]]:_(s32) = G_PHI %[[regretdefault]](s32), %[[BB_DEFAULT]], %[[regretc100]](s32), %[[BB_CASE100]] -; CHECK: $w0 = COPY %[[regret]](s32) -; CHECK: RET_ReallyLR implicit $w0 -; -define i32 @switch(i32 %argc) { -entry: - switch i32 %argc, label %default [ - i32 100, label %case100 - i32 200, label %case200 - ] - -default: - %tmp0 = add i32 %argc, 0 - br label %return - -case100: - %tmp1 = add i32 %argc, 1 - br label %return - -case200: - %tmp2 = add i32 %argc, 2 - br label %return - -return: - %res = phi i32 [ %tmp0, %default ], [ %tmp1, %case100 ], [ %tmp2, %case200 ] - ret i32 %res -} - - ; The switch lowering code changes the CFG, which means that the original - ; %entry block is no longer a predecessor for the phi instruction. We need to - ; use the correct lowered MachineBasicBlock instead. -; CHECK-LABEL: name: test_cfg_remap -; CHECK: bb.{{[0-9]+.[a-zA-Z0-9.]+}}: -; CHECK-NEXT: successors: %{{bb.[0-9]+}}(0x40000000), %[[NOTCASE1_BLOCK:bb.[0-9]+]](0x40000000) -; CHECK: [[NOTCASE1_BLOCK]].{{[a-zA-Z0-9.]+}}: -; CHECK-NEXT: successors: %{{bb.[0-9]+}}(0x40000000), %[[NOTCASE57_BLOCK:bb.[0-9]+]](0x40000000) -; CHECK: [[NOTCASE57_BLOCK]].{{[a-zA-Z0-9.]+}}: -; CHECK-NEXT: successors: %[[PHI_BLOCK:bb.[0-9]+]](0x80000000) -; CHECK: G_BR %[[PHI_BLOCK]] -; -; CHECK: [[PHI_BLOCK]].{{[a-zA-Z0-9.]+}}: -; CHECK-NEXT: G_PHI %{{.*}}(s32), %[[NOTCASE57_BLOCK:bb.[0-9]+]], %{{.*}}(s32), -; -define i32 @test_cfg_remap(i32 %in) { -entry: - switch i32 %in, label %phi.block [i32 1, label %next - i32 57, label %other] - -next: - br label %phi.block - -other: - ret i32 undef - -phi.block: - %res = phi i32 [1, %entry], [42, %next] - ret i32 %res -} - -; CHECK-LABEL: name: test_cfg_remap_multiple_preds -; CHECK: G_PHI [[ENTRY:%.*]](s32), %bb.{{[0-9]+}}, [[ENTRY]](s32), %bb.{{[0-9]+}} -define i32 @test_cfg_remap_multiple_preds(i32 %in) { -entry: - switch i32 %in, label %odd [i32 1, label %next - i32 57, label %other - i32 128, label %phi.block - i32 256, label %phi.block] -odd: - unreachable - -next: - br label %phi.block - -other: - ret i32 undef - -phi.block: - %res = phi i32 [1, %entry], [1, %entry], [42, %next] - ret i32 12 -} - ; Tests for indirect br. ; CHECK-LABEL: name: indirectbr ; CHECK: body: