Support critical edge splitting for jump tables

[MatzeB]

Summary

Add support for splitting critical edges coming from an indirect jump
using a jump table ("switch jumps").

This introduces the TargetInstrInfo::getJumpTableIndex callback to
allows targets to return an index into MachineJumpTableInfo for a
given indirect jump. It also updates to
MachineBasicBlock::SplitCriticalEdge to allow splitting of critical
edges by rewriting jump table entries.

This is largely based on work done by Zhixuan Huan in D132202.

[MatzeB]

rebase and ping.

[craig.topper]

llvm/lib/Target/X86/X86InstrInfo.cpp

3238

The non-PIC code has the %X scaled by 8, but the PIC code doesn't show a scale. What accounts for the difference?

3244

Drop else after return

[MatzeB]

llvm/lib/Target/X86/X86InstrInfo.cpp

3238

The full code pattern looks something like with the scaling happening in the MOVSX64rm32. I just didn't explicitely mention it as we don't bother looking at that part of the pattern because we only need to find the %jump-table operand. It looks something like this:

%XX = ...
%0:gr64 = LEA64r $rip, 1, $noreg, %jump-table.0, $noreg
%1:gr64 = MOVSX64rm32 %0:gr64, 4, %XX:gr64_nosp, 0, $noreg :: (load (s32) from jump-table)
%2:gr64 = ADD64rr %1:gr64(tied-def 0), %0:gr64, implicit-def dead $eflags

I will update the comment here to reduce the confusion.

[efriedma]

llvm/lib/CodeGen/MachineBasicBlock.cpp

1106

Have we proven at this point that this jump is the only use of the jump table in question? With optimizations like tail duplication, you could have multiple basic blocks referencing the same table.

[MatzeB]

• Fix unnecessary/dead jump getting added behind the indirect jump
• Ensure that jump table does not have multiple users and do not split otherwise

[MatzeB]

llvm/lib/CodeGen/MachineBasicBlock.cpp

1106

Good point!

As far as I can tell this case is somewhat rare as most switch-jumps are preceded by a range check which is not profitable for tail-duplication. Given that I decided to just detect and not performing the edge splitting in case of multiple users.

[MatzeB]

ping

[craig.topper]

llvm/lib/Target/X86/X86InstrInfo.cpp

3243

I'm not sure I understand this code. The MOVSXrm32 is loading from %0, sign extending it, and then adds what it loaded also to %0?

[MatzeB]

llvm/lib/Target/X86/X86InstrInfo.cpp

3243

This is how clang generates the code. I mention it here as a reminder for the pattern the code below is searching for.

If you look at the assembly of an example compiled with -fPIC you see that the entries in the table record the basic block address relative to the beginning of the jump table. Hence we first need to load from the table and in a 2nd step add the base address of the table to get the final address.

I see something like this for small examples:

   ...
   leaq    .LJTI0_0(%rip), %rax
   movslq  (%rax,%rdi,4), %rcx
   addq    %rax, %rcx
   jmpq    *%rcx
.LBB0_2:
   ...
.LBB0_3:
   ...
...

...

.LJTI0_0:
   .long   .LBB0_2-.LJTI0_0
   .long   .LBB0_3-.LJTI0_0
   ...

[craig.topper]

LGTM

llvm/lib/Target/X86/X86InstrInfo.cpp

3243

Thanks for the explanation.

llvm/include/llvm/CodeGen/TargetInstrInfo.h

public:
   ///
   /// @param MO The MachineOperand in question. MO.isReg() should always
   /// be true.
   /// @return Whether this operand is allowed to be used PC-relatively.
   virtual bool isPCRelRegisterOperandLegal(const MachineOperand &MO) const {
     return false;
   }
 
+  /// Return an index for MachineJumpTableInfo if \p insn is an indirect jump
+  /// using a jump table, otherwise -1.
+  virtual int getJumpTableIndex(const MachineInstr &MI) const { return -1; }
+
 protected:
   /// Target-dependent implementation for IsCopyInstr.
   /// If the specific machine instruction is a instruction that moves/copies
   /// value from one register to another register return destination and source
   /// registers as machine operands.
   virtual std::optional<DestSourcePair>
   isCopyInstrImpl(const MachineInstr &MI) const {
     return std::nullopt;

llvm/lib/CodeGen/MachineBasicBlock.cpp

 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/CodeGen/LiveIntervals.h"
 #include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/Config/llvm-config.h"

 void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
   getParent()->splice(NewAfter->getIterator(), getIterator());
 }
 
 void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
   getParent()->splice(++NewBefore->getIterator(), getIterator());
 }
 
