Index: lib/Target/X86/X86InstrInfo.h
===================================================================
--- lib/Target/X86/X86InstrInfo.h
+++ 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 @@
   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();
 
Index: lib/Target/X86/X86InstrInfo.cpp
===================================================================
--- lib/Target/X86/X86InstrInfo.cpp
+++ lib/Target/X86/X86InstrInfo.cpp
@@ -5411,10 +5411,17 @@
                   // 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 bool FoldTablesChecked = false;
   if (!FoldTablesChecked) {
+    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 @@
 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 *
@@ -10728,13 +10741,13 @@
 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;
@@ -10850,13 +10863,13 @@
   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();
@@ -10981,18 +10994,18 @@
 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