[GlobalISel][IRTranslator] Change switch table translation to generate jump tables and range checks.

[aemerson]

Summary

This change makes use of the newly refactored SwitchLoweringUtils code from SelectionDAG to in order to generate jump tables and range checks where appropriate.

Much of this code is ported from SDAG with some modifications. We generate G_JUMP_TABLE and G_BRJT instructions when JT opportunities are found. This means that targets which previously relied on the naive one MBB per case stmt translation will now start falling back until they add support for the new opcodes.

For range checks, we don't generate any previously unused operations. This just recognizes contiguous ranges of case values and generates a single block per range. Single case value blocks are just a special case of ranges so we get that support almost for free.

There are still some optimizations missing that I haven't ported over, and bit-tests are also unimplemented. This patch series is already complex enough.

Actual arm64 support for selection of jump tables is coming in a later patch.

[paquette]

llvm/include/llvm/CodeGen/GlobalISel/IRTranslator.h

505 ↗

(On Diff #204169)

I think you can capitalize irt etc. in here

Also, can irt ever be null (I doubt it, but still)? Should there be an assert?

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

429 ↗

(On Diff #204169)

for (auto &I : ... )?

430 ↗

(On Diff #204169)

Is *I.getCaseSuccessor() always guaranteed to not be nullptr?

433–435 ↗

(On Diff #204169)

Could this use the above IRTranslator::getEdgeProbability function? Then you don't have to check BPI here.

441 ↗

(On Diff #204169)

This (and the remainder of this function) seems like it could be factored out into a clusterAdjacentCases helper function.

495 ↗

(On Diff #204169)

to appease the llvm style gods, this should be nextBlock

524 ↗

(On Diff #204169)

Is it worth pulling JTH.SValue out into a variable?

650 ↗

(On Diff #204169)

llvm::stable_sort?

659–668 ↗

(On Diff #204169)

I feel like this is somewhat unintuitive. Is there a way to simplify this using some STL magic?

691 ↗

(On Diff #204169)

This switch makes this function rather large. Would it make sense to factor it out into a helper function?

693 ↗

(On Diff #204169)

Debug output would be nice here

729–732 ↗

(On Diff #204169)

remove braces to appease llvm style gods

777–778 ↗

(On Diff #204169)

brace formatting seems wonky here

2024 ↗

(On Diff #204169)

Just curious, why 16?

2129 ↗

(On Diff #204169)

capital i to appease the llvm style gods, but I'll pretend I didn't see this ;)

[aemerson]

llvm/include/llvm/CodeGen/GlobalISel/IRTranslator.h

505 ↗

(On Diff #204169)

It's a deliberate choice for me. I'm not sure if it's correct but there's some precedent for this around the codebase. I prefer in cases where we have identically named member variables and parameters to just use lower case for the very short lived parameters.

It won't be null since it's used in one place, I'll put an assert anyway.

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

429 ↗

(On Diff #204169)

Ok.

430 ↗

(On Diff #204169)

Yes I think so.

433–435 ↗

(On Diff #204169)

I don't think it computes exactly the same thing, SI.getNumCases() + 1 can't be replaced because the successors of SI's parent BB is not necessarily the same as the successors of the switchinst itself.

441 ↗

(On Diff #204169)

Not sure what you mean here, the clustering is already done in this call to sortAndRangeify(). The rest of the function is unrelated.

495 ↗

(On Diff #204169)

Ok.

524 ↗

(On Diff #204169)

Ok.

650 ↗

(On Diff #204169)

I don't think the Low values can overlap, so we don't need stable sort here.

693 ↗

(On Diff #204169)

Ok.

729–732 ↗

(On Diff #204169)

Ok.

777–778 ↗

(On Diff #204169)

Because switch cases aren't indented relative to the switch.

2024 ↗

(On Diff #204169)

Pointer storage is cheap, and set growth is expensive, just a rough guess.

2129 ↗

(On Diff #204169)

Ok.

[paquette]

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

413 ↗

(On Diff #205226)

Just return after this to eliminate the else?

464–466 ↗

(On Diff #205226)

clang-format for braces

508–513 ↗

(On Diff #205226)

Does this function have to exist at all? Can you just use getNextNode?

551–567 ↗

(On Diff #205226)

I think this can probably be simplified to reduce nesting, since the if case is much longer than the else if here.

E.g.

if (JTH.OmitRangeCheck && JT.MBB != nextBlock(SwitchBB)) {
    MIB.buildBr(*JT.MBB);
    return true;
}

auto Cst...
return true;

586–588 ↗

(On Diff #205226)

clang-format

762 ↗

(On Diff #205226)

I think we should check the function attributes for optnone here as well.

[aemerson]

Addressed comments.

[paquette]

LGTM

[MaskRay]

@aemerson Hi, I committed rL364124 to fix the link error on -DBUILD_SHARED_LIBS=on builds, but I am not sure if the dependency should be added. Can you take a look?

[aemerson]

In D63169#1554622, @MaskRay wrote:

@aemerson Hi, I committed rL364124 to fix the link error on -DBUILD_SHARED_LIBS=on builds, but I am not sure if the dependency should be added. Can you take a look?

Thanks, I think it might be able to remove that dependency from this commit but until I do that fix looks fine.

Amara

llvm/trunk/include/llvm/CodeGen/GlobalISel/IRTranslator.h

 #define LLVM_CODEGEN_GLOBALISEL_IRTRANSLATOR_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
 #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 <memory>
 #include <utility>
 
 namespace llvm {
 
 class AllocaInst;
 class BasicBlock;
 class CallInst;
 class CallLowering;
 class Constant;
 class DataLayout;
+class FunctionLoweringInfo;
 class Instruction;
 class MachineBasicBlock;
 class MachineFunction;
 class MachineInstr;
 class MachineRegisterInfo;
 class OptimizationRemarkEmitter;
 class PHINode;
 class TargetPassConfig;
private:
   /// \pre \p U is a binary operation.
   bool translateBinaryOp(unsigned Opcode, const User &U,
                          MachineIRBuilder &MIRBuilder);
 
   /// Translate branch (br) instruction.
   /// \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);
 
   bool translateExtractValue(const User &U, MachineIRBuilder &MIRBuilder);
 
   bool translateInsertValue(const User &U, MachineIRBuilder &MIRBuilder);
 
   bool translateSelect(const User &U, MachineIRBuilder &MIRBuilder);
private:
   const DataLayout *DL;
 
   /// Current target configuration. Controls how the pass handles errors.
   const TargetPassConfig *TPC;
 
   /// Current optimization remark emitter. Used to report failures.
   std::unique_ptr<OptimizationRemarkEmitter> 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<GISelSwitchLowering> 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
   /// not exist, they are created.
   ArrayRef<unsigned> getOrCreateVRegs(const Value &Val);
 
   unsigned getOrCreateVReg(const Value &Val) {
     auto Regs = getOrCreateVRegs(Val);
private:
   /// preceding the original though (e.g. switch instructions).
   SmallVector<MachineBasicBlock *, 1> getMachinePredBBs(CFGEdge Edge) {
     auto RemappedEdge = MachinePreds.find(Edge);
     if (RemappedEdge != MachinePreds.end())
       return RemappedEdge->second;
     return SmallVector<MachineBasicBlock *, 4>(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();
 
   StringRef getPassName() const override { return "IRTranslator"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 

llvm/trunk/include/llvm/CodeGen/SwitchLoweringUtils.h

 };
 
 using CaseBitsVector = std::vector<CaseBits>;
 
 /// This structure is used to communicate between SelectionDAGBuilder and
 /// SDISel for the code generation of additional basic blocks needed by
 /// multi-case switch statements.
 struct CaseBlock {
+  // 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:
   // If MHS is not null: (LHS <= MHS) and (MHS <= RHS).
   const Value *CmpLHS, *CmpMHS, *CmpRHS;
 
   // The block to branch to if the setcc is true/false.
   MachineBasicBlock *TrueBB, *FalseBB;
 
   // The block into which to emit the code for the setcc and branches.
   MachineBasicBlock *ThisBB;
 
   /// 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,
             BranchProbability trueprob = BranchProbability::getUnknown(),
             BranchProbability falseprob = BranchProbability::getUnknown())
       : 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 {
   /// The virtual register containing the index of the jump table entry
   /// to jump to.
   unsigned Reg;
   /// The JumpTableIndex for this jump table in the function.
   unsigned JTI;

llvm/trunk/lib/CodeGen/GlobalISel/IRTranslator.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/GlobalISel/IRTranslator.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #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"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
if (!CurBB.isLayoutSuccessor(&TgtBB))
     MIRBuilder.buildBr(TgtBB);
 
   // Link successors.
   for (const BasicBlock *Succ : successors(&BrInst))
     CurBB.addSuccessor(&getMBB(*Succ));
   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<SwitchInst>(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<uint32_t>(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<SwitchInst>(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<ConstantInt>(CB.CmpLHS)->getValue();
+    const APInt& High = cast<ConstantInt>(CB.CmpRHS)->getValue();
+
+    unsigned CmpOpReg = getOrCreateVReg(*CB.CmpMHS);
+    if (cast<ConstantInt>(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<UnreachableInst>(
+          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;
 }
 
 bool IRTranslator::translateIndirectBr(const User &U,
                                        MachineIRBuilder &MIRBuilder) {
   const IndirectBrInst &BrInst = cast<IndirectBrInst>(U);
 
#endif // ifndef NDEBUG
   for (auto &Phi : PendingPHIs) {
     const PHINode *PI = Phi.first;
     ArrayRef<MachineInstr *> ComponentPHIs = Phi.second;
     EntryBuilder->setDebugLoc(PI->getDebugLoc());
 #ifndef NDEBUG
     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<const BasicBlock *, 4> HandledPreds;
-
+    SmallSet<const MachineBasicBlock *, 16> SeenPreds;
     for (unsigned i = 0; i < PI->getNumIncomingValues(); ++i) {
       auto IRPred = PI->getIncomingBlock(i);
-      if (HandledPreds.count(IRPred))
-        continue;
-
-      HandledPreds.insert(IRPred);
       ArrayRef<unsigned> 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]);
           MIB.addMBB(Pred);
         }
       }
     }
   }
#include "llvm/IR/Instruction.def"
   } else if (auto *BA = dyn_cast<BlockAddress>(&C)) {
     EntryBuilder->buildBlockAddress(Reg, BA);
   } else
     return false;
 
   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.
   PendingPHIs.clear();
   VMap.reset();
   FrameIndices.clear();
   MachinePreds.clear();
   // MachineIRBuilder::DebugLoc can outlive the DILocation it holds. Clear it
   // to avoid accessing free’d memory (in runOnMachineFunction) and to avoid
   // destroying it twice (in ~IRTranslator() and ~LLVMContext())
   EntryBuilder.reset();
   CurBuilder.reset();
+  FuncInfo.clear();
 }
 
 bool IRTranslator::runOnMachineFunction(MachineFunction &CurMF) {
   MF = &CurMF;
   const Function &F = MF->getFunction();
   if (F.empty())
     return false;
   GISelCSEAnalysisWrapper &Wrapper =
if (EnableCSE) {
     CurBuilder = make_unique<MachineIRBuilder>();
   }
   CLI = MF->getSubtarget().getCallLowering();
   CurBuilder->setMF(*MF);
   EntryBuilder->setMF(*MF);
   MRI = &MF->getRegInfo();
   DL = &F.getParent()->getDataLayout();
   ORE = llvm::make_unique<OptimizationRemarkEmitter>(&F);
+  FuncInfo.MF = MF;
+  FuncInfo.BPI = nullptr;
+  const auto &TLI = *MF->getSubtarget().getTargetLowering();
+  const TargetMachine &TM = MF->getTarget();
+  SL = make_unique<GISelSwitchLowering>(this, FuncInfo);
+  SL->init(TLI, TM, *DL);
+
+  EnableOpts = TM.getOptLevel() != CodeGenOpt::None && !skipFunction(F);
 
   assert(PendingPHIs.empty() && "stale PHIs");
 
   if (!DL->isLittleEndian()) {
     // Currently we don't properly handle big endian code.
     OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure",
                                F.getSubprogram(), &F.getEntryBlock());
     R << "unable to translate in big endian mode";
#endif // ifndef NDEBUG
           InstStr << Inst;
 
           R << ": '" << InstStr.str() << "'";
         }
 
         reportTranslationError(*MF, *TPC, *ORE, R);
         return false;
       }
+
+      finalizeBasicBlock();
     }
 #ifndef NDEBUG
     WrapperObserver.removeObserver(&Verifier);
 #endif
   }
 
   finishPendingPhis();
 

llvm/trunk/lib/CodeGen/SwitchLoweringUtils.cpp

#ifndef NDEBUG
   // Clusters must be non-empty, sorted, and only contain Range clusters.
   assert(!Clusters.empty());
   for (CaseCluster &C : Clusters)
     assert(C.Kind == CC_Range);
   for (unsigned i = 1, e = Clusters.size(); i < e; ++i)
     assert(Clusters[i - 1].High->getValue().slt(Clusters[i].Low->getValue()));
 #endif
 
+  assert(TLI && "TLI not set!");
   if (!TLI->areJTsAllowed(SI->getParent()->getParent()))
     return;
 
   const unsigned MinJumpTableEntries = TLI->getMinimumJumpTableEntries();
   const unsigned SmallNumberOfEntries = MinJumpTableEntries / 2;
 
   // Bail if not enough cases.
   const int64_t N = Clusters.size();

llvm/trunk/test/CodeGen/AArch64/GlobalISel/arm64-irtranslator-switch.ll

+; 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
+}
+

llvm/trunk/test/CodeGen/AArch64/GlobalISel/arm64-irtranslator.ll

define void @condbr(i1* %tstaddr) {
   %tst = load i1, i1* %tstaddr
   br i1 %tst, label %true, label %false
 true:
   ret void
 false:
   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:
 ;
 ; ABI/constant lowering and IR-level entry basic block.
 ; CHECK: bb.{{[0-9]+.[a-zA-Z0-9.]+}}:
 ; Make sure we have one successor
 ; CHECK-NEXT: successors: %[[BB_L1:bb.[0-9]+]](0x80000000)