+static int findJumpTableIndex(const MachineBasicBlock &MBB) {
+  MachineBasicBlock::const_iterator TerminatorI = MBB.getFirstTerminator();
+  if (TerminatorI == MBB.end())
+    return -1;
+  const MachineInstr &Terminator = *TerminatorI;
+  const TargetInstrInfo *TII = MBB.getParent()->getSubtarget().getInstrInfo();
+  return TII->getJumpTableIndex(Terminator);
+}
+
 void MachineBasicBlock::updateTerminator(
     MachineBasicBlock *PreviousLayoutSuccessor) {
   LLVM_DEBUG(dbgs() << "Updating terminators on " << printMBBReference(*this)
                     << "\n");
 
   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
   // A block with no successors has no concerns with fall-through edges.
   if (this->succ_empty())
if (UpdateLiveIns)
     addLiveIns(*SplitBB, LiveRegs);
 
   if (LIS)
     LIS->insertMBBInMaps(SplitBB);
 
   return SplitBB;
 }
 
+// Returns `true` if there are possibly other users of the jump table at
+// `JumpTableIndex` except for the ones in `IgnoreMBB`.
+static bool jumpTableHasOtherUses(const MachineFunction &MF,
+                                  const MachineBasicBlock &IgnoreMBB,
+                                  int JumpTableIndex) {
+  assert(JumpTableIndex >= 0 && "need valid index");
+  const MachineJumpTableInfo &MJTI = *MF.getJumpTableInfo();
+  const MachineJumpTableEntry &MJTE = MJTI.getJumpTables()[JumpTableIndex];
+  // Take any basic block from the table; every user of the jump table must
+  // show up in the predecessor list.
+  const MachineBasicBlock *MBB = nullptr;
+  for (MachineBasicBlock *B : MJTE.MBBs) {
+    if (B != nullptr) {
+      MBB = B;
+      break;
+    }
+  }
+  if (MBB == nullptr)
+    return true; // can't rule out other users if there isn't any block.
+  const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
+  SmallVector<MachineOperand, 4> Cond;
+  for (MachineBasicBlock *Pred : MBB->predecessors()) {
+    if (Pred == &IgnoreMBB)
+      continue;
+    MachineBasicBlock *DummyT = nullptr;
+    MachineBasicBlock *DummyF = nullptr;
+    Cond.clear();
+    if (!TII.analyzeBranch(*Pred, DummyT, DummyF, Cond,
+                           /*AllowModify=*/false)) {
+      // analyzable direct jump
+      continue;
+    }
+    int PredJTI = findJumpTableIndex(*Pred);
+    if (PredJTI >= 0) {
+      if (PredJTI == JumpTableIndex)
+        return true;
+      continue;
+    }
+    // Be conservative for unanalyzable jumps.
+    return true;
+  }
+  return false;
+}
+
 MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(
     MachineBasicBlock *Succ, Pass &P,
     std::vector<SparseBitVector<>> *LiveInSets) {
   if (!canSplitCriticalEdge(Succ))
     return nullptr;
 
   MachineFunction *MF = getParent();
   MachineBasicBlock *PrevFallthrough = getNextNode();
   DebugLoc DL;  // FIXME: this is nowhere
 
   MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
+
+  // Is there an indirect jump with jump table?
+  bool ChangedIndirectJump = false;
+  int JTI = findJumpTableIndex(*this);
+  if (JTI >= 0) {
+    MachineJumpTableInfo &MJTI = *MF->getJumpTableInfo();
+    MJTI.ReplaceMBBInJumpTable(JTI, Succ, NMBB);
+    ChangedIndirectJump = true;
+  }
+
   MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
   LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)
                     << " -- " << printMBBReference(*NMBB) << " -- "
                     << printMBBReference(*Succ) << '\n');
 
   LiveIntervals *LIS = P.getAnalysisIfAvailable<LiveIntervals>();
   SlotIndexes *Indexes = P.getAnalysisIfAvailable<SlotIndexes>();
   if (LIS)
