Index: include/llvm/CodeGen/AsmPrinter.h =================================================================== --- include/llvm/CodeGen/AsmPrinter.h +++ include/llvm/CodeGen/AsmPrinter.h @@ -50,6 +50,7 @@ class MachineConstantPoolValue; class MachineFunction; class MachineInstr; +class MachineJumpMapInfo; class MachineJumpTableInfo; class MachineLoopInfo; class MachineModuleInfo; @@ -303,6 +304,11 @@ /// 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. /// @@ -418,6 +424,9 @@ /// 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; Index: include/llvm/CodeGen/FunctionLoweringInfo.h =================================================================== --- include/llvm/CodeGen/FunctionLoweringInfo.h +++ include/llvm/CodeGen/FunctionLoweringInfo.h @@ -43,6 +43,7 @@ class MachineModuleInfo; class MachineRegisterInfo; class SelectionDAG; +class SwitchAnalysis; class MVT; class TargetLowering; class Value; @@ -58,6 +59,7 @@ const TargetLowering *TLI; MachineRegisterInfo *RegInfo; BranchProbabilityInfo *BPI; + SwitchAnalysis *SWAN; /// CanLowerReturn - true iff the function's return value can be lowered to /// registers. bool CanLowerReturn; Index: include/llvm/CodeGen/ISDOpcodes.h =================================================================== --- include/llvm/CodeGen/ISDOpcodes.h +++ include/llvm/CodeGen/ISDOpcodes.h @@ -60,7 +60,7 @@ 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, @@ -132,6 +132,7 @@ TargetGlobalTLSAddress, TargetFrameIndex, TargetJumpTable, + TargetJumpMap, TargetConstantPool, TargetExternalSymbol, TargetBlockAddress, @@ -585,6 +586,11 @@ /// 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 Index: include/llvm/CodeGen/MachineFunction.h =================================================================== --- include/llvm/CodeGen/MachineFunction.h +++ include/llvm/CodeGen/MachineFunction.h @@ -41,6 +41,7 @@ class MachineRegisterInfo; class MachineFrameInfo; class MachineConstantPool; +class MachineJumpMapInfo; class MachineJumpTableInfo; class MachineModuleInfo; class MCContext; @@ -214,6 +215,9 @@ // 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; @@ -389,6 +393,17 @@ 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 @@ -702,6 +717,12 @@ // 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. Index: include/llvm/CodeGen/MachineInstrBuilder.h =================================================================== --- include/llvm/CodeGen/MachineInstrBuilder.h +++ include/llvm/CodeGen/MachineInstrBuilder.h @@ -151,6 +151,12 @@ 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)); Index: include/llvm/CodeGen/MachineJumpMapInfo.h =================================================================== --- /dev/null +++ include/llvm/CodeGen/MachineJumpMapInfo.h @@ -0,0 +1,143 @@ +//===-- 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 +#include +#include + +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 MBBs; + + /// Size of the key + unsigned KeySize; + + explicit MachineJumpMapEntry(std::map &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 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 &DestBBs, + MachineBasicBlock *Default, unsigned KeySize); + + /// isEmpty - Return true if there are no jump maps. + bool isEmpty() const { return JumpMaps.empty(); } + + const std::vector &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 Index: include/llvm/CodeGen/MachineMemOperand.h =================================================================== --- include/llvm/CodeGen/MachineMemOperand.h +++ include/llvm/CodeGen/MachineMemOperand.h @@ -73,6 +73,9 @@ /// 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); Index: include/llvm/CodeGen/MachineOperand.h =================================================================== --- include/llvm/CodeGen/MachineOperand.h +++ include/llvm/CodeGen/MachineOperand.h @@ -54,6 +54,7 @@ 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 @@ -251,6 +252,8 @@ 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. @@ -438,7 +441,7 @@ } int getIndex() const { - assert((isFI() || isCPI() || isTargetIndex() || isJTI()) && + assert((isFI() || isCPI() || isTargetIndex() || isJTI() || isJMI()) && "Wrong MachineOperand accessor"); return Contents.OffsetedInfo.Val.Index; } @@ -544,7 +547,7 @@ } void setIndex(int Idx) { - assert((isFI() || isCPI() || isTargetIndex() || isJTI()) && + assert((isFI() || isCPI() || isTargetIndex() || isJTI() || isJMI()) && "Wrong MachineOperand mutator"); Contents.OffsetedInfo.Val.Index = Idx; } @@ -679,6 +682,13 @@ 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); Index: include/llvm/CodeGen/Passes.h =================================================================== --- include/llvm/CodeGen/Passes.h +++ include/llvm/CodeGen/Passes.h @@ -351,6 +351,10 @@ /// 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. /// Index: include/llvm/CodeGen/PseudoSourceValue.h =================================================================== --- include/llvm/CodeGen/PseudoSourceValue.h +++ include/llvm/CodeGen/PseudoSourceValue.h @@ -38,6 +38,7 @@ enum PSVKind { Stack, GOT, + JumpMap, JumpTable, ConstantPool, FixedStack, @@ -67,6 +68,7 @@ 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; @@ -149,7 +151,8 @@ /// Manages creation of pseudo source values. class PseudoSourceValueManager { - const PseudoSourceValue StackPSV, GOTPSV, JumpTablePSV, ConstantPoolPSV; + const PseudoSourceValue StackPSV, GOTPSV, JumpMapPSV, + JumpTablePSV, ConstantPoolPSV; std::map> FSValues; StringMap> ExternalCallEntries; @@ -177,6 +180,10 @@ /// 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); Index: include/llvm/CodeGen/RuntimeLibcalls.h =================================================================== --- include/llvm/CodeGen/RuntimeLibcalls.h +++ include/llvm/CodeGen/RuntimeLibcalls.h @@ -480,6 +480,19 @@ // 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 }; Index: include/llvm/CodeGen/SelectionDAG.h =================================================================== --- include/llvm/CodeGen/SelectionDAG.h +++ include/llvm/CodeGen/SelectionDAG.h @@ -554,6 +554,11 @@ 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); Index: include/llvm/CodeGen/SelectionDAGNodes.h =================================================================== --- include/llvm/CodeGen/SelectionDAGNodes.h +++ include/llvm/CodeGen/SelectionDAGNodes.h @@ -1552,6 +1552,27 @@ } }; +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; Index: include/llvm/CodeGen/SwitchAnalysis.h =================================================================== --- /dev/null +++ include/llvm/CodeGen/SwitchAnalysis.h @@ -0,0 +1,112 @@ +//===--------- 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 +#include +#include + +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 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> 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 &Clusters, + const SmallVectorImpl &TotalCases, + unsigned First, unsigned Last, + unsigned Density) const; + std::vector 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 Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -349,6 +349,7 @@ void initializeStripNonLineTableDebugInfoPass(PassRegistry&); void initializeStripSymbolsPass(PassRegistry&); void initializeStructurizeCFGPass(PassRegistry&); +void initializeSwitchLegacyAnalysisPass(PassRegistry&); void initializeTailCallElimPass(PassRegistry&); void initializeTailDuplicatePassPass(PassRegistry&); void initializeTargetLibraryInfoWrapperPassPass(PassRegistry&); Index: include/llvm/Target/TargetLowering.h =================================================================== --- include/llvm/Target/TargetLowering.h +++ include/llvm/Target/TargetLowering.h @@ -73,6 +73,7 @@ class MachineBasicBlock; class MachineFunction; class MachineInstr; +class MachineJumpMapInfo; class MachineJumpTableInfo; class MachineLoop; class MachineRegisterInfo; @@ -784,6 +785,18 @@ 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 { @@ -1214,6 +1227,13 @@ 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; @@ -1224,6 +1244,15 @@ /// 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(); } @@ -1570,6 +1599,13 @@ 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); @@ -1577,6 +1613,15 @@ /// 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) { @@ -2410,6 +2455,10 @@ 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; Index: include/llvm/Target/TargetLoweringObjectFile.h =================================================================== --- include/llvm/Target/TargetLoweringObjectFile.h +++ include/llvm/Target/TargetLoweringObjectFile.h @@ -111,6 +111,8 @@ 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. Index: include/llvm/Target/TargetSelectionDAG.td =================================================================== --- include/llvm/Target/TargetSelectionDAG.td +++ include/llvm/Target/TargetSelectionDAG.td @@ -352,6 +352,10 @@ "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, [], Index: jmdev/jmfind.c =================================================================== --- /dev/null +++ jmdev/jmfind.c @@ -0,0 +1,32 @@ +#include + +#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) Index: lib/CodeGen/AsmPrinter/AsmPrinter.cpp =================================================================== --- lib/CodeGen/AsmPrinter/AsmPrinter.cpp +++ lib/CodeGen/AsmPrinter/AsmPrinter.cpp @@ -41,6 +41,7 @@ #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" @@ -1100,6 +1101,9 @@ // 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, @@ -1648,6 +1652,80 @@ 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 &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 &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. @@ -2497,6 +2575,11 @@ 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); @@ -2697,7 +2780,7 @@ // 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; Index: lib/CodeGen/BranchFolding.cpp =================================================================== --- lib/CodeGen/BranchFolding.cpp +++ lib/CodeGen/BranchFolding.cpp @@ -25,6 +25,7 @@ #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" @@ -188,21 +189,27 @@ 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; - - // Remember that this JT is live. - JTIsLive.set(Op.getIndex()); + 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()); + } } } @@ -214,6 +221,14 @@ 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; } @@ -244,6 +259,7 @@ case MachineOperand::MO_FrameIndex: case MachineOperand::MO_ConstantPoolIndex: case MachineOperand::MO_JumpTableIndex: + case MachineOperand::MO_JumpMapIndex: OperandHash = Op.getIndex(); break; case MachineOperand::MO_GlobalAddress: @@ -1296,6 +1312,10 @@ // 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; @@ -1583,6 +1603,9 @@ // 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; Index: lib/CodeGen/CMakeLists.txt =================================================================== --- lib/CodeGen/CMakeLists.txt +++ lib/CodeGen/CMakeLists.txt @@ -133,6 +133,7 @@ StackMaps.cpp StackProtector.cpp StackSlotColoring.cpp + SwitchAnalysis.cpp TailDuplication.cpp TailDuplicator.cpp TargetFrameLoweringImpl.cpp Index: lib/CodeGen/CodeGen.cpp =================================================================== --- lib/CodeGen/CodeGen.cpp +++ lib/CodeGen/CodeGen.cpp @@ -86,6 +86,7 @@ initializeStackMapLivenessPass(Registry); initializeStackProtectorPass(Registry); initializeStackSlotColoringPass(Registry); + initializeSwitchLegacyAnalysisPass(Registry); initializeTailDuplicatePassPass(Registry); initializeTargetPassConfigPass(Registry); initializeTwoAddressInstructionPassPass(Registry); Index: lib/CodeGen/MIRPrinter.cpp =================================================================== --- lib/CodeGen/MIRPrinter.cpp +++ lib/CodeGen/MIRPrinter.cpp @@ -857,6 +857,9 @@ 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()); @@ -969,6 +972,9 @@ case PseudoSourceValue::GOT: OS << "got"; break; + case PseudoSourceValue::JumpMap: + OS << "jump-map"; + break; case PseudoSourceValue::JumpTable: OS << "jump-table"; break; Index: lib/CodeGen/MachineFunction.cpp =================================================================== --- lib/CodeGen/MachineFunction.cpp +++ lib/CodeGen/MachineFunction.cpp @@ -23,6 +23,7 @@ #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" @@ -140,6 +141,7 @@ Alignment = AlignAllFunctions; JumpTableInfo = nullptr; + JumpMapInfo = nullptr; if (isFuncletEHPersonality(classifyEHPersonality( Fn->hasPersonalityFn() ? Fn->getPersonalityFn() : nullptr))) { @@ -190,6 +192,11 @@ Allocator.Deallocate(JumpTableInfo); } + if (JumpMapInfo) { + JumpMapInfo->~MachineJumpMapInfo(); + Allocator.Deallocate(JumpMapInfo); + } + if (WinEHInfo) { WinEHInfo->~WinEHFuncInfo(); Allocator.Deallocate(WinEHInfo); @@ -211,6 +218,17 @@ 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"); @@ -436,6 +454,10 @@ if (JumpTableInfo) JumpTableInfo->print(OS); + // Print JumpMap Information + if (JumpMapInfo) + JumpMapInfo->print(OS); + // Print Constant Pool ConstantPool->print(OS); @@ -562,6 +584,23 @@ 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(); @@ -852,6 +891,85 @@ 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 &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 Index: lib/CodeGen/MachineFunctionPass.cpp =================================================================== --- lib/CodeGen/MachineFunctionPass.cpp +++ lib/CodeGen/MachineFunctionPass.cpp @@ -25,6 +25,7 @@ #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" @@ -86,6 +87,7 @@ AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); + AU.addPreserved(); FunctionPass::getAnalysisUsage(AU); } Index: lib/CodeGen/MachineInstr.cpp =================================================================== --- lib/CodeGen/MachineInstr.cpp +++ lib/CodeGen/MachineInstr.cpp @@ -253,6 +253,8 @@ 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: @@ -313,6 +315,8 @@ 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()); @@ -444,6 +448,9 @@ case MachineOperand::MO_JumpTableIndex: OS << "'; break; + case MachineOperand::MO_JumpMapIndex: + OS << "'; + break; case MachineOperand::MO_GlobalAddress: OS << "printAsOperand(OS, /*PrintType=*/false, MST); @@ -550,6 +557,10 @@ 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()); } Index: lib/CodeGen/PseudoSourceValue.cpp =================================================================== --- lib/CodeGen/PseudoSourceValue.cpp +++ lib/CodeGen/PseudoSourceValue.cpp @@ -21,7 +21,7 @@ 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) {} @@ -38,19 +38,19 @@ 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( @@ -99,6 +99,7 @@ PseudoSourceValueManager::PseudoSourceValueManager() : StackPSV(PseudoSourceValue::Stack), GOTPSV(PseudoSourceValue::GOT), + JumpMapPSV(PseudoSourceValue::JumpMap), JumpTablePSV(PseudoSourceValue::JumpTable), ConstantPoolPSV(PseudoSourceValue::ConstantPool) {} @@ -112,6 +113,10 @@ return &ConstantPoolPSV; } +const PseudoSourceValue *PseudoSourceValueManager::getJumpMap() { + return &JumpMapPSV; +} + const PseudoSourceValue *PseudoSourceValueManager::getJumpTable() { return &JumpTablePSV; } Index: lib/CodeGen/SelectionDAG/InstrEmitter.cpp =================================================================== --- lib/CodeGen/SelectionDAG/InstrEmitter.cpp +++ lib/CodeGen/SelectionDAG/InstrEmitter.cpp @@ -410,6 +410,8 @@ MIB.addFrameIndex(FI->getIndex()); } else if (JumpTableSDNode *JT = dyn_cast(Op)) { MIB.addJumpTableIndex(JT->getIndex(), JT->getTargetFlags()); + } else if (JumpMapSDNode *JM = dyn_cast(Op)) { + MIB.addJumpMapIndex(JM->getIndex(), JM->getTargetFlags()); } else if (ConstantPoolSDNode *CP = dyn_cast(Op)) { int Offset = CP->getOffset(); unsigned Align = CP->getAlignment(); Index: lib/CodeGen/SelectionDAG/LegalizeDAG.cpp =================================================================== --- lib/CodeGen/SelectionDAG/LegalizeDAG.cpp +++ lib/CodeGen/SelectionDAG/LegalizeDAG.cpp @@ -17,6 +17,7 @@ #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" @@ -3615,6 +3616,89 @@ 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(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 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. @@ -3816,6 +3900,7 @@ 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: Index: lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h =================================================================== --- lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h +++ lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h @@ -73,6 +73,7 @@ if (isa(Node)) return true; if (isa(Node)) return true; if (isa(Node)) return true; + if (isa(Node)) return true; if (isa(Node)) return true; if (isa(Node)) return true; if (isa(Node)) return true; Index: lib/CodeGen/SelectionDAG/SelectionDAG.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -427,6 +427,11 @@ ID.AddInteger(cast(N)->getIndex()); ID.AddInteger(cast(N)->getTargetFlags()); break; + case ISD::JumpMap: + case ISD::TargetJumpMap: + ID.AddInteger(cast(N)->getIndex()); + ID.AddInteger(cast(N)->getTargetFlags()); + break; case ISD::ConstantPool: case ISD::TargetConstantPool: { const ConstantPoolSDNode *CP = cast(N); @@ -1283,6 +1288,25 @@ 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(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, Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -142,7 +142,9 @@ /// 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. @@ -152,6 +154,7 @@ union { MachineBasicBlock *MBB; unsigned JTCasesIndex; + unsigned JMCasesIndex; unsigned BTCasesIndex; }; BranchProbability Prob; @@ -179,6 +182,18 @@ 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; @@ -271,6 +286,37 @@ }; typedef std::pair 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): @@ -322,6 +368,11 @@ 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, @@ -352,7 +403,8 @@ /// 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 @@ -572,6 +624,9 @@ /// JTCases - Vector of JumpTable structures used to communicate /// SwitchInst code generation information. std::vector JTCases; + /// JMCases - Vector of JumpMap structures used to communicate + /// SwitchInst code generation information. + std::vector JMCases; /// BitTestCases - Vector of BitTestBlock structures used to communicate /// SwitchInst code generation information. std::vector BitTestCases; @@ -809,6 +864,7 @@ unsigned Reg, BitTestCase &B, MachineBasicBlock *SwitchBB); + void visitJumpMap(JumpMapBlock &JM); void visitJumpTable(JumpTable &JT); void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH, MachineBasicBlock *SwitchBB); Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -32,12 +32,14 @@ #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" @@ -83,6 +85,7 @@ "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 @@ -1949,6 +1952,29 @@ 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, @@ -2366,6 +2392,11 @@ 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) @@ -8596,6 +8627,126 @@ 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 DestBBs; + DenseMap 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 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, @@ -8809,6 +8960,23 @@ } } 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, @@ -9013,9 +9181,11 @@ 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); @@ -9112,7 +9282,7 @@ 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); @@ -9165,6 +9335,14 @@ } 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]; @@ -9224,6 +9402,12 @@ } 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, @@ -9436,12 +9620,19 @@ } findJumpTables(Clusters, &SI, DefaultMBB); - findBitTestClusters(Clusters, &SI); + // 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); @@ -9457,7 +9648,13 @@ 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}); @@ -9473,6 +9670,6 @@ continue; } - lowerWorkItem(W, SI.getCondition(), SwitchMBB, DefaultMBB); + lowerWorkItem(W, SI.getCondition(), SwitchMBB, DefaultMBB, JumpMapB); } } Index: lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp @@ -98,6 +98,7 @@ 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"; @@ -137,6 +138,7 @@ 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"; @@ -268,6 +270,7 @@ 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"; @@ -442,6 +445,10 @@ OS << "<" << JTDN->getIndex() << ">"; if (unsigned int TF = JTDN->getTargetFlags()) OS << " [TF=" << TF << ']'; + } else if (const JumpMapSDNode *JMDN = dyn_cast(this)) { + OS << "<" << JMDN->getIndex() << ">"; + if (unsigned int TF = JMDN->getTargetFlags()) + OS << " [TF=" << TF << ']'; } else if (const ConstantPoolSDNode *CP = dyn_cast(this)){ int offset = CP->getOffset(); if (CP->isMachineConstantPoolEntry()) Index: lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -47,6 +47,7 @@ #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" @@ -325,6 +326,10 @@ AU.addRequired(); if (UseMBPI && OptLevel != CodeGenOpt::None) AU.addRequired(); + if (OptLevel != CodeGenOpt::None) { + AU.addRequired(); + AU.addPreserved(); + } MachineFunctionPass::getAnalysisUsage(AU); } @@ -411,6 +416,11 @@ else FuncInfo->BPI = nullptr; + if(OptLevel != CodeGenOpt::None) + FuncInfo->SWAN = &getAnalysis().getSWAN(); + else + FuncInfo->SWAN = nullptr; + SDB->init(GFI, *AA, LibInfo); MF->setHasInlineAsm(false); @@ -1808,6 +1818,28 @@ } 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) { @@ -2790,6 +2822,7 @@ case ISD::MCSymbol: case ISD::TargetBlockAddress: case ISD::TargetJumpTable: + case ISD::TargetJumpMap: case ISD::TargetGlobalTLSAddress: case ISD::TargetGlobalAddress: case ISD::TokenFactor: Index: lib/CodeGen/SelectionDAG/TargetLowering.cpp =================================================================== --- lib/CodeGen/SelectionDAG/TargetLowering.cpp +++ lib/CodeGen/SelectionDAG/TargetLowering.cpp @@ -17,6 +17,7 @@ #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" @@ -317,6 +318,17 @@ 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(); Index: lib/CodeGen/SwitchAnalysis.cpp =================================================================== --- /dev/null +++ lib/CodeGen/SwitchAnalysis.cpp @@ -0,0 +1,340 @@ +//===--------- 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 &Clusters, + const SmallVectorImpl &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::JumpMapCases(SwitchInst& SI, const bool OptForSize) { + std::vector 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 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 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 MinPartitions(N); + SmallVector LastElement(N); + SmallVector 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 Switches; + // for (auto& F : M) { + bool SizeOpt = Fn.optForSize(); + for (auto& BB : Fn) { + for (auto& BI : BB) { + if (isa(BI)) { + SwitchInst &SI = cast(BI); + std::vector 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(SI.getCondition()) && + cast(*(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"); + } +} Index: lib/CodeGen/TargetLoweringBase.cpp =================================================================== --- lib/CodeGen/TargetLoweringBase.cpp +++ lib/CodeGen/TargetLoweringBase.cpp @@ -20,6 +20,7 @@ #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" @@ -50,6 +51,10 @@ ("min-jump-table-entries", cl::init(4), cl::Hidden, cl::desc("Set minimum number of entries to use a jump table.")); +static cl::opt 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 MaximumJumpTableSize ("max-jump-table-size", cl::init(0), cl::Hidden, cl::desc("Set maximum size of jump tables; zero for no limit.")); @@ -66,6 +71,10 @@ cl::desc("Minimum density for building a jump table in " "an optsize function")); +static cl::opt 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 @@ -500,6 +509,19 @@ 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"; @@ -1914,6 +1936,14 @@ return MinimumJumpTableEntries; } +unsigned TargetLoweringBase::getMinimumJumpMapEntries() const { + return MinimumJumpMapEntries; +} + +void TargetLoweringBase::setMinimumJumpMapEntries(unsigned Val) { + MinimumJumpMapEntries = Val; +} + void TargetLoweringBase::setMinimumJumpTableEntries(unsigned Val) { MinimumJumpTableEntries = Val; } @@ -1930,6 +1960,30 @@ 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 //===----------------------------------------------------------------------===// Index: lib/CodeGen/TargetPassConfig.cpp =================================================================== --- lib/CodeGen/TargetPassConfig.cpp +++ lib/CodeGen/TargetPassConfig.cpp @@ -24,6 +24,7 @@ #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" @@ -530,6 +531,11 @@ 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 @@ -554,6 +560,7 @@ // to ensure that the IR is valid. if (!DisableVerify) addPass(createVerifierPass()); + } /// Add the complete set of target-independent postISel code generator passes. Index: lib/Target/ARM/ARMExpandPseudoInsts.cpp =================================================================== --- lib/Target/ARM/ARMExpandPseudoInsts.cpp +++ lib/Target/ARM/ARMExpandPseudoInsts.cpp @@ -647,6 +647,7 @@ 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: Index: lib/Target/TargetLoweringObjectFile.cpp =================================================================== --- lib/Target/TargetLoweringObjectFile.cpp +++ lib/Target/TargetLoweringObjectFile.cpp @@ -252,6 +252,14 @@ 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 Index: lib/Target/X86/X86AsmPrinter.cpp =================================================================== --- lib/Target/X86/X86AsmPrinter.cpp +++ lib/Target/X86/X86AsmPrinter.cpp @@ -77,8 +77,9 @@ } /// 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()) { @@ -393,6 +394,7 @@ 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: @@ -417,6 +419,7 @@ 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: Index: lib/Target/X86/X86ISelDAGToDAG.cpp =================================================================== --- lib/Target/X86/X86ISelDAGToDAG.cpp +++ lib/Target/X86/X86ISelDAGToDAG.cpp @@ -70,17 +70,18 @@ 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 { @@ -140,6 +141,7 @@ else dbgs() << "nul"; dbgs() << " JT" << JT << " Align" << Align << '\n'; + dbgs() << " JM" << JM << " Align" << Align << '\n'; } #endif }; @@ -263,6 +265,9 @@ } 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); @@ -783,6 +788,9 @@ } else if (JumpTableSDNode *J = dyn_cast(N0)) { AM.JT = J->getIndex(); AM.SymbolFlags = J->getTargetFlags(); + } else if (JumpMapSDNode *J = dyn_cast(N0)) { + AM.JM = J->getIndex(); + AM.SymbolFlags = J->getTargetFlags(); } else if (BlockAddressSDNode *BA = dyn_cast(N0)) { X86ISelAddressMode Backup = AM; AM.BlockAddr = BA->getBlockAddress(); @@ -823,6 +831,9 @@ } else if (JumpTableSDNode *J = dyn_cast(N0)) { AM.JT = J->getIndex(); AM.SymbolFlags = J->getTargetFlags(); + } else if (JumpMapSDNode *J = dyn_cast(N0)) { + AM.JM = J->getIndex(); + AM.SymbolFlags = J->getTargetFlags(); } else if (BlockAddressSDNode *BA = dyn_cast(N0)) { AM.BlockAddr = BA->getBlockAddress(); AM.Disp += BA->getOffset(); @@ -1126,7 +1137,7 @@ // 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(N)) Index: lib/Target/X86/X86ISelLowering.h =================================================================== --- lib/Target/X86/X86ISelLowering.h +++ lib/Target/X86/X86ISelLowering.h @@ -139,7 +139,7 @@ /// 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, @@ -702,6 +702,7 @@ /// 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; @@ -1164,6 +1165,7 @@ 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; Index: lib/Target/X86/X86ISelLowering.cpp =================================================================== --- lib/Target/X86/X86ISelLowering.cpp +++ lib/Target/X86/X86ISelLowering.cpp @@ -310,6 +310,7 @@ } 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 }) { @@ -430,6 +431,7 @@ 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); @@ -14396,11 +14398,11 @@ 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 { @@ -14446,6 +14448,21 @@ return Result; } +SDValue X86TargetLowering::LowerJumpMap(SDValue Op, SelectionDAG &DAG) const { + auto PtrVT = getPointerTy(DAG.getDataLayout()); + JumpMapSDNode *JM = cast(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(Op)->getSymbol(); @@ -23785,6 +23802,7 @@ 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); Index: lib/Target/X86/X86InstrCompiler.td =================================================================== --- lib/Target/X86/X86InstrCompiler.td +++ lib/Target/X86/X86InstrCompiler.td @@ -1032,6 +1032,8 @@ (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)), @@ -1050,6 +1052,9 @@ 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]>; Index: lib/Target/X86/X86MCInstLower.cpp =================================================================== --- lib/Target/X86/X86MCInstLower.cpp +++ lib/Target/X86/X86MCInstLower.cpp @@ -239,7 +239,7 @@ 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); @@ -375,6 +375,8 @@ 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: Index: utils/TableGen/CodeGenDAGPatterns.cpp =================================================================== --- utils/TableGen/CodeGenDAGPatterns.cpp +++ utils/TableGen/CodeGenDAGPatterns.cpp @@ -2189,6 +2189,7 @@ Operator->getName() != "tglobaltlsaddr" && Operator->getName() != "tconstpool" && Operator->getName() != "tjumptable" && + Operator->getName() != "tjumpmap" && Operator->getName() != "tframeindex" && Operator->getName() != "texternalsym" && Operator->getName() != "tblockaddress" &&