[CodeGen] JumpMaps switch statement optimization (stub)

[MartaW]

Summary

The patch partially implements JumpMaps switch statement optimization (refer to "(RFC) JumpMaps: switch statement optimization" on llvm-dev).
The transformation is not fully implemented yet; the code is required for further discussion.
The JumpMaps emission is turned on with --enable-jump-maps flag (disabled by default).

Current caveats:

1. no support for PIC model
2. search functions are not created / linked automatically, the code generated with optimization needs to be manually linked to __jmfind_x_x functions which (not optimized and generic) implementation can be found in a temporary file jmdev/jmfind.c. The right solution for functions creation / calls / linking are to be discused.
3. the analysis pass should be run on a module, not on a function. it is also not up to date with last changes to SelectionDAGBuilder and TargetLowering.
4. No regression tests fail with JumpMaps disabled. 8 regression tests fails with enabled JumpMaps are expected and caused by either modifying switch statement lowering (JumpMaps change switches handling so, naturally, basic blocks and emitted code look different) or lack of support for PIC model yet. These tests are: LLVM :: CodeGen/Generic/MachineBranchProb.ll LLVM :: CodeGen/X86/branchfolding-catchpads.ll LLVM :: CodeGen/X86/early-ifcvt.ll LLVM :: CodeGen/X86/switch-bt.ll LLVM :: CodeGen/X86/switch-edge-weight.ll LLVM :: CodeGen/X86/switch.ll LLVM :: CodeGen/X86/tail-merge-unreachable.ll LLVM :: CodeGen/X86/x86-shrink-wrapping.ll

[efriedma]