for (MachineInstr &MI :
          llvm::make_range(getFirstInstrTerminator(), instr_end()))
       Terminators.push_back(&MI);
   }
 
   // Since we replaced all uses of Succ with NMBB, that should also be treated
   // as the fallthrough successor
   if (Succ == PrevFallthrough)
     PrevFallthrough = NMBB;
+
+  if (!ChangedIndirectJump)
     updateTerminator(PrevFallthrough);
 
   if (Indexes) {
     SmallVector<MachineInstr*, 4> NewTerminators;
     for (MachineInstr &MI :
          llvm::make_range(getFirstInstrTerminator(), instr_end()))
       NewTerminators.push_back(&MI);
 
     for (MachineInstr *Terminator : Terminators) {
if (Succ->isInlineAsmBrIndirectTarget())
     return false;
 
   const MachineFunction *MF = getParent();
   // Performance might be harmed on HW that implements branching using exec mask
   // where both sides of the branches are always executed.
   if (MF->getTarget().requiresStructuredCFG())
     return false;
 
+  // Do we have an Indirect jump with a jumptable that we can rewrite?
+  int JTI = findJumpTableIndex(*this);
+  if (JTI >= 0 && !jumpTableHasOtherUses(*MF, *this, JTI))
+    return true;
+
   // We may need to update this's terminator, but we can't do that if
-  // analyzeBranch fails. If this uses a jump table, we won't touch it.
+  // analyzeBranch fails.
   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
   SmallVector<MachineOperand, 4> Cond;
   // AnalyzeBanch should modify this, since we did not allow modification.
   if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
                          /*AllowModify*/ false))
     return false;
 

llvm/lib/Target/X86/X86InstrInfo.h

void replaceBranchWithTailCall(MachineBasicBlock &MBB,
                                  SmallVectorImpl<MachineOperand> &Cond,
                                  const MachineInstr &TailCall) const override;
 
   bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
                      MachineBasicBlock *&FBB,
                      SmallVectorImpl<MachineOperand> &Cond,
                      bool AllowModify) const override;
 
