[X86] Use a std::vector for the memory unfolding table.

Previously we used a DenseMap which is costly to set up due to multiple full table rehashes as the size increases and causes the table to be reallocated.

This patch changes the table to a vector of structs. We now walk the reg->mem tables and push new entries in the mem->reg table for each row not marked TB_NO_REVERSE. Once all the table entries have been created, we sort the vector. Then we can use a binary search for lookups.

Differential Revision: https://reviews.llvm.org/D48585

llvm-svn: 335994

2 files changed, 56 insertions, 26 deletions

diff --git a/llvm/lib/Target/X86/X86InstrInfo.cpp b/llvm/lib/Target/X86/X86InstrInfo.cpp
index c20696e77fd..9cd42a59d2b 100644
--- a/llvm/lib/Target/X86/X86InstrInfo.cpp
+++ b/llvm/lib/Target/X86/X86InstrInfo.cpp
@@ -5411,10 +5411,17 @@ X86InstrInfo::X86InstrInfo(X86Subtarget &STI)
                   // Index 4, folded load
                   Entry.Flags | TB_INDEX_4 | TB_FOLDED_LOAD);
 
+  // Sort the memory->reg unfold table.
+  array_pod_sort(MemOp2RegOpTable.begin(), MemOp2RegOpTable.end());
+
 #ifndef NDEBUG
   // Make sure the tables are sorted.
   static std::atomic<bool> FoldTablesChecked(false);
   if (!FoldTablesChecked.load(std::memory_order_relaxed)) {
+    assert(std::adjacent_find(MemOp2RegOpTable.begin(),
+                              MemOp2RegOpTable.end()) ==
+           MemOp2RegOpTable.end() &&
+           "MemOp2RegOpTable is not unique!");
     assert(std::is_sorted(std::begin(MemoryFoldTable2Addr),
                           std::end(MemoryFoldTable2Addr)) &&
            std::adjacent_find(std::begin(MemoryFoldTable2Addr),
@@ -5459,11 +5466,17 @@ X86InstrInfo::X86InstrInfo(X86Subtarget &STI)
 void
 X86InstrInfo::AddTableEntry(MemOp2RegOpTableType &M2RTable,
                             uint16_t RegOp, uint16_t MemOp, uint16_t Flags) {
-  if ((Flags & TB_NO_REVERSE) == 0) {
-    assert(!M2RTable.count(MemOp) &&
-         "Duplicated entries in unfolding maps?");
-    M2RTable[MemOp] = std::make_pair(RegOp, Flags);
-  }
+  if ((Flags & TB_NO_REVERSE) == 0)
+    M2RTable.push_back({MemOp, RegOp, Flags});
+}
+
+const X86InstrInfo::MemOp2RegOpTableTypeEntry *
+X86InstrInfo::lookupUnfoldTable(unsigned MemOp) const {
+  auto I = std::lower_bound(MemOp2RegOpTable.begin(), MemOp2RegOpTable.end(),
+                            MemOp);
+  if (I != MemOp2RegOpTable.end() && I->MemOp == MemOp)
+    return &*I;
+  return nullptr;
 }
 
 static const X86MemoryFoldTableEntry *
@@ -10722,13 +10735,13 @@ MachineInstr *X86InstrInfo::foldMemoryOperandImpl(
 bool X86InstrInfo::unfoldMemoryOperand(
     MachineFunction &MF, MachineInstr &MI, unsigned Reg, bool UnfoldLoad,
     bool UnfoldStore, SmallVectorImpl<MachineInstr *> &NewMIs) const {
-  auto I = MemOp2RegOpTable.find(MI.getOpcode());
-  if (I == MemOp2RegOpTable.end())
+  const MemOp2RegOpTableTypeEntry *I = lookupUnfoldTable(MI.getOpcode());
+  if (I == nullptr)
     return false;
-  unsigned Opc = I->second.first;
-  unsigned Index = I->second.second & TB_INDEX_MASK;
-  bool FoldedLoad = I->second.second & TB_FOLDED_LOAD;
-  bool FoldedStore = I->second.second & TB_FOLDED_STORE;
+  unsigned Opc = I->RegOp;
+  unsigned Index = I->Flags & TB_INDEX_MASK;
+  bool FoldedLoad = I->Flags & TB_FOLDED_LOAD;
+  bool FoldedStore = I->Flags & TB_FOLDED_STORE;
   if (UnfoldLoad && !FoldedLoad)
     return false;
   UnfoldLoad &= FoldedLoad;
@@ -10844,13 +10857,13 @@ X86InstrInfo::unfoldMemoryOperand(SelectionDAG &DAG, SDNode *N,
   if (!N->isMachineOpcode())
     return false;
 
-  auto I = MemOp2RegOpTable.find(N->getMachineOpcode());
-  if (I == MemOp2RegOpTable.end())
+  const MemOp2RegOpTableTypeEntry *I = lookupUnfoldTable(N->getMachineOpcode());
+  if (I == nullptr)
     return false;
-  unsigned Opc = I->second.first;
-  unsigned Index = I->second.second & TB_INDEX_MASK;
-  bool FoldedLoad = I->second.second & TB_FOLDED_LOAD;
-  bool FoldedStore = I->second.second & TB_FOLDED_STORE;
+  unsigned Opc = I->RegOp;
+  unsigned Index = I->Flags & TB_INDEX_MASK;
+  bool FoldedLoad = I->Flags & TB_FOLDED_LOAD;
+  bool FoldedStore = I->Flags & TB_FOLDED_STORE;
   const MCInstrDesc &MCID = get(Opc);
   MachineFunction &MF = DAG.getMachineFunction();
   const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
@@ -10975,18 +10988,18 @@ X86InstrInfo::unfoldMemoryOperand(SelectionDAG &DAG, SDNode *N,
 unsigned X86InstrInfo::getOpcodeAfterMemoryUnfold(unsigned Opc,
                                       bool UnfoldLoad, bool UnfoldStore,
                                       unsigned *LoadRegIndex) const {
-  auto I = MemOp2RegOpTable.find(Opc);
-  if (I == MemOp2RegOpTable.end())
+  const MemOp2RegOpTableTypeEntry *I = lookupUnfoldTable(Opc);
+  if (I == nullptr)
     return 0;
-  bool FoldedLoad = I->second.second & TB_FOLDED_LOAD;
-  bool FoldedStore = I->second.second & TB_FOLDED_STORE;
+  bool FoldedLoad = I->Flags & TB_FOLDED_LOAD;
+  bool FoldedStore = I->Flags & TB_FOLDED_STORE;
   if (UnfoldLoad && !FoldedLoad)
     return 0;
   if (UnfoldStore && !FoldedStore)
     return 0;
   if (LoadRegIndex)
-    *LoadRegIndex = I->second.second & TB_INDEX_MASK;
-  return I->second.first;
+    *LoadRegIndex = I->Flags & TB_INDEX_MASK;
+  return I->RegOp;
 }
 
 bool
diff --git a/llvm/lib/Target/X86/X86InstrInfo.h b/llvm/lib/Target/X86/X86InstrInfo.h
index aa31c837924..562b4385c49 100644
--- a/llvm/lib/Target/X86/X86InstrInfo.h
+++ b/llvm/lib/Target/X86/X86InstrInfo.h
@@ -17,9 +17,9 @@
 #include "MCTargetDesc/X86BaseInfo.h"
 #include "X86InstrFMA3Info.h"
 #include "X86RegisterInfo.h"
-#include "llvm/ADT/DenseMap.h"
 #include "llvm/CodeGen/ISDOpcodes.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
+#include <vector>
 
 #define GET_INSTRINFO_HEADER
 #include "X86GenInstrInfo.inc"
@@ -168,14 +168,31 @@ class X86InstrInfo final : public X86GenInstrInfo {
   X86Subtarget &Subtarget;
   const X86RegisterInfo RI;
 
+  struct MemOp2RegOpTableTypeEntry {
+    uint16_t MemOp;
+    uint16_t RegOp;
+    uint16_t Flags;
+
+    bool operator<(const MemOp2RegOpTableTypeEntry &RHS) const {
+      return MemOp < RHS.MemOp;
+    }
+    bool operator==(const MemOp2RegOpTableTypeEntry &RHS) const {
+      return MemOp == RHS.MemOp;
+    }
+    friend bool operator<(const MemOp2RegOpTableTypeEntry &TE,
+                          unsigned Opcode) {
+      return TE.MemOp < Opcode;
+    }
+  };
+
   /// MemOp2RegOpTable - Load / store unfolding opcode map.
   ///
-  typedef DenseMap<unsigned, std::pair<uint16_t, uint16_t>>
-      MemOp2RegOpTableType;
+  typedef std::vector<MemOp2RegOpTableTypeEntry> MemOp2RegOpTableType;
   MemOp2RegOpTableType MemOp2RegOpTable;
 
   static void AddTableEntry(MemOp2RegOpTableType &M2RTable, uint16_t RegOp,
                             uint16_t MemOp, uint16_t Flags);
+  const MemOp2RegOpTableTypeEntry *lookupUnfoldTable(unsigned MemOp) const;
 
   virtual void anchor();