(I'm planning to look at this and add some comments; expect a reply next week.)

[MatzeB]

I like the general idea of jumpmaps as detailed on the mailinglist.

Can you motivate why this uses a new type of MachineOperand/ISDOpcode instead of somehow using just the existing JumpTable things?

[wwa]

I suppose it could be done with JumpTable struct, given some additional data but I feel that it is much more clean and elegant with a separete one.
For instance, a target might need special lowering for JumpMaps but not JumpTables, so it could use TargetLowering::setOperationAction(ISD::JumpMap, Custom).
If JumpMaps and JumpTables are combined under a single ISD, then Target has to look into the struct to figure out how to handle it.

Having a separete ISD reuses the existing Lowering logic best.

In D32742#751541, @MatzeB wrote:

I like the general idea of jumpmaps as detailed on the mailinglist.

Can you motivate why this uses a new type of MachineOperand/ISDOpcode instead of somehow using just the existing JumpTable things?

include/llvm/CodeGen/AsmPrinter.h

 class GlobalIndirectSymbol;
 class GlobalValue;
 class GlobalVariable;
 class GCStrategy;
 class MachineBasicBlock;
 class MachineConstantPoolValue;
 class MachineFunction;
 class MachineInstr;
+class MachineJumpMapInfo;
 class MachineJumpTableInfo;
 class MachineLoopInfo;
 class MachineModuleInfo;
 class MachineOptimizationRemarkEmitter;
 class MCAsmInfo;
 class MCCFIInstruction;
 class MCContext;
 class MCExpr;
public:
   bool needsSEHMoves();
 
   /// Print to the current output stream assembly representations of the
   /// constants in the constant pool MCP. This is used to print out constants
   /// which have been "spilled to memory" by the code generator.
   ///
   virtual void EmitConstantPool();
 
+  /// Print assembly representations of the jump maps used by the current
+  /// function to the current output stream.
+  ///
+  virtual void EmitJumpMapInfo();
+
   /// Print assembly representations of the jump tables used by the current
   /// function to the current output stream.
   ///
   virtual void EmitJumpTableInfo();
 
   /// Emit the specified global variable to the .s file.
   virtual void EmitGlobalVariable(const GlobalVariable *GV);
 
public:
   /// Return the MCSymbol for a private symbol with global value name as its
   /// base, with the specified suffix.
   MCSymbol *getSymbolWithGlobalValueBase(const GlobalValue *GV,
                                          StringRef Suffix) const;
 
   /// Return the MCSymbol for the specified ExternalSymbol.
   MCSymbol *GetExternalSymbolSymbol(StringRef Sym) const;
 
+  /// Return the symbol for the specified jump map entry.
+  MCSymbol *GetJMISymbol(unsigned JMID, bool isLinkerPrivate = false) const;
+
   /// Return the symbol for the specified jump table entry.
   MCSymbol *GetJTISymbol(unsigned JTID, bool isLinkerPrivate = false) const;
 
   /// Return the symbol for the specified jump table .set
   /// FIXME: privatize to AsmPrinter.
   MCSymbol *GetJTSetSymbol(unsigned UID, unsigned MBBID) const;
 
   /// Return the MCSymbol used to satisfy BlockAddress uses of the specified

include/llvm/CodeGen/FunctionLoweringInfo.h

 class GlobalVariable;
 class Instruction;
 class MachineInstr;
 class MachineBasicBlock;
 class MachineFunction;
 class MachineModuleInfo;
 class MachineRegisterInfo;
 class SelectionDAG;
+class SwitchAnalysis;
 class MVT;
 class TargetLowering;
 class Value;
 
 //===--------------------------------------------------------------------===//
 /// FunctionLoweringInfo - This contains information that is global to a
 /// function that is used when lowering a region of the function.
 ///
 class FunctionLoweringInfo {
 public:
   const Function *Fn;
   MachineFunction *MF;
   const TargetLowering *TLI;
   MachineRegisterInfo *RegInfo;
   BranchProbabilityInfo *BPI;
+  SwitchAnalysis *SWAN;
   /// CanLowerReturn - true iff the function's return value can be lowered to
   /// registers.
   bool CanLowerReturn;
 
   /// True if part of the CSRs will be handled via explicit copies.
   bool SplitCSR;
 
   /// DemoteRegister - if CanLowerReturn is false, DemoteRegister is a vreg

include/llvm/CodeGen/ISDOpcodes.h

enum NodeType {
     /// been extended, and the second is a value type node indicating the width
     /// of the extension
     AssertSext, AssertZext,
 
     /// Various leaf nodes.
     BasicBlock, VALUETYPE, CONDCODE, Register, RegisterMask,
     Constant, ConstantFP,
     GlobalAddress, GlobalTLSAddress, FrameIndex,
-    JumpTable, ConstantPool, ExternalSymbol, BlockAddress,
+    JumpTable, JumpMap, ConstantPool, ExternalSymbol, BlockAddress,
 
     /// The address of the GOT
     GLOBAL_OFFSET_TABLE,
 
     /// FRAMEADDR, RETURNADDR - These nodes represent llvm.frameaddress and
     /// llvm.returnaddress on the DAG.  These nodes take one operand, the index
     /// of the frame or return address to return.  An index of zero corresponds
     /// to the current function's frame or return address, an index of one to
enum NodeType {
 
     /// TargetGlobalAddress - Like GlobalAddress, but the DAG does no folding or
     /// anything else with this node, and this is valid in the target-specific
     /// dag, turning into a GlobalAddress operand.
     TargetGlobalAddress,
     TargetGlobalTLSAddress,
     TargetFrameIndex,
     TargetJumpTable,
+    TargetJumpMap,
     TargetConstantPool,
     TargetExternalSymbol,
     TargetBlockAddress,
 
     MCSymbol,
 
     /// TargetIndex - Like a constant pool entry, but with completely
     /// target-dependent semantics. Holds target flags, a 32-bit index, and a
enum NodeType {
     /// is the value to branch to, which must be of the same type as the
     /// target's pointer type.
     BRIND,
 
     /// BR_JT - Jumptable branch. The first operand is the chain, the second
     /// is the jumptable index, the last one is the jumptable entry index.
     BR_JT,
 
+    /// BR_JM - Jumpmap branch. The first operand is the chain, the second
+    /// is the jumpmap index, the third one is the jumpmap condition value,
+    /// the last one is the size of cases' keys in bits.
+    BR_JM,
+
     /// BRCOND - Conditional branch.  The first operand is the chain, the
     /// second is the condition, the third is the block to branch to if the
     /// condition is true.  If the type of the condition is not i1, then the
     /// high bits must conform to getBooleanContents.
     BRCOND,
 
     /// BR_CC - Conditional branch.  The behavior is like that of SELECT_CC, in
     /// that the condition is represented as condition code, and two nodes to

include/llvm/CodeGen/MachineFunction.h

 namespace llvm {
 
 class Value;
 class Function;
 class GCModuleInfo;
 class MachineRegisterInfo;
 class MachineFrameInfo;
 class MachineConstantPool;
+class MachineJumpMapInfo;
 class MachineJumpTableInfo;
 class MachineModuleInfo;
 class MCContext;
 class Pass;
 class PseudoSourceValueManager;
 class TargetMachine;
 class TargetSubtargetInfo;
 class TargetRegisterClass;
class MachineFunction {
   MachineFunctionInfo *MFInfo;
 
   // Keep track of objects allocated on the stack.
   MachineFrameInfo *FrameInfo;
 
   // Keep track of constants which are spilled to memory
   MachineConstantPool *ConstantPool;
 
+  // Keep track of jump maps for switch instructions
+  MachineJumpMapInfo *JumpMapInfo;
+
   // Keep track of jump tables for switch instructions
   MachineJumpTableInfo *JumpTableInfo;
 
   // Keeps track of Windows exception handling related data. This will be null
   // for functions that aren't using a funclet-based EH personality.
   WinEHFuncInfo *WinEHInfo = nullptr;
 
   // Function-level unique numbering for MachineBasicBlocks.  When a
public:
 
   /// getFrameInfo - Return the frame info object for the current function.
   /// This object contains information about objects allocated on the stack
   /// frame of the current function in an abstract way.
   ///
   MachineFrameInfo &getFrameInfo() { return *FrameInfo; }
   const MachineFrameInfo &getFrameInfo() const { return *FrameInfo; }
 
+  /// getJumpMapInfo - Return the jump map info object for the current
+  /// function. This object contains information about jump maps in the
+  /// current function. If the current function has no jump maps, this will
+  /// return null.
+  const MachineJumpMapInfo *getJumpMapInfo() const { return JumpMapInfo; }
+  MachineJumpMapInfo *getJumpMapInfo() { return JumpMapInfo; }
+
+  /// getOrCreateJumpMapInfo - Get the JumpMapInfo for this function, if it
+  /// does already exist, allocate one.
+  MachineJumpMapInfo *getOrCreateJumpMapInfo(unsigned JMEntryKind);
+
   /// getJumpTableInfo - Return the jump table info object for the current
   /// function.  This object contains information about jump tables in the
   /// current function.  If the current function has no jump tables, this will
   /// return null.
   const MachineJumpTableInfo *getJumpTableInfo() const { return JumpTableInfo; }
   MachineJumpTableInfo *getJumpTableInfo() { return JumpTableInfo; }
 
   /// getOrCreateJumpTableInfo - Get the JumpTableInfo for this function, if it
public:
 
   /// Allocate a string and populate it with the given external symbol name.
   const char *createExternalSymbolName(StringRef Name);
 
   //===--------------------------------------------------------------------===//
   // Label Manipulation.
   //
 
+  /// getJMISymbol - Return the MCSymbol for the specified non-empty jump map.
+  /// If isLinkerPrivate is specified, an 'l' label is returned, otherwise a
+  /// normal 'L' label is returned.
+  MCSymbol *getJMISymbol(unsigned JMI, MCContext &Ctx,
+                         bool isLinkerPrivate = false) const;
+
   /// getJTISymbol - Return the MCSymbol for the specified non-empty jump table.
   /// If isLinkerPrivate is specified, an 'l' label is returned, otherwise a
   /// normal 'L' label is returned.
   MCSymbol *getJTISymbol(unsigned JTI, MCContext &Ctx,
                          bool isLinkerPrivate = false) const;
 
   /// getPICBaseSymbol - Return a function-local symbol to represent the PIC
   /// base.

include/llvm/CodeGen/MachineInstrBuilder.h

public:
 
   const MachineInstrBuilder &addTargetIndex(unsigned Idx, int64_t Offset = 0,
                                           unsigned char TargetFlags = 0) const {
     MI->addOperand(*MF, MachineOperand::CreateTargetIndex(Idx, Offset,
                                                           TargetFlags));
     return *this;
   }
 
+  const MachineInstrBuilder &addJumpMapIndex(unsigned Idx,
+                                          unsigned char TargetFlags = 0) const {
+    MI->addOperand(*MF, MachineOperand::CreateJMI(Idx, TargetFlags));
+    return *this;
+  }
+
   const MachineInstrBuilder &addJumpTableIndex(unsigned Idx,
                                           unsigned char TargetFlags = 0) const {
     MI->addOperand(*MF, MachineOperand::CreateJTI(Idx, TargetFlags));
     return *this;
   }
 
   const MachineInstrBuilder &addGlobalAddress(const GlobalValue *GV,
                                               int64_t Offset = 0,

include/llvm/CodeGen/MachineJumpMapInfo.h

+//===-- CodeGen/MachineJumpMapInfo.h - Abstract Jump Tables  --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// The MachineJumpMapInfo class keeps track of jump maps referenced by
+// lowered switch instructions in the MachineFunction.
+//
+// Instructions reference the address of these jump maps through the use of
+// MO_JumpMapIndex values.  When emitting assembly or machine code, these
+// virtual address references are converted to refer to the address of the
+// function jump maps.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_MACHINEJUMPMAPINFO_H
+#define LLVM_CODEGEN_MACHINEJUMPMAPINFO_H
+
+#include <cassert>
+#include <vector>
+#include <map>
+
+namespace llvm {
+
+class MachineBasicBlock;
+class DataLayout;
+class raw_ostream;
+
+/// MachineJumpMapEntry - One jump map in the jump map info.
+///
+struct MachineJumpMapEntry {
+  /// The default case basic block
+  MachineBasicBlock *Default;
+
+  /// MBBs - The case => basic block mapping
+  std::map<uint64_t, MachineBasicBlock*> MBBs;
+
+  /// Size of the key
+  unsigned KeySize;
+
+  explicit MachineJumpMapEntry(std::map<uint64_t, MachineBasicBlock*> &M,
+                               MachineBasicBlock* D,
+                               unsigned S)
+  : Default(D), MBBs(M), KeySize(S) {}
+  unsigned getKeySize() const {
+    return KeySize;
+  }
+};
+
+class MachineJumpMapInfo {
+public:
+  /// JMEntryKind - This enum indicates how each entry of the jump map is
+  /// represented and emitted.
+  enum JMEntryKind {
+    /// EK_BlockAddress - Each entry is a plain address of block, e.g.:
+    ///     .word LBB123
+    EK_BlockAddress,
+
+    // NOTE: not supported for now: // JMFIXME
+#if 0
+    /// EK_GPRel64BlockAddress - Each entry is an address of block, encoded
+    /// with a relocation as gp-relative, e.g.:
+    ///     .gpdword LBB123
+    EK_GPRel64BlockAddress,
+
+    /// EK_GPRel32BlockAddress - Each entry is an address of block, encoded
+    /// with a relocation as gp-relative, e.g.:
+    ///     .gprel32 LBB123
+    EK_GPRel32BlockAddress,
+
+    /// EK_LabelDifference32 - Each entry is the address of the block minus
+    /// the address of the jump map.  This is used for PIC jump maps where
+    /// gprel32 is not supported.  e.g.:
+    ///      .word LBB123 - LJTI1_2
+    /// If the .set directive is supported, this is emitted as:
+    ///      .set L4_5_set_123, LBB123 - LJTI1_2
+    ///      .word L4_5_set_123
+    EK_LabelDifference32,
+
+    /// EK_Inline - Jump map entries are emitted inline at their point of
+    /// use. It is the responsibility of the target to emit the entries.
+    EK_Inline,
+
+    /// EK_Custom32 - Each entry is a 32-bit value that is custom lowered by the
+    /// TargetLowering::LowerCustomJumpMapEntry hook.
+    EK_Custom32
+#endif
+  };
+private:
+  JMEntryKind EntryKind;
+  std::vector<MachineJumpMapEntry> JumpMaps;
+public:
+  explicit MachineJumpMapInfo(JMEntryKind Kind): EntryKind(Kind) {}
+
+  JMEntryKind getEntryKind() const { return EntryKind; }
+
+  /// getEntryAlignment - Return the alignment of jump map entry.
+  unsigned getEntryAlignment(const DataLayout &TD) const;
+
+  /// getEntrySize - Return the size of a value in the jump map.
+  unsigned getValueSize(const DataLayout &TD) const;
+
+  /// createJumpMapIndex - Create a new jump map.
+  unsigned createJumpMapIndex(std::map<uint64_t,MachineBasicBlock*> &DestBBs,
+                              MachineBasicBlock *Default, unsigned KeySize);
+
+  /// isEmpty - Return true if there are no jump maps.
+  bool isEmpty() const { return JumpMaps.empty(); }
+
+  const std::vector<MachineJumpMapEntry> &getJumpMaps() const {
+    return JumpMaps;
+  }
+
+  /// RemoveJumpMap - Mark the specific index as being dead.  This will
+  /// prevent it from being emitted.
+  void RemoveJumpMap(unsigned Idx) {
+    JumpMaps[Idx].MBBs.clear();
+  }
+
+  /// ReplaceMBBInJumpMaps - If Old is the target of any jump maps, update
+  /// the jump maps to branch to New instead.
+  bool ReplaceMBBInJumpMaps(MachineBasicBlock *Old, MachineBasicBlock *New);
+
+  /// ReplaceMBBInJumpMap - If Old is a target of the jump maps, update
+  /// the jump map to branch to New instead.
+  bool ReplaceMBBInJumpMap(unsigned Idx, MachineBasicBlock *Old,
+                             MachineBasicBlock *New);
+
+  /// print - Used by the MachineFunction printer to print information about
+  /// jump maps.  Implemented in MachineFunction.cpp
+  void print(raw_ostream &OS) const;
+
+  /// dump - Call to stderr.
+  void dump() const;
+};
+
+} // End llvm namespace
+
+#endif

include/llvm/CodeGen/MachineMemOperand.h

struct MachinePointerInfo {
   /// Return a MachinePointerInfo record that refers to the specified
   /// FrameIndex.
   static MachinePointerInfo getFixedStack(MachineFunction &MF, int FI,
                                           int64_t Offset = 0);
 
   /// Return a MachinePointerInfo record that refers to a jump table entry.
   static MachinePointerInfo getJumpTable(MachineFunction &MF);
 
+  /// Return a MachinePointerInfo record that refers to a jump map entry.
+  static MachinePointerInfo getJumpMap(MachineFunction &MF);
+
   /// Return a MachinePointerInfo record that refers to a GOT entry.
   static MachinePointerInfo getGOT(MachineFunction &MF);
 
   /// Stack pointer relative access.
   static MachinePointerInfo getStack(MachineFunction &MF, int64_t Offset);
 };
 
 

include/llvm/CodeGen/MachineOperand.h

enum MachineOperandType : unsigned char {
     MO_Register,          ///< Register operand.
     MO_Immediate,         ///< Immediate operand
     MO_CImmediate,        ///< Immediate >64bit operand
     MO_FPImmediate,       ///< Floating-point immediate operand
     MO_MachineBasicBlock, ///< MachineBasicBlock reference
     MO_FrameIndex,        ///< Abstract Stack Frame Index
     MO_ConstantPoolIndex, ///< Address of indexed Constant in Constant Pool
     MO_TargetIndex,       ///< Target-dependent index+offset operand.
+    MO_JumpMapIndex,      ///< Address of indexed Jump Map for switch
     MO_JumpTableIndex,    ///< Address of indexed Jump Table for switch
     MO_ExternalSymbol,    ///< Name of external global symbol
     MO_GlobalAddress,     ///< Address of a global value
     MO_BlockAddress,      ///< Address of a basic block
     MO_RegisterMask,      ///< Mask of preserved registers.
     MO_RegisterLiveOut,   ///< Mask of live-out registers.
     MO_Metadata,          ///< Metadata reference (for debug info)
     MO_MCSymbol,          ///< MCSymbol reference (for debug/eh info)
public:
   /// isMBB - Tests if this is a MO_MachineBasicBlock operand.
   bool isMBB() const { return OpKind == MO_MachineBasicBlock; }
   /// isFI - Tests if this is a MO_FrameIndex operand.
   bool isFI() const { return OpKind == MO_FrameIndex; }
   /// isCPI - Tests if this is a MO_ConstantPoolIndex operand.
   bool isCPI() const { return OpKind == MO_ConstantPoolIndex; }
   /// isTargetIndex - Tests if this is a MO_TargetIndex operand.
   bool isTargetIndex() const { return OpKind == MO_TargetIndex; }
+  /// isJMI - Tests if this is a MO_JumpMapIndex operand.
+  bool isJMI() const { return OpKind == MO_JumpMapIndex; }
   /// isJTI - Tests if this is a MO_JumpTableIndex operand.
   bool isJTI() const { return OpKind == MO_JumpTableIndex; }
   /// isGlobal - Tests if this is a MO_GlobalAddress operand.
   bool isGlobal() const { return OpKind == MO_GlobalAddress; }
   /// isSymbol - Tests if this is a MO_ExternalSymbol operand.
   bool isSymbol() const { return OpKind == MO_ExternalSymbol; }
   /// isBlockAddress - Tests if this is a MO_BlockAddress operand.
   bool isBlockAddress() const { return OpKind == MO_BlockAddress; }
public:
   }
 
   MachineBasicBlock *getMBB() const {
     assert(isMBB() && "Wrong MachineOperand accessor");
     return Contents.MBB;
   }
 
   int getIndex() const {
-    assert((isFI() || isCPI() || isTargetIndex() || isJTI()) &&
+    assert((isFI() || isCPI() || isTargetIndex() || isJTI() || isJMI()) &&
            "Wrong MachineOperand accessor");
     return Contents.OffsetedInfo.Val.Index;
   }
 
   const GlobalValue *getGlobal() const {
     assert(isGlobal() && "Wrong MachineOperand accessor");
     return Contents.OffsetedInfo.Val.GV;
   }
void setOffset(int64_t Offset) {
     assert((isGlobal() || isSymbol() || isMCSymbol() || isCPI() ||
             isTargetIndex() || isBlockAddress()) &&
            "Wrong MachineOperand mutator");
     SmallContents.OffsetLo = unsigned(Offset);
     Contents.OffsetedInfo.OffsetHi = int(Offset >> 32);
   }
 
   void setIndex(int Idx) {
-    assert((isFI() || isCPI() || isTargetIndex() || isJTI()) &&
+    assert((isFI() || isCPI() || isTargetIndex() || isJTI() || isJMI()) &&
            "Wrong MachineOperand mutator");
     Contents.OffsetedInfo.Val.Index = Idx;
   }
 
   void setMBB(MachineBasicBlock *MBB) {
     assert(isMBB() && "Wrong MachineOperand mutator");
     Contents.MBB = MBB;
   }
public:
   static MachineOperand CreateTargetIndex(unsigned Idx, int64_t Offset,
                                           unsigned char TargetFlags = 0) {
     MachineOperand Op(MachineOperand::MO_TargetIndex);
     Op.setIndex(Idx);
     Op.setOffset(Offset);
     Op.setTargetFlags(TargetFlags);
     return Op;
   }
+  static MachineOperand CreateJMI(unsigned Idx,
+                                  unsigned char TargetFlags = 0) {
+    MachineOperand Op(MachineOperand::MO_JumpMapIndex);
+    Op.setIndex(Idx);
+    Op.setTargetFlags(TargetFlags);
+    return Op;
+  }
   static MachineOperand CreateJTI(unsigned Idx,
                                   unsigned char TargetFlags = 0) {
     MachineOperand Op(MachineOperand::MO_JumpTableIndex);
     Op.setIndex(Idx);
     Op.setTargetFlags(TargetFlags);
     return Op;
   }
   static MachineOperand CreateGA(const GlobalValue *GV, int64_t Offset,

include/llvm/CodeGen/Passes.h

/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
 
   /// createJumpInstrTables - This pass creates jump-instruction tables.
   ModulePass *createJumpInstrTablesPass();
 
   /// createForwardControlFlowIntegrityPass - This pass adds control-flow
   /// integrity.
   ModulePass *createForwardControlFlowIntegrityPass();
 
+  // JMFIXME: should be a module pass
+  /// createSwitchLegacyAnalysisPass - This pass analyses switch statements.
+  FunctionPass *createSwitchLegacyAnalysisPass(const TargetMachine *TM);
+
   /// InterleavedAccess Pass - This pass identifies and matches interleaved
   /// memory accesses to target specific intrinsics.
   ///
   FunctionPass *createInterleavedAccessPass(const TargetMachine *TM);
 
   /// LowerEmuTLS - This pass generates __emutls_[vt].xyz variables for all
   /// TLS variables for the emulated TLS model.
   ///

include/llvm/CodeGen/PseudoSourceValue.h

 /// Special value supplied for machine level alias analysis. It indicates that
 /// a memory access references the functions stack frame (e.g., a spill slot),
 /// below the stack frame (e.g., argument space), or constant pool.
 class PseudoSourceValue {
 public:
   enum PSVKind {
     Stack,
     GOT,
+    JumpMap,
     JumpTable,
     ConstantPool,
     FixedStack,
     GlobalValueCallEntry,
     ExternalSymbolCallEntry,
     TargetCustom
   };
 
public:
 
   virtual ~PseudoSourceValue();
 
   PSVKind kind() const { return Kind; }
 
   bool isStack() const { return Kind == Stack; }
   bool isGOT() const { return Kind == GOT; }
   bool isConstantPool() const { return Kind == ConstantPool; }
+  bool isJumpMap() const { return Kind == JumpMap; }
   bool isJumpTable() const { return Kind == JumpTable; }
   unsigned getTargetCustom() const {
     return (Kind >= TargetCustom) ? ((Kind+1) - TargetCustom) : 0;
   }
 
   /// Test whether the memory pointed to by this PseudoSourceValue has a
   /// constant value.
   virtual bool isConstant(const MachineFrameInfo *) const;
static inline bool classof(const PseudoSourceValue *V) {
     return V->kind() == ExternalSymbolCallEntry;
   }
 
   const char *getSymbol() const { return ES; }
 };
 
 /// Manages creation of pseudo source values.
 class PseudoSourceValueManager {
-  const PseudoSourceValue StackPSV, GOTPSV, JumpTablePSV, ConstantPoolPSV;
+  const PseudoSourceValue StackPSV, GOTPSV, JumpMapPSV,
+                          JumpTablePSV, ConstantPoolPSV;
   std::map<int, std::unique_ptr<FixedStackPseudoSourceValue>> FSValues;
   StringMap<std::unique_ptr<const ExternalSymbolPseudoSourceValue>>
       ExternalCallEntries;
   ValueMap<const GlobalValue *,
            std::unique_ptr<const GlobalValuePseudoSourceValue>>
       GlobalCallEntries;
 
 public:
public:
   /// pools are constant, this doesn't need to identify a specific constant
   /// pool entry.
   const PseudoSourceValue *getConstantPool();
 
   /// Return a pseudo source value referencing a jump table. Since jump tables
   /// are constant, this doesn't need to identify a specific jump table.
   const PseudoSourceValue *getJumpTable();
 
+  /// Return a pseudo source value referencing a jump map. Since jump maps
+  /// are constant, this doesn't need to identify a specific jump map.
+  const PseudoSourceValue *getJumpMap();
+
   /// Return a pseudo source value referencing a fixed stack frame entry,
   /// e.g., a spill slot.
   const PseudoSourceValue *getFixedStack(int FI);
 
   const PseudoSourceValue *getGlobalValueCallEntry(const GlobalValue *GV);
 
   const PseudoSourceValue *getExternalSymbolCallEntry(const char *ES);
 };
 
 } // end namespace llvm
 
 #endif

include/llvm/CodeGen/RuntimeLibcalls.h

enum Libcall {
     ATOMIC_FETCH_NAND_16,
 
     // Stack Protector Fail.
     STACKPROTECTOR_CHECK_FAIL,
 
     // Deoptimization.
     DEOPTIMIZE,
 
+    // JMFIXME
+    // Jump Maps library calls
+    JUMPMAP_FIND_I8_I8,
+    JUMPMAP_FIND_I16_I8,
+    JUMPMAP_FIND_I16_I16,
+    JUMPMAP_FIND_I32_I8,
+    JUMPMAP_FIND_I32_I16,
+    JUMPMAP_FIND_I32_I32,
+    JUMPMAP_FIND_I64_I8,
+    JUMPMAP_FIND_I64_I16,
+    JUMPMAP_FIND_I64_I32,
+    JUMPMAP_FIND_I64_I64,
+
     UNKNOWN_LIBCALL
   };
 
   /// getFPEXT - Return the FPEXT_*_* value for the given types, or
   /// UNKNOWN_LIBCALL if there is none.
   Libcall getFPEXT(EVT OpVT, EVT RetVT);
 
   /// getFPROUND - Return the FPROUND_*_* value for the given types, or

include/llvm/CodeGen/SelectionDAG.h

#endif
   SDValue getTargetFrameIndex(int FI, EVT VT) {
     return getFrameIndex(FI, VT, true);
   }
   SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
                        unsigned char TargetFlags = 0);
   SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
     return getJumpTable(JTI, VT, true, TargetFlags);
   }
+  SDValue getJumpMap(int JMI, EVT VT, bool isTarget = false,
+                       unsigned char TargetFlags = 0);
+  SDValue getTargetJumpMap(int JMI, EVT VT, unsigned char TargetFlags = 0) {
+    return getJumpMap(JMI, VT, true, TargetFlags);
+  }
   SDValue getConstantPool(const Constant *C, EVT VT,
                           unsigned Align = 0, int Offs = 0, bool isT=false,
                           unsigned char TargetFlags = 0);
   SDValue getTargetConstantPool(const Constant *C, EVT VT,
                                 unsigned Align = 0, int Offset = 0,
                                 unsigned char TargetFlags = 0) {
     return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
   }

include/llvm/CodeGen/SelectionDAGNodes.h

public:
   unsigned char getTargetFlags() const { return TargetFlags; }
 
   static bool classof(const SDNode *N) {
     return N->getOpcode() == ISD::JumpTable ||
            N->getOpcode() == ISD::TargetJumpTable;
   }
 };
 
+class JumpMapSDNode : public SDNode {
+  int JMI;
+  unsigned char TargetFlags;
+
+  friend class SelectionDAG;
+
+  JumpMapSDNode(int jmi, EVT VT, bool isTarg, unsigned char TF)
+    : SDNode(isTarg ? ISD::TargetJumpMap : ISD::JumpMap,
+      0, DebugLoc(), getSDVTList(VT)), JMI(jmi), TargetFlags(TF) {
+  }
+
+public:
+  int getIndex() const { return JMI; }
+  unsigned char getTargetFlags() const { return TargetFlags; }
+
+  static bool classof(const SDNode *N) {
+    return N->getOpcode() == ISD::JumpMap ||
+           N->getOpcode() == ISD::TargetJumpMap;
+  }
+};
+
 class ConstantPoolSDNode : public SDNode {
   friend class SelectionDAG;
 
   union {
     const Constant *ConstVal;
     MachineConstantPoolValue *MachineCPVal;
   } Val;
   int Offset;  // It's a MachineConstantPoolValue if top bit is set.

include/llvm/CodeGen/SwitchAnalysis.h

+//===--------- SwitchAnalysis.cpp - Implement the Switch Analysis ----------==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// The analysis finds the switches and attempts to determine whether they will
+// be lowered to jump tables or jump maps during building of selection DAGs.
+// Further analysis is done for the switches which will be turned into jump
+// maps. The goal is to determine which functions should be used for jump maps
+// lookup. For instance, if there are two switches:
+//           * i32 condition, all keys can be stored in i8
+//           * i32 condition, all keys can be stored in i16
+// we don't want to create both i32_i8 and i32_i16 lookup versions, only i32_i16
+// version should be used as it can handle both cases.
+//
+//===----------------------------------------------------------------------===//
+
+
+#ifndef LLVM_CODEGEN_SWITCHANALYSIS_H
+#define LLVM_CODEGEN_SWITCHANALYSIS_H
+
+#include "llvm/ADT/APInt.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Pass.h"
+#include "llvm/Target/TargetLowering.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
+#include <map>
+#include <string>
+#include <vector>
+
+namespace llvm{
+
+class BasicBlock;
+class FunctionPass;
+class Function;
+class raw_ostream;
+
+
+// JMFIXME: this analysis should be a ModulePass for better results.
+class SwitchAnalysis {
+public:
+  typedef std::tuple<unsigned, unsigned, unsigned> SwitchStatement;
+
+  SwitchAnalysis(const TargetMachine *TM) : TM(TM) {}
+
+  static StringRef name() { return "Switch Analysis"; }
+
+  void print(raw_ostream &OS) const;
+  void analyze(Function &Fn);
+
+  unsigned recommendedCondSize(unsigned cond);
+  unsigned recommendedKeySize(unsigned cond);
+
+private:
+  std::map<unsigned, std::tuple<unsigned, unsigned>> Results;
+  const TargetMachine *TM;
+  const TargetLoweringBase *TL;
+
+  // JMFIXME: Clusterification, jump table finding and density checks should be
+  // common for both the analysis and SelectionDAGBuilder in order to avoid
+  // disparity in the future (common include, perhaps?).
+  struct CaseCluster {
+    const ConstantInt *Low, *High;
+    BasicBlock *BB;
+
+    static CaseCluster range(const ConstantInt *Low,
+                             const ConstantInt *High,
+                             BasicBlock *BB) {
+      CaseCluster CI;
+      CI.Low = Low;
+      CI.High = High;
+      CI.BB = BB;
+      return CI;
+    }
+  };
+  bool isDense(const std::vector<CaseCluster> &Clusters,
+               const SmallVectorImpl<unsigned> &TotalCases,
+               unsigned First, unsigned Last,
+               unsigned Density) const;
+  std::vector<CaseCluster> JumpMapCases(SwitchInst& SI, const bool OptForSize);
+};
+
+/// Legacy pass
+class SwitchLegacyAnalysis : public FunctionPass {
+  const TargetMachine *TM = nullptr;
+  SwitchAnalysis SWAN;
+public:
+  static char ID;
+  SwitchLegacyAnalysis(const TargetMachine *TM)
+                : FunctionPass(ID), TM(TM), SWAN(TM) {
+    initializeSwitchLegacyAnalysisPass(*PassRegistry::getPassRegistry());
+  }
+  SwitchLegacyAnalysis() : FunctionPass(ID), SWAN(nullptr) {
+    initializeSwitchLegacyAnalysisPass(*PassRegistry::getPassRegistry());
+  }
+
+  SwitchAnalysis &getSWAN() { return SWAN; }
+  const SwitchAnalysis &getSWAN() const { return SWAN; }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+  bool runOnFunction(Function &Fn) override;
+};
+} // End llvm namespace
+
+#endif

include/llvm/InitializePasses.h

 void initializeStripDeadDebugInfoPass(PassRegistry&);
 void initializeStripDeadPrototypesLegacyPassPass(PassRegistry&);
 void initializeStripDebugDeclarePass(PassRegistry&);
 void initializeStripGCRelocatesPass(PassRegistry&);
 void initializeStripNonDebugSymbolsPass(PassRegistry&);
 void initializeStripNonLineTableDebugInfoPass(PassRegistry&);
 void initializeStripSymbolsPass(PassRegistry&);
 void initializeStructurizeCFGPass(PassRegistry&);
+void initializeSwitchLegacyAnalysisPass(PassRegistry&);
 void initializeTailCallElimPass(PassRegistry&);
 void initializeTailDuplicatePassPass(PassRegistry&);
 void initializeTargetLibraryInfoWrapperPassPass(PassRegistry&);
 void initializeTargetPassConfigPass(PassRegistry&);
 void initializeTargetTransformInfoWrapperPassPass(PassRegistry&);
 void initializeThreadSanitizerPass(PassRegistry&);
 void initializeTwoAddressInstructionPassPass(PassRegistry&);
 void initializeTypeBasedAAWrapperPassPass(PassRegistry&);

include/llvm/Target/TargetLowering.h

 class CCValAssign;
 class FastISel;
 class FunctionLoweringInfo;
 class IntrinsicInst;
 struct KnownBits;
 class MachineBasicBlock;
 class MachineFunction;
 class MachineInstr;
+class MachineJumpMapInfo;
 class MachineJumpTableInfo;
 class MachineLoop;
 class MachineRegisterInfo;
 class MCContext;
 class MCExpr;
 class TargetRegisterClass;
 class TargetLibraryInfo;
 class TargetRegisterInfo;
public:
   bool areJTsAllowed(const Function *Fn) const {
     if (Fn->getFnAttribute("no-jump-tables").getValueAsString() == "true")
       return false;
 
     return isOperationLegalOrCustom(ISD::BR_JT, MVT::Other) ||
            isOperationLegalOrCustom(ISD::BRIND, MVT::Other);
   }
 
+  /// Return true if lowering to a jump map is allowed.
+  bool areJMsAllowed(const Function *Fn) const {
+    if (!areJTsAllowed(Fn))
+      return false;
+    if (!areJumpMapsEnabled())
+      return false;
+
+    return isOperationLegalOrCustom(ISD::BR_JM, MVT::Other) ||
+           (isOperationLegalOrCustom(ISD::BRIND, MVT::Other) &&
+            getMinimumJumpMapEntries() > 0);
+  }
+
   /// Check whether the range [Low,High] fits in a machine word.
   bool rangeFitsInWord(const APInt &Low, const APInt &High,
                        const DataLayout &DL) const {
     // FIXME: Using the pointer type doesn't seem ideal.
     uint64_t BW = DL.getPointerSizeInBits();
     uint64_t Range = (High - Low).getLimitedValue(UINT64_MAX - 1) + 1;
     return Range <= BW;
   }
bool usesUnderscoreSetJmp() const {
     return UseUnderscoreSetJmp;
   }
 
   /// Determine if we should use _longjmp or longjmp to implement llvm.longjmp.
   bool usesUnderscoreLongJmp() const {
     return UseUnderscoreLongJmp;
   }
 
+  /// Return lower limit for number of blocks in a jump map.
+  unsigned getMinimumJumpMapEntries() const;
+
+  /// Return upper limit for number of entries in a jump map.
+  /// Zero if no limit.
+  unsigned getMaximumJumpMapSize() const;
+
   /// Return lower limit for number of blocks in a jump table.
   unsigned getMinimumJumpTableEntries() const;
 
   /// Return lower limit of the density in a jump table.
   unsigned getMinimumJumpTableDensity(bool OptForSize) const;
 
   /// Return upper limit for number of entries in a jump table.
   /// Zero if no limit.
   unsigned getMaximumJumpTableSize() const;
 
+  /// Return the density of jump tables for normal functions.
+  unsigned getJumpTableDensity() const;
+
+  /// Return the density of jump tables for -Os and -Oz functions.
+  unsigned getOptsizeJumpTableDensity() const;
+
+  /// Return true if jump maps are allowed, otherwise return false.
+  bool areJumpMapsEnabled() const;
+
   virtual bool isJumpTableRelative() const {
     return TM.isPositionIndependent();
   }
 
   /// If a physical register, this specifies the register that
   /// llvm.savestack/llvm.restorestack should save and restore.
   unsigned getStackPointerRegisterToSaveRestore() const {
     return StackPointerRegisterToSaveRestore;
protected:
   }
 
   /// Indicate whether this target prefers to use _longjmp to implement
   /// llvm.longjmp or the version without _.  Defaults to false.
   void setUseUnderscoreLongJmp(bool Val) {
     UseUnderscoreLongJmp = Val;
   }
 
+  /// Indicate the minimum number of blocks to generate jump maps.
+  void setMinimumJumpMapEntries(unsigned Val);
+
+  /// Indicate the maximum number of entries in jump maps.
+  /// Set to zero to generate unlimited jump maps.
+  void setMaximumJumpMapSize(unsigned);
+
   /// Indicate the minimum number of blocks to generate jump tables.
   void setMinimumJumpTableEntries(unsigned Val);
 
   /// Indicate the maximum number of entries in jump tables.
   /// Set to zero to generate unlimited jump tables.
   void setMaximumJumpTableSize(unsigned);
 
+  /// Indicate the density of jump tables for normal functions.
+  void setJumpTableDensity(unsigned);
+
+  /// Indicate the density of jump tables for -Os and -Oz functions.
+  void setOptsizeJumpTableDensity(unsigned);
+
+  /// Indicate whether jump maps generation should be enabled.
+  void setJumpMapsEnabled(bool);
+
   /// If set to a physical register, this specifies the register that
   /// llvm.savestack/llvm.restorestack should save and restore.
   void setStackPointerRegisterToSaveRestore(unsigned R) {
     StackPointerRegisterToSaveRestore = R;
   }
 
   /// Tells the code generator that the target has multiple (allocatable)
   /// condition registers that can be used to store the results of comparisons
public:
 
   virtual const MCExpr *
   LowerCustomJumpTableEntry(const MachineJumpTableInfo * /*MJTI*/,
                             const MachineBasicBlock * /*MBB*/, unsigned /*uid*/,
                             MCContext &/*Ctx*/) const {
     llvm_unreachable("Need to implement this hook if target has custom JTIs");
   }
 
+  /// Return the entry encoding for a jump map in the current function.  The
+  /// returned value is a member of the MachineJumpMapInfo::JMEntryKind enum.
+  virtual unsigned getJumpMapEncoding() const;
+
   /// Returns relocation base for the given PIC jumptable.
   virtual SDValue getPICJumpTableRelocBase(SDValue Table,
                                            SelectionDAG &DAG) const;
 
   /// This returns the relocation base for the given PIC jumptable, the same as
   /// getPICJumpTableRelocBase, but as an MCExpr.
   virtual const MCExpr *
   getPICJumpTableRelocBaseExpr(const MachineFunction *MF,

include/llvm/Target/TargetLoweringObjectFile.h

virtual void getNameWithPrefix(SmallVectorImpl<char> &OutName,
                                  const TargetMachine &TM) const;
 
   virtual MCSection *getSectionForJumpTable(const Function &F,
                                             const TargetMachine &TM) const;
 
   virtual bool shouldPutJumpTableInFunctionSection(bool UsesLabelDifference,
                                                    const Function &F) const;
 
+  virtual MCSection *getSectionForJumpMap(const Function &F,
+                                          const TargetMachine &TM) const;
   /// Targets should implement this method to assign a section to globals with
   /// an explicit section specfied. The implementation of this method can
   /// assume that GO->hasSection() is true.
   virtual MCSection *
   getExplicitSectionGlobal(const GlobalObject *GO, SectionKind Kind,
                            const TargetMachine &TM) const = 0;
 
   /// Return an MCExpr to use for a reference to the specified global variable

include/llvm/Target/TargetSelectionDAG.td

 def constpool   : SDNode<"ISD::ConstantPool",         SDTPtrLeaf, [],
                          "ConstantPoolSDNode">;
 def tconstpool  : SDNode<"ISD::TargetConstantPool",   SDTPtrLeaf, [],
                          "ConstantPoolSDNode">;
 def jumptable   : SDNode<"ISD::JumpTable",            SDTPtrLeaf, [],
                          "JumpTableSDNode">;
 def tjumptable  : SDNode<"ISD::TargetJumpTable",      SDTPtrLeaf, [],
                          "JumpTableSDNode">;
+def jumpmap     : SDNode<"ISD::Map",                  SDTPtrLeaf, [],
+                         "JumpMapSDNode">;
+def tjumpmap    : SDNode<"ISD::TargetJumpMap",        SDTPtrLeaf, [],
+                         "JumpMapSDNode">;
 def frameindex  : SDNode<"ISD::FrameIndex",           SDTPtrLeaf, [],
                          "FrameIndexSDNode">;
 def tframeindex : SDNode<"ISD::TargetFrameIndex",     SDTPtrLeaf, [],
                          "FrameIndexSDNode">;
 def externalsym : SDNode<"ISD::ExternalSymbol",       SDTPtrLeaf, [],
                          "ExternalSymbolSDNode">;
 def texternalsym: SDNode<"ISD::TargetExternalSymbol", SDTPtrLeaf, [],
                          "ExternalSymbolSDNode">;

jmdev/jmfind.c

+#include <stdint.h>
+
+#define MAKE_JMFIND(M,N,O) \
+uint##M##_t __jmfind_i##O##_i##N (uintptr_t jmap, uint##O##_t cond) {\
+  uint##N##_t *keys  = (uint##N##_t *)jmap;\
+  uint##N##_t begin  = 1;\
+  uint##N##_t end    = 1 + *keys;\
+  uint##M##_t *vals  = (uint##M##_t*)(keys+end);\
+  if((uint##O##_t)((uint##N##_t)(cond)) != cond) return vals[0];\
+  do {\
+    uint##N##_t t = (begin + end) >> 1;\
+    uint##N##_t t_val = keys[t];\
+    if(t_val == cond)\
+      return vals[t];\
+    if(t_val > cond)\
+      end = t;\
+    else\
+      begin = t + 1;\
+  } while(begin != end);\
+  return vals[0];\
+}
+
+MAKE_JMFIND(ptr,8,8)
+MAKE_JMFIND(ptr,8,16)
+MAKE_JMFIND(ptr,16,16)
+MAKE_JMFIND(ptr,8,32)
+MAKE_JMFIND(ptr,16,32)
+MAKE_JMFIND(ptr,32,32)
+MAKE_JMFIND(ptr,8,64)
+MAKE_JMFIND(ptr,16,64)
+MAKE_JMFIND(ptr,32,64)
+MAKE_JMFIND(ptr,64,64)

lib/CodeGen/AsmPrinter/AsmPrinter.cpp

 #include "llvm/CodeGen/GCStrategy.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBundle.h"
+#include "llvm/CodeGen/MachineJumpMapInfo.h"
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineModuleInfoImpls.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
for (const HandlerInfo &HI : Handlers) {
     NamedRegionTimer T(HI.TimerName, HI.TimerDescription, HI.TimerGroupName,
                        HI.TimerGroupDescription, TimePassesIsEnabled);
     HI.Handler->markFunctionEnd();
   }
 
   // Print out jump tables referenced by the function.
   EmitJumpTableInfo();
 
+  // Print out jump maps referenced by the function.
+  EmitJumpMapInfo();
+
   // Emit post-function debug and/or EH information.
   for (const HandlerInfo &HI : Handlers) {
     NamedRegionTimer T(HI.TimerName, HI.TimerDescription, HI.TimerGroupName,
                        HI.TimerGroupDescription, TimePassesIsEnabled);
     HI.Handler->endFunction(MF);
   }
 
   OutStreamer->AddBlankLine();
void AsmPrinter::EmitJumpTableEntry(const MachineJumpTableInfo *MJTI,
   }
 
   assert(Value && "Unknown entry kind!");
 
   unsigned EntrySize = MJTI->getEntrySize(getDataLayout());
   OutStreamer->EmitValue(Value, EntrySize);
 }
 
+/// EmitJumpMapInfo - Print assembly representations of the jump maps used
+/// by the current function to the current output stream.
+///
+void AsmPrinter::EmitJumpMapInfo() {
+  const DataLayout &DL = MF->getDataLayout();
+  const MachineJumpMapInfo *MJMI = MF->getJumpMapInfo();
+  if (!MJMI) return;
+  const std::vector<MachineJumpMapEntry> &JM = MJMI->getJumpMaps();
+  if (JM.empty()) return;
+
+  // Pick the directive to use to print the jump map entries, and switch to
+  // the appropriate section.
+  const Function *F = MF->getFunction();
+  const TargetLoweringObjectFile &TLOF = getObjFileLowering();
+  bool JMInDiffSection = !TLOF.shouldPutJumpTableInFunctionSection(false, *F);
+  if (JMInDiffSection) {
+    // Drop it in the readonly section.
+    MCSection *ReadOnlySection = TLOF.getSectionForJumpMap(*F, TM);
+    OutStreamer->SwitchSection(ReadOnlySection);
+  }
+
+  EmitAlignment(Log2_32(MJMI->getEntryAlignment(DL)));
+
+  // Jump maps in code sections are marked with a data_region directive
+  // where that's supported.
+  if (!JMInDiffSection)
+    OutStreamer->EmitDataRegion(MCDR_DataRegionJT32);
+
+  for (unsigned JMI = 0, e = JM.size(); JMI != e; ++JMI) {
+    const std::map<uint64_t, MachineBasicBlock*> &JMBBs = JM[JMI].MBBs;
+
+    // If this jump map was deleted, ignore it.
+    if (JMBBs.empty()) continue;
+
+    // JMFIXME: This map layout was arbitrary chosen for a particular target.
+    //          Would be nice if it was TargetLowering-driven.
+    int KeySize = JM[JMI].getKeySize();
+    if(!(JMBBs.size() % 2) && KeySize == 1) {
+      const MCExpr *Cnt = MCConstantExpr::create(0, OutContext);
+      OutStreamer->EmitValue(Cnt, KeySize);
+    }
+
+    // On some targets (e.g. Darwin) we want to emit two consecutive labels
+    // before each jump map. The first label is never referenced, but tells
+    // the assembler and linker the extents of the jump map object.  The
+    // second label is actually referenced by the code.
+    if (JMInDiffSection && DL.hasLinkerPrivateGlobalPrefix())
+      // FIXME: This doesn't have to have any specific name, just any randomly
+      // named and numbered 'l' label would work.  Simplify GetJMISymbol.
+      OutStreamer->EmitLabel(GetJMISymbol(JMI, true));
+
+    OutStreamer->EmitLabel(GetJMISymbol(JMI));
+
+    // Emit the map struct
+    const MCExpr *Cnt = MCConstantExpr::create(JMBBs.size(), OutContext);
+    OutStreamer->EmitValue(Cnt, KeySize);
+    for (auto it = JMBBs.begin(); it != JMBBs.end(); it++) {
+      const MCExpr *Key = MCConstantExpr::create(it->first, OutContext);
+      OutStreamer->EmitValue(Key, KeySize);
+    }
+    int ValSize = MJMI->getValueSize(DL);
+    const MCExpr *Dfl = MCSymbolRefExpr::create(JM[JMI].Default->getSymbol(),
+                                                OutContext);
+    OutStreamer->EmitValue(Dfl, ValSize);
+    for (auto it = JMBBs.begin(); it != JMBBs.end(); it++) {
+      const MCExpr *Val = MCSymbolRefExpr::create(it->second->getSymbol(),
+                                                  OutContext);
+      OutStreamer->EmitValue(Val, ValSize);
+    }
+  }
+  if (!JMInDiffSection)
+    OutStreamer->EmitDataRegion(MCDR_DataRegionEnd);
+}
+
 /// EmitSpecialLLVMGlobal - Check to see if the specified global is a
 /// special global used by LLVM.  If so, emit it and return true, otherwise
 /// do nothing and return false.
 bool AsmPrinter::EmitSpecialLLVMGlobal(const GlobalVariable *GV) {
   if (GV->getName() == "llvm.used") {
     if (MAI->hasNoDeadStrip())    // No need to emit this at all.
       EmitLLVMUsedList(cast<ConstantArray>(GV->getInitializer()));
     return true;

 /// GetCPISymbol - Return the symbol for the specified constant pool entry.
 MCSymbol *AsmPrinter::GetCPISymbol(unsigned CPID) const {
   const DataLayout &DL = getDataLayout();
   return OutContext.getOrCreateSymbol(Twine(DL.getPrivateGlobalPrefix()) +
                                       "CPI" + Twine(getFunctionNumber()) + "_" +
                                       Twine(CPID));
 }
 
+/// GetJMISymbol - Return the symbol for the specified jump map entry.
+MCSymbol *AsmPrinter::GetJMISymbol(unsigned JMID, bool isLinkerPrivate) const {
+  return MF->getJMISymbol(JMID, OutContext, isLinkerPrivate);
+}
+
 /// GetJTISymbol - Return the symbol for the specified jump table entry.
 MCSymbol *AsmPrinter::GetJTISymbol(unsigned JTID, bool isLinkerPrivate) const {
   return MF->getJTISymbol(JTID, OutContext, isLinkerPrivate);
 }
 
 /// GetJTSetSymbol - Return the symbol for the specified jump table .set
 /// FIXME: privatize to AsmPrinter.
 MCSymbol *AsmPrinter::GetJTSetSymbol(unsigned UID, unsigned MBBID) const {
for (const auto &MI : Pred->terminators()) {
     // If it is not a simple branch, we are in a table somewhere.
     if (!MI.isBranch() || MI.isIndirectBranch())
       return false;
 
     // If we are the operands of one of the branches, this is not a fall
     // through. Note that targets with delay slots will usually bundle
     // terminators with the delay slot instruction.
     for (ConstMIBundleOperands OP(MI); OP.isValid(); ++OP) {
-      if (OP->isJTI())
+      if (OP->isJTI() || OP->isJMI())
         return false;
       if (OP->isMBB() && OP->getMBB() == MBB)
         return false;
     }
   }
 
   return true;
 }

lib/CodeGen/BranchFolding.cpp

 #include "BranchFolding.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/Analysis.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineJumpMapInfo.h"
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/IR/DebugInfoMetadata.h"
while (MadeChangeThisIteration) {
     // block placement.
     if (!AfterBlockPlacement || MadeChangeThisIteration)
       MadeChangeThisIteration |= OptimizeBranches(MF);
     if (EnableHoistCommonCode)
       MadeChangeThisIteration |= HoistCommonCode(MF);
     MadeChange |= MadeChangeThisIteration;
   }
 
-  // See if any jump tables have become dead as the code generator
+  // See if any jump tables or maps have become dead as the code generator
   // did its thing.
   MachineJumpTableInfo *JTI = MF.getJumpTableInfo();
-  if (!JTI)
+  MachineJumpMapInfo *JMI = MF.getJumpMapInfo();
+  if (!JTI & !JMI)
     return MadeChange;
 
-  // Walk the function to find jump tables that are live.
-  BitVector JTIsLive(JTI->getJumpTables().size());
+  // Walk the function to find jump tables and maps that are live.
+  BitVector JTIsLive(JTI ? JTI->getJumpTables().size() : 0);
+  BitVector JMIsLive(JMI ? JMI->getJumpMaps().size() : 0);
   for (const MachineBasicBlock &BB : MF) {
     for (const MachineInstr &I : BB)
       for (const MachineOperand &Op : I.operands()) {
-        if (!Op.isJTI()) continue;
-
+        if (Op.isJTI()){
           // Remember that this JT is live.
           JTIsLive.set(Op.getIndex());
         }
+        else if(Op.isJMI()){
+          // Remember that this JM is live.
+          JMIsLive.set(Op.getIndex());
+        }
+      }
   }
 
   // Finally, remove dead jump tables.  This happens when the
   // indirect jump was unreachable (and thus deleted).
   for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i)
     if (!JTIsLive.test(i)) {
       JTI->RemoveJumpTable(i);
       MadeChange = true;
     }
 
+  // Remove dead jump maps as well. This happens when the
+  // indirect jump was unreachable (and thus deleted).
+  for (unsigned i = 0, e = JMIsLive.size(); i != e; ++i)
+    if (!JMIsLive.test(i)) {
+      JMI->RemoveJumpMap(i);
+      MadeChange = true;
+    }
+
   return MadeChange;
 }
 
 //===----------------------------------------------------------------------===//
 //  Tail Merging of Blocks
 //===----------------------------------------------------------------------===//
 
 /// HashMachineInstr - Compute a hash value for MI and its operands.
case MachineOperand::MO_Immediate:
       OperandHash = Op.getImm();
       break;
     case MachineOperand::MO_MachineBasicBlock:
       OperandHash = Op.getMBB()->getNumber();
       break;
     case MachineOperand::MO_FrameIndex:
     case MachineOperand::MO_ConstantPoolIndex:
     case MachineOperand::MO_JumpTableIndex:
+    case MachineOperand::MO_JumpMapIndex:
       OperandHash = Op.getIndex();
       break;
     case MachineOperand::MO_GlobalAddress:
     case MachineOperand::MO_ExternalSymbol:
       // Global address / external symbol are too hard, don't bother, but do
       // pull in the offset.
       OperandHash = Op.getOffset();
       break;
if (FallThrough == MF.end()) {
       while (!MBB->pred_empty()) {
         MachineBasicBlock *Pred = *(MBB->pred_end()-1);
         Pred->ReplaceUsesOfBlockWith(MBB, &*FallThrough);
       }
       // If MBB was the target of a jump table, update jump tables to go to the
       // fallthrough instead.
       if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
         MJTI->ReplaceMBBInJumpTables(MBB, &*FallThrough);
+      // If MBB was the target of a jump map, update jump maps to go to the
+      // fallthrough instead.
+      if (MachineJumpMapInfo *MJMI = MF.getJumpMapInfo())
+        MJMI->ReplaceMBBInJumpMaps(MBB, &*FallThrough);
       MadeChange = true;
     }
     return MadeChange;
   }
 
   // Check to see if we can simplify the terminator of the block before this
   // one.
   MachineBasicBlock &PrevBB = *std::prev(MachineFunction::iterator(MBB));
if (CurTBB && CurCond.empty() && !CurFBB &&
                 PMBB->CorrectExtraCFGEdges(NewCurTBB, nullptr, false);
               }
             }
           }
 
           // Change any jumptables to go to the new MBB.
           if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
             MJTI->ReplaceMBBInJumpTables(MBB, CurTBB);
+          // Change any jumpmaps to go to the new MBB.
+          if (MachineJumpMapInfo *MJMI = MF.getJumpMapInfo())
+            MJMI->ReplaceMBBInJumpMaps(MBB, CurTBB);
           if (DidChange) {
             ++NumBranchOpts;
             MadeChange = true;
             if (!HasBranchToSelf) return MadeChange;
           }
         }
       }
 

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   SlotIndexes.cpp
   SpillPlacement.cpp
   SplitKit.cpp
   StackColoring.cpp
   StackMapLivenessAnalysis.cpp
   StackMaps.cpp
   StackProtector.cpp
   StackSlotColoring.cpp
+  SwitchAnalysis.cpp
   TailDuplication.cpp
   TailDuplicator.cpp
   TargetFrameLoweringImpl.cpp
   TargetInstrInfo.cpp
   TargetLoweringBase.cpp
   TargetLoweringObjectFileImpl.cpp
   TargetOptionsImpl.cpp
   TargetPassConfig.cpp

lib/CodeGen/CodeGen.cpp

void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializeRenameIndependentSubregsPass(Registry);
   initializeSafeStackPass(Registry);
   initializeShrinkWrapPass(Registry);
   initializeSlotIndexesPass(Registry);
   initializeStackColoringPass(Registry);
   initializeStackMapLivenessPass(Registry);
   initializeStackProtectorPass(Registry);
   initializeStackSlotColoringPass(Registry);
+  initializeSwitchLegacyAnalysisPass(Registry);
   initializeTailDuplicatePassPass(Registry);
   initializeTargetPassConfigPass(Registry);
   initializeTwoAddressInstructionPassPass(Registry);
   initializeUnpackMachineBundlesPass(Registry);
   initializeUnreachableBlockElimLegacyPassPass(Registry);
   initializeUnreachableMachineBlockElimPass(Registry);
   initializeVirtRegMapPass(Registry);
   initializeVirtRegRewriterPass(Registry);
   initializeWinEHPreparePass(Registry);
   initializeXRayInstrumentationPass(Registry);
 }
 
 void LLVMInitializeCodeGen(LLVMPassRegistryRef R) {
   initializeCodeGen(*unwrap(R));
 }

lib/CodeGen/MIRPrinter.cpp

else
       OS << "<unknown>";
     OS << ')';
     printOffset(Op.getOffset());
     break;
   }
   case MachineOperand::MO_JumpTableIndex:
     OS << "%jump-table." << Op.getIndex();
     break;
+  case MachineOperand::MO_JumpMapIndex:
+    OS << "%jump-map." << Op.getIndex();
+    break;
   case MachineOperand::MO_ExternalSymbol:
     OS << '$';
     printLLVMNameWithoutPrefix(OS, Op.getSymbolName());
     printOffset(Op.getOffset());
     break;
   case MachineOperand::MO_GlobalAddress:
     Op.getGlobal()->printAsOperand(OS, /*PrintType=*/false, MST);
     printOffset(Op.getOffset());
if (const Value *Val = Op.getValue()) {
     assert(PVal && "Expected a pseudo source value");
     switch (PVal->kind()) {
     case PseudoSourceValue::Stack:
       OS << "stack";
       break;
     case PseudoSourceValue::GOT:
       OS << "got";
       break;
+    case PseudoSourceValue::JumpMap:
+      OS << "jump-map";
+      break;
     case PseudoSourceValue::JumpTable:
       OS << "jump-table";
       break;
     case PseudoSourceValue::ConstantPool:
       OS << "constant-pool";
       break;
     case PseudoSourceValue::FixedStack:
       printStackObjectReference(

lib/CodeGen/MachineFunction.cpp

 #include "llvm/ADT/SmallString.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunctionInitializer.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineJumpMapInfo.h"
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/PseudoSourceValue.h"
 #include "llvm/CodeGen/WinEHFuncInfo.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfo.h"
void MachineFunction::init() {
   if (!Fn->hasFnAttribute(Attribute::OptimizeForSize))
     Alignment = std::max(Alignment,
                          STI->getTargetLowering()->getPrefFunctionAlignment());
 
   if (AlignAllFunctions)
     Alignment = AlignAllFunctions;
 
   JumpTableInfo = nullptr;
+  JumpMapInfo = nullptr;
 
   if (isFuncletEHPersonality(classifyEHPersonality(
           Fn->hasPersonalityFn() ? Fn->getPersonalityFn() : nullptr))) {
     WinEHInfo = new (Allocator) WinEHFuncInfo();
   }
 
   assert(Target.isCompatibleDataLayout(getDataLayout()) &&
          "Can't create a MachineFunction using a Module with a "
void MachineFunction::clear() {
   ConstantPool->~MachineConstantPool();
   Allocator.Deallocate(ConstantPool);
 
   if (JumpTableInfo) {
     JumpTableInfo->~MachineJumpTableInfo();
     Allocator.Deallocate(JumpTableInfo);
   }
 
+  if (JumpMapInfo) {
+    JumpMapInfo->~MachineJumpMapInfo();
+    Allocator.Deallocate(JumpMapInfo);
+  }
+
   if (WinEHInfo) {
     WinEHInfo->~WinEHFuncInfo();
     Allocator.Deallocate(WinEHInfo);
   }
 }
 
 const DataLayout &MachineFunction::getDataLayout() const {
   return Fn->getParent()->getDataLayout();
 }
 
 /// Get the JumpTableInfo for this function.
 /// If it does not already exist, allocate one.
 MachineJumpTableInfo *MachineFunction::
 getOrCreateJumpTableInfo(unsigned EntryKind) {
   if (JumpTableInfo) return JumpTableInfo;
 
   JumpTableInfo = new (Allocator)
     MachineJumpTableInfo((MachineJumpTableInfo::JTEntryKind)EntryKind);
   return JumpTableInfo;
 }
 
+/// Get the JumpMapInfo for this function.
+/// If it does not already exist, allocate one.
+MachineJumpMapInfo *MachineFunction::
+getOrCreateJumpMapInfo(unsigned EntryKind) {
+  if (JumpMapInfo) return JumpMapInfo;
+
+  JumpMapInfo = new (Allocator)
+    MachineJumpMapInfo((MachineJumpMapInfo::JMEntryKind)EntryKind);
+  return JumpMapInfo;
+}
+
 /// Should we be emitting segmented stack stuff for the function
 bool MachineFunction::shouldSplitStack() const {
   return getFunction()->hasFnAttribute("split-stack");
 }
 
 /// This discards all of the MachineBasicBlock numbers and recomputes them.
 /// This guarantees that the MBB numbers are sequential, dense, and match the
 /// ordering of the blocks within the function.  If a specific MachineBasicBlock
void MachineFunction::print(raw_ostream &OS, const SlotIndexes *Indexes) const {
 
   // Print Frame Information
   FrameInfo->print(*this, OS);
 
   // Print JumpTable Information
   if (JumpTableInfo)
     JumpTableInfo->print(OS);
 
+  // Print JumpMap Information
+  if (JumpMapInfo)
+    JumpMapInfo->print(OS);
+
   // Print Constant Pool
   ConstantPool->print(OS);
 
   const TargetRegisterInfo *TRI = getSubtarget().getRegisterInfo();
 
   if (RegInfo && !RegInfo->livein_empty()) {
     OS << "Function Live Ins: ";
     for (MachineRegisterInfo::livein_iterator
MCSymbol *MachineFunction::getJTISymbol(unsigned JTI, MCContext &Ctx,
   StringRef Prefix = isLinkerPrivate ? DL.getLinkerPrivateGlobalPrefix()
                                      : DL.getPrivateGlobalPrefix();
   SmallString<60> Name;
   raw_svector_ostream(Name)
     << Prefix << "JTI" << getFunctionNumber() << '_' << JTI;
   return Ctx.getOrCreateSymbol(Name);
 }
 
+/// Return the MCSymbol for the specified non-empty jump map.
+/// If isLinkerPrivate is specified, an 'l' label is returned, otherwise a
+/// normal 'L' label is returned.
+MCSymbol *MachineFunction::getJMISymbol(unsigned JMI, MCContext &Ctx,
+                                        bool isLinkerPrivate) const {
+  const DataLayout &DL = getDataLayout();
+  assert(JumpMapInfo && "No jump maps");
+  assert(JMI < JumpMapInfo->getJumpMaps().size() && "Invalid JMI!");
+
+  StringRef Prefix = isLinkerPrivate ? DL.getLinkerPrivateGlobalPrefix()
+                                     : DL.getPrivateGlobalPrefix();
+  SmallString<60> Name;
+  raw_svector_ostream(Name)
+    << Prefix << "JMI" << getFunctionNumber() << '_' << JMI;
+  return Ctx.getOrCreateSymbol(Name);
+}
+
 /// Return a function-local symbol to represent the PIC base.
 MCSymbol *MachineFunction::getPICBaseSymbol() const {
   const DataLayout &DL = getDataLayout();
   return Ctx.getOrCreateSymbol(Twine(DL.getPrivateGlobalPrefix()) +
                                Twine(getFunctionNumber()) + "$pb");
 }
 
 /// \name Exception Handling
void MachineJumpTableInfo::print(raw_ostream &OS) const {
 
   OS << '\n';
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void MachineJumpTableInfo::dump() const { print(dbgs()); }
 #endif
 
+//===----------------------------------------------------------------------===//
+//  MachineJumpMapInfo implementation
+//===----------------------------------------------------------------------===//
+
+/// Return the size of a value in the jump map.
+unsigned MachineJumpMapInfo::getValueSize(const DataLayout &TD) const {
+  switch (getEntryKind()) {
+  case MachineJumpMapInfo::EK_BlockAddress:
+    return TD.getPointerSize();
+  }
+  llvm_unreachable("Unknown jump map encoding!");
+}
+
+/// Return the alignment of the jump map entry.
+unsigned MachineJumpMapInfo::getEntryAlignment(const DataLayout &TD) const {
+  switch (getEntryKind()) {
+  case MachineJumpMapInfo::EK_BlockAddress:
+    return TD.getPointerABIAlignment();
+  }
+  llvm_unreachable("Unknown jump map encoding!");
+}
+
+/// Create a new jump map entry in the jump map info.
+unsigned MachineJumpMapInfo::createJumpMapIndex(
+                               std::map<uint64_t, MachineBasicBlock*> &DestBBs,
+                               MachineBasicBlock *Default,
+                               unsigned KeySize) {
+  assert(!DestBBs.empty() && "Cannot create an empty jump map!");
+  JumpMaps.push_back(MachineJumpMapEntry(DestBBs, Default, KeySize));
+  return JumpMaps.size()-1;
+}
+
+/// If Old is the target of any jump maps, update the jump maps to branch
+/// to New instead.
+bool MachineJumpMapInfo::ReplaceMBBInJumpMaps(MachineBasicBlock *Old,
+                                                  MachineBasicBlock *New) {
+  assert(Old != New && "Not making a change?");
+  bool MadeChange = false;
+  for (size_t i = 0, e = JumpMaps.size(); i != e; ++i)
+    ReplaceMBBInJumpMap(i, Old, New);
+  return MadeChange;
+}
+
+/// If Old is a target of the jump maps, update the jump map to branch to
+/// New instead.
+bool MachineJumpMapInfo::ReplaceMBBInJumpMap(unsigned Idx,
+                                                 MachineBasicBlock *Old,
+                                                 MachineBasicBlock *New) {
+  assert(Old != New && "Not making a change?");
+  bool MadeChange = false;
+  MachineJumpMapEntry &JME = JumpMaps[Idx];
+  for(auto &MapEntry : JME.MBBs)
+    if (MapEntry.second == Old) {
+      MapEntry.second = New;
+      MadeChange = true;
+    }
+  return MadeChange;
+}
+
+void MachineJumpMapInfo::print(raw_ostream &OS) const {
+  if (JumpMaps.empty()) return;
+
+  OS << "Jump Maps:\n";
+
+  for (unsigned i = 0, e = JumpMaps.size(); i != e; ++i) {
+    OS << "  jm#" << i << ": ";
+    OS << " DefaultBB#" << JumpMaps[i].Default->getNumber();
+    for (auto it = JumpMaps[i].MBBs.begin(); it != JumpMaps[i].MBBs.end(); it++) {
+      OS << " KEY:" << it->first;
+      OS << " BB#"  << it->second->getNumber();
+    }
+  }
+
+  OS << '\n';
+}
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+LLVM_DUMP_METHOD void MachineJumpMapInfo::dump() const { print(dbgs()); }
+#endif
 
 //===----------------------------------------------------------------------===//
 //  MachineConstantPool implementation
 //===----------------------------------------------------------------------===//
 
 void MachineConstantPoolValue::anchor() { }
 
 Type *MachineConstantPoolEntry::getType() const {

lib/CodeGen/MachineFunctionPass.cpp

 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/StackProtector.h"
+#include "llvm/CodeGen/SwitchAnalysis.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 
 using namespace llvm;
 
 Pass *MachineFunctionPass::createPrinterPass(raw_ostream &O,
                                              const std::string &Banner) const {
   return createMachineFunctionPrinterPass(O, Banner);
void MachineFunctionPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addPreserved<AAResultsWrapperPass>();
   AU.addPreserved<GlobalsAAWrapperPass>();
   AU.addPreserved<IVUsersWrapperPass>();
   AU.addPreserved<LoopInfoWrapperPass>();
   AU.addPreserved<MemoryDependenceWrapperPass>();
   AU.addPreserved<ScalarEvolutionWrapperPass>();
   AU.addPreserved<SCEVAAWrapperPass>();
   AU.addPreserved<StackProtector>();
+  AU.addPreserved<SwitchLegacyAnalysis>();
 
   FunctionPass::getAnalysisUsage(AU);
 }

lib/CodeGen/MachineInstr.cpp

case MachineOperand::MO_MachineBasicBlock:
     return getMBB() == Other.getMBB();
   case MachineOperand::MO_FrameIndex:
     return getIndex() == Other.getIndex();
   case MachineOperand::MO_ConstantPoolIndex:
   case MachineOperand::MO_TargetIndex:
     return getIndex() == Other.getIndex() && getOffset() == Other.getOffset();
   case MachineOperand::MO_JumpTableIndex:
     return getIndex() == Other.getIndex();
+  case MachineOperand::MO_JumpMapIndex:
+    return getIndex() == Other.getIndex();
   case MachineOperand::MO_GlobalAddress:
     return getGlobal() == Other.getGlobal() && getOffset() == Other.getOffset();
   case MachineOperand::MO_ExternalSymbol:
     return !strcmp(getSymbolName(), Other.getSymbolName()) &&
            getOffset() == Other.getOffset();
   case MachineOperand::MO_BlockAddress:
     return getBlockAddress() == Other.getBlockAddress() &&
            getOffset() == Other.getOffset();
hash_code llvm::hash_value(const MachineOperand &MO) {
   case MachineOperand::MO_FrameIndex:
     return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getIndex());
   case MachineOperand::MO_ConstantPoolIndex:
   case MachineOperand::MO_TargetIndex:
     return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getIndex(),
                         MO.getOffset());
   case MachineOperand::MO_JumpTableIndex:
     return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getIndex());
+  case MachineOperand::MO_JumpMapIndex:
+    return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getIndex());
   case MachineOperand::MO_ExternalSymbol:
     return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getOffset(),
                         MO.getSymbolName());
   case MachineOperand::MO_GlobalAddress:
     return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getGlobal(),
                         MO.getOffset());
   case MachineOperand::MO_BlockAddress:
     return hash_combine(MO.getType(), MO.getTargetFlags(),
void MachineOperand::print(raw_ostream &OS, ModuleSlotTracker &MST,
   case MachineOperand::MO_TargetIndex:
     OS << "<ti#" << getIndex();
     if (getOffset()) OS << "+" << getOffset();
     OS << '>';
     break;
   case MachineOperand::MO_JumpTableIndex:
     OS << "<jt#" << getIndex() << '>';
     break;
+  case MachineOperand::MO_JumpMapIndex:
+    OS << "<jm#" << getIndex() << '>';
+    break;
   case MachineOperand::MO_GlobalAddress:
     OS << "<ga:";
     getGlobal()->printAsOperand(OS, /*PrintType=*/false, MST);
     if (getOffset()) OS << "+" << getOffset();
     OS << '>';
     break;
   case MachineOperand::MO_ExternalSymbol:
     OS << "<es:" << getSymbolName();
MachinePointerInfo MachinePointerInfo::getFixedStack(MachineFunction &MF,
                                                      int FI, int64_t Offset) {
   return MachinePointerInfo(MF.getPSVManager().getFixedStack(FI), Offset);
 }
 
 MachinePointerInfo MachinePointerInfo::getJumpTable(MachineFunction &MF) {
   return MachinePointerInfo(MF.getPSVManager().getJumpTable());
 }
 
+MachinePointerInfo MachinePointerInfo::getJumpMap(MachineFunction &MF) {
+  return MachinePointerInfo(MF.getPSVManager().getJumpMap());
+}
+
 MachinePointerInfo MachinePointerInfo::getGOT(MachineFunction &MF) {
   return MachinePointerInfo(MF.getPSVManager().getGOT());
 }
 
 MachinePointerInfo MachinePointerInfo::getStack(MachineFunction &MF,
                                                 int64_t Offset) {
   return MachinePointerInfo(MF.getPSVManager().getStack(), Offset);
 }

lib/CodeGen/PseudoSourceValue.cpp

 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
 static const char *const PSVNames[] = {
-    "Stack", "GOT", "JumpTable", "ConstantPool", "FixedStack",
+    "Stack", "GOT", "JumpMap", "JumpTable", "ConstantPool", "FixedStack",
     "GlobalValueCallEntry", "ExternalSymbolCallEntry"};
 
 PseudoSourceValue::PseudoSourceValue(PSVKind Kind) : Kind(Kind) {}
 
 PseudoSourceValue::~PseudoSourceValue() {}
 
 void PseudoSourceValue::printCustom(raw_ostream &O) const {
   if (Kind < TargetCustom)
     O << PSVNames[Kind];
   else
     O << "TargetCustom" << Kind;
 }
 
 bool PseudoSourceValue::isConstant(const MachineFrameInfo *) const {
   if (isStack())
     return false;
-  if (isGOT() || isConstantPool() || isJumpTable())
+  if (isGOT() || isConstantPool() || isJumpTable() || isJumpMap())
     return true;
   llvm_unreachable("Unknown PseudoSourceValue!");
 }
 
 bool PseudoSourceValue::isAliased(const MachineFrameInfo *) const {
-  if (isStack() || isGOT() || isConstantPool() || isJumpTable())
+  if (isStack() || isGOT() || isConstantPool() || isJumpTable() || isJumpMap())
     return false;
   llvm_unreachable("Unknown PseudoSourceValue!");
 }
 
 bool PseudoSourceValue::mayAlias(const MachineFrameInfo *) const {
-  return !(isGOT() || isConstantPool() || isJumpTable());
+  return !(isGOT() || isConstantPool() || isJumpTable() || isJumpMap());
 }
 
 bool FixedStackPseudoSourceValue::isConstant(
     const MachineFrameInfo *MFI) const {
   return MFI && MFI->isImmutableObjectIndex(FI);
 }
 
 bool FixedStackPseudoSourceValue::isAliased(const MachineFrameInfo *MFI) const {
GlobalValuePseudoSourceValue::GlobalValuePseudoSourceValue(
     const GlobalValue *GV)
     : CallEntryPseudoSourceValue(GlobalValueCallEntry), GV(GV) {}
 
 ExternalSymbolPseudoSourceValue::ExternalSymbolPseudoSourceValue(const char *ES)
     : CallEntryPseudoSourceValue(ExternalSymbolCallEntry), ES(ES) {}
 
 PseudoSourceValueManager::PseudoSourceValueManager()
     : StackPSV(PseudoSourceValue::Stack), GOTPSV(PseudoSourceValue::GOT),
+      JumpMapPSV(PseudoSourceValue::JumpMap),
       JumpTablePSV(PseudoSourceValue::JumpTable),
       ConstantPoolPSV(PseudoSourceValue::ConstantPool) {}
 
 const PseudoSourceValue *PseudoSourceValueManager::getStack() {
   return &StackPSV;
 }
 
 const PseudoSourceValue *PseudoSourceValueManager::getGOT() { return &GOTPSV; }
 
 const PseudoSourceValue *PseudoSourceValueManager::getConstantPool() {
   return &ConstantPoolPSV;
 }
 
+const PseudoSourceValue *PseudoSourceValueManager::getJumpMap() {
+  return &JumpMapPSV;
+}
+
 const PseudoSourceValue *PseudoSourceValueManager::getJumpTable() {
   return &JumpTablePSV;
 }
 
 const PseudoSourceValue *PseudoSourceValueManager::getFixedStack(int FI) {
   std::unique_ptr<FixedStackPseudoSourceValue> &V = FSValues[FI];
   if (!V)
     V = llvm::make_unique<FixedStackPseudoSourceValue>(FI);

lib/CodeGen/SelectionDAG/InstrEmitter.cpp

if (Op.isMachineOpcode()) {
     MIB.addGlobalAddress(TGA->getGlobal(), TGA->getOffset(),
                          TGA->getTargetFlags());
   } else if (BasicBlockSDNode *BBNode = dyn_cast<BasicBlockSDNode>(Op)) {
     MIB.addMBB(BBNode->getBasicBlock());
   } else if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Op)) {
     MIB.addFrameIndex(FI->getIndex());
   } else if (JumpTableSDNode *JT = dyn_cast<JumpTableSDNode>(Op)) {
     MIB.addJumpTableIndex(JT->getIndex(), JT->getTargetFlags());
+  } else if (JumpMapSDNode *JM = dyn_cast<JumpMapSDNode>(Op)) {
+    MIB.addJumpMapIndex(JM->getIndex(), JM->getTargetFlags());
   } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Op)) {
     int Offset = CP->getOffset();
     unsigned Align = CP->getAlignment();
     Type *Type = CP->getType();
     // MachineConstantPool wants an explicit alignment.
     if (Align == 0) {
       Align = MF->getDataLayout().getPrefTypeAlignment(Type);
       if (Align == 0) {

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineJumpMapInfo.h"
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/CodeGen/SelectionDAGNodes.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DerivedTypes.h"
if (TLI.isJumpTableRelative()) {
       // RelocBase can be JumpTable, GOT or some sort of global base.
       Addr = DAG.getNode(ISD::ADD, dl, PTy, Addr,
                           TLI.getPICJumpTableRelocBase(Table, DAG));
     }
     Tmp1 = DAG.getNode(ISD::BRIND, dl, MVT::Other, LD.getValue(1), Addr);
     Results.push_back(Tmp1);
     break;
   }
+  case ISD::BR_JM: {
+    SDValue Chain = Node->getOperand(0);
+    SDValue JMap = Node->getOperand(1);
+    SDValue Cond = Node->getOperand(2);
+    SDValue MinSizeNode = Node->getOperand(3);
+    unsigned MinSize = dyn_cast<ConstantSDNode>(MinSizeNode)
+                          ->getConstantIntValue()->getValue().getZExtValue();
+
+    RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
+    switch(Cond.getSimpleValueType().SimpleTy) {
+      case MVT::i8: {
+        if(MinSize == 8) LC = RTLIB::JUMPMAP_FIND_I8_I8;
+        else llvm_unreachable("Expand BR_JM: unknown key size");
+        break;
+      }
+      case MVT::i16: {
+        if(MinSize == 8) LC = RTLIB::JUMPMAP_FIND_I16_I8;
+        else if(MinSize == 16) LC = RTLIB::JUMPMAP_FIND_I16_I16;
+        else llvm_unreachable("Expand BR_JM: unknown key size");
+        break;
+      }
+      case MVT::i32: {
+        switch(MinSize) {
+          case 8: { LC = RTLIB::JUMPMAP_FIND_I32_I8; break; }
+          case 16: { LC = RTLIB::JUMPMAP_FIND_I32_I16; break; }
+          case 32: { LC = RTLIB::JUMPMAP_FIND_I32_I32; break; }
+          default:{ llvm_unreachable("Expand BR_JM: unknown key size"); }
+        }
+        break;
+      }
+      case MVT::i64:{
+        switch(MinSize) {
+          case 8: { LC = RTLIB::JUMPMAP_FIND_I64_I8; break; }
+          case 16: { LC = RTLIB::JUMPMAP_FIND_I64_I16; break; }
+          case 32: { LC = RTLIB::JUMPMAP_FIND_I64_I32; break; }
+          case 64:{ LC = RTLIB::JUMPMAP_FIND_I64_I64; break; }
+          default: { llvm_unreachable("Expand BR_JM: unknown key size"); }
+        }
+        break;
+      }
+      default:{
+        llvm_unreachable("Expand BR_JM: unknown condition VTy");
+      }
+    }
+
+    // JMFIXME Make a tailcall check
+    // JMFIXME libcall is a temporary solution
+    TargetLowering::ArgListTy Args;
+    TargetLowering::ArgListEntry Entry;
+
+    EVT MapVT   = JMap.getValueType();
+    Type *MapTy = MapVT.getTypeForEVT(*DAG.getContext());
+    Entry.Ty    = MapTy;
+    Entry.Node  = JMap;
+    Args.push_back(Entry);
+
+    EVT CondVT   = Cond.getValueType();
+    Type *CondTy = CondVT.getTypeForEVT(*DAG.getContext());
+    Entry.Ty     = CondTy;
+    Entry.Node   = Cond;
+    Args.push_back(Entry);
+
+    SDValue Callee = DAG.getExternalSymbol(
+          TLI.getLibcallName(LC), TLI.getPointerTy(DAG.getDataLayout()));
+
+    Type *RetTy = EVT(TLI.getPointerTy(DAG.getDataLayout()))
+      .getTypeForEVT(*DAG.getContext());
+
+    TargetLowering::CallLoweringInfo CLI(DAG);
+    CLI.setDebugLoc(SDLoc(Node)).setChain(Chain)
+      .setCallee(TLI.getLibcallCallingConv(LC), RetTy, Callee, std::move(Args));
+
+    std::pair<SDValue,SDValue> CallInfo = TLI.LowerCallTo(CLI);
+
+    if (TM.getRelocationModel() == Reloc::PIC_) {
+      llvm_unreachable("Expand BR_JM: Reloc::PIC_ not supported");
+    }
+
+    SDValue Res = DAG.getNode(ISD::BRIND, dl, MVT::Other,
+                              CallInfo.second, CallInfo.first);
+    Results.push_back(Res);
+    break;
+  }
   case ISD::BRCOND:
     // Expand brcond's setcc into its constituent parts and create a BR_CC
     // Node.
     Tmp1 = Node->getOperand(0);
     Tmp2 = Node->getOperand(1);
     if (Tmp2.getOpcode() == ISD::SETCC) {
       Tmp1 = DAG.getNode(ISD::BR_CC, dl, MVT::Other,
                          Tmp1, Tmp2.getOperand(2),
case ISD::SHL: {
     ReplaceNode(SDValue(Node, 0), Result);
     break;
   }
   case ISD::GLOBAL_OFFSET_TABLE:
   case ISD::GlobalAddress:
   case ISD::GlobalTLSAddress:
   case ISD::ExternalSymbol:
   case ISD::ConstantPool:
+  case ISD::JumpMap:
   case ISD::JumpTable:
   case ISD::INTRINSIC_W_CHAIN:
   case ISD::INTRINSIC_WO_CHAIN:
   case ISD::INTRINSIC_VOID:
     // FIXME: Custom lowering for these operations shouldn't return null!
     break;
   }
 

lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h

static bool isPassiveNode(SDNode *Node) {
       if (isa<RegisterSDNode>(Node))       return true;
       if (isa<RegisterMaskSDNode>(Node))   return true;
       if (isa<GlobalAddressSDNode>(Node))  return true;
       if (isa<BasicBlockSDNode>(Node))     return true;
       if (isa<FrameIndexSDNode>(Node))     return true;
       if (isa<ConstantPoolSDNode>(Node))   return true;
       if (isa<TargetIndexSDNode>(Node))    return true;
       if (isa<JumpTableSDNode>(Node))      return true;
+      if (isa<JumpMapSDNode>(Node))        return true;
       if (isa<ExternalSymbolSDNode>(Node)) return true;
       if (isa<MCSymbolSDNode>(Node))       return true;
       if (isa<BlockAddressSDNode>(Node))   return true;
       if (Node->getOpcode() == ISD::EntryToken ||
           isa<MDNodeSDNode>(Node)) return true;
       return false;
     }
 

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
   case ISD::TargetFrameIndex:
     ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
     break;
   case ISD::JumpTable:
   case ISD::TargetJumpTable:
     ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
     ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
     break;
+  case ISD::JumpMap:
+  case ISD::TargetJumpMap:
+    ID.AddInteger(cast<JumpMapSDNode>(N)->getIndex());
+    ID.AddInteger(cast<JumpMapSDNode>(N)->getTargetFlags());
+    break;
   case ISD::ConstantPool:
   case ISD::TargetConstantPool: {
     const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
     ID.AddInteger(CP->getAlignment());
     ID.AddInteger(CP->getOffset());
     if (CP->isMachineConstantPoolEntry())
       CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
     else
if (SDNode *E = FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
   auto *N = newSDNode<JumpTableSDNode>(JTI, VT, isTarget, TargetFlags);
   CSEMap.InsertNode(N, IP);
   InsertNode(N);
   return SDValue(N, 0);
 }
 
+SDValue SelectionDAG::getJumpMap(int JMI, EVT VT, bool isTarget,
+                                   unsigned char TargetFlags) {
+  assert((TargetFlags == 0 || isTarget) &&
+         "Cannot set target flags on target-independent jump maps");
+  unsigned Opc = isTarget ? ISD::TargetJumpMap : ISD::JumpMap;
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, Opc, getVTList(VT), None);
+  ID.AddInteger(JMI);
+  ID.AddInteger(TargetFlags);
+  void *IP = nullptr;
+  if (SDNode *E = FindNodeOrInsertPos(ID, IP))
+    return SDValue(E, 0);
+
+  auto *N = newSDNode<JumpMapSDNode>(JMI, VT, isTarget, TargetFlags);
+  CSEMap.InsertNode(N, IP);
+  InsertNode(N);
+  return SDValue(N, 0);
+}
+
 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
                                       unsigned Alignment, int Offset,
                                       bool isTarget,
                                       unsigned char TargetFlags) {
   assert((TargetFlags == 0 || isTarget) &&
          "Cannot set target flags on target-independent globals");
   if (Alignment == 0)
     Alignment = MF->getFunction()->optForSize()

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

private:
 
   enum CaseClusterKind {
     /// A cluster of adjacent case labels with the same destination, or just one
     /// case.
     CC_Range,
     /// A cluster of cases suitable for jump table lowering.
     CC_JumpTable,
     /// A cluster of cases suitable for bit test lowering.
-    CC_BitTests
+    CC_BitTests,
+    /// A cluster of cases suitable for jump map lowering.
+    CC_JumpMap
   };
 
   /// A cluster of case labels.
   struct CaseCluster {
     CaseClusterKind Kind;
     const ConstantInt *Low, *High;
     union {
       MachineBasicBlock *MBB;
       unsigned JTCasesIndex;
+      unsigned JMCasesIndex;
       unsigned BTCasesIndex;
     };
     BranchProbability Prob;
 
     static CaseCluster range(const ConstantInt *Low, const ConstantInt *High,
                              MachineBasicBlock *MBB, BranchProbability Prob) {
       CaseCluster C;
       C.Kind = CC_Range;
static CaseCluster jumpTable(const ConstantInt *Low,
       C.Kind = CC_JumpTable;
       C.Low = Low;
       C.High = High;
       C.JTCasesIndex = JTCasesIndex;
       C.Prob = Prob;
       return C;
     }
 
+    static CaseCluster jumpMap(const ConstantInt *Low,
+                               const ConstantInt *High, unsigned JMCasesIndex,
+                               BranchProbability Prob) {
+      CaseCluster C;
+      C.Kind = CC_JumpMap;
+      C.Low = Low;
+      C.High = High;
+      C.JMCasesIndex = JMCasesIndex;
+      C.Prob = Prob;
+      return C;
+    }
+
     static CaseCluster bitTests(const ConstantInt *Low, const ConstantInt *High,
                                 unsigned BTCasesIndex, BranchProbability Prob) {
       CaseCluster C;
       C.Kind = CC_BitTests;
       C.Low = Low;
       C.High = High;
       C.BTCasesIndex = BTCasesIndex;
       C.Prob = Prob;
struct JumpTableHeader {
     APInt First;
     APInt Last;
     const Value *SValue;
     MachineBasicBlock *HeaderBB;
     bool Emitted;
   };
   typedef std::pair<JumpTableHeader, JumpTable> JumpTableBlock;
 
+  struct JumpMapBlock {
+    JumpMapBlock(unsigned R, unsigned J, MachineBasicBlock *M,
+                 MachineBasicBlock *D, const Value *C, unsigned S,
+                 EVT T, unsigned CS)
+                  : Reg(R), JMI(J), MBB(M), DBB(D),
+                    Condition(C), MinSize(S), KeyTy(T), CondSize(CS),
+                    Inserted(false), Emitted(false){}
+
+    /// Reg - the virtual register containing the index of the jump map entry
+    /// to jump to.
+    unsigned Reg;
+    /// JMI - the JumpMapIndex for this jump map in the function.
+    unsigned JMI;
+    /// MBB - the MBB into which to emit the code for the indirect jump.
+    MachineBasicBlock *MBB;
+    /// DBB - the BB of the default case.
+    MachineBasicBlock *DBB;
+    /// Condition - the SValue containing the switch condition of the jump map.
+    const Value *Condition;
+    /// MinSize - the jump map minimal key size in bits.
+    unsigned MinSize;
+    /// KeyTy - the type of the jump map keys.
+    EVT KeyTy;
+    /// CondSize - the size of the switch condition to be chosen.
+    unsigned CondSize;
+    /// Inserted - has jump map block been inserted?
+    bool Inserted;
+    /// Inserted - has jump map block been emitted?
+    bool Emitted;
+  };
+
   struct BitTestCase {
     BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr,
                 BranchProbability Prob):
       Mask(M), ThisBB(T), TargetBB(Tr), ExtraProb(Prob) { }
     uint64_t Mask;
     MachineBasicBlock *ThisBB;
     MachineBasicBlock *TargetBB;
     BranchProbability ExtraProb;
private:
   bool buildJumpTable(const CaseClusterVector &Clusters, unsigned First,
                       unsigned Last, const SwitchInst *SI,
                       MachineBasicBlock *DefaultMBB, CaseCluster &JTCluster);
 
   /// Find clusters of cases suitable for jump table lowering.
   void findJumpTables(CaseClusterVector &Clusters, const SwitchInst *SI,
                       MachineBasicBlock *DefaultMBB);
 
+  /// Build a jump map cluster from Clusters[First..Last]. Returns false if it
+  /// decides it's not a good idea.
+  bool buildJumpMap(const CaseClusterVector &Clusters, const SwitchInst *SI,
+                    MachineBasicBlock *DefaultMBB, CaseCluster &JMCluster);
+
   /// Build a bit test cluster from Clusters[First..Last]. Returns false if it
   /// decides it's not a good idea.
   bool buildBitTests(CaseClusterVector &Clusters, unsigned First, unsigned Last,
                      const SwitchInst *SI, CaseCluster &BTCluster);
 
   /// Find clusters of cases suitable for bit test lowering.
   void findBitTestClusters(CaseClusterVector &Clusters, const SwitchInst *SI);
 
private:
 
   /// Emit comparison and split W into two subtrees.
   void splitWorkItem(SwitchWorkList &WorkList, const SwitchWorkListItem &W,
                      Value *Cond, MachineBasicBlock *SwitchMBB);
 
   /// Lower W.
   void lowerWorkItem(SwitchWorkListItem W, Value *Cond,
                      MachineBasicBlock *SwitchMBB,
-                     MachineBasicBlock *DefaultMBB);
+                     MachineBasicBlock *DefaultMBB,
+                     JumpMapBlock* JumpMap);
 
 
   /// A class which encapsulates all of the information needed to generate a
   /// stack protector check and signals to isel via its state being initialized
   /// that a stack protector needs to be generated.
   ///
   /// *NOTE* The following is a high level documentation of SelectionDAG Stack
   /// Protector Generation. The reason that it is placed here is for a lack of
public:
   const TargetLibraryInfo *LibInfo;
 
   /// SwitchCases - Vector of CaseBlock structures used to communicate
   /// SwitchInst code generation information.
   std::vector<CaseBlock> SwitchCases;
   /// JTCases - Vector of JumpTable structures used to communicate
   /// SwitchInst code generation information.
   std::vector<JumpTableBlock> JTCases;
+  /// JMCases - Vector of JumpMap structures used to communicate
+  /// SwitchInst code generation information.
+  std::vector<JumpMapBlock> JMCases;
   /// BitTestCases - Vector of BitTestBlock structures used to communicate
   /// SwitchInst code generation information.
   std::vector<BitTestBlock> BitTestCases;
   /// A StackProtectorDescriptor structure used to communicate stack protector
   /// information in between SelectBasicBlock and FinishBasicBlock.
   StackProtectorDescriptor SPDescriptor;
 
   // Emit PHI-node-operand constants only once even if used by multiple
public:
   void visitSPDescriptorFailure(StackProtectorDescriptor &SPD);
   void visitBitTestHeader(BitTestBlock &B, MachineBasicBlock *SwitchBB);
   void visitBitTestCase(BitTestBlock &BB,
                         MachineBasicBlock* NextMBB,
                         BranchProbability BranchProbToNext,
                         unsigned Reg,
                         BitTestCase &B,
                         MachineBasicBlock *SwitchBB);
+  void visitJumpMap(JumpMapBlock &JM);
   void visitJumpTable(JumpTable &JT);
   void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH,
                             MachineBasicBlock *SwitchBB);
 
 private:
   // These all get lowered before this pass.
   void visitInvoke(const InvokeInst &I);
   void visitResume(const ResumeInst &I);

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

 #include "llvm/CodeGen/Analysis.h"
 #include "llvm/CodeGen/FastISel.h"
 #include "llvm/CodeGen/FunctionLoweringInfo.h"
 #include "llvm/CodeGen/GCMetadata.h"
 #include "llvm/CodeGen/GCStrategy.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineJumpMapInfo.h"
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/CodeGen/SelectionDAGTargetInfo.h"
 #include "llvm/CodeGen/StackMaps.h"
+#include "llvm/CodeGen/SwitchAnalysis.h"
 #include "llvm/CodeGen/WinEHFuncInfo.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"

 static unsigned LimitFloatPrecision;
 
 static cl::opt<unsigned, true>
 LimitFPPrecision("limit-float-precision",
                  cl::desc("Generate low-precision inline sequences "
                           "for some float libcalls"),
                  cl::location(LimitFloatPrecision),
                  cl::init(0));
+
 // Limit the width of DAG chains. This is important in general to prevent
 // DAG-based analysis from blowing up. For example, alias analysis and
 // load clustering may not complete in reasonable time. It is difficult to
 // recognize and avoid this situation within each individual analysis, and
 // future analyses are likely to have the same behavior. Limiting DAG width is
 // the safe approach and will be especially important with global DAGs.
 //
 // MaxParallelChains default is arbitrarily high to avoid affecting
void SelectionDAGBuilder::visitJumpTableHeader(JumpTable &JT,
   // Avoid emitting unnecessary branches to the next block.
   if (JT.MBB != NextBlock(SwitchBB))
     BrCond = DAG.getNode(ISD::BR, dl, MVT::Other, BrCond,
                          DAG.getBasicBlock(JT.MBB));
 
   DAG.setRoot(BrCond);
 }
 
+/// visitJumpMap - Emit JumpMap node in the current MBB
+void SelectionDAGBuilder::visitJumpMap(JumpMapBlock &JM) {
+  // Emit the code for the jump map
+  SDLoc dl      = getCurSDLoc();
+  SDValue Chain = getControlRoot();
+  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
+  EVT PTy = TLI.getPointerTy(DAG.getDataLayout());
+
+  SDValue Condition = getValue(JM.Condition);
+  EVT KeyTy = JM.KeyTy;
+  if (Condition.getOpcode() == ISD::ZERO_EXTEND
+      && Condition.getOperand(0).getValueType() == KeyTy
+      && JM.MinSize == JM.CondSize) {
+    Condition = Condition.getOperand(0);
+  }
+  SDValue MinSize = DAG.getConstant(JM.MinSize, dl, MVT::i8);
+
+  SDValue JMOp = DAG.getJumpMap(JM.JMI, PTy);
+  SDValue BrJM = DAG.getNode(ISD::BR_JM, dl, MVT::Other, Chain,
+                             JMOp, Condition, MinSize);
+  DAG.setRoot(BrJM);
+}
+
 /// Create a LOAD_STACK_GUARD node, and let it carry the target specific global
 /// variable if there exists one.
 static SDValue getLoadStackGuard(SelectionDAG &DAG, const SDLoc &DL,
                                  SDValue &Chain) {
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
   EVT PtrTy = TLI.getPointerTy(DAG.getDataLayout());
   MachineFunction &MF = DAG.getMachineFunction();
   Value *Global = TLI.getSDagStackGuard(*MF.getFunction()->getParent());

 
 void SelectionDAGBuilder::UpdateSplitBlock(MachineBasicBlock *First,
                                            MachineBasicBlock *Last) {
   // Update JTCases.
   for (unsigned i = 0, e = JTCases.size(); i != e; ++i)
     if (JTCases[i].first.HeaderBB == First)
       JTCases[i].first.HeaderBB = Last;
 
+  // Update JMCases.
+  for (unsigned i = 0, e = JMCases.size(); i != e; ++i)
+    if (JMCases[i].MBB == First)
+      JMCases[i].MBB = Last;
+
   // Update BitTestCases.
   for (unsigned i = 0, e = BitTestCases.size(); i != e; ++i)
     if (BitTestCases[i].Parent == First)
       BitTestCases[i].Parent = Last;
 }
 
 void SelectionDAGBuilder::visitIndirectBr(const IndirectBrInst &I) {
   MachineBasicBlock *IndirectBrMBB = FuncInfo.MBB;
uint64_t SelectionDAGBuilder::getJumpTableNumCases(
     unsigned Last) const {
   assert(Last >= First);
   assert(TotalCases[Last] >= TotalCases[First]);
   uint64_t NumCases =
       TotalCases[Last] - (First == 0 ? 0 : TotalCases[First - 1]);
   return NumCases;
 }
 
+// JMFIXME compute and update branch probabilities
+bool SelectionDAGBuilder::buildJumpMap(const CaseClusterVector &Clusters,
+                                       const SwitchInst *SI,
+                                       MachineBasicBlock *DefaultMBB,
+                                       CaseCluster &JMCluster) {
+  auto Prob = BranchProbability::getZero();
+  std::map<uint64_t, MachineBasicBlock*> DestBBs;
+  DenseMap<MachineBasicBlock*, BranchProbability> JMProbs;
+  unsigned ClustersNum = Clusters.size();
+
+  // Initialize probabilities in JMProbs.
+  unsigned FirstIndex = 0;
+  unsigned LastIndex = 0;
+  unsigned JTCount = 0;
+  for (unsigned I = 0; I < ClustersNum; ++I) {
+    if (Clusters[I].Kind != CC_JumpTable) {
+      if (FirstIndex == 0)
+        FirstIndex = I;
+      LastIndex = I;
+      JMProbs[Clusters[I].MBB] = BranchProbability::getZero();
+    } else {
+      ++JTCount;
+    }
+  }
+
+  const ConstantInt *First = Clusters[FirstIndex].Low;
+  const ConstantInt *Last = Clusters[LastIndex].High;
+
+  unsigned KeySize = 0;
+  unsigned JMCount = 0;
+
+  for (unsigned I = 0; I < ClustersNum; ++I) {
+    if (Clusters[I].Kind != CC_JumpTable) {
+      assert(Clusters[I].Kind == CC_Range);
+      Prob += Clusters[I].Prob;
+      for (APInt J = Clusters[I].Low->getValue();;){
+        JMCount++;
+        uint64_t Jkey = J.getZExtValue();
+        KeySize = KeySize > J.getActiveBits() ? KeySize : J.getActiveBits();
+        DestBBs[Jkey] = Clusters[I].MBB;
+        if(J.eq(Clusters[I].High->getValue())) break;
+        ++J;
+      }
+      JMProbs[Clusters[I].MBB] += Clusters[I].Prob;
+    }
+  }
+
+  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
+  if (JMCount < TLI.getMinimumJumpMapEntries())
+    return false;
+
+  EVT KeyTy = MVT::Other;
+  if     (KeySize <= 8)  { KeyTy = MVT::i8;  KeySize = 8;  }
+  else if(KeySize <= 16) { KeyTy = MVT::i16; KeySize = 16; }
+  else if(KeySize <= 32) { KeyTy = MVT::i32; KeySize = 32; }
+  else if(KeySize <= 64) { KeyTy = MVT::i64; KeySize = 64; }
+  else                   { llvm_unreachable("Unsupported KeyTy"); }
+
+  MachineFunction *CurMF = FuncInfo.MF;
+
+  // If there are any jump tables, create a basis block handling JM search.
+  // If not, JM search is emitted right to the switch MBB.
+  MachineBasicBlock *JumpMapMBB = JTCount > 0 ?
+                                CurMF->CreateMachineBasicBlock(SI->getParent())
+                                : FuncInfo.MBBMap[SI->getParent()];
+  // Add successors.
+  auto DefaultProb = getEdgeProbability(FuncInfo.MBBMap[SI->getParent()],
+                                        DefaultMBB);
+  addSuccessorWithProb(JumpMapMBB, DefaultMBB, DefaultProb);
+  SmallPtrSet<MachineBasicBlock *, 8> Done;
+  for (auto& Succ : DestBBs) {
+    MachineBasicBlock *DestBB = Succ.second;
+    if (Done.count(DestBB))
+      continue;
+    addSuccessorWithProb(JumpMapMBB, DestBB, JMProbs[DestBB]);
+    Done.insert(DestBB);
+  }
+  JumpMapMBB->normalizeSuccProbs();
+
+  // If switch analysis for condition type is available, use it
+  SDValue SwitchCond = getValue(SI->getCondition());
+  EVT KeyEVTTy = KeyTy;
+  if ((SwitchCond.getOpcode() == ISD::ZERO_EXTEND) &&
+       SwitchCond.getOperand(0).getValueType() == KeyEVTTy) {
+    SwitchCond = SwitchCond.getOperand(0);
+  }
+  unsigned SwitchCondSize = SwitchCond.getValueSizeInBits();
+  unsigned RecCondSize = 0;
+  unsigned RecKeySize = 0;
+  if (FuncInfo.SWAN != nullptr) {
+    RecCondSize = FuncInfo.SWAN->recommendedCondSize(SwitchCondSize);
+    RecKeySize = FuncInfo.SWAN->recommendedKeySize(SwitchCondSize);
+  }
+  if (RecCondSize != 0 && RecKeySize != 0) {
+    KeySize = RecKeySize;
+    switch (KeySize) {
+      case 8: KeyTy = MVT::i8; break;
+      case 16: KeyTy = MVT::i16; break;
+      case 32: KeyTy = MVT::i32; break;
+      case 64: KeyTy = MVT::i64; break;
+      default: llvm_unreachable("Unsupported KeyTy");
+    }
+  }
+
+  unsigned JMI = CurMF->getOrCreateJumpMapInfo(TLI.getJumpMapEncoding())
+                      ->createJumpMapIndex(DestBBs, DefaultMBB,
+                                           KeyTy.getStoreSize());
+
+  // Set up the jump map info.
+  JumpMapBlock JM(-1U, JMI, JumpMapMBB, DefaultMBB, SI->getCondition(),
+                  KeySize, KeyTy, RecCondSize);
+  if (JumpMapMBB == FuncInfo.MBBMap[SI->getParent()])
+    JM.Inserted = true;
+
+  JMCases.emplace_back(std::move(JM));
+  JMCluster = CaseCluster::jumpMap(First, Last, JMCases.size() - 1, Prob);
+
+  return true;
+}
+
 bool SelectionDAGBuilder::buildJumpTable(const CaseClusterVector &Clusters,
                                          unsigned First, unsigned Last,
                                          const SwitchInst *SI,
                                          MachineBasicBlock *DefaultMBB,
                                          CaseCluster &JTCluster) {
   assert(First <= Last);
 
   auto Prob = BranchProbability::getZero();
if (NumClusters >= MinJumpTableEntries &&
         buildJumpTable(Clusters, First, Last, SI, DefaultMBB, JTCluster)) {
       Clusters[DstIndex++] = JTCluster;
     } else {
       for (unsigned I = First; I <= Last; ++I)
         std::memmove(&Clusters[DstIndex++], &Clusters[I], sizeof(Clusters[I]));
     }
   }
   Clusters.resize(DstIndex);
+
+  // All jump tables are created. If possible, build a jump map
+  // out of remaining cases.
+  if (TLI.areJMsAllowed(SI->getParent()->getParent())) {
+    CaseCluster JMCluster;
+    if (buildJumpMap(Clusters, SI, DefaultMBB, JMCluster)) {
+      unsigned Count = 0;
+      unsigned ClustersSize = Clusters.size();
+      for (unsigned I = 0; I <= ClustersSize; ++I) {
+        if (Clusters[I].Kind == CC_JumpTable) {
+          std::memmove(&Clusters[Count++], &Clusters[I], sizeof(Clusters[I]));
+        }
+      }
+      Clusters.resize(Count + 1);
+      Clusters[Clusters.size() - 1] = JMCluster;
+    }
+  }
 }
 
 bool SelectionDAGBuilder::buildBitTests(CaseClusterVector &Clusters,
                                         unsigned First, unsigned Last,
                                         const SwitchInst *SI,
                                         CaseCluster &BTCluster) {
   assert(First <= Last);
   if (First == Last)
if (buildBitTests(Clusters, First, Last, SI, BitTestCluster)) {
       std::memmove(&Clusters[DstIndex], &Clusters[First],
                    sizeof(Clusters[0]) * NumClusters);
       DstIndex += NumClusters;
     }
   }
   Clusters.resize(DstIndex);
 }
 
+// JMFIXME compute and update branch probabilities
 void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond,
                                         MachineBasicBlock *SwitchMBB,
-                                        MachineBasicBlock *DefaultMBB) {
+                                        MachineBasicBlock *DefaultMBB,
+                                        JumpMapBlock* JumpMap) {
   MachineFunction *CurMF = FuncInfo.MF;
   MachineBasicBlock *NextMBB = nullptr;
   MachineFunction::iterator BBI(W.MBB);
   if (++BBI != FuncInfo.MF->end())
     NextMBB = &*BBI;
 
   unsigned Size = W.LastCluster - W.FirstCluster + 1;
 
void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond,
   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) {
     MachineBasicBlock *Fallthrough;
     if (I == W.LastCluster) {
       // For the last cluster, fall through to the default destination.
-      Fallthrough = DefaultMBB;
+      Fallthrough = JumpMap != nullptr ? JumpMap->MBB : DefaultMBB;
     } else {
       Fallthrough = CurMF->CreateMachineBasicBlock(CurMBB->getBasicBlock());
       CurMF->insert(BBI, Fallthrough);
       // Put Cond in a virtual register to make it available from the new blocks.
       ExportFromCurrentBlock(Cond);
     }
     UnhandledProbs -= I->Prob;
 
switch (I->Kind) {
 
         // If we're in the right place, emit the jump table header right now.
         if (CurMBB == SwitchMBB) {
           visitJumpTableHeader(*JT, *JTH, SwitchMBB);
           JTH->Emitted = true;
         }
         break;
       }
+      case CC_JumpMap: {
+        // This case is hit only if a jump map is the only switch cluster.
+        // Emit it in this place.
+        JumpMapBlock& JM = JMCases[I->JMCasesIndex];
+        visitJumpMap(JM);
+        JM.Emitted = true;
+        break;
+      }
       case CC_BitTests: {
         // FIXME: Optimize away range check based on pivot comparisons.
         BitTestBlock *BTB = &BitTestCases[I->BTCasesIndex];
 
         // The bit test blocks haven't been inserted yet; insert them here.
         for (BitTestCase &BTC : BTB->Cases)
           CurMF->insert(BBI, BTC.ThisBB);
 
switch (I->Kind) {
         else
           SwitchCases.push_back(CB);
 
         break;
       }
     }
     CurMBB = Fallthrough;
   }
+  // We have finished cases lowering. If the fallthrough is a jump map,
+  // insert it here:
+  if (JumpMap != nullptr && CurMBB == JumpMap->MBB && !JumpMap->Inserted) {
+    CurMF->insert(BBI, JumpMap->MBB);
+    JumpMap->Inserted = true;
+  }
 }
 
 unsigned SelectionDAGBuilder::caseClusterRank(const CaseCluster &CC,
                                               CaseClusterIt First,
                                               CaseClusterIt Last) {
   return std::count_if(First, Last + 1, [&](const CaseCluster &X) {
     if (X.Prob != CC.Prob)
       return X.Prob > CC.Prob;
if (Clusters.empty()) {
     if (DefaultMBB != NextBlock(SwitchMBB)) {
       DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(), MVT::Other,
                               getControlRoot(), DAG.getBasicBlock(DefaultMBB)));
     }
     return;
   }
 
   findJumpTables(Clusters, &SI, DefaultMBB);
+  // Create bit tests only if there is no jump map
+  JumpMapBlock* JumpMapB = nullptr;
+  if (Clusters.back().Kind != CC_JumpMap) {
     findBitTestClusters(Clusters, &SI);
+  } else {
+    JumpMapB = &JMCases[Clusters.back().JMCasesIndex];
+  }
 
   DEBUG({
     dbgs() << "Case clusters: ";
     for (const CaseCluster &C : Clusters) {
       if (C.Kind == CC_JumpTable) dbgs() << "JT:";
+      if (C.Kind == CC_JumpMap) dbgs() << "JM:";
       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;
+  CaseClusterIt Last;
+  // Don't run lowering on jump maps if they are not the only cluster
+  if (JumpMapB != nullptr && Clusters.size() > 1) {
+    Last = Clusters.end() - 2;
+  } else {
+    Last = Clusters.end() - 1;
+  }
   auto DefaultProb = getEdgeProbability(SwitchMBB, DefaultMBB);
   WorkList.push_back({SwitchMBB, First, Last, nullptr, nullptr, DefaultProb});
 
   while (!WorkList.empty()) {
     SwitchWorkListItem W = WorkList.back();
     WorkList.pop_back();
     unsigned NumClusters = W.LastCluster - W.FirstCluster + 1;
 
     if (NumClusters > 3 && TM.getOptLevel() != CodeGenOpt::None &&
         !DefaultMBB->getParent()->getFunction()->optForMinSize()) {
       // For optimized builds, lower large range as a balanced binary tree.
       splitWorkItem(WorkList, W, SI.getCondition(), SwitchMBB);
       continue;
     }
 
-    lowerWorkItem(W, SI.getCondition(), SwitchMBB, DefaultMBB);
+    lowerWorkItem(W, SI.getCondition(), SwitchMBB, DefaultMBB, JumpMapB);
   }
 }

lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp

case ISD::Constant:
     if (cast<ConstantSDNode>(this)->isOpaque())
       return "OpaqueConstant";
     return "Constant";
   case ISD::ConstantFP:                 return "ConstantFP";
   case ISD::GlobalAddress:              return "GlobalAddress";
   case ISD::GlobalTLSAddress:           return "GlobalTLSAddress";
   case ISD::FrameIndex:                 return "FrameIndex";
   case ISD::JumpTable:                  return "JumpTable";
+  case ISD::JumpMap:                    return "JumpMap";
   case ISD::GLOBAL_OFFSET_TABLE:        return "GLOBAL_OFFSET_TABLE";
   case ISD::RETURNADDR:                 return "RETURNADDR";
   case ISD::ADDROFRETURNADDR:           return "ADDROFRETURNADDR";
   case ISD::FRAMEADDR:                  return "FRAMEADDR";
   case ISD::LOCAL_RECOVER:              return "LOCAL_RECOVER";
   case ISD::READ_REGISTER:              return "READ_REGISTER";
   case ISD::WRITE_REGISTER:             return "WRITE_REGISTER";
   case ISD::FRAME_TO_ARGS_OFFSET:       return "FRAME_TO_ARGS_OFFSET";
case ISD::TargetConstant:
     if (cast<ConstantSDNode>(this)->isOpaque())
       return "OpaqueTargetConstant";
     return "TargetConstant";
   case ISD::TargetConstantFP:           return "TargetConstantFP";
   case ISD::TargetGlobalAddress:        return "TargetGlobalAddress";
   case ISD::TargetGlobalTLSAddress:     return "TargetGlobalTLSAddress";
   case ISD::TargetFrameIndex:           return "TargetFrameIndex";
   case ISD::TargetJumpTable:            return "TargetJumpTable";
+  case ISD::TargetJumpMap:              return "TargetJumpMap";
   case ISD::TargetConstantPool:         return "TargetConstantPool";
   case ISD::TargetExternalSymbol:       return "TargetExternalSymbol";
   case ISD::MCSymbol:                   return "MCSymbol";
   case ISD::TargetBlockAddress:         return "TargetBlockAddress";
 
   case ISD::CopyToReg:                  return "CopyToReg";
   case ISD::CopyFromReg:                return "CopyFromReg";
   case ISD::UNDEF:                      return "undef";
#endif
   case ISD::ADDRSPACECAST:              return "addrspacecast";
   case ISD::FP16_TO_FP:                 return "fp16_to_fp";
   case ISD::FP_TO_FP16:                 return "fp_to_fp16";
 
     // Control flow instructions
   case ISD::BR:                         return "br";
   case ISD::BRIND:                      return "brind";
   case ISD::BR_JT:                      return "br_jt";
+  case ISD::BR_JM:                      return "br_jm";
   case ISD::BRCOND:                     return "brcond";
   case ISD::BR_CC:                      return "br_cc";
   case ISD::CALLSEQ_START:              return "callseq_start";
   case ISD::CALLSEQ_END:                return "callseq_end";
 
     // EH instructions
   case ISD::CATCHRET:                   return "catchret";
   case ISD::CLEANUPRET:                 return "cleanupret";
if (const MachineSDNode *MN = dyn_cast<MachineSDNode>(this)) {
     if (unsigned int TF = GADN->getTargetFlags())
       OS << " [TF=" << TF << ']';
   } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) {
     OS << "<" << FIDN->getIndex() << ">";
   } else if (const JumpTableSDNode *JTDN = dyn_cast<JumpTableSDNode>(this)) {
     OS << "<" << JTDN->getIndex() << ">";
     if (unsigned int TF = JTDN->getTargetFlags())
       OS << " [TF=" << TF << ']';
+  } else if (const JumpMapSDNode *JMDN = dyn_cast<JumpMapSDNode>(this)) {
+    OS << "<" << JMDN->getIndex() << ">";
+    if (unsigned int TF = JMDN->getTargetFlags())
+      OS << " [TF=" << TF << ']';
   } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
     int offset = CP->getOffset();
     if (CP->isMachineConstantPoolEntry())
       OS << "<" << *CP->getMachineCPVal() << ">";
     else
       OS << "<" << *CP->getConstVal() << ">";
     if (offset > 0)
       OS << " + " << offset;

lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

 #include "llvm/CodeGen/MachinePassRegistry.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/MachineValueType.h"
 #include "llvm/CodeGen/SchedulerRegistry.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/CodeGen/SelectionDAGISel.h"
 #include "llvm/CodeGen/SelectionDAGNodes.h"
 #include "llvm/CodeGen/StackProtector.h"
+#include "llvm/CodeGen/SwitchAnalysis.h"
 #include "llvm/CodeGen/ValueTypes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InlineAsm.h"
void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<AAResultsWrapperPass>();
   AU.addRequired<GCModuleInfo>();
   AU.addRequired<StackProtector>();
   AU.addPreserved<StackProtector>();
   AU.addPreserved<GCModuleInfo>();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
   if (UseMBPI && OptLevel != CodeGenOpt::None)
     AU.addRequired<BranchProbabilityInfoWrapperPass>();
+  if (OptLevel != CodeGenOpt::None) {
+    AU.addRequired<SwitchLegacyAnalysis>();
+    AU.addPreserved<SwitchLegacyAnalysis>();
+  }
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 /// SplitCriticalSideEffectEdges - Look for critical edges with a PHI value that
 /// may trap on it.  In this case we have to split the edge so that the path
 /// through the predecessor block that doesn't go to the phi block doesn't
 /// execute the possibly trapping instruction.
 ///
bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
   CurDAG->init(*MF, *ORE);
   FuncInfo->set(Fn, *MF, CurDAG);
 
   if (UseMBPI && OptLevel != CodeGenOpt::None)
     FuncInfo->BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
   else
     FuncInfo->BPI = nullptr;
 
+  if(OptLevel != CodeGenOpt::None)
+    FuncInfo->SWAN = &getAnalysis<SwitchLegacyAnalysis>().getSWAN();
+  else
+    FuncInfo->SWAN = nullptr;
+
   SDB->init(GFI, *AA, LibInfo);
 
   MF->setHasInlineAsm(false);
 
   FuncInfo->SplitCSR = false;
 
   // We split CSR if the target supports it for the given function
   // and the function has only return exits.
for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
            .addMBB(SDB->JTCases[i].first.HeaderBB);
       // JT BB. Just iterate over successors here
       if (FuncInfo->MBB->isSuccessor(PHIBB))
         PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(FuncInfo->MBB);
     }
   }
   SDB->JTCases.clear();
 
+  for (unsigned i = 0, e = SDB->JMCases.size(); i != e; ++i) {
+    // Emit a jump map if it's necessary.
+    if(!SDB->JMCases[i].Emitted) {
+      FuncInfo->MBB = SDB->JMCases[i].MBB;
+      FuncInfo->InsertPt = FuncInfo->MBB->end();
+      SDB->visitJumpMap(SDB->JMCases[i]);
+      CurDAG->setRoot(SDB->getRoot());
+      SDB->clear();
+      CodeGenAndEmitDAG();
+    }
+    for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
+         pi != pe; ++pi) {
+      MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
+      MachineBasicBlock *PHIBB = PHI->getParent();
+      assert(PHI->isPHI() &&
+             "This is not a machine PHI node that we are updating!");
+      if (FuncInfo->MBB->isSuccessor(PHIBB))
+        PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(FuncInfo->MBB);
+    }
+  }
+  SDB->JMCases.clear();
+
   // If we generated any switch lowering information, build and codegen any
   // additional DAGs necessary.
   for (unsigned i = 0, e = SDB->SwitchCases.size(); i != e; ++i) {
     // Set the current basic block to the mbb we wish to insert the code into
     FuncInfo->MBB = SDB->SwitchCases[i].ThisBB;
     FuncInfo->InsertPt = FuncInfo->MBB->end();
 
     // Determine the unique successors.
void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch,
   case ISD::TargetConstant:
   case ISD::TargetConstantFP:
   case ISD::TargetConstantPool:
   case ISD::TargetFrameIndex:
   case ISD::TargetExternalSymbol:
   case ISD::MCSymbol:
   case ISD::TargetBlockAddress:
   case ISD::TargetJumpTable:
+  case ISD::TargetJumpMap:
   case ISD::TargetGlobalTLSAddress:
   case ISD::TargetGlobalAddress:
   case ISD::TokenFactor:
   case ISD::CopyFromReg:
   case ISD::CopyToReg:
   case ISD::EH_LABEL:
   case ISD::LIFETIME_START:
   case ISD::LIFETIME_END:

lib/CodeGen/SelectionDAG/TargetLowering.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Target/TargetLowering.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/CodeGen/CallingConvLower.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineJumpMapInfo.h"
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/MC/MCAsmInfo.h"

 /// getPICJumpTableRelocBase, but as an MCExpr.
 const MCExpr *
 TargetLowering::getPICJumpTableRelocBaseExpr(const MachineFunction *MF,
                                              unsigned JTI,MCContext &Ctx) const{
   // The normal PIC reloc base is the label at the start of the jump table.
   return MCSymbolRefExpr::create(MF->getJTISymbol(JTI, Ctx), Ctx);
 }
 
+/// Return the entry encoding for a jump map in the current function. The
+/// returned value is a member of the MachineJumpMapInfo::JMEntryKind enum.
+unsigned TargetLowering::getJumpMapEncoding() const {
+  // In non-pic modes, just use the address of a block.
+  // JMFIXME implement PIC_ support for jump maps.
+  if (!isPositionIndependent())
+    return MachineJumpMapInfo::EK_BlockAddress;
+
+  llvm_unreachable("Reloc::PIC_ jump maps not supported");
+}
+
 bool
 TargetLowering::isOffsetFoldingLegal(const GlobalAddressSDNode *GA) const {
   const TargetMachine &TM = getTargetMachine();
   const GlobalValue *GV = GA->getGlobal();
 
   // If the address is not even local to this DSO we will have to load it from
   // a got and then add the offset.
   if (!TM.shouldAssumeDSOLocal(*GV->getParent(), GV))

lib/CodeGen/SwitchAnalysis.cpp

+//===--------- SwitchAnalysis.cpp - Implement the Switch Analysis ----------==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// The analysis finds the switches and attempts to determine whether they will
+// be lowered to jump tables or jump maps during building of selection DAGs.
+// Further analysis is done for the switches which will be turned into jump
+// maps. The goal is to determine which functions should be used for jump maps
+// lookup. For instance, if there are two switches:
+//           * i32 condition, all keys can be stored in i8
+//           * i32 condition, all keys can be stored in i16
+// we don't want to create both i32_i8 and i32_i16 lookup versions, only i32_i16
+// version should be used as it can handle both cases.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/ISDOpcodes.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/SwitchAnalysis.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "switch-analysis"
+
+/// Legacy pass
+char SwitchLegacyAnalysis::ID = 0;
+INITIALIZE_TM_PASS(SwitchLegacyAnalysis, "switchanalysis",
+                   "Switch Legacy Analysis", false, true)
+
+FunctionPass *llvm::createSwitchLegacyAnalysisPass(const TargetMachine *TM) {
+  return new SwitchLegacyAnalysis(TM);
+}
+
+bool SwitchLegacyAnalysis::runOnFunction(Function &Fn) {
+  SWAN.analyze(Fn);
+  return false;
+}
+
+bool SwitchAnalysis::isDense(const std::vector<CaseCluster> &Clusters,
+                             const SmallVectorImpl<unsigned> &TotalCases,
+                             unsigned First, unsigned Last,
+                             unsigned Density) const {
+  const APInt &LowCase = Clusters[First].Low->getValue();
+  const APInt &HighCase = Clusters[Last].High->getValue();
+  uint64_t Diff = (HighCase - LowCase).getLimitedValue((UINT64_MAX - 1) / 100);
+  uint64_t Range = Diff + 1;
+  uint64_t NumCases =
+      TotalCases[Last] - (First == 0 ? 0 : TotalCases[First - 1]);
+  return NumCases * 100 >= Range * Density;
+}
+
+std::vector<SwitchAnalysis::CaseCluster>
+SwitchAnalysis::JumpMapCases(SwitchInst& SI, const bool OptForSize) {
+  std::vector<CaseCluster> Remaining;
+  // Ask TargetLoweringBase about minimal number of clusters in a jump table.
+  // If such information cannot be obtained or jump tables are illegal,
+  // return false.
+  unsigned MinJumpTableSize = 0;
+  if (TL) {
+    MinJumpTableSize = TL->getMinimumJumpTableEntries();
+    if (!TL->isOperationLegalOrCustom(ISD::BR_JT, MVT::Other) &&
+        !TL->isOperationLegalOrCustom(ISD::BRIND, MVT::Other)) {
+      MinJumpTableSize = 0;
+    }
+  }
+  if (MinJumpTableSize == 0) {
+    return Remaining;
+  }
+
+  // JMFIXME: This part is copy-pasted from SelectionDAGBuilder.
+  // This is not the most elegant solution as it may cause disparity
+  // when SelectionDAGBuilder changes.
+  // A common interface for clusterification, computing density
+  // and partitioning would be a better solution.
+  // Compute cases clusterification analogous to the one in SelectionDAGBuilder.
+  std::vector<CaseCluster> Clusters;
+  Clusters.reserve(SI.getNumCases());
+  for (auto& C : SI.cases()) {
+    const ConstantInt *CaseVal = C.getCaseValue();
+    Clusters.push_back(CaseCluster::range(CaseVal, CaseVal,
+                                          C.getCaseSuccessor()));
+  }
+  std::sort(Clusters.begin(), Clusters.end(),
+            [](const CaseCluster &a, const CaseCluster &b) {
+    return a.Low->getValue().slt(b.Low->getValue());
+  });
+  unsigned N = Clusters.size();
+  unsigned DstIndex = 0;
+  for (unsigned SrcIndex = 0; SrcIndex < N; ++SrcIndex) {
+    CaseCluster &CC = Clusters[SrcIndex];
+    const ConstantInt *CaseVal = CC.Low;
+    BasicBlock *Succ = CC.BB;
+    if (DstIndex != 0 && Clusters[DstIndex - 1].BB == Succ &&
+        (CaseVal->getValue() - Clusters[DstIndex - 1].High->getValue()) == 1) {
+      Clusters[DstIndex - 1].High = CaseVal;
+    } else {
+      std::memmove(&Clusters[DstIndex++], &Clusters[SrcIndex],
+      sizeof(Clusters[SrcIndex]));
+    }
+  }
+  Clusters.resize(DstIndex);
+  N = Clusters.size();
+
+  // Analyse density, partitioning...
+  // For more comments refer SelectionDAGBuilder::findJumpTables(...)
+  const unsigned MinJumpTableEntries = TL->getMinimumJumpTableEntries();
+  const unsigned SmallNumberOfEntries = MinJumpTableEntries / 2;
+  const unsigned MaxJumpTableSize =
+                            OptForSize || TL->getMaximumJumpTableSize() == 0
+                            ? UINT_MAX : TL->getMaximumJumpTableSize();
+
+  if (N < 2 || N < MinJumpTableEntries)
+    return Remaining;
+
+  SmallVector<unsigned, 8> TotalCases(N);
+  for (unsigned i = 0; i < N; ++i) {
+    const APInt &Hi = Clusters[i].High->getValue();
+    const APInt &Lo = Clusters[i].Low->getValue();
+    TotalCases[i] = (Hi - Lo).getLimitedValue() + 1;
+    if (i != 0)
+      TotalCases[i] += TotalCases[i - 1];
+  }
+
+  const unsigned MinDensity =
+      OptForSize ? TL->getOptsizeJumpTableDensity() : TL->getJumpTableDensity();
+
+  unsigned JumpTableSize = (Clusters[N - 1].High->getValue() -
+                            Clusters[0].Low->getValue())
+                              .getLimitedValue(UINT_MAX - 1) + 1;
+  if (JumpTableSize <= MaxJumpTableSize &&
+    isDense(Clusters, TotalCases, 0, N - 1, MinDensity)) {
+      return Remaining;
+  }
+
+  SmallVector<unsigned, 8> MinPartitions(N);
+  SmallVector<unsigned, 8> LastElement(N);
+  SmallVector<unsigned, 8> PartitionsScore(N);
+  enum PartitionScores : unsigned {
+    NoTable = 0,
+    Table = 1,
+    FewCases = 1,
+    SingleCase = 2
+  };
+
+  MinPartitions[N - 1] = 1;
+  LastElement[N - 1] = N - 1;
+  PartitionsScore[N - 1] = PartitionScores::SingleCase;
+
+  for (int64_t i = N - 2; i >= 0; i--) {
+    MinPartitions[i] = MinPartitions[i + 1] + 1;
+    LastElement[i] = i;
+    PartitionsScore[i] = PartitionsScore[i + 1] + PartitionScores::SingleCase;
+
+    for (int64_t j = N - 1; j > i; j--) {
+      JumpTableSize = (Clusters[j].High->getValue() -
+           Clusters[i].Low->getValue())
+          .getLimitedValue(UINT_MAX - 1) + 1;
+      if (JumpTableSize <= MaxJumpTableSize &&
+          isDense(Clusters, TotalCases, i, j, MinDensity)) {
+        unsigned NumPartitions = 1 + (j == N - 1 ? 0 : MinPartitions[j + 1]);
+        unsigned Score = j == N - 1 ? 0 : PartitionsScore[j + 1];
+        int64_t NumEntries = j - i + 1;
+
+        if (NumEntries == 1)
+          Score += PartitionScores::SingleCase;
+        else if (NumEntries <= SmallNumberOfEntries)
+          Score += PartitionScores::FewCases;
+        else if (NumEntries >= MinJumpTableEntries)
+          Score += PartitionScores::Table;
+
+        if (NumPartitions < MinPartitions[i] ||
+            (NumPartitions == MinPartitions[i] && Score > PartitionsScore[i])) {
+          MinPartitions[i] = NumPartitions;
+          LastElement[i] = j;
+          PartitionsScore[i] = Score;
+        }
+      }
+    }
+  }
+
+  // We know the partitioning now.
+  // Gather all the cases which do not belong to partitions.
+  DstIndex = 0;
+  for (unsigned First = 0, Last; First < N; First = Last + 1) {
+    Last = LastElement[First];
+    unsigned NumClusters = Last - First + 1;
+    if (NumClusters < MinJumpTableEntries) {
+      for (unsigned I = First; I <= Last; ++I) {
+        Remaining.push_back(Clusters[I]);
+      }
+    }
+  }
+  return Remaining;
+}
+
+void SwitchAnalysis::analyze(Function &Fn) {
+  TL = TM ? TM->getSubtargetImpl(Fn)->getTargetLowering() : nullptr;
+  // TL = TM ? TM->getSubtargetImpl(*M.begin())->getTargetLowering() : nullptr;
+  unsigned MinJumpMapSize = 0;
+  if (TL) {
+    MinJumpMapSize = TL->getMinimumJumpMapEntries();
+    // If we are sure that we will not emit jump maps
+    // there is no point in continuing the analysis.
+    if (!(TL->isOperationLegalOrCustom(ISD::BR_JM, MVT::Other) ||
+        (TL->isOperationLegalOrCustom(ISD::BRIND, MVT::Other) &&
+         MinJumpMapSize > 0))) {
+      return;
+    }
+  }
+  if (MinJumpMapSize <= 0) {
+    return;
+  }
+  // DEBUG(dbgs() << "\n---- SwitchModuleAnalysis for "
+  // << M.getModuleIdentifier() << " ----\n");
+  DEBUG(dbgs() << "\n---- SwitchAnalysis for "
+               << Fn.getName() << " ----\n");
+  SmallVector<SwitchStatement, 4> Switches;
+  // for (auto& F : M) {
+    bool SizeOpt = Fn.optForSize();
+    for (auto& BB : Fn) {
+      for (auto& BI : BB) {
+        if (isa<SwitchInst>(BI)) {
+          SwitchInst &SI = cast<SwitchInst>(BI);
+          std::vector<CaseCluster> Remaining = JumpMapCases(SI, SizeOpt);
+          if (Remaining.empty()) {
+            DEBUG(dbgs() << "   | Found a full jump table candidate."
+                         << " Filtering out from further analysis.\n");
+            continue;
+          }
+          unsigned KeySize = 0;
+          unsigned CasesCount = 0;
+          for (auto& C : Remaining) {
+            for (APInt I = C.Low->getValue();;){
+              ++CasesCount;
+              KeySize = KeySize > I.getActiveBits() ? KeySize
+                                                    : I.getActiveBits();
+              if (I.eq(C.High->getValue())) break;
+              ++I;
+            }
+          }
+          if( CasesCount < MinJumpMapSize) {
+            DEBUG(dbgs() << "   | Found a potential jump map smaller"
+                         << " than minimal jump map (" << CasesCount << ")."
+                         << " Filtering out from further analysis.\n");
+            continue;
+          }
+
+          if (KeySize <= 8) KeySize = 8;
+          else if (KeySize <= 16) KeySize = 16;
+          else if (KeySize <= 32) KeySize = 32;
+          else if (KeySize <= 64) KeySize = 64;
+          else {
+            DEBUG(dbgs() << "   | Found unsupported switch type."
+                         << " Filtering out from further analysis.\n");
+            continue;
+          }
+
+          unsigned CondSize = (isa<ZExtInst>(SI.getCondition()) &&
+                               cast<ZExtInst>(*(SI.getCondition()))
+                                .getSrcTy()->getIntegerBitWidth() == KeySize)
+            ? KeySize
+            : SI.getCondition()->getType()->getIntegerBitWidth();
+
+          Switches.emplace_back (std::make_tuple(CondSize, KeySize,
+                                                 CasesCount));
+          std::string JMType = (CasesCount == SI.getNumCases()) ? "full"
+                                                                : "partial";
+          DEBUG(dbgs() << "   | Found a " << JMType << " jump map: CondSize:"
+                       << std::get<0>(Switches.back())
+                       << ", MaxKeySize: " << std::get<1>(Switches.back())
+                       << ", #Cases: " << std::get<2>(Switches.back()) << "\n");
+        }
+      }
+    }
+  // }
+  // Selecting appropriate jump map functions for switches types
+  // Find minimal jump map key size for each type
+
+  // JMFIXME: use better heuristics here, the heuristics here are just
+  // an example.
+  // JMFIXME: make more target hooks, it also should depend on
+  // speed-opt / size-opt choice
+  for (auto& S : Switches) {
+    unsigned c, k;
+    std::tie(c, k, std::ignore) = S;
+    if (Results.find(c) == Results.end() || std::get<1>(Results[c]) < k) {
+      Results[c] = std::make_tuple(c, k);
+    }
+  }
+  if (Results.find(16) != Results.end() && Results.find(8) != Results.end()) {
+    Results[8] = Results[16];
+  }
+  for (auto& R : Results) {
+    unsigned  c, k;
+    std::tie(c, k) = R.second;
+    DEBUG(dbgs() << "   Suggested jump map for type i"
+                 << R.first << ": i" << c << " -> i" << k << "\n");
+  }
+   DEBUG(dbgs() << "\n");
+}
+
+unsigned SwitchAnalysis::recommendedCondSize(unsigned cond) {
+  if (Results.find(cond) != Results.end()) {
+    return std::get<0>(Results[cond]);;
+  }
+  return 0;
+}
+
+unsigned SwitchAnalysis::recommendedKeySize(unsigned cond) {
+  if (Results.find(cond) != Results.end()) {
+    return std::get<1>(Results[cond]);
+  }
+  return 0;
+}
+
+void SwitchAnalysis::print(raw_ostream &OS) const {
+  if (Results.size() < 1) {
+    OS << "---- No jump map candidates found. ----\n";
+    return;
+  }
+  OS << "---- Suggested jump map types for switch condition type: ----\n";
+  for (auto& R : Results) {
+    unsigned  c, k;
+    std::tie(c, k) = R.second;
+    DEBUG(dbgs() << "   | i" << R.first << ": i" << c << " -> i" << k << "\n");
+  }
+}

lib/CodeGen/TargetLoweringBase.cpp

 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/CodeGen/Analysis.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineJumpMapInfo.h"
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/StackMaps.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/Mangler.h"
 #include "llvm/MC/MCAsmInfo.h"
static cl::opt<bool> JumpIsExpensiveOverride(
     "jump-is-expensive", cl::init(false),
     cl::desc("Do not create extra branches to split comparison logic."),
     cl::Hidden);
 
 static cl::opt<unsigned> MinimumJumpTableEntries
   ("min-jump-table-entries", cl::init(4), cl::Hidden,
    cl::desc("Set minimum number of entries to use a jump table."));
 
+static cl::opt<unsigned> MinimumJumpMapEntries
+  ("min-jump-map-entries", cl::init(6), cl::Hidden,
+   cl::desc("Set minimum number of entries to use a jump map."));
+
 static cl::opt<unsigned> MaximumJumpTableSize
   ("max-jump-table-size", cl::init(0), cl::Hidden,
    cl::desc("Set maximum size of jump tables; zero for no limit."));
 
 /// Minimum jump table density for normal functions.
 static cl::opt<unsigned>
     JumpTableDensity("jump-table-density", cl::init(10), cl::Hidden,
                      cl::desc("Minimum density for building a jump table in "
                               "a normal function"));
 
 /// Minimum jump table density for -Os or -Oz functions.
 static cl::opt<unsigned> OptsizeJumpTableDensity(
     "optsize-jump-table-density", cl::init(40), cl::Hidden,
     cl::desc("Minimum density for building a jump table in "
              "an optsize function"));
 
+static cl::opt<bool> JumpMapsEnabled
+  ("enable-jump-maps", cl::init(false),
+   cl::desc("Enable generation of jump maps"));
+
 // Although this default value is arbitrary, it is not random. It is assumed
 // that a condition that evaluates the same way by a higher percentage than this
 // is best represented as control flow. Therefore, the default value N should be
 // set such that the win from N% correct executions is greater than the loss
 // from (100 - N)% mispredicted executions for the majority of intended targets.
 static cl::opt<int> MinPercentageForPredictableBranch(
     "min-predictable-branch", cl::init(99),
     cl::desc("Minimum percentage (0-100) that a condition must be either true "
static void InitLibcallNames(const char **Names, const Triple &TT) {
   Names[RTLIB::ATOMIC_FETCH_XOR_8] = "__atomic_fetch_xor_8";
   Names[RTLIB::ATOMIC_FETCH_XOR_16] = "__atomic_fetch_xor_16";
   Names[RTLIB::ATOMIC_FETCH_NAND_1] = "__atomic_fetch_nand_1";
   Names[RTLIB::ATOMIC_FETCH_NAND_2] = "__atomic_fetch_nand_2";
   Names[RTLIB::ATOMIC_FETCH_NAND_4] = "__atomic_fetch_nand_4";
   Names[RTLIB::ATOMIC_FETCH_NAND_8] = "__atomic_fetch_nand_8";
   Names[RTLIB::ATOMIC_FETCH_NAND_16] = "__atomic_fetch_nand_16";
 
+  // JMFIXME
+  // Jump Maps library calls
+  Names[RTLIB::JUMPMAP_FIND_I8_I8] = "__jmfind_i8_i8";
+  Names[RTLIB::JUMPMAP_FIND_I16_I8] = "__jmfind_i16_i8";
+  Names[RTLIB::JUMPMAP_FIND_I16_I16] = "__jmfind_i16_i16";
+  Names[RTLIB::JUMPMAP_FIND_I32_I8] = "__jmfind_i32_i8";
+  Names[RTLIB::JUMPMAP_FIND_I32_I16] = "__jmfind_i32_i16";
+  Names[RTLIB::JUMPMAP_FIND_I32_I32] = "__jmfind_i32_i32";
+  Names[RTLIB::JUMPMAP_FIND_I64_I8] = "__jmfind_i64_i8";
+  Names[RTLIB::JUMPMAP_FIND_I64_I16] = "__jmfind_i64_i16";
+  Names[RTLIB::JUMPMAP_FIND_I64_I32] = "__jmfind_i64_i32";
+  Names[RTLIB::JUMPMAP_FIND_I64_I64] = "__jmfind_i64_i64";
+
   if (TT.isGNUEnvironment()) {
     Names[RTLIB::SINCOS_F32] = "sincosf";
     Names[RTLIB::SINCOS_F64] = "sincos";
     Names[RTLIB::SINCOS_F80] = "sincosl";
     Names[RTLIB::SINCOS_F128] = "sincosl";
     Names[RTLIB::SINCOS_PPCF128] = "sincosl";
   }
 

 Value *TargetLoweringBase::getSSPStackGuardCheck(const Module &M) const {
   return nullptr;
 }
 
 unsigned TargetLoweringBase::getMinimumJumpTableEntries() const {
   return MinimumJumpTableEntries;
 }
 
+unsigned TargetLoweringBase::getMinimumJumpMapEntries() const {
+  return MinimumJumpMapEntries;
+}
+
+void TargetLoweringBase::setMinimumJumpMapEntries(unsigned Val) {
+  MinimumJumpMapEntries = Val;
+}
+
 void TargetLoweringBase::setMinimumJumpTableEntries(unsigned Val) {
   MinimumJumpTableEntries = Val;
 }
 
 unsigned TargetLoweringBase::getMinimumJumpTableDensity(bool OptForSize) const {
   return OptForSize ? OptsizeJumpTableDensity : JumpTableDensity;
 }
 
 unsigned TargetLoweringBase::getMaximumJumpTableSize() const {
   return MaximumJumpTableSize;
 }
 
 void TargetLoweringBase::setMaximumJumpTableSize(unsigned Val) {
   MaximumJumpTableSize = Val;
 }
 
+unsigned TargetLoweringBase::getJumpTableDensity() const {
+  return JumpTableDensity;
+}
+
+void TargetLoweringBase::setJumpTableDensity(unsigned Val) {
+  JumpTableDensity = Val;
+}
+
+unsigned TargetLoweringBase::getOptsizeJumpTableDensity() const {
+  return OptsizeJumpTableDensity;
+}
+
+void TargetLoweringBase::setOptsizeJumpTableDensity(unsigned Val) {
+  OptsizeJumpTableDensity = Val;
+}
+
+void TargetLoweringBase::setJumpMapsEnabled(bool isEnabled) {
+  JumpMapsEnabled = isEnabled;
+}
+
+bool TargetLoweringBase::areJumpMapsEnabled() const {
+  return JumpMapsEnabled;
+}
+
 //===----------------------------------------------------------------------===//
 //  Reciprocal Estimates
 //===----------------------------------------------------------------------===//
 
 /// Get the reciprocal estimate attribute string for a function that will
 /// override the target defaults.
 static StringRef getRecipEstimateForFunc(MachineFunction &MF) {
   const Function *F = MF.getFunction();

lib/CodeGen/TargetPassConfig.cpp

 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/Passes.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/RegAllocRegistry.h"
 #include "llvm/CodeGen/RegisterUsageInfo.h"
+#include "llvm/CodeGen/SwitchAnalysis.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetMachine.h"

 }
 
 /// Add pass to prepare the LLVM IR for code generation. This should be done
 /// before exception handling preparation passes.
 void TargetPassConfig::addCodeGenPrepare() {
   if (getOptLevel() != CodeGenOpt::None && !DisableCGP)
     addPass(createCodeGenPreparePass(TM));
   addPass(createRewriteSymbolsPass());
+  // Analyze switch statements. The result of the analysis
+  // is used during SelectionDAG building.
+  // JMFIXME: It should be a module pass
+  if (getOptLevel() != CodeGenOpt::None)
+    addPass(createSwitchLegacyAnalysisPass(TM));
 }
 
 /// Add common passes that perform LLVM IR to IR transforms in preparation for
 /// instruction selection.
 void TargetPassConfig::addISelPrepare() {
   addPreISel();
 
   // Force codegen to run according to the callgraph.
   if (requiresCodeGenSCCOrder())
     addPass(new DummyCGSCCPass);
 
   // Add both the safe stack and the stack protection passes: each of them will
   // only protect functions that have corresponding attributes.
   addPass(createSafeStackPass(TM));
   addPass(createStackProtectorPass(TM));
 
   if (PrintISelInput)
     addPass(createPrintFunctionPass(
         dbgs(), "\n\n*** Final LLVM Code input to ISel ***\n"));
 
   // All passes which modify the LLVM IR are now complete; run the verifier
   // to ensure that the IR is valid.
   if (!DisableVerify)
     addPass(createVerifierPass());
+
 }
 
 /// Add the complete set of target-independent postISel code generator passes.
 ///
 /// This can be read as the standard order of major LLVM CodeGen stages. Stages
 /// with nontrivial configuration or multiple passes are broken out below in
 /// add%Stage routines.
 ///

lib/Target/ARM/ARMExpandPseudoInsts.cpp

case MachineOperand::MO_FPImmediate:
     return false;
   case MachineOperand::MO_MachineBasicBlock:
     return true;
   case MachineOperand::MO_FrameIndex:
     return false;
   case MachineOperand::MO_ConstantPoolIndex:
   case MachineOperand::MO_TargetIndex:
   case MachineOperand::MO_JumpTableIndex:
+  case MachineOperand::MO_JumpMapIndex:
   case MachineOperand::MO_ExternalSymbol:
   case MachineOperand::MO_GlobalAddress:
   case MachineOperand::MO_BlockAddress:
     return true;
   case MachineOperand::MO_RegisterMask:
   case MachineOperand::MO_RegisterLiveOut:
     return false;
   case MachineOperand::MO_Metadata:

lib/Target/TargetLoweringObjectFile.cpp

 MCSection *TargetLoweringObjectFile::getSectionForJumpTable(
     const Function &F, const TargetMachine &TM) const {
   unsigned Align = 0;
   return getSectionForConstant(F.getParent()->getDataLayout(),
                                SectionKind::getReadOnly(), /*C=*/nullptr,
                                Align);
 }
 
+MCSection *TargetLoweringObjectFile::getSectionForJumpMap(
+    const Function &F, const TargetMachine &TM) const {
+  unsigned Align = 0;
+  return getSectionForConstant(F.getParent()->getDataLayout(),
+                               SectionKind::getReadOnly(), /*C=*/nullptr,
+                               Align);
+}
+
 bool TargetLoweringObjectFile::shouldPutJumpTableInFunctionSection(
     bool UsesLabelDifference, const Function &F) const {
   // In PIC mode, we need to emit the jump table to the same section as the
   // function body itself, otherwise the label differences won't make sense.
   // FIXME: Need a better predicate for this: what about custom entries?
   if (UsesLabelDifference)
     return true;
 

lib/Target/X86/X86AsmPrinter.cpp

bool X86AsmPrinter::runOnMachineFunction(MachineFunction &MF) {
   // Emit the XRay table for this function.
   emitXRayTable();
 
   // We didn't modify anything.
   return false;
 }
 
 /// printSymbolOperand - Print a raw symbol reference operand.  This handles
-/// jump tables, constant pools, global address and external symbols, all of
-/// which print to a label with various suffixes for relocation types etc.
+/// jump tables, jump maps, constant pools, global address and external symbols,
+/// all of which print to a label with various suffixes for relocation types
+/// etc.
 static void printSymbolOperand(X86AsmPrinter &P, const MachineOperand &MO,
                                raw_ostream &O) {
   switch (MO.getType()) {
   default: llvm_unreachable("unknown symbol type!");
   case MachineOperand::MO_ConstantPoolIndex:
     P.GetCPISymbol(MO.getIndex())->print(O, P.MAI);
     P.printOffset(MO.getOffset(), O);
     break;
case 'a': // This is an address.  Currently only 'i' and 'r' are expected.
       switch (MO.getType()) {
       default:
         return true;
       case MachineOperand::MO_Immediate:
         O << MO.getImm();
         return false;
       case MachineOperand::MO_ConstantPoolIndex:
       case MachineOperand::MO_JumpTableIndex:
+      case MachineOperand::MO_JumpMapIndex:
       case MachineOperand::MO_ExternalSymbol:
         llvm_unreachable("unexpected operand type!");
       case MachineOperand::MO_GlobalAddress:
         printSymbolOperand(*this, MO, O);
         if (Subtarget->isPICStyleRIPRel())
           O << "(%rip)";
         return false;
       case MachineOperand::MO_Register:
         O << '(';
         printOperand(*this, MI, OpNo, O);
         O << ')';
         return false;
       }
 
     case 'c': // Don't print "$" before a global var name or constant.
       switch (MO.getType()) {
       default:
         printOperand(*this, MI, OpNo, O);
         break;
       case MachineOperand::MO_Immediate:
         O << MO.getImm();
         break;
       case MachineOperand::MO_ConstantPoolIndex:
       case MachineOperand::MO_JumpTableIndex:
+      case MachineOperand::MO_JumpMapIndex:
       case MachineOperand::MO_ExternalSymbol:
         llvm_unreachable("unexpected operand type!");
       case MachineOperand::MO_GlobalAddress:
         printSymbolOperand(*this, MO, O);
         break;
       }
       return false;
 

lib/Target/X86/X86ISelDAGToDAG.cpp

struct X86ISelAddressMode {
     int32_t Disp;
     SDValue Segment;
     const GlobalValue *GV;
     const Constant *CP;
     const BlockAddress *BlockAddr;
     const char *ES;
     MCSymbol *MCSym;
     int JT;
+    int JM;
     unsigned Align;    // CP alignment.
     unsigned char SymbolFlags;  // X86II::MO_*
 
     X86ISelAddressMode()
         : BaseType(RegBase), Base_FrameIndex(0), Scale(1), IndexReg(), Disp(0),
           Segment(), GV(nullptr), CP(nullptr), BlockAddr(nullptr), ES(nullptr),
-          MCSym(nullptr), JT(-1), Align(0), SymbolFlags(X86II::MO_NO_FLAG) {}
+          MCSym(nullptr), JT(-1), JM(-1), Align(0), SymbolFlags(X86II::MO_NO_FLAG) {}
 
     bool hasSymbolicDisplacement() const {
       return GV != nullptr || CP != nullptr || ES != nullptr ||
-             MCSym != nullptr || JT != -1 || BlockAddr != nullptr;
+             MCSym != nullptr || JT != -1 || JM != -1 || BlockAddr != nullptr;
     }
 
     bool hasBaseOrIndexReg() const {
       return BaseType == FrameIndexBase ||
              IndexReg.getNode() != nullptr || Base_Reg.getNode() != nullptr;
     }
 
     /// Return true if this addressing mode is already RIP-relative.
void dump() {
       else
         dbgs() << "nul";
       dbgs() << " MCSym ";
       if (MCSym)
         dbgs() << MCSym;
       else
         dbgs() << "nul";
       dbgs() << " JT" << JT << " Align" << Align << '\n';
+      dbgs() << " JM" << JM << " Align" << Align << '\n';
     }
 #endif
   };
 }
 
 namespace {
   //===--------------------------------------------------------------------===//
   /// ISel - X86-specific code to select X86 machine instructions for
inline void getAddressOperands(X86ISelAddressMode &AM, const SDLoc &DL,
         Disp = CurDAG->getTargetExternalSymbol(AM.ES, MVT::i32, AM.SymbolFlags);
       } else if (AM.MCSym) {
         assert(!AM.Disp && "Non-zero displacement is ignored with MCSym.");
         assert(AM.SymbolFlags == 0 && "oo");
         Disp = CurDAG->getMCSymbol(AM.MCSym, MVT::i32);
       } else if (AM.JT != -1) {
         assert(!AM.Disp && "Non-zero displacement is ignored with JT.");
         Disp = CurDAG->getTargetJumpTable(AM.JT, MVT::i32, AM.SymbolFlags);
+      } else if (AM.JM != -1) {
+        assert(!AM.Disp && "Non-zero displacement is ignored with JM.");
+        Disp = CurDAG->getTargetJumpMap(AM.JM, MVT::i32, AM.SymbolFlags);
       } else if (AM.BlockAddr)
         Disp = CurDAG->getTargetBlockAddress(AM.BlockAddr, MVT::i32, AM.Disp,
                                              AM.SymbolFlags);
       else
         Disp = CurDAG->getTargetConstant(AM.Disp, DL, MVT::i32);
 
       if (AM.Segment.getNode())
         Segment = AM.Segment;
if (Subtarget->is64Bit() && N.getOpcode() == X86ISD::WrapperRIP &&
     } else if (ExternalSymbolSDNode *S = dyn_cast<ExternalSymbolSDNode>(N0)) {
       AM.ES = S->getSymbol();
       AM.SymbolFlags = S->getTargetFlags();
     } else if (auto *S = dyn_cast<MCSymbolSDNode>(N0)) {
       AM.MCSym = S->getMCSymbol();
     } else if (JumpTableSDNode *J = dyn_cast<JumpTableSDNode>(N0)) {
       AM.JT = J->getIndex();
       AM.SymbolFlags = J->getTargetFlags();
+    } else if (JumpMapSDNode *J = dyn_cast<JumpMapSDNode>(N0)) {
+      AM.JM = J->getIndex();
+      AM.SymbolFlags = J->getTargetFlags();
     } else if (BlockAddressSDNode *BA = dyn_cast<BlockAddressSDNode>(N0)) {
       X86ISelAddressMode Backup = AM;
       AM.BlockAddr = BA->getBlockAddress();
       AM.SymbolFlags = BA->getTargetFlags();
       if (foldOffsetIntoAddress(BA->getOffset(), AM)) {
         AM = Backup;
         return true;
       }
if (!Subtarget->is64Bit() ||
     } else if (ExternalSymbolSDNode *S = dyn_cast<ExternalSymbolSDNode>(N0)) {
       AM.ES = S->getSymbol();
       AM.SymbolFlags = S->getTargetFlags();
     } else if (auto *S = dyn_cast<MCSymbolSDNode>(N0)) {
       AM.MCSym = S->getMCSymbol();
     } else if (JumpTableSDNode *J = dyn_cast<JumpTableSDNode>(N0)) {
       AM.JT = J->getIndex();
       AM.SymbolFlags = J->getTargetFlags();
+    } else if (JumpMapSDNode *J = dyn_cast<JumpMapSDNode>(N0)) {
+      AM.JM = J->getIndex();
+      AM.SymbolFlags = J->getTargetFlags();
     } else if (BlockAddressSDNode *BA = dyn_cast<BlockAddressSDNode>(N0)) {
       AM.BlockAddr = BA->getBlockAddress();
       AM.Disp += BA->getOffset();
       AM.SymbolFlags = BA->getTargetFlags();
     } else
       llvm_unreachable("Unhandled symbol reference node.");
     return false;
   }
bool X86DAGToDAGISel::matchAddressRecursively(SDValue N, X86ISelAddressMode &AM,
 
   // If this is already a %rip relative address, we can only merge immediates
   // into it.  Instead of handling this in every case, we handle it here.
   // RIP relative addressing: %rip + 32-bit displacement!
   if (AM.isRIPRelative()) {
     // FIXME: JumpTable and ExternalSymbol address currently don't like
     // displacements.  It isn't very important, but this should be fixed for
     // consistency.
-    if (!(AM.ES || AM.MCSym) && AM.JT != -1)
+    if (!(AM.ES || AM.MCSym) && AM.JT != -1) // JMFIXME ? What's with JMs?
       return true;
 
     if (ConstantSDNode *Cst = dyn_cast<ConstantSDNode>(N))
       if (!foldOffsetIntoAddress(Cst->getSExtValue(), AM))
         return false;
     return true;
   }
 

lib/Target/X86/X86ISelLowering.h

enum NodeType : unsigned {
 
       /// Repeat move, corresponds to X86::REP_MOVSx.
       REP_MOVS,
 
       /// On Darwin, this node represents the result of the popl
       /// at function entry, used for PIC code.
       GlobalBaseReg,
 
-      /// A wrapper node for TargetConstantPool, TargetJumpTable,
+      /// A wrapper node for TargetConstantPool, TargetJumpTable, TargetJumpMap,
       /// TargetExternalSymbol, TargetGlobalAddress, TargetGlobalTLSAddress,
       /// MCSymbol and TargetBlockAddress.
       Wrapper,
 
       /// Special wrapper used under X86-64 PIC mode for RIP
       /// relative displacements.
       WrapperRIP,
 
public:
     const MCExpr *
     LowerCustomJumpTableEntry(const MachineJumpTableInfo *MJTI,
                               const MachineBasicBlock *MBB, unsigned uid,
                               MCContext &Ctx) const override;
 
     /// Returns relocation base for the given PIC jumptable.
     SDValue getPICJumpTableRelocBase(SDValue Table,
                                      SelectionDAG &DAG) const override;
+
     const MCExpr *
     getPICJumpTableRelocBaseExpr(const MachineFunction *MF,
                                  unsigned JTI, MCContext &Ctx) const override;
 
     /// Return the desired alignment for ByVal aggregate
     /// function arguments in the caller parameter area. For X86, aggregates
     /// that contains are placed at 16-byte boundaries while the rest are at
     /// 4-byte boundaries.
private:
     SDValue LowerFP_TO_INT(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerToBT(SDValue And, ISD::CondCode CC, const SDLoc &dl,
                       SelectionDAG &DAG) const;
     SDValue LowerSETCC(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerSETCCE(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerSELECT(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerBRCOND(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerJumpTable(SDValue Op, SelectionDAG &DAG) const;
+    SDValue LowerJumpMap(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerDYNAMIC_STACKALLOC(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerVASTART(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerVAARG(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerRETURNADDR(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerADDROFRETURNADDR(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerFRAMEADDR(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerFRAME_TO_ARGS_OFFSET(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerEH_RETURN(SDValue Op, SelectionDAG &DAG) const;

lib/Target/X86/X86ISelLowering.cpp

for (auto VT : { MVT::i8, MVT::i16, MVT::i32, MVT::i64 }) {
     // Add/Sub overflow ops with MVT::Glues are lowered to EFLAGS dependences.
     setOperationAction(ISD::ADDC, VT, Custom);
     setOperationAction(ISD::ADDE, VT, Custom);
     setOperationAction(ISD::SUBC, VT, Custom);
     setOperationAction(ISD::SUBE, VT, Custom);
   }
 
   setOperationAction(ISD::BR_JT            , MVT::Other, Expand);
+  setOperationAction(ISD::BR_JM            , MVT::Other, Expand);
   setOperationAction(ISD::BRCOND           , MVT::Other, Custom);
   for (auto VT : { MVT::f32, MVT::f64, MVT::f80, MVT::f128,
                    MVT::i8,  MVT::i16, MVT::i32, MVT::i64 }) {
     setOperationAction(ISD::BR_CC,     VT, Expand);
     setOperationAction(ISD::SELECT_CC, VT, Expand);
   }
   if (Subtarget.is64Bit())
     setOperationAction(ISD::SIGN_EXTEND_INREG, MVT::i32, Legal);
X86TargetLowering::X86TargetLowering(const X86TargetMachine &TM,
   if (TM.Options.ExceptionModel == ExceptionHandling::SjLj)
     setLibcallName(RTLIB::UNWIND_RESUME, "_Unwind_SjLj_Resume");
 
   // Darwin ABI issue.
   for (auto VT : { MVT::i32, MVT::i64 }) {
     if (VT == MVT::i64 && !Subtarget.is64Bit())
       continue;
     setOperationAction(ISD::ConstantPool    , VT, Custom);
+    setOperationAction(ISD::JumpMap         , VT, Custom);
     setOperationAction(ISD::JumpTable       , VT, Custom);
     setOperationAction(ISD::GlobalAddress   , VT, Custom);
     setOperationAction(ISD::GlobalTLSAddress, VT, Custom);
     setOperationAction(ISD::ExternalSymbol  , VT, Custom);
     setOperationAction(ISD::BlockAddress    , VT, Custom);
   }
 
   // 64-bit shl, sra, srl (iff 32-bit x86)
unsigned X86TargetLowering::getGlobalWrapperKind(const GlobalValue *GV) const {
   CodeModel::Model M = getTargetMachine().getCodeModel();
   if (Subtarget.isPICStyleRIPRel() &&
       (M == CodeModel::Small || M == CodeModel::Kernel))
     return X86ISD::WrapperRIP;
 
   return X86ISD::Wrapper;
 }
 
-// ConstantPool, JumpTable, GlobalAddress, and ExternalSymbol are lowered as
-// their target counterpart wrapped in the X86ISD::Wrapper node. Suppose N is
-// one of the above mentioned nodes. It has to be wrapped because otherwise
-// Select(N) returns N. So the raw TargetGlobalAddress nodes, etc. can only
-// be used to form addressing mode. These wrapped nodes will be selected
+// ConstantPool, JumpTable, JumpMap, GlobalAddress, and ExternalSymbol are
+// lowered as their target counterpart wrapped in the X86ISD::Wrapper node.
+// Suppose N is one of the above mentioned nodes. It has to be wrapped because
+// otherwise Select(N) returns N. So the raw TargetGlobalAddress nodes, etc. can
+// only be used to form addressing mode. These wrapped nodes will be selected
 // into MOV32ri.
 SDValue
 X86TargetLowering::LowerConstantPool(SDValue Op, SelectionDAG &DAG) const {
   ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(Op);
 
   // In PIC mode (unless we're in RIPRel PIC mode) we add an offset to the
   // global base reg.
   unsigned char OpFlag = Subtarget.classifyLocalReference(nullptr);
SDValue X86TargetLowering::LowerJumpTable(SDValue Op, SelectionDAG &DAG) const {
   if (OpFlag)
     Result =
         DAG.getNode(ISD::ADD, DL, PtrVT,
                     DAG.getNode(X86ISD::GlobalBaseReg, SDLoc(), PtrVT), Result);
 
   return Result;
 }
 
+SDValue X86TargetLowering::LowerJumpMap(SDValue Op, SelectionDAG &DAG) const {
+  auto PtrVT = getPointerTy(DAG.getDataLayout());
+  JumpMapSDNode *JM = cast<JumpMapSDNode>(Op);
+
+  // JMFIXME : handle relocation
+
+  unsigned char OpFlag = Subtarget.classifyLocalReference(nullptr);
+  SDValue Result = DAG.getTargetJumpMap(JM->getIndex(), PtrVT, OpFlag);
+  SDLoc DL(JM);
+
+  Result = DAG.getNode(getGlobalWrapperKind(), DL, PtrVT, Result);
+
+  return Result;
+}
+
 SDValue
 X86TargetLowering::LowerExternalSymbol(SDValue Op, SelectionDAG &DAG) const {
   const char *Sym = cast<ExternalSymbolSDNode>(Op)->getSymbol();
 
   // In PIC mode (unless we're in RIPRel PIC mode) we add an offset to the
   // global base reg.
   const Module *Mod = DAG.getMachineFunction().getFunction()->getParent();
   unsigned char OpFlag = Subtarget.classifyGlobalReference(nullptr, *Mod);
SDValue X86TargetLowering::LowerOperation(SDValue Op, SelectionDAG &DAG) const {
   case ISD::FNEG:               return LowerFABSorFNEG(Op, DAG);
   case ISD::FCOPYSIGN:          return LowerFCOPYSIGN(Op, DAG);
   case ISD::FGETSIGN:           return LowerFGETSIGN(Op, DAG);
   case ISD::SETCC:              return LowerSETCC(Op, DAG);
   case ISD::SETCCE:             return LowerSETCCE(Op, DAG);
   case ISD::SELECT:             return LowerSELECT(Op, DAG);
   case ISD::BRCOND:             return LowerBRCOND(Op, DAG);
   case ISD::JumpTable:          return LowerJumpTable(Op, DAG);
+  case ISD::JumpMap:            return LowerJumpMap(Op, DAG);
   case ISD::VASTART:            return LowerVASTART(Op, DAG);
   case ISD::VAARG:              return LowerVAARG(Op, DAG);
   case ISD::VACOPY:             return LowerVACOPY(Op, Subtarget, DAG);
   case ISD::INTRINSIC_WO_CHAIN: return LowerINTRINSIC_WO_CHAIN(Op, Subtarget, DAG);
   case ISD::INTRINSIC_VOID:
   case ISD::INTRINSIC_W_CHAIN:  return LowerINTRINSIC_W_CHAIN(Op, Subtarget, DAG);
   case ISD::RETURNADDR:         return LowerRETURNADDR(Op, DAG);
   case ISD::ADDROFRETURNADDR:   return LowerADDROFRETURNADDR(Op, DAG);

lib/Target/X86/X86InstrCompiler.td

 
 // In kernel code model, we can get the address of a label
 // into a register with 'movq'.  FIXME: This is a hack, the 'imm' predicate of
 // the MOV64ri32 should accept these.
 def : Pat<(i64 (X86Wrapper tconstpool  :$dst)),
           (MOV64ri32 tconstpool  :$dst)>, Requires<[KernelCode]>;
 def : Pat<(i64 (X86Wrapper tjumptable  :$dst)),
           (MOV64ri32 tjumptable  :$dst)>, Requires<[KernelCode]>;
+def : Pat<(i64 (X86Wrapper tjumpmap  :$dst)),
+          (MOV64ri32 tjumpmap  :$dst)>, Requires<[KernelCode]>;
 def : Pat<(i64 (X86Wrapper tglobaladdr :$dst)),
           (MOV64ri32 tglobaladdr :$dst)>, Requires<[KernelCode]>;
 def : Pat<(i64 (X86Wrapper texternalsym:$dst)),
           (MOV64ri32 texternalsym:$dst)>, Requires<[KernelCode]>;
 def : Pat<(i64 (X86Wrapper mcsym:$dst)),
           (MOV64ri32 mcsym:$dst)>, Requires<[KernelCode]>;
 def : Pat<(i64 (X86Wrapper tblockaddress:$dst)),
           (MOV64ri32 tblockaddress:$dst)>, Requires<[KernelCode]>;
 
 // If we have small model and -static mode, it is safe to store global addresses
 // directly as immediates.  FIXME: This is really a hack, the 'imm' predicate
 // for MOV64mi32 should handle this sort of thing.
 def : Pat<(store (i64 (X86Wrapper tconstpool:$src)), addr:$dst),
           (MOV64mi32 addr:$dst, tconstpool:$src)>,
           Requires<[NearData, IsNotPIC]>;
 def : Pat<(store (i64 (X86Wrapper tjumptable:$src)), addr:$dst),
           (MOV64mi32 addr:$dst, tjumptable:$src)>,
           Requires<[NearData, IsNotPIC]>;
+def : Pat<(store (i64 (X86Wrapper tjumpmap:$src)), addr:$dst),
+          (MOV64mi32 addr:$dst, tjumpmap:$src)>,
+          Requires<[NearData, IsNotPIC]>;
 def : Pat<(store (i64 (X86Wrapper tglobaladdr:$src)), addr:$dst),
           (MOV64mi32 addr:$dst, tglobaladdr:$src)>,
           Requires<[NearData, IsNotPIC]>;
 def : Pat<(store (i64 (X86Wrapper texternalsym:$src)), addr:$dst),
           (MOV64mi32 addr:$dst, texternalsym:$src)>,
           Requires<[NearData, IsNotPIC]>;
 def : Pat<(store (i64 (X86Wrapper mcsym:$src)), addr:$dst),
           (MOV64mi32 addr:$dst, mcsym:$src)>,

lib/Target/X86/X86MCInstLower.cpp

if (MO.isJTI()) {
       Expr = MCSymbolRefExpr::create(Label, Ctx);
     }
     break;
   }
 
   if (!Expr)
     Expr = MCSymbolRefExpr::create(Sym, RefKind, Ctx);
 
-  if (!MO.isJTI() && !MO.isMBB() && MO.getOffset())
+  if (!MO.isJTI() && !MO.isJMI() && !MO.isMBB() && MO.getOffset())
     Expr = MCBinaryExpr::createAdd(Expr,
                                    MCConstantExpr::create(MO.getOffset(), Ctx),
                                    Ctx);
   return MCOperand::createExpr(Expr);
 }
 
 
 /// \brief Simplify FOO $imm, %{al,ax,eax,rax} to FOO $imm, for instruction with
X86MCInstLower::LowerMachineOperand(const MachineInstr *MI,
   case MachineOperand::MO_MachineBasicBlock:
   case MachineOperand::MO_GlobalAddress:
   case MachineOperand::MO_ExternalSymbol:
     return LowerSymbolOperand(MO, GetSymbolFromOperand(MO));
   case MachineOperand::MO_MCSymbol:
     return LowerSymbolOperand(MO, MO.getMCSymbol());
   case MachineOperand::MO_JumpTableIndex:
     return LowerSymbolOperand(MO, AsmPrinter.GetJTISymbol(MO.getIndex()));
+  case MachineOperand::MO_JumpMapIndex:
+    return LowerSymbolOperand(MO, AsmPrinter.GetJMISymbol(MO.getIndex()));
   case MachineOperand::MO_ConstantPoolIndex:
     return LowerSymbolOperand(MO, AsmPrinter.GetCPISymbol(MO.getIndex()));
   case MachineOperand::MO_BlockAddress:
     return LowerSymbolOperand(
         MO, AsmPrinter.GetBlockAddressSymbol(MO.getBlockAddress()));
   case MachineOperand::MO_RegisterMask:
     // Ignore call clobbers.
     return None;

utils/TableGen/CodeGenDAGPatterns.cpp

if (Operator->isSubClassOf("Intrinsic"))
       error("Cannot use '" + Operator->getName() + "' in an output pattern!");
 
     if (Operator->isSubClassOf("SDNode") &&
         Operator->getName() != "imm" &&
         Operator->getName() != "fpimm" &&
         Operator->getName() != "tglobaltlsaddr" &&
         Operator->getName() != "tconstpool" &&
         Operator->getName() != "tjumptable" &&
+        Operator->getName() != "tjumpmap" &&
         Operator->getName() != "tframeindex" &&
         Operator->getName() != "texternalsym" &&
         Operator->getName() != "tblockaddress" &&
         Operator->getName() != "tglobaladdr" &&
         Operator->getName() != "bb" &&
         Operator->getName() != "vt" &&
         Operator->getName() != "mcsym")
       error("Cannot use '" + Operator->getName() + "' in an output pattern!");