+  int getJumpTableIndex(const MachineInstr &MI) const override;
+
   std::optional<ExtAddrMode>
   getAddrModeFromMemoryOp(const MachineInstr &MemI,
                           const TargetRegisterInfo *TRI) const override;
 
   bool getConstValDefinedInReg(const MachineInstr &MI, const Register Reg,
                                int64_t &ImmVal) const override;
 
   bool preservesZeroValueInReg(const MachineInstr *MI,

llvm/lib/Target/X86/X86InstrInfo.cpp

bool X86InstrInfo::analyzeBranch(MachineBasicBlock &MBB,
                                  MachineBasicBlock *&TBB,
                                  MachineBasicBlock *&FBB,
                                  SmallVectorImpl<MachineOperand> &Cond,
                                  bool AllowModify) const {
   SmallVector<MachineInstr *, 4> CondBranches;
   return AnalyzeBranchImpl(MBB, TBB, FBB, Cond, CondBranches, AllowModify);
 }
 
+static int getJumpTableIndexFromAddr(const MachineInstr &MI) {
+  const MCInstrDesc &Desc = MI.getDesc();
+  int MemRefBegin = X86II::getMemoryOperandNo(Desc.TSFlags);
+  assert(MemRefBegin >= 0 && "instr should have memory operand");
+  MemRefBegin += X86II::getOperandBias(Desc);
+
+  const MachineOperand &MO = MI.getOperand(MemRefBegin + X86::AddrDisp);
+  if (!MO.isJTI())
+    return -1;
+
+  return MO.getIndex();
+}
+
+static int getJumpTableIndexFromReg(const MachineRegisterInfo &MRI,
+                                    Register Reg) {
+  if (!Reg.isVirtual())
+    return -1;
+  MachineInstr *MI = MRI.getUniqueVRegDef(Reg);
+  if (MI == nullptr)
+    return -1;
+  unsigned Opcode = MI->getOpcode();
+  if (Opcode != X86::LEA64r && Opcode != X86::LEA32r)
+    return -1;
+  return getJumpTableIndexFromAddr(*MI);
+}
+
+int X86InstrInfo::getJumpTableIndex(const MachineInstr &MI) const {
+  unsigned Opcode = MI.getOpcode();
+  // Switch-jump pattern for non-PIC code looks like:
+  //   JMP64m $noreg, 8, %X, %jump-table.X, $noreg
+  if (Opcode == X86::JMP64m || Opcode == X86::JMP32m) {
+    return getJumpTableIndexFromAddr(MI);
+  }
+  // The pattern for PIC code looks like:
+  //   %0 = LEA64r $rip, 1, $noreg, %jump-table.X
+  //   %1 = MOVSX64rm32 %0, 4, XX, 0, $noreg
+  //   %2 = ADD64rr %1, %0
+  //   JMP64r %2
+  if (Opcode == X86::JMP64r || Opcode == X86::JMP32r) {
+    Register Reg = MI.getOperand(0).getReg();
+    if (!Reg.isVirtual())
+      return -1;
+    const MachineFunction &MF = *MI.getParent()->getParent();
+    const MachineRegisterInfo &MRI = MF.getRegInfo();
+    MachineInstr *Add = MRI.getUniqueVRegDef(Reg);
+    if (Add == nullptr)
+      return -1;
+    if (Add->getOpcode() != X86::ADD64rr && Add->getOpcode() != X86::ADD32rr)
+      return -1;
+    int JTI1 = getJumpTableIndexFromReg(MRI, Add->getOperand(1).getReg());
+    if (JTI1 >= 0)
+      return JTI1;
+    int JTI2 = getJumpTableIndexFromReg(MRI, Add->getOperand(2).getReg());
+    if (JTI2 >= 0)
+      return JTI2;
+  }
+  return -1;
+}
+
 bool X86InstrInfo::analyzeBranchPredicate(MachineBasicBlock &MBB,
                                           MachineBranchPredicate &MBP,
                                           bool AllowModify) const {
   using namespace std::placeholders;
 
   SmallVector<MachineOperand, 4> Cond;
   SmallVector<MachineInstr *, 4> CondBranches;
   if (AnalyzeBranchImpl(MBB, MBP.TrueDest, MBP.FalseDest, Cond, CondBranches,

llvm/test/CodeGen/X86/switch-jmp-edge-split.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=x86_64-- -run-pass=machine-sink -verify-machineinstrs  -o - %s | FileCheck %s
+
+---
+name:            func_no_pic
+tracksRegLiveness: true
+jumpTable:
+  kind:            block-address
+  entries:
+    - id:              0
+      blocks:          [ '%bb.4', '%bb.1', '%bb.2', '%bb.3' ]
+body:             |
+  ; CHECK-LABEL: name: func_no_pic
+  ; CHECK: bb.0:
+  ; CHECK-NEXT:   successors: %bb.5(0x20000000), %bb.1(0x20000000), %bb.2(0x20000000), %bb.3(0x20000000)
+  ; CHECK-NEXT:   liveins: $edi
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gr64_nosp = COPY $rdi
+  ; CHECK-NEXT:   JMP64m $noreg, 8, [[COPY]], %jump-table.0, $noreg :: (load (s64) from jump-table)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.5:
+  ; CHECK-NEXT:   successors: %bb.4(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32ri:%[0-9]+]]:gr32 = MOV32ri 42
+  ; CHECK-NEXT:   JMP_1 %bb.4
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.4(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32ri1:%[0-9]+]]:gr32 = MOV32ri 6
+  ; CHECK-NEXT:   JMP_1 %bb.4
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.4(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32ri2:%[0-9]+]]:gr32 = MOV32ri 1
+  ; CHECK-NEXT:   JMP_1 %bb.4
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   successors: %bb.4(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32ri3:%[0-9]+]]:gr32 = MOV32ri 92
+  ; CHECK-NEXT:   JMP_1 %bb.4
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.4:
+  ; CHECK-NEXT:   [[PHI:%[0-9]+]]:gr32 = PHI [[MOV32ri]], %bb.5, [[MOV32ri1]], %bb.1, [[MOV32ri2]], %bb.2, [[MOV32ri3]], %bb.3
+  ; CHECK-NEXT:   $eax = COPY [[PHI]]
+  ; CHECK-NEXT:   RET 0
+  bb.0:
+    successors: %bb.4, %bb.1, %bb.2, %bb.3
+    liveins: $edi
+
+    %0:gr64_nosp = COPY $rdi
+    ; MachineSink should split the critical edges and sink the next two
+    ; insns out of the switch-jump header into new less frequently executed
+    ; blocks.
+    %1:gr32 = MOV32ri 42
+    JMP64m $noreg, 8, %0, %jump-table.0, $noreg :: (load (s64) from jump-table)
+
+  bb.1:
+    %2:gr32 = MOV32ri 6
+    JMP_1 %bb.4
+
+  bb.2:
+    %3:gr32 = MOV32ri 1
+    JMP_1 %bb.4
+
+  bb.3:
+    %4:gr32 = MOV32ri 92
+    JMP_1 %bb.4
+
+  bb.4:
+    %5:gr32 = PHI %1, %bb.0, %2, %bb.1, %3, %bb.2, %4, %bb.3
+    $eax = COPY %5
+    RET 0
+
+...
+---
+name:            func_pic
+tracksRegLiveness: true
+jumpTable:
+  kind:            label-difference32
+  entries:
+    - id:              0
+      blocks:          [ '%bb.4', '%bb.1', '%bb.2', '%bb.3' ]
+body:             |
+  ; CHECK-LABEL: name: func_pic
+  ; CHECK: bb.0:
+  ; CHECK-NEXT:   successors: %bb.5(0x20000000), %bb.1(0x20000000), %bb.2(0x20000000), %bb.3(0x20000000)
+  ; CHECK-NEXT:   liveins: $edi
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gr64_nosp = COPY $rdi
+  ; CHECK-NEXT:   [[LEA64r:%[0-9]+]]:gr64 = LEA64r $rip, 1, $noreg, %jump-table.0, $noreg
+  ; CHECK-NEXT:   [[MOVSX64rm32_:%[0-9]+]]:gr64 = MOVSX64rm32 [[LEA64r]], 4, [[COPY]], 0, $noreg :: (load (s32) from jump-table)
+  ; CHECK-NEXT:   [[ADD64rr:%[0-9]+]]:gr64 = ADD64rr [[MOVSX64rm32_]], [[LEA64r]], implicit-def dead $eflags
+  ; CHECK-NEXT:   JMP64r killed [[ADD64rr]]
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.5:
+  ; CHECK-NEXT:   successors: %bb.4(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32ri:%[0-9]+]]:gr32 = MOV32ri 42
+  ; CHECK-NEXT:   JMP_1 %bb.4
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.4(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32ri1:%[0-9]+]]:gr32 = MOV32ri 6
+  ; CHECK-NEXT:   JMP_1 %bb.4
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.4(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32ri2:%[0-9]+]]:gr32 = MOV32ri 1
+  ; CHECK-NEXT:   JMP_1 %bb.4
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   successors: %bb.4(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32ri3:%[0-9]+]]:gr32 = MOV32ri 92
+  ; CHECK-NEXT:   JMP_1 %bb.4
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.4:
+  ; CHECK-NEXT:   [[PHI:%[0-9]+]]:gr32 = PHI [[MOV32ri]], %bb.5, [[MOV32ri1]], %bb.1, [[MOV32ri2]], %bb.2, [[MOV32ri3]], %bb.3
+  ; CHECK-NEXT:   $eax = COPY [[PHI]]
+  ; CHECK-NEXT:   RET 0
+  bb.0:
+    successors: %bb.4, %bb.1, %bb.2, %bb.3
+    liveins: $edi
+
+    %0:gr64_nosp = COPY $rdi
+    ; MachineSink should split the critical edges and sink the next two
+    ; insns out of the switch-jump header into new less frequently executed
+    ; blocks.
+    %1:gr32 = MOV32ri 42
+    %2:gr64 = LEA64r $rip, 1, $noreg, %jump-table.0, $noreg
+    %3:gr64 = MOVSX64rm32 %2, 4, %0, 0, $noreg :: (load (s32) from jump-table)
+    %4:gr64 = ADD64rr %3, %2, implicit-def dead $eflags
+    JMP64r killed %4
+
+  bb.1:
+    %5:gr32 = MOV32ri 6
+    JMP_1 %bb.4
+
+  bb.2:
+    %6:gr32 = MOV32ri 1
+    JMP_1 %bb.4
+
+  bb.3:
+    %7:gr32 = MOV32ri 92
+    JMP_1 %bb.4
+
+  bb.4:
+    %8:gr32 = PHI %1, %bb.0, %5, %bb.1, %6, %bb.2, %7, %bb.3
+    $eax = COPY %8
+    RET 0
+
+...
+---
+name:            multiple_jump_table_users
+tracksRegLiveness: true
+jumpTable:
+  kind:            block-address
+  entries:
+    - id:              0
+      blocks:          [ '%bb.6', '%bb.3', '%bb.4', '%bb.5' ]
+body:             |
+  ; CHECK-LABEL: name: multiple_jump_table_users
+  ; CHECK: bb.0:
+  ; CHECK-NEXT:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
+  ; CHECK-NEXT:   liveins: $edi
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gr64_nosp = COPY $rdi
+  ; CHECK-NEXT:   CMP64ri8 [[COPY]], 42, implicit-def $eflags
+  ; CHECK-NEXT:   JCC_1 %bb.1, 15, implicit $eflags
+  ; CHECK-NEXT:   JMP_1 %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.6(0x20000000), %bb.3(0x20000000), %bb.4(0x20000000), %bb.5(0x20000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   INLINEASM &"", 1 /* sideeffect attdialect */
+  ; CHECK-NEXT:   [[MOV32ri:%[0-9]+]]:gr32 = MOV32ri 13
+  ; CHECK-NEXT:   JMP64m $noreg, 8, [[COPY]], %jump-table.0, $noreg :: (load (s64) from jump-table)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.6(0x20000000), %bb.3(0x20000000), %bb.4(0x20000000), %bb.5(0x20000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   INLINEASM &"", 1 /* sideeffect attdialect */
+  ; CHECK-NEXT:   [[MOV32ri1:%[0-9]+]]:gr32 = MOV32ri 42
+  ; CHECK-NEXT:   JMP64m $noreg, 8, [[COPY]], %jump-table.0, $noreg :: (load (s64) from jump-table)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   successors: %bb.6(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32ri2:%[0-9]+]]:gr32 = MOV32ri 6
+  ; CHECK-NEXT:   JMP_1 %bb.6
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.4:
+  ; CHECK-NEXT:   successors: %bb.6(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32ri3:%[0-9]+]]:gr32 = MOV32ri 1
+  ; CHECK-NEXT:   JMP_1 %bb.6
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.5:
+  ; CHECK-NEXT:   successors: %bb.6(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32ri4:%[0-9]+]]:gr32 = MOV32ri 92
+  ; CHECK-NEXT:   JMP_1 %bb.6
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.6:
+  ; CHECK-NEXT:   [[PHI:%[0-9]+]]:gr32 = PHI [[MOV32ri]], %bb.1, [[MOV32ri1]], %bb.2, [[MOV32ri2]], %bb.3, [[MOV32ri3]], %bb.4, [[MOV32ri4]], %bb.5
+  ; CHECK-NEXT:   $eax = COPY [[PHI]]
+  ; CHECK-NEXT:   RET 0
+  bb.0:
+    liveins: $edi
+    %0:gr64_nosp = COPY $rdi
+
+    CMP64ri8 %0:gr64_nosp, 42, implicit-def $eflags
+    JCC_1 %bb.1, 15, implicit $eflags
+    JMP_1 %bb.2
+
+  bb.1:
+    successors: %bb.6, %bb.3, %bb.4, %bb.5
+    INLINEASM &"", 1 /* sideeffect attdialect */
+    %1:gr32 = MOV32ri 13
+    JMP64m $noreg, 8, %0, %jump-table.0, $noreg :: (load (s64) from jump-table)
+
+  bb.2:
+    successors: %bb.6, %bb.3, %bb.4, %bb.5
+    INLINEASM &"", 1 /* sideeffect attdialect */
+    %2:gr32 = MOV32ri 42
+    ; This is a 2d user of jump-table.0 . This case is not supported yet;
+    ; Should not attempt edge splitting.
+    JMP64m $noreg, 8, %0, %jump-table.0, $noreg :: (load (s64) from jump-table)
+
+  bb.3:
+    %3:gr32 = MOV32ri 6
+    JMP_1 %bb.6
+
+  bb.4:
+    %4:gr32 = MOV32ri 1
+    JMP_1 %bb.6
+
+  bb.5:
+    %5:gr32 = MOV32ri 92
+    JMP_1 %bb.6
+
+  bb.6:
+    %6:gr32 = PHI %1, %bb.1, %2, %bb.2, %3, %bb.3, %4, %bb.4, %5, %bb.5
+    $eax = COPY %6
+    RET 0
+...

llvm/test/CodeGen/X86/switch-phi-const.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc %s -o - -mtriple=x86_64-- | FileCheck %s
 @g = global i32 0
 @effect = global i32 0
 
 define void @switch_phi_const(i32 %x) {
 ; CHECK-LABEL: switch_phi_const:
 ; CHECK:       # %bb.0: # %bb0
 ; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
-; CHECK-NEXT:    leal -1(%rdi), %ecx
-; CHECK-NEXT:    cmpl $54, %ecx
-; CHECK-NEXT:    ja .LBB0_8
+; CHECK-NEXT:    leal -1(%rdi), %eax
+; CHECK-NEXT:    cmpl $54, %eax
+; CHECK-NEXT:    ja .LBB0_9
 ; CHECK-NEXT:  # %bb.1: # %bb0
-; CHECK-NEXT:    movl $42, %eax
-; CHECK-NEXT:    jmpq *.LJTI0_0(,%rcx,8)
-; CHECK-NEXT:  .LBB0_2: # %case_7
+; CHECK-NEXT:    jmpq *.LJTI0_0(,%rax,8)
+; CHECK-NEXT:  .LBB0_3: # %case_7
 ; CHECK-NEXT:    movq g@GOTPCREL(%rip), %rax
 ; CHECK-NEXT:    movl (%rax), %edi
 ; CHECK-NEXT:    movq effect@GOTPCREL(%rip), %rax
 ; CHECK-NEXT:    movl $7, (%rax)
-; CHECK-NEXT:  .LBB0_3: # %case_1_loop
+; CHECK-NEXT:  .LBB0_4: # %case_1_loop
 ; CHECK-NEXT:    movq effect@GOTPCREL(%rip), %rax
 ; CHECK-NEXT:    movl $1, (%rax)
-; CHECK-NEXT:  .LBB0_4: # %case_5
+; CHECK-NEXT:  .LBB0_5: # %case_5
 ; CHECK-NEXT:    movq effect@GOTPCREL(%rip), %rax
 ; CHECK-NEXT:    movl $5, (%rax)
-; CHECK-NEXT:  .LBB0_5: # %case_13
+; CHECK-NEXT:  .LBB0_6: # %case_13
 ; CHECK-NEXT:    movq effect@GOTPCREL(%rip), %rax
 ; CHECK-NEXT:    movl $13, (%rax)
-; CHECK-NEXT:  .LBB0_6: # %case_42
+; CHECK-NEXT:  .LBB0_7: # %case_42
 ; CHECK-NEXT:    movq effect@GOTPCREL(%rip), %rax
 ; CHECK-NEXT:    movl %edi, (%rax)
 ; CHECK-NEXT:    movl $55, %eax
-; CHECK-NEXT:  .LBB0_7: # %case_55
+; CHECK-NEXT:  .LBB0_8: # %case_55
 ; CHECK-NEXT:    movq effect@GOTPCREL(%rip), %rcx
 ; CHECK-NEXT:    movl %eax, (%rcx)
-; CHECK-NEXT:  .LBB0_8: # %default
+; CHECK-NEXT:  .LBB0_9: # %default
 ; CHECK-NEXT:    retq
+; CHECK-NEXT:  .LBB0_2:
+; CHECK-NEXT:    movl $42, %eax
+; CHECK-NEXT:    jmp .LBB0_8
 bb0:
   switch i32 %x, label %default [
   i32 1, label %case_1_loop
   i32 5, label %case_5
   i32 7, label %case_7
   i32 13, label %case_13
   i32 42, label %case_42
   i32 55, label %case_55

 @effect64 = global i64 0
 
 define void @switch_trunc_phi_const(i32 %x) {
 ; CHECK-LABEL: switch_trunc_phi_const:
 ; CHECK:       # %bb.0: # %bb0
 ; CHECK-NEXT:    movzbl %dil, %eax
 ; CHECK-NEXT:    leal -1(%rax), %ecx
 ; CHECK-NEXT:    cmpl $54, %ecx
-; CHECK-NEXT:    ja .LBB1_8
+; CHECK-NEXT:    ja .LBB1_9
 ; CHECK-NEXT:  # %bb.1: # %bb0
-; CHECK-NEXT:    movl $3895, %edx # imm = 0xF37
 ; CHECK-NEXT:    jmpq *.LJTI1_0(,%rcx,8)
-; CHECK-NEXT:  .LBB1_8: # %default
+; CHECK-NEXT:  .LBB1_2:
+; CHECK-NEXT:    movl $3895, %eax # imm = 0xF37
+; CHECK-NEXT:    jmp .LBB1_7
+; CHECK-NEXT:  .LBB1_9: # %default
 ; CHECK-NEXT:    retq
-; CHECK-NEXT:  .LBB1_2: # %case_1_loop
+; CHECK-NEXT:  .LBB1_3: # %case_1_loop
 ; CHECK-NEXT:    movq effect64@GOTPCREL(%rip), %rcx
 ; CHECK-NEXT:    movq $1, (%rcx)
-; CHECK-NEXT:  .LBB1_3: # %case_5
+; CHECK-NEXT:  .LBB1_4: # %case_5
 ; CHECK-NEXT:    movq effect64@GOTPCREL(%rip), %rcx
 ; CHECK-NEXT:    movq $5, (%rcx)
-; CHECK-NEXT:  .LBB1_4: # %case_13
+; CHECK-NEXT:  .LBB1_5: # %case_13
 ; CHECK-NEXT:    movq effect64@GOTPCREL(%rip), %rcx
 ; CHECK-NEXT:    movq $13, (%rcx)
-; CHECK-NEXT:  .LBB1_5: # %case_42
+; CHECK-NEXT:  .LBB1_6: # %case_42
+; CHECK-NEXT:    movq effect64@GOTPCREL(%rip), %rcx
+; CHECK-NEXT:    movq %rax, (%rcx)
+; CHECK-NEXT:    movl $55, %eax
+; CHECK-NEXT:  .LBB1_7: # %case_55
 ; CHECK-NEXT:    movq effect64@GOTPCREL(%rip), %rcx
 ; CHECK-NEXT:    movq %rax, (%rcx)
-; CHECK-NEXT:    movl $55, %edx
-; CHECK-NEXT:  .LBB1_6: # %case_55
-; CHECK-NEXT:    movq effect64@GOTPCREL(%rip), %rax
-; CHECK-NEXT:    movq %rdx, (%rax)
-; CHECK-NEXT:  .LBB1_7: # %case_7
+; CHECK-NEXT:  .LBB1_8: # %case_7
 ; CHECK-NEXT:    movq g64@GOTPCREL(%rip), %rax
 ; CHECK-NEXT:    movq (%rax), %rax
 ; CHECK-NEXT:    movq effect64@GOTPCREL(%rip), %rcx
 ; CHECK-NEXT:    movq $7, (%rcx)
-; CHECK-NEXT:    jmp .LBB1_2
+; CHECK-NEXT:    jmp .LBB1_3
 bb0:
   %x_trunc = trunc i32 %x to i8
   switch i8 %x_trunc, label %default [
   i8 1, label %case_1_loop
   i8 5, label %case_5
   i8 7, label %case_7
   i8 13, label %case_13
   i8 42, label %